The Jacobi Eigenvalue Algorithm

Every square matrix describes a transformation: stretch, shrink, rotate, shear. Hidden inside any symmetric matrix — one that equals its own transpose — are special directions called eigenvectors along which the transformation acts as a pure stretch. The stretch factors are the eigenvalues, and knowing them unlocks the geometry of the whole transformation.

Finding eigenvalues is one of the central tasks of numerical computing. Physicists need them for quantum energy levels, engineers for vibration modes, data scientists for dimensionality reduction. The naive approach — solving the characteristic polynomial $\det(A - \lambda I) = 0$ — becomes numerically unstable and computationally brutal for large matrices.

In 1846, the mathematician Carl Gustav Jacob Jacobi described a beautifully simple alternative: apply a sequence of plane rotations, each one annihilating a single off-diagonal entry, until the matrix is diagonal. When the dust settles, the diagonal entries are the eigenvalues. The algorithm is still in active use today, nearly 180 years later.

Below is a symmetric $3 \times 3$ matrix. Each Step button applies one Jacobi rotation, targeting the largest off-diagonal entry and annihilating it. Watch the off-diagonal values shrink toward zero while the diagonal converges to the eigenvalues.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="matrix-wrap">
  <div class="matrix-label">{{label_matrix}}</div>
  <table id="matrix" class="matrix"></table>
</div>
<div class="stats-row">
  <span class="stat-item"><span class="stat-label">{{label_off_diag}}:</span> <span id="off-norm" class="stat-val">—</span></span>
  <span class="stat-item"><span class="stat-label">{{label_steps}}:</span> <span id="step-count" class="stat-val">0</span></span>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-sweep" type="button">{{btn_sweep}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.matrix-wrap { margin: .4rem 0 .6rem; }
.matrix-label { font-size: .8rem; font-weight: 600; color: #5a7088; margin-bottom: .3rem; text-transform: uppercase; letter-spacing: .04em; }
.matrix { border-collapse: separate; border-spacing: 4px; }
.matrix td { width: 56px; height: 40px; text-align: center; font: 600 13px ui-monospace, monospace;
             border-radius: 6px; border: 1px solid #cdd9e3; transition: background .3s, color .3s; }
.matrix td.diag { background: #e0eedb; color: #1a5c2a; border-color: #a8d4a0; }
.matrix td.off-hi { background: #fde8e8; color: #a01010; border-color: #f5b3b3; }
.matrix td.off { background: #f0f4f8; color: #334; border-color: #cdd9e3; }
.stats-row { display: flex; gap: 1.2rem; margin: .3rem 0 .5rem; flex-wrap: wrap; }
.stat-item { font-size: .88rem; }
.stat-label { color: #555; }
.stat-val { font-weight: 700; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; color: #333; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d5f9e; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

After enough steps, the matrix is essentially diagonal. The three diagonal entries are the eigenvalues — the stretch factors of the original transformation along its principal axes. Press Reset to start over with a fresh random matrix.

How does the Jacobi algorithm behave as a computation?

• One rotation, one entry zeroed. A Jacobi rotation is a $2 \times 2$ rotation embedded in an $n \times n$ identity matrix. Multiplying $A$ on both sides takes $O(n)$ work and drives one off-diagonal entry to exactly zero — but may slightly disturb others already zeroed.
• A sweep costs $O(n^2)$ rotations, $O(n^3)$ arithmetic. One complete sweep through all $\frac{n(n-1)}{2}$ off-diagonal positions is called a sweep, and costs $O(n^3)$ floating-point operations — the same order as a matrix multiplication.
• Convergence is quadratic (and proven). Jacobi proved in 1846 that the sum of squares of off-diagonal entries decreases by a constant factor each sweep. The method always converges for symmetric real matrices. Once the off-diagonal norm falls below a threshold $\varepsilon$, the diagonal entries approximate eigenvalues to within $O(\varepsilon)$.
• Modern alternatives exist. For large $n$, the QR algorithm (1961, Francis and Kublanovskaya) typically runs faster in practice. But Jacobi remains the preferred choice when high accuracy is needed for small dense matrices, and its parallel variants excel on modern hardware.

The key theoretical point: the sum $S = \sum_{i \neq j} a_{ij}^{2}$ after zeroing entry $(p, q)$ satisfies $S' \leq S \cdot \bigl(1 - \tfrac{2}{n(n-1)}\bigr)$, guaranteeing geometric convergence. Dimensionality reduction via PCA relies on exactly this kind of eigensolver.

Finding eigenvalues of symmetric matrices is one of the most common operations in quantitative science, and Jacobi's rotations underpin many of those computations:

• Quantum mechanics: energy levels of a physical system are eigenvalues of its Hamiltonian matrix. Small systems are still diagonalized by Jacobi methods.
• Structural engineering: the natural vibration frequencies of a bridge or aircraft wing are eigenvalues of a stiffness-mass matrix. Identifying them prevents resonance disasters.
• Principal Component Analysis (PCA): the directions of maximum variance in a dataset are eigenvectors of its covariance matrix. Jacobi-style sweeps are used when the matrix is small and accuracy matters.
• Computer graphics: inertia tensors, stress tensors, and deformation gradients are all symmetric matrices whose eigenvectors define principal axes for physical simulation.
• Signal processing: the signal and noise subspaces in MUSIC and ESPRIT algorithms for direction-of-arrival estimation are found by eigendecomposition of covariance matrices.

Any time a problem reduces to "find the principal axes of this symmetric object," you are one Jacobi sweep away from the answer. The algorithm's beauty lies in its directness: it does not approximate eigenvalues — it becomes them.

The Jacobi eigenvalue algorithm is a rare thing in computing: a method that is simultaneously simple, provably correct, and still useful after nearly two centuries. It asks a deceptively modest question — "what if I just rotate away the biggest off-diagonal entry, over and over?" — and the answer is that the matrix diagonalizes, revealing its eigenvalues one rotation at a time.

From quantum energy levels to the principal components of your data, eigenvalues of symmetric matrices are everywhere. The next time a physicist solves a Hamiltonian or a data scientist runs PCA, somewhere in the machinery is the same geometric insight Jacobi had in 1846: rotate the coordinate system until the transformation has nowhere left to hide.