THE QR ALGORITHM eigenvalues by factor-and-swap, repeated
One of the great algorithms of the 20th century: to find a matrix’s eigenvalues, factor it as A = QR (orthogonal times triangular, via Householder dart 089), then remultiply in reverse A’ = RQ, and repeat. The matrix marches to triangular form with the eigenvalues sitting on the diagonal. No characteristic polynomial, no root-finding.
THE TECHNIQUE factor, swap, repeat
Given A, compute A = QR with Q orthogonal and R upper-triangular; then set A’ = RQ (same eigenvalues, since RQ = QTAQ is a similarity). Iterate: the sub-diagonal entries shrink and the diagonal converges to the eigenvalues (a “shift” makes it converge cubically). Below: a symmetric matrix marching to diagonal. live demo
HISTORY & CREDIT two inventors, and an older idea
“QR is named for a person” — no; a surname the QR decomposition. And it has two independent inventors, not one. cited
1954 / 1958 · Heinz Rutishauser — the quotient-difference algorithm, then the LR algorithm (LU-factor and swap): the direct ancestor. QR is its orthogonal (stable) analogue. 1959–61 · John G. F. Francis (UK) — Part I received October 1959; the shifted, deflating, practical form. He then left the field and was untraceable for decades. 1961 · Vera N. Kublanovskaya (USSR) — independently, received Feb 1961. Fairly the Francis-Kublanovskaya algorithm; Francis was earlier. the standing · named a “top-10 algorithm of the 20th century” — it is how eigenvalues are actually computed today.
A method whose inventor vanished, rediscovered decades later running quietly inside every solver. Francis 1959 / Kublanovskaya 1961
RECOMMEND FOR I-13 Householder + a reverse multiply
Every step is real f64 on a symmetric matrix — and the 2×2 marches to its eigenvalues:
$ i13 run eig.i13 # symmetric [[2,1],[1,2]]
lambda = 3, 1 # QR converges the diagonal to the exact eigenvalues
Recommend: for a real symmetric input everything is f64 — the QR factor (via Householder, dart 089), the reverse multiply RQ, the sub-diagonal convergence test (sqrt/fabs), and the diagonal read-off all run (verified eigenvalues 3, 1). The matrix is 2-D — PS-004 — flattened to A[i*n+j], the runaway want. Note: the 2×2 closed form (a+d)/2 ± √(((a−d)/2)²+b²) is what the iteration converges to — verified as the ground truth above.