# Any convergence rule for ${\mathbf X}_k={\mathbf A}{\mathbf X}_{k-1}{\mathbf B}$?

We know iteration ${\mathbf X}_k=\mathbf{A}{\mathbf X}_{k-1}$ converges if the spectral radius of $\mathbf A$ is smaller than 1 (see here). Is there any known rule for iteration ${\mathbf X}_k={\mathbf A}{\mathbf X}_{k-1}{\mathbf B}$ to converge? Any reference is helpful. Thanks!

Here ${\mathbf X}_k$ is a matrix, for example ${\mathbf X}_k$ is $N\times n$, $\bf A$ is $N\times N$ and $\bf B$ is $n \times n$.

• @JochenGlueck Thanks for pointing this out. Sorry for the confusing notation. – Tony Aug 30 '18 at 16:36
• This can be re-written as: $x_k \gets (B^T \otimes A) x_{k-1}$, where $x_k = \text{vec}(X_k)$. Now, the convergence analysis in terms of spectral radius is clear. – Suvrit Aug 30 '18 at 16:45
• @Suvrit: Yes, but I think the question is whether one can give good criteria for convergence of the powers of $(B^T \otimes A)$ in terms of $A$ and $B$. – Jochen Glueck Aug 30 '18 at 16:46
• @JochenGlueck one can, e.g., $\rho(A\otimes B) = \rho(A)\rho(B)$, where $\rho$ denotes the spectral radius, ..., does this not suffice? – Suvrit Aug 30 '18 at 16:48
• @Survrit: Well, what you wrote suffices to prove that the sequence converges to $0$ for every given $X_0$ if and only if $\rho(A)\rho(B)<1$. In order to characterise mere convergence of the sequence for every $X_0$ though, one needs a criterion to charaterise, in case that $\rho(A)\rho(B) = 1$, whether $1$ is the only eigenvalue of $B^T\otimes A$ and whether this eigenvalue is semi-simple. Maybe such a criterion is not difficult to obtain, but at the moment I'm not sure about it. – Jochen Glueck Aug 30 '18 at 17:11

For every square matrix $C$, let $r(C)$ denote its spectral value. We say that a complex number $\lambda$ is

• a dominant eigenvalue of $C$ if $\lambda$ is the only eigenvalue of $C$ with modulus $r(C)$.

• a semisimple eigenvalue of $C$ if it is an eigenvalue of $C$ and its algebraic multiplicity coincides with its geometric multiplicity.

Theorem. The following assertions are equivalent:

(i) The sequence $(X_K)$ converges for every $X_0$.

(ii) We have either $r(A)r(B) < 1$, or we have $r(A)r(B) = 1$ and the matrices $A$ and $B$ both have dominant eigenvalues which are semisimple and whose product equals $1$.

Proof. "(ii) $\Rightarrow$ (i)" First, let $r(A)r(B) < 1$. By multiplying $A$ and $B$ with appropriate positive numbers that are inverse to each other we may assume that $r(A) < 1$ and $r(B) < 1$. Hence, $X_k = A^kX_0 B^k \to 0$ as $k \to \infty$.

If instead $r(A)r(B) = 1$ we may assume without loss of generality that $r(A) = r(B) = 1$. Let $\lambda$ denote the dominant eigenvalue of $A$; then $\lambda$ has modulus $1$ and $\overline{\lambda}$ is the dominant eigenvalue of $B$. By replacing $A$ with $\overline{\lambda}A$ and $B$ with $\lambda B$ we may assume that $A$ and $B$ have $1$ as a dominant eigenvalue and that this eigenvalue is semisimple. Hence, $A^k$ and $B^k$ are both convergent as $k \to \infty$, which implies that $X_k$ is convergent, too.

"(i) $\Rightarrow$ (ii)" Assume that (i) holds and that $r(A)r(B) \ge 1$. We have to prove that the second alternative in (ii) holds. Let $\lambda$ and $\mu$ denote eigenvalues of $A$ and $B$ of maximal modulus; let $v$ denote an eigenvector for $\lambda$ of $A$ and let $w$ denote an eigenvector for $\mu$ of the transposed matrix $B^T$ of $B$. If we choose $X_0 = v w^T$, then $X_k = A^k v w^T B^k = (\lambda\mu)^k v w^T$. Since this sequence is convergent and $\lvert\lambda \mu\rvert = r(A) r(B) \ge 1$, it follows that $\lambda \mu = 1$.

Since $\lambda$ and $\mu$ were arbitrary eigenvalues of maximal modulus (of matrix $A$ and $B$, respectively), it follows that each of the matrices $A$ and $B$ can have only one eigenvalue of maximal modulus, which is thus a dominant eigenvalue of this matrix.

Now, let $\lambda$ and $\mu$ denote the dominant eigenvalues of $A$ and $B$; we have already seen that $\lambda \mu = 1$. If one of those eigenvalues was not semisimple, than we could find a generalised eigenvector of rank $\ge 2$ for it (for $A$ or $B^T$, respectively), and a similar argument as above would show that $(X_k)$ cannot be bounded if $X_0$ is chosen appropriately.

Remark. The above argument also shows that $X_k \to 0$ for every $X_0$ if and only if $r(A)r(B) < 1$. This has already been observed by Suvrit in the comments.