Norm of off-diagonal matrix terms decreases under similarity transformation with Givens matrix. Detail of proof.

227 Views Asked by At

Let $A$ be a symmetric matrix, and $B=J(p, q,\theta) A J^T(p, q,\theta)$, where $J$ is the Givens rotation matrix that rotates in the $p, q$ plane by an angle $\theta$.

Consider the magnitude $\text{off}(B)$, as the square root of the sum of squares of the off-diagonal terms of $B$:

$$\text{off}(B)^2={\left\lVert B \right\rVert}_F - \sum_{i=1}^n b_{ii}^2$$

In relating it to the value of that magnitude for the original matrix, $\text{off}(A)$, and reach the known result: $\text{off}(B)^2 = \text{off}(A)^2 -2a_{pq}^2$ (see ref. [3]), it is made the following:

\begin{array}{ll} \text{off}(B)^2 &= {\left\lVert A \right\rVert}_F - \sum_{i=1}^n b_{ii}^2 = {\left\lVert A \right\rVert}_F - \sum_{i \neq p, q} b_{ii}^2 - (b_{pp}^2+b_{qq}^2) &= {\left\lVert A \right\rVert}_F - \sum_{i \neq p, q} a_{ii}^2 - (b_{pp}^2+b_{qq}^2)\\ &\uparrow &\uparrow \\ & \left\lVert A \right\rVert_F=\left\lVert B \right\rVert_F \ \textrm{, because} \ J \ \text{is orthogonal} &\textrm{only}\ p\textrm{-th} \ \textrm{and} \ q\textrm{-th} \ \textrm{rows and columns of A change} \\ \\ &={\left\lVert A \right\rVert}_F - \sum_{i \neq p, q} a_{ii}^2 - (a_{pp}^2+ 2a_{pq}^2 +a_{qq}^2) \\ &\uparrow \\ &?? \ \textrm{(my question)} \end{array}

I understand this implies that $$b_{pp}^2+b_{qq}^2 = a_{pp}^2+ 2a_{pq}^2 +a_{qq}^2\quad (1)$$

To verify this, I calculate the value of the transformed $p$-th and $q$-th diagonal terms:

\begin{align} b_{pp} &= c^2a_{pp}-2csa_{pq}+s^2a_{qq}\\ b_{qq} &= s^2a_{pp}+2csa_{pq}+c^2a_{qq} \end{align}

with $c$ and $s$ being $\cos(\theta)$ and $\sin(\theta)$ respectively.

I then square and add them, leading to a long expression that seems far from being the stated result $(1)$. For example, the coefficient of $a_{pp}$ turns out to be $c^4+ s^4$, instead of $1$, and so does the coefficient of $a_{qq}$.

Does this resulting long trigonometric expression just ends up leading to eq. $(1)$? Or just am I missing something in the procedure?

Possibly this not a general result and other conditions need to be imposed for that to happen. This result is used to prove that the Jacobi eigenvalue algorithm converges to a diagonal matrix upon the repeated application of this transformation. In it, the angle $\theta$ is chosen such that the entries in the $(p,q)$ and $(q,p)$ positions are zeroed after the transformation, i.e. $b_{pq}$, $b_{qp}=0$. As pointed in the comments, for size-2 matrices and $\theta=-\frac{\pi}{2}$, it does not hold.

References:

[1] https://en.wikipedia.org/wiki/Givens_rotation
[2] https://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm
[3] https://web.stanford.edu/class/cme335/lecture7.pdf

1

There are 1 best solutions below

4
On BEST ANSWER

Equality $(1)$ is false in general. E.g. $$ \pmatrix{0&-1\\ 1&0}\pmatrix{0&1\\ 1&0}\pmatrix{0&1\\ -1&0}=\pmatrix{0&-1\\ -1&0}. $$ However, in the context of the linked lecture notes, $p,q$ and $\theta$ are chosen such that $b_{pq}=b_{qp}=0$. It follows that $$ a_{pp}^2+a_{pq}^2+a_{qp}^2+a_{qq}^2 =b_{pp}^2+\underbrace{b_{pq}^2+b_{qp}^2}_{0+0}+b_{qq}^2 =b_{pp}^2+b_{qq}^2. $$ For instance, in the example above, if we use a Givens rotation for an angle $\pi/4$, we have $$ \frac{1}{\sqrt{2}}\pmatrix{1&1\\ -1&1}\underbrace{\pmatrix{0&1\\ 1&0}}_A\frac{1}{\sqrt{2}}\pmatrix{1&-1\\ 1&1}=\underbrace{\pmatrix{1&0\\ 0&-1}}_B, $$ so that $a_{pp}^2+2a_{pq}^2+a_{qq}^2=b_{pp}^2+b_{qq}^2$ and $\operatorname{off}(B)^2=0<2=\operatorname{off}(A)^2$.