6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @JochenGlueck Thanks for pointing this out. Sorry for the confusing notation. $\endgroup$ – Tony Aug 30 '18 at 16:36
  • 7
    $\begingroup$ 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. $\endgroup$ – Suvrit Aug 30 '18 at 16:45
  • 1
    $\begingroup$ @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$. $\endgroup$ – Jochen Glueck Aug 30 '18 at 16:46
  • 3
    $\begingroup$ @JochenGlueck one can, e.g., $\rho(A\otimes B) = \rho(A)\rho(B)$, where $\rho$ denotes the spectral radius, ..., does this not suffice? $\endgroup$ – Suvrit Aug 30 '18 at 16:48
  • 3
    $\begingroup$ @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. $\endgroup$ – Jochen Glueck Aug 30 '18 at 17:11
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.