1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ My bad thanks for the comment, I removed the vector $\mathbf{x}$ it was a typo, it should be just $\mathbf{A}^T \mathbf{E}$ $\endgroup$
    – Denizalp
    Commented Jun 24, 2020 at 20:48
  • $\begingroup$ They are nonnegative with entries between 0 (included) and 1 (included). I hope the first paragraph is not confusing. $\endgroup$
    – Denizalp
    Commented Jun 24, 2020 at 21:25
  • $\begingroup$ I found the indexing very easy to misread. For other's benefit: $\mathbf A$ is column stochastic and $\mathbf E$ is row stochastic. $\endgroup$ Commented Jun 24, 2020 at 23:47

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
7
  • $\begingroup$ Thanks for the answer! The thing that I am mostly curious about is: are there cases when the spectral radius will be equal to 1 and we will still have convergence? Maybe with extra assumption on the matrices $\mathbf{A}$ and $\mathbf{E}$, such that they can converge despite having a spectral radius of 1 since my experiments show that there are cases when the spectral radius is 1 and we have convergence. $\endgroup$
    – Denizalp
    Commented Jun 24, 2020 at 21:43
  • $\begingroup$ Well it will depend on the matrix and the (generalized) eigenvalues. Just think about how the powers of a matrix act on an eigenvector. If you take an eigenvector in the eigenspace of $\lambda$ where $|\lambda|=1$ then the process won't converge if $\lambda\neq 1$. If you pick an eigenvector corresponding to a smaller eigenvalue, or a vector in the span of eigenspaces with corresponding eigenvalues of norm less than 1 then the process will converge to $0$. Chances are that is what happened in your experiments. $\endgroup$
    – user293794
    Commented Jun 24, 2020 at 21:50
  • $\begingroup$ Thanks for all of this! Does this means that if there is an eigenvalue strictly less than one but there is also at least 1 eigenvalue equal to 1, we will have convergence? $\endgroup$
    – Denizalp
    Commented Jun 24, 2020 at 22:03
  • $\begingroup$ No not necessarily. Let me put it this way: $\lim_{n\rightarrow\infty}(A^TE)^nx$ exists if and only if $x$ belongs to a generalized eigenspace spanned by eigenvectors corresponding to eigenvalues which are equal to $1$ or have norm less than $1$. You should be able to prove this just by writing $x$ as a sum of generalized eigenvectors. $\endgroup$
    – user293794
    Commented Jun 25, 2020 at 0:14
  • $\begingroup$ I think I understand what you are saying, thank you, this helps me a lot. I guess in my experiments my initial vector choice $\mathbf{x}(0)$ led to convergence which makes sense in the context of this problem. If I wanted to prove that the process converges for certain initializations of the vector $\mathbf{x}(0)$ what would I need to do to get those conditions in this specific situation? As a side note, based on the context of this problem I am guessing that the space of converging initial vectors is any simplex in $\mathbb{R}^m$. Could I prove this? $\endgroup$
    – Denizalp
    Commented Jun 25, 2020 at 0:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .