Let $\mathbf{A}$ be a matrix of size $n \times m$ with $\sum_{j = 1}^m A_{ij} = 1$ and $\mathbf{E}$ be a matrix of size $n \times m$ with $\sum_{i = 1}^n E_{ij} = 1$ and $\forall i,j \ \ \ \ 1 \geq E_{ij} \geq 0, \ \ \ 1 \geq A_{ij} \geq 0$. Consider the following iterative process:
$$\mathbf{x}(t) = \mathbf{A}^T \mathbf{E} \mathbf{x}(t-1) $$
where $\mathbf{x}$ is a vector of size $m$
I have experiments for randomly initialized matrices that satisfy the above conditions. All of these matrices have spectral radii less than or equal to 1. For the case when the spectral radius is equal to 1, the process still converges in my experiment. (Note that the matrix $(\mathbf{A}^T \mathbf{E})^k$ converges to a non-zero matrix as $k \to \infty$).
Two questions:
- How could I prove a bound on the spectral radius of the matrix $\mathbf{A}^T \mathbf{E}$?
- How could I prove that the process converges when the spectral radius is equal to 1. Are there any conditions that I can put on the matrices $\mathbf{A}$ and $\mathbf{E}$ such that even if the spectral radius is 1, the process will still converge?
P.S.: I know that an iterative process converges when the spectral radius is strictly less than 1 and that it diverges when the spectral radius is strictly greater than 1. However, I am having trouble understanding the case when the spectral radius is 1, as I have seen discussion making use of the Jordan normal form to prove convergence when the spectral radius is equal to 1. Could you point me to any resources that could allow me to solve this?
Best Answer
To prove the bound on the spectral radius, consider the transpose $E^TA$ which has the same spectral radius. Let $x$ be an eigenvector of eigenvalue $\lambda$ and let $x_k$ be the entry of $x$ with the largest absolute value. Then
$$|(E^TAx)_k| = \left|\sum_{j=1}^m(E^TA)_{kj}x_j \right|=|\sum_{j=1}^m\sum_{i=1}^nE^T_{ki}A_{ij}x_j|=|\sum_{i=1}^nE_{ik}\sum_{j=1}^mA_{ij}x_j|\leq\sum_{i=1}^nE_{ik}\sum_{j=1}^m A_{ij}|x_j|\leq\\ \sum_{i=1}^nE_{ik}\sum_{j=1}^m A_{ij}|x_k|\leq \sum_{i=1}^nE_{ik}|x_k|=|x_k|$$ We have also that $|(E^TAx)_k|=|\lambda x_k|$ so we have shown that $|\lambda x_k|\leq |x_k|$, which implies that result.
Now, it is not true that the process will necesarily converge if the spectral radius is equal to $1$. This is to be expected as there is a reason theorems about convergence are stated for spectral radius strictly less than $1$. To see a counter-example, take $n=m=2$, $E=I_2$ and $A=\begin{pmatrix}0&1\\ 1&0\end{pmatrix}$ so that $A^TE=A$. Then $A^n=\begin{cases}A& \text{n is odd}\\I_2&\text{n is even}\end{cases}$ so the process will not converge when applied for instance to $x=(1,0)$.