Eigenvalue properties of matrix whose element-wise absolute value is row-stochastic

329 Views Asked by At

Suppose I have a matrix $A\in\mathbb{R}^{n\times n}$ such that the matrix $B=(|a_{ij}|)$ (matrix of absolute values of $A$) is row-stochastic. Suppose also that the eigenvalue $1$ of $B$ is simple. Suppose further that $1$ is also an eigenvalue of $A$.

Can I say something about the eigenvalue $1$ of $A$? Is it also simple? Does the eigenspace corresponding to $1$ for $A$ relate to the eigenspace corresponding to $1$ for B? Are $A$ and $B$ similar?

(Additional: $A$ can be assumed symmetric, if this helps or simplifies things. And irreducible.)

Thanks a lot.

1

There are 1 best solutions below

8
On BEST ANSWER

By reindexing the rows and columns of $A$, we may assume that $A$ and $|A|$ are in block upper triangular forms, where each diagonal sub-blocks of $|A|$ is irreducible and corresponds to a strongly connected component in the directed graph associated with the sign pattern of $|A|$. Denote the $j$-th diagonal sub-block of $A$ by $A_j$. By assumption, $1$ is a simple eigenvalue of some $|A_k|$ and it is not an eigenvalue of any other $|A_j|$. We now have the following observations.

(I) $1$ is a simple eigenvalue of $A$

Since $|A|$ is row stochastic, it is power bounded. Hence $A$ is power bounded too and $1$ is a semisimple eigenvalue of $A$. So, to prove that $1$ is actually a simple eigenvalue of $A$, it remains to show that the corresponding eigenspace is one-dimensional.

Recall that $1$ is a simple eigenvalue of the $k$-th diagonal sub-block $|A_k|$. If $1$ is an eigenvalue of $A_j$ for some $j\ne k$, then $1=\rho(A_j)\le\|A_j\|_\infty=\||A_j|\|_\infty\le\||A|\|_\infty=1$, meaning that $\||A_j|\|_\infty=1$ and in turn $1=\rho(A_j)\le\rho(|A_j|)\le\||A_j|\|_\infty=1$. Consequently, $\rho(|A_j|)=1$. However, as $|A_j|$ is nonnegative, $\rho(|A_j|)$ is an eigenvalue of $|A_j|$. Therefore $1$ is an eigenvalue of $|A_j|$, but this is impossible because $1$ is a simple eigenvalue of $|A|$. Therefore, we conclude that $A_k$ is the only diagonal sub-block of $A$ that has $1$ as an eigenvalue.

Let $v$ be an eigenvector of $A_k$ for the eigenvalue $1$. Let also $D=\operatorname{diag}(\operatorname{sign}(v))$ (the sign of $0$ is taken to be $1$) and $A_k'=D^{-1}A_kD$. Then $|A_k'|=|A_k|$ and $p=Dv$ is a nonnegative eigenvector of $A_k'$ corresponding to the eigenvalue $1$. Since $|A_k'|$ is irreducible, it has a positive left Perron vector $q$ for the eigenvalue $1$. As $$ q^Tp = (q^T|A_k'|)p \color{red}{\ge} q^T(A_k'p) = q^Tp, $$ the red inequality must be tight and $q^T(|A_k'|-A_k')p=0$. Since $q$ is positive and $(|A_k'|-A_k')p$ is nonnegative, we must have $(|A_k'|-A_k')p=0$. Therefore $|A_k'|p=A_k'p=p$, i.e. $p$ is a Perron vector of $|A_k'|$. As $|A_k'|$ is irreducible, $p$ must be positive. This means the original eigenvector $v$ of $A_k$ must be entrywise nonzero.

Therefore, the eigenspace of $A_k$ for the eigenvalue $1$ is one-dimensional, because given any two linearly independent eigenvectors for the same eigenvalue, there always exists a non-trivial linear combination of them that contains a zero entry.

Hence $1$ is a simple eigenvalue of $A$.

(II) $|A_k|$ is always similar to $A_k$; hence $|A|$ is similar to $A$ when it is irreducible

We have shown in the above that $(|A_k'|-A_k')p=0$ and $p$ is positive. Hence $|A_k'|=A_k'$, meaning that $|A_k|=D^{-1}A_kD$, i.e. $|A_k|$ is always similar to $A_k$. In particular, when $|A|$ is irreducible, it is similar to $A$.

However, in general, $|A|$ not always similar to $A$. In fact, if $|A|$ is similar to $A$, we can always construct a reducible matrix $$ \widetilde{A}=\pmatrix{A&0\\ \frac{1}{3n}ee^T&\frac13\pmatrix{1&1\\ 1&-1}}, $$ so that $\left|\widetilde{A}\right|$ is row stochastic, and $1$ is a simple eigenvalue of $\left|\widetilde{A}\right|$ and also an eigenvalue of $\widetilde{A}$, but the matrices $\widetilde{A}$ and $\left|\widetilde{A}\right|$ are not similar to each other because they have different traces.

(III) When $|A|\ne A$, it is possible that the Perron vector of $|A|$ is also an eigenvector of $A$, but not for the eigenvalue $1$.

Let $e$ be the all-one vector, so that $|A|e=e$. If $|A|\ne A$ and $Ae=\lambda e$, then $\lambda$ cannot possibly be equal to $1$, otherwise we would have $(|A|-A)e=0$, which is impossible because $0\ne|A|-A\ge0$ and $e>0$.

Yet, it is possible that $Ae=\lambda e$ for some $\lambda\ne1$. For example, we have $Ae=0$ when $$ A=\pmatrix{\frac12&-\frac12\\ -\frac12&\frac12}. $$