The QR Algorithm

Every square matrix hides a set of special numbers called eigenvalues. They govern how the matrix stretches or rotates space, and they appear throughout science: the resonant frequencies of a structure, the energy levels of a quantum system, the ranking scores behind PageRank, the principal components in data analysis.

For decades, computing even one eigenvalue of a large matrix was a painful chore. Then in 1961, independently and almost simultaneously, J.H. Wilkinson, John Francis (in England) and Vera Kublanovskaya (in the USSR) discovered an iteration so elegant it seems like magic: factor the matrix, swap the two pieces, multiply them back together, and repeat.

After enough repetitions the matrix converges to a triangular form, and the eigenvalues simply read off the diagonal. This is the QR algorithm — named after the two matrices in its core factorization — and it was later voted one of the top ten algorithms of the 20th century by the journal Computing in Science and Engineering.

Below is a live 3×3 matrix undergoing QR iteration. At each step the matrix A is factored into Q (orthogonal) and R (upper-triangular), then the pieces are recombined as R·Q to form the next iterate.

<div class="demo-wrap">
  <div class="controls">
    <button id="stepBtn" type="button">{{btn_step}}</button>
    <button id="runBtn" type="button">{{btn_run}}</button>
    <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
    <span class="iter-label">{{label_iteration}} <span id="iterCount">0</span></span>
  </div>
  <div class="panels">
    <div class="panel">
      <div class="panel-title">{{panel_matrix}}</div>
      <div id="matA" class="matrix"></div>
    </div>
    <div class="panel">
      <div class="panel-title">{{panel_offdiag}}</div>
      <div id="chart" class="chart">
        <canvas id="cvs" width="256" height="90"></canvas>
      </div>
    </div>
  </div>
  <div class="eigen-row">
    <span class="eigen-label">{{label_diagonal}}</span>
    <span id="diagVals" class="diag-vals"></span>
  </div>
  <div class="eigen-row">
    <span class="eigen-label">{{label_true_ev}}</span>
    <span id="trueVals" class="diag-vals true"></span>
  </div>
  <div id="status" class="status"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.demo-wrap { padding: 4px 0; }
.controls { display: flex; align-items: center; gap: 8px; flex-wrap: wrap; margin-bottom: 10px; }
button { font: 600 13px system-ui; padding: 6px 14px; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.iter-label { font-size: 13px; color: #555; margin-left: 4px; }
.panels { display: flex; gap: 14px; flex-wrap: wrap; align-items: flex-start; margin-bottom: 10px; }
.panel { background: #f4f7fa; border: 1px solid #d0d9e4; border-radius: 8px; padding: 10px 12px; }
.panel-title { font-size: 12px; font-weight: 600; color: #4a6080; margin-bottom: 8px; }
.matrix { display: grid; grid-template-columns: repeat(3, 68px); gap: 3px; }
.cell { width: 68px; height: 34px; display: flex; align-items: center; justify-content: center;
        font: 500 12px ui-monospace, monospace; border-radius: 5px; transition: background 0.3s; }
.cell.diag { background: #dbeafe; border: 1px solid #93c5fd; color: #1e3a5f; }
.cell.off  { background: #fef3c7; border: 1px solid #fcd34d; color: #78350f; }
.cell.off.tiny { background: #f0fdf4; border: 1px solid #86efac; color: #166534; }
.chart { background: #fff; border: 1px solid #d0d9e4; border-radius: 6px; padding: 4px; }
canvas { display: block; }
.eigen-row { display: flex; align-items: baseline; gap: 8px; margin: 3px 0; flex-wrap: wrap; }
.eigen-label { font-size: 12px; font-weight: 600; color: #4a6080; white-space: nowrap; }
.diag-vals { font: 500 12px ui-monospace, monospace; color: #1d3557; }
.diag-vals.true { color: #15803d; }
.status { font-size: 13px; font-weight: 600; min-height: 1.3em; margin-top: 6px; color: #15803d; }

// Code not found

Press Step to advance one iteration, or Run to animate. Watch the off-diagonal entries shrink toward zero — when they are small enough, the numbers on the main diagonal are the eigenvalues. The true eigenvalues (computed exactly) are shown for comparison.

Status: solved (1961, Francis & Kublanovskaya) — efficient and numerically stable in practice.

The QR algorithm is beautifully analyzable:

• Why it works. Each QR step is an orthogonal similarity transformation: $A_{k+1} = R_k Q_k = Q_k^T A_k Q_k$. Similarity transformations preserve eigenvalues, so every iterate has the same eigenvalues. As the iterates accumulate, the off-diagonal entries are driven toward zero by the geometry of repeated matrix multiplication.
• Convergence rate. Without modifications, convergence can be slow — linear at best. Add a shift (subtract a scalar before factoring, add it back after) and convergence becomes cubic for simple eigenvalues. The Wilkinson shift chooses the shift adaptively, giving outstanding reliability in practice.
• Cost per step. A naive QR step on an n×n matrix costs $O(n^{3})$ arithmetic operations. The practical algorithm first reduces A to upper Hessenberg form ($O(n^{3})$ once), then each QR step costs only $O(n^{2})$. Total cost for all n eigenvalues: $O(n^{3})$, which is optimal to within constants for dense matrices.
• Symmetric vs general. For symmetric (or Hermitian) matrices, the algorithm reduces to the symmetric QR algorithm with guaranteed real eigenvalues and globally quadratic convergence. For general matrices, convergence is guaranteed under mild conditions, but pathological cases can arise — the Francis double-step and implicit-shift variants handle these in practice.

The QR algorithm is considered solved in the sense that the standard implementations (LAPACK's dsyev, dgeev) are numerically stable, efficient, and trusted in production software worldwide. The theoretical question of an optimal $O(n^{2})$ eigenvalue algorithm remains open, connecting to deep questions in matrix multiplication.

Eigenvalue computation is one of the most broadly useful operations in all of applied mathematics. The QR algorithm sits at the center of:

• Structural engineering: the natural frequencies of a building or bridge are eigenvalues of its stiffness matrix. Compute them wrong and resonance can be catastrophic.
• Quantum physics: the energy levels of an atom or molecule are eigenvalues of its Hamiltonian operator, discretized into a matrix and solved by QR-based methods.
• Machine learning (PCA): principal component analysis finds the directions of greatest variance by computing eigenvalues (and eigenvectors) of the data covariance matrix — the QR algorithm under the hood.
• Graph analysis and PageRank: the ranking score in PageRank is the dominant eigenvector of a huge sparse matrix; power iteration (a cousin of QR) drives it.
• Control systems: the stability of a controller depends on whether all eigenvalues of a system matrix lie inside the unit disk or left half-plane — a question answered by the QR algorithm.
• Scientific simulation: differential equations, fluid dynamics, and population models are all studied via the eigenstructure of linearized operators.

Without fast, reliable eigenvalue computation, vast swaths of modern science and engineering would grind to a halt.

The QR algorithm is a rare thing in computing: an idea that is both simple to state and provably optimal in practice. Factor the matrix into Q and R, multiply in reverse order, repeat — and the eigenvalues crystallize on the diagonal as if by magic.

The magic is not accidental. Each step is a similarity transformation, so eigenvalues are preserved while the off-diagonal entries are steadily squeezed. Add shifts for speed, Hessenberg reduction to cut cost, and implicit steps for numerical stability, and you have the algorithm that powers LAPACK, MATLAB, NumPy, and virtually every piece of scientific software on earth.

If you have ever computed a principal component, simulated a vibrating structure, or trusted a control system, you have quietly relied on Francis and Kublanovskaya's 1961 discovery — one of the most consequential loops in the history of algorithms.