1
$\begingroup$

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

$\endgroup$
0

1 Answer 1

1
+50
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Giving another thought to this, I am still thinking how this generalizes to higher dimensions. In the $n=2$ case you are able to write the full norms explicitly (only have four terms). In the general case we know the norms are preserved as well, however not only the $(p, p)$, $(q, p)$, $(p, q)$ and $(p, p)$ entries are changed, but the rest of elements in their row and column as well. $\endgroup$
    – abcd
    Aug 14, 2021 at 18:41
  • $\begingroup$ I understand then the relation would be in general $\sum_{i \neq p, q} \left(a_{ip}^2 + a_{iq}^2 + a_{pi}^2 + a_{qi}^2\right) + a_{pp}^2 +a_{pq}^2+a_{qp}^2+a_{qq}^2 =\sum_{i \neq p, q} \left(b_{ip}^2 + b_{iq}^2 + b_{pi}^2 +b_{qi}^2\right) + b_{pp}^2+b_{pq}^2+b_{qp}^2+b_{qq}^2$ How can we prove the terms within the sum symbols cancel? $\endgroup$
    – abcd
    Aug 14, 2021 at 19:03
  • 1
    $\begingroup$ @abcd This has already been explained in the lecture notes. Suppose $(p,q)=(1,2)$. Let $R$ denotes the $2\times2$ rotation matrix for an angle $\theta$. Partition $A$ as $\pmatrix{X&Y\\ Z&W}$ where $X$ is $2\times2$. Then $$B=\pmatrix{R\\ &I}\pmatrix{X&Y\\ Z&W}\pmatrix{R^T\\ &I}=\pmatrix{RXR^T&RY\\ ZR^T&W}...$$ $\endgroup$
    – user1551
    Aug 14, 2021 at 19:14
  • 1
    $\begingroup$ ...In the $2\times2$ case, we have $\operatorname{off}(RXR^T)^2<\operatorname{off}(X)^2$. Therefore \begin{aligned}\operatorname{off}(B)^2&=\operatorname{off}(RXR^T)^2+\|RY\|_F^2+\|ZR^T\|_F+\operatorname{off}(W)^2\\ &=\operatorname{off}(RXR^T)^2+\|Y\|_F^2+\|Z\|_F+\operatorname{off}(W)^2\\ &<\operatorname{off}(X)^2+\|Y\|_F^2+\|Z\|_F+\operatorname{off}(W)^2\\ &=\operatorname{off}(A)^2.\end{aligned} $\endgroup$
    – user1551
    Aug 14, 2021 at 19:15

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.