Jacobi eigenvalue algorithm

Remarks

The rotation $J$ is an orthogonal matrix, so $A'$ is similar to $A$ and the Frobenius norm $\norm{A'}_F = \norm{A}_F$ is unchanged. On the $2 \times 2$ block in rows and columns $p, q$, the choice of $\theta$ diagonalizes the block. So the sum of squares of that block's diagonal grows by $2 a_{pq}^2$. The other entries in rows and columns $p, q$ are only rotated, so their total square sum does not change. If $\abs{a_{pq}}$ is maximal among the $n(n-1)$ off-diagonal entries, then $a_{pq}^2 \ge \mathrm{off}(A)^2 / (n(n-1))$, which gives the linear bound. The diagonal entries of $A_k$ approach the eigenvalues because each eigenvalue lies within $\mathrm{off}(A_k)$ of some diagonal entry, by Weyl's inequality.

Example: for $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$, $\cot 2\theta = 0$ gives $\theta = \pi/4$, and one rotation gives $\mathrm{diag}(1, 3)$. In practice the local convergence is quadratic once the off-diagonal part is small. The product $J_0 J_1 \cdots J_k$ of the rotations converges to an orthogonal matrix whose columns are eigenvectors.

Going deeper

For a student

The method dates from Jacobi in 1846 and was revived on early computers. It is slower than the QR algorithm on a serial computer. But it computes small eigenvalues of well-scaled positive definite matrices to high relative accuracy, and it is easy to parallelize. Cyclic variants sweep through all pairs in a fixed order instead of searching for the largest entry, and they also converge. A one-sided version applied to $A^T A$ implicitly computes the singular value decomposition.