2
$\begingroup$

Suppose we have a matrix $A$ $$ A= \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix}, $$ its transposed matrix $A^T$, and $Z_0=I$. And we have updating equation $$Z_{k+1}=\frac{AZ_kA^T+A^TZ_kA}{\|AZ_kA^T+A^TZ_kA\|_F}, k=0, 1,\dots $$

the matrix norm $\|\cdot\|_F$ i use here is Frobenius norm. Then, I want to solve $$\lim_{k\rightarrow+\infty}Z_{2k}$$

I calculated for $k=1,2$ $$ Z_1=\frac{1}{\sqrt{6}} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \qquad Z_2= 2 \begin{bmatrix} \sqrt{\frac{2}{3}} & 0 & 0 \\ 0 & \sqrt{\frac{2}{3}} & 0 \\ 0 & 0 & \sqrt{\frac{2}{3}} \end{bmatrix}, $$ but I don't know what to do from here. Can someone tell me what should be the next step?

I know the answer and it will be $$\begin{equation} \begin{bmatrix} 0.5774 & 0 & 0 \\ 0 & 0.5774 & 0 \\ 0 & 0 & 0.5774 \\ \end{bmatrix} \end{equation} $$ but I have no idea what should be the intermediate steps.

$\endgroup$
2
  • $\begingroup$ What norm are you using? $\endgroup$ – Simply Beautiful Art Jun 29 '20 at 12:32
  • 1
    $\begingroup$ @SimplyBeautifulArt frobenius norm. I edited the post $\endgroup$ – J.Maisel Jun 29 '20 at 12:40
3
$\begingroup$

This sequence is a power iteration corresponding to the linear map $\Phi: \Bbb R^{3 \times 3} \to \Bbb R^{3 \times 3}$ defined by $$ \Phi(X) = AXA^T + A^TXA. $$ With that said, we will be able to deduce the behavior of this sequence if we find the largest (in magnitude) eigenvalues of $\Phi$. One approach to this problem is to compute the matrix of this map, then compute the eigenvalues of the resulting matrix. Using the properties of vectorization, we find that the matrix of this map is $$ [\Phi] = A \otimes A + A^T \otimes A^T = \left(\begin{array}{ccc|ccc|ccc} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{array}\right). $$ Applying a permutation similarity associated with the permutation $[1\ 5\ 9\mid4\ 8\mid 2\ 6\mid 3\mid 7]$ yields $$ M = \left(\begin{array}{ccc|cc|cc|c|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right). $$ In fact, the invariant subspaces corresponding to the block-structure above correspond to the diagonals of $X$.

We see that the largest eigenvalues of $\Phi$ correspond to the upper-left block. These are $\pm \sqrt{2}$, with associated eigenvectors $(1,\pm \sqrt{2}, 1)$. These two eigenvectors span an eigenspace of $M$ corresponding to the eigenvalue $2$ of $\Phi^2$. As it turns out, the matrix subspace corresponding to this eigenspace is $$ \left\{\pmatrix{a & 0 & 0\\ 0 & b & 0 \\ 0 & 0 & a} : a,b \in \Bbb R\right\}. $$ Because $Z_0 = I$ is an element of this subspace, it follows that $\Phi^2(Z_0) = 2Z_0$, so that $Z_{2} = 2Z_0/\|2 Z_0\| = 2I/(2I) = I/\sqrt{3}$, and correspondingly $Z_{2k} = I/\sqrt{3}$ for all $k$.


Attempt at a cleaner approach: we note that $\Phi$ is given by $$ \Phi \pmatrix{x_{11} & x_{12} & x_{13}\\x_{21} & x_{22} & x_{23}\\ x_{31} & x_{32} & x_{33}} = \pmatrix{x_{22} & x_{23} & 0\\x_{32} & x_{33} & 0\\0 & 0 & 0} + \pmatrix{0&0&0\\0&x_{11} & x_{12}\\0 & x_{21} & x_{22}}. $$ We can see that if $\Phi(X) = \lambda X$ with $\lambda \neq 0$, we must have $x_{31} = x_{13} = 0$. That simplifies the equation to $$ \pmatrix{x_{22} & x_{23} & 0\\x_{32} & x_{33} & 0\\0 & 0 & 0} + \pmatrix{0&0&0\\0&x_{11} & x_{12}\\0 & x_{21} & x_{22}} = \lambda\pmatrix{x_{11} & x_{12} & 0\\x_{21} & x_{22} & x_{23}\\ 0 & x_{32} & x_{33}}. $$

$\endgroup$
2
  • $\begingroup$ sorry but I'm not familiar with "permutation similarity" method, how did you get $M$? I still don't understand there. $\endgroup$ – J.Maisel Jun 29 '20 at 14:46
  • 1
    $\begingroup$ @J.Maisel No problem. $M$ is the matrix $P^{-1}[\Phi]P = P^T[\Phi]P$, where $P$ is the permutation matrix whose first column is column $1$ of the identity matrix, second column is column $5$ of the identity matrix, third column is column $9$ of the identity matrix, and so forth. $\endgroup$ – Ben Grossmann Jun 29 '20 at 15:36
3
$\begingroup$

Hint:

Show by induction that $Z_k$ is of the form

$$Z_k=\begin{bmatrix}a_k&0&0\\0&b_k&0\\0&0&a_k\end{bmatrix}$$

and that $Z_{2k}$ is a scalar multiple of the identity matrix. Since $\|Z_k\|_F=1$, it follows that $Z_{2k}=I/\|I\|_F$.

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