Jacobi rotation

In numerical linear algebra, a Jacobi rotation is a rotation, Q_kℓ, of a 2-dimensional linear subspace of an n-dimensional inner product space, chosen to zero a symmetric pair of off-diagonal entries of an n×n real symmetric matrix, A, when applied as a similarity transformation:

${\displaystyle A\mapsto Q_{k\ell }^{T}AQ_{k\ell }=A'.\,\!}$

${\displaystyle {\begin{bmatrix}{*}&&&\cdots &&&*\\&\ddots &&&&&\\&&a_{kk}&\cdots &a_{k\ell }&&\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\&&a_{\ell k}&\cdots &a_{\ell \ell }&&\\&&&&&\ddots &\\{*}&&&\cdots &&&*\end{bmatrix}}\to {\begin{bmatrix}{*}&&&\cdots &&&*\\&\ddots &&&&&\\&&a'_{kk}&\cdots &0&&\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\&&0&\cdots &a'_{\ell \ell }&&\\&&&&&\ddots &\\{*}&&&\cdots &&&*\end{bmatrix}}.}$

It is the core operation in the Jacobi eigenvalue algorithm, which is numerically stable and well-suited to implementation on parallel processors .

Only rows k and ℓ and columns k and ℓ of A will be affected, and that A′ will remain symmetric. Also, an explicit matrix for Q_kℓ is rarely computed; instead, auxiliary values are computed and A is updated in an efficient and numerically stable way. However, for reference, we may write the matrix as

${\displaystyle Q_{k\ell }={\begin{bmatrix}1&&&&&&\\&\ddots &&&&0&\\&&c&\cdots &s&&\\&&\vdots &\ddots &\vdots &&\\&&-s&\cdots &c&&\\&0&&&&\ddots &\\&&&&&&1\end{bmatrix}}.}$

That is, Q_kℓ is an identity matrix except for four entries, two on the diagonal (q_kk and q_ℓℓ, both equal to c) and two symmetrically placed off the diagonal (q_kℓ and q_ℓk, equal to s and −s, respectively). Here c = cos θ and s = sin θ for some angle θ; but to apply the rotation, the angle itself is not required. Using Kronecker delta notation, the matrix entries can be written:

${\displaystyle q_{ij}=\delta _{ij}+(\delta _{ik}\delta _{jk}+\delta _{i\ell }\delta _{j\ell })(c-1)+(\delta _{ik}\delta _{j\ell }-\delta _{i\ell }\delta _{jk})s.\,\!}$

Suppose h is an index other than k or ℓ (which must themselves be distinct). Then the similarity update produces, algebraically:

${\displaystyle a'_{hk}=a'_{kh}=ca_{hk}-sa_{h\ell }\,\!}$

${\displaystyle a'_{h\ell }=a'_{\ell h}=ca_{h\ell }+sa_{hk}\,\!}$

${\displaystyle a'_{k\ell }=a'_{\ell k}=(c^{2}-s^{2})a_{k\ell }+sc(a_{kk}-a_{\ell \ell })=0\,\!}$

${\displaystyle a'_{kk}=c^{2}a_{kk}+s^{2}a_{\ell \ell }-2sca_{k\ell }\,\!}$

${\displaystyle a'_{\ell \ell }=s^{2}a_{kk}+c^{2}a_{\ell \ell }+2sca_{k\ell }.\,\!}$