QR Algorithm¶

An eigenvalue iteration that repeatedly QR-factorizes a shifted matrix and reverses the factors, preserving similarity while driving it toward real or complex Schur form for deflation.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2577
Origin domain: numerical linear algebra
Subdomain: eigenvalue algorithms
Aliases: QR iteration

Core Idea¶

The QR algorithm computes matrix eigenvalues through a sequence of orthogonal or unitary similarity transformations. In the unshifted idealization, factor the current square matrix as A_k=Q_k R_k, then reverse the factors: A_(k+1)=R_k Q_k. Because R_k Q_k=Q_k^* A_k Q_k, the new matrix is similar to the old one and has the same eigenvalues. Under appropriate conditions, repeated steps drive the matrix toward triangular complex Schur form, or quasi-triangular real Schur form.^[1]^[2]

Practical QR is not merely this classroom loop. Dense solvers normally reduce the matrix to upper Hessenberg form, choose shifts to accelerate convergence, chase the resulting bulge implicitly, detect negligible subdiagonal entries, and deflate converged blocks. These roles make the method both recognizable and computationally viable.^[3]^[4]

Structural Signature¶

Recognition roles:

square input matrix whose eigenvalues are sought;
similarity invariant preserving the spectrum through orthogonal/unitary transformations;
QR factorization step, explicit or implicit;
factor reversal producing the next iterate;
shift selection, often based on a trailing block;
structured reduction, usually Hessenberg or tridiagonal for efficient iterations;
convergence monitor on subdiagonal entries or blocks; and
deflation and Schur readout extracting eigenvalues as one-by-one or two-by-two diagonal blocks.

An implementation may perform no visible full QR factorization: the implicit Q theorem permits equivalent bulge-chasing transformations. It still belongs when the shifted QR similarity step and deflation logic govern the computation.

What It Is Not¶

QR factorization alone decomposes a matrix and supports least squares; it is one operation used by the QR eigenvalue algorithm. The QR algorithm is not Gram–Schmidt, although Gram–Schmidt can theoretically construct a QR factorization. Stable implementations use Householder reflectors or rotations.^[4]

It is not the power method, inverse iteration, Jacobi eigenvalue method, singular-value QR algorithm, or QZ algorithm for generalized eigenvalue problems. It does not guarantee convergence at the same rate for every matrix or shift policy. For a nonsymmetric real matrix, the real endpoint can contain two-by-two blocks representing complex-conjugate eigenvalue pairs rather than a real diagonal matrix.

Scope of Application¶

QR is the foundational dense eigenvalue method for real and complex matrices. Symmetric or Hermitian problems reduce to tridiagonal form and preserve that structure; general problems reduce to Hessenberg form. Applications span vibrations, stability, control, quantum models, Markov processes, data analysis, and any computation requiring a full or substantial spectrum.

Large sparse problems often use Krylov methods when only a few eigenvalues are wanted, because a full dense QR computation wastes structure and storage. Specialized symmetric eigensolvers may use divide-and-conquer, bisection, or MRRR after reduction. QR remains the conceptual and implementation baseline, not the only eigenvalue tool.^[2]^[4]

Clarity¶

For a shifted step, factor A_k-mu_k I=Q_k R_k and set A_(k+1)=R_k Q_k+mu_k I. Substitution gives A_(k+1)=Q_k^* A_k Q_k. Thus shifts change convergence behavior without changing eigenvalues. When a subdiagonal entry becomes negligible relative to nearby diagonal entries, the matrix splits approximately into independent blocks and the converged block can be deflated.

The algorithm returns Schur structure before it necessarily returns eigenvectors. Eigenvalues come from diagonal entries in complex arithmetic or diagonal one-by-one and two-by-two blocks in real arithmetic. Eigenvectors require accumulation or back transformation and can be ill-conditioned even when the Schur form is computed stably.

Manages Complexity¶

Similarity transformation converts a global polynomial-root problem into progressive structural simplification. Hessenberg reduction makes later iterations cheap because zeros below the first subdiagonal are preserved. Shifts focus progress near a target eigenvalue; deflation shrinks the active problem; bulge chasing realizes the transformation without dense factorization at every step.^[3]

The method also manages numerical stability by using orthogonal transformations, which do not magnify vector norms in exact arithmetic. Complexity remains substantial for dense matrices, and convergence tests must respect floating-point scale. Premature deflation corrupts accuracy; overly strict tests waste iterations.

Abstract Reasoning¶

The similarity equation is the load-bearing proof. Every exact iterate has the same characteristic polynomial. If off-diagonal structure converges away, the invariant spectrum becomes readable from triangular blocks. This separates correctness of the target from convergence of the representation.

Shifts can be chosen from trailing entries because they need not equal exact eigenvalues to preserve similarity. Exceptional shifts and multi-shift strategies handle stagnation. Symmetry preservation predicts real eigenvalues and a diagonal endpoint for symmetric inputs; general real inputs predict quasi-triangular blocks. None of these facts licenses treating individual intermediate diagonal entries as final eigenvalues before convergence.^[2]

Knowledge Transfer¶

The literal role package transfers among symmetric, nonsymmetric, real, complex, single-shift, double-shift, and multishift solvers. Reduction, shifted similarity, bulge chasing, convergence, and deflation remain recognizable while kernels differ.

The broader pattern—preserve an invariant while iteratively changing representation toward readable normal form—transfers beyond matrices. That residue belongs to Iteration, Invariance, Refinement, and Normal Form. Without QR factors and spectral Schur structure it is not the QR algorithm.

Examples¶

Diagonal matrix. A diagonal matrix is already Schur form. QR steps preserve it up to harmless sign/phase conventions, and every one-by-one block can be deflated immediately.

Symmetric two-by-two matrix. Orthogonal similarity drives the off-diagonal entry toward zero; the two diagonal limits are the real eigenvalues. A Wilkinson-style shift chosen from the trailing block accelerates this behavior.^[2]

Real rotation matrix. A planar rotation with nonreal eigenvalues cannot converge to a real diagonal matrix. Its real Schur form retains a two-by-two block, demonstrating why “triangular” must be qualified in real arithmetic.

Dense general matrix. First reduce to Hessenberg form. Each implicit shifted step introduces a small bulge, chases it down with orthogonal transformations, restores Hessenberg form, and deflates when a subdiagonal entry is negligible.^[3]

Shift comparison. Applying unshifted QR to a matrix with clustered eigenvalues can leave a trailing subdiagonal entry decreasing frustratingly slowly. Choosing a shift from the trailing one-by-one or two-by-two block changes the factorization but not the similarity invariant; the same spectral target can become visible in far fewer iterations. This demonstrates that a shift is an acceleration policy, not a perturbation of the requested eigenvalues.

Eigenvector boundary. Once a solver has produced Schur form, it can accumulate the orthogonal transformations and solve triangular systems to recover eigenvectors. That downstream stage may reveal severe conditioning even when backward error in the Schur form is small. The example prevents “QR computes eigenvalues stably” from being inflated into a universal claim that every individual eigenvector is accurately determined.

Structural Tensions¶

Simple recurrence versus practical implementation. The explicit loop is explanatory but inefficient. Diagnostic: verify Hessenberg reduction, implicit shifts, and deflation in a production claim.
Spectral invariance versus convergence. Similarity preserves eigenvalues even when iterates stagnate. Diagnostic: separate invariant correctness from subdiagonal convergence evidence.
Aggressive deflation versus accuracy. Early splitting saves work but can alter sensitive blocks. Diagnostic: scale the deflation test to neighboring entries and machine precision.
Real arithmetic versus complex spectrum. Real matrices may have nonreal pairs. Diagnostic: accept two-by-two real Schur blocks rather than demand a real diagonal.
Autonomy versus QR factorization plus Iteration. Those are components. Diagnostic: remove factor reversal and spectrum-preserving deflation; if the eigenvalue method disappears, QR Algorithm retains an autonomous residual.

Structural–Framed Character¶

The similarity skeleton is structural; shift strategy, block size, convergence thresholds, and hardware kernels are framed implementation choices. Variants can differ dramatically in performance without changing identity. Numerical behavior also depends on matrix conditioning and floating-point environment.

Structural Core vs. Domain Accent¶

The core is invariant-preserving iteration toward a normal form. The domain accent supplies matrices, QR factorization, Hessenberg reduction, eigenvalues, shifts, Householder transformations, Schur blocks, and deflation. Those terms are indispensable.

The candidate is therefore domain-specific. It specializes Algorithm and relates to Iteration and Invariance, but does not qualify as a substrate-independent prime.

QR Algorithm specializes prime:algorithm, the minimal proposed parent. It instantiates Iteration through repeated similarity steps, Invariance through spectrum preservation, Refinement through deflation, and Decomposition through QR/Schur forms. Jacobi Method is a sibling eigenvalue algorithm rather than an ancestor.

Relationships to Other Abstractions¶

Current abstraction QR Algorithm Domain-specific

Parents (1) — more general patterns this builds on

QR Algorithm is a kind of Algorithm Prime

QR Algorithm specializes prime:algorithm, the minimal proposed parent.

Hierarchy paths (2) — routes to 2 parentless roots

QR Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

QR Algorithm sits in a sparse region of the domain-specific corpus (84^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Applied Linear & Special Functions (18 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

QR factorization: one matrix decomposition, not eigenvalue iteration.
Gram–Schmidt: basis-orthogonalization procedure.
Power/inverse iteration: targets selected eigenpairs through vector iteration.
QZ algorithm: generalized eigenvalue method for a matrix pair.
SVD QR iteration: related bidiagonal singular-value kernel with a different target.
Schur decomposition: output form/theorem rather than the iterative method.
Jacobi method: rotation-based eigenvalue algorithm, chiefly symmetric.
QR code: unrelated two-dimensional barcode.

References¶

[1] J. G. F. Francis, “The QR Transformation, Parts I and II,” The Computer Journal 4 (1961–1962), https://doi.org/10.1093/comjnl/4.3.265 and https://doi.org/10.1093/comjnl/4.4.332. registry ↩

[2] Gene H. Golub and Charles F. Van Loan, Matrix Computations, fourth edition, Johns Hopkins University Press, 2013, Chapter 7, ISBN 978-1-4214-0794-4. registry ↩a ↩b ↩c ↩d

[3] David S. Watkins, “The QR Algorithm Revisited,” SIAM Review 50 (2008): 133–145, https://doi.org/10.1137/060659454. registry ↩a ↩b ↩c

[4] E. Anderson et al., LAPACK Users' Guide, third edition, SIAM, 1999, eigenvalue-problem and QR-factorization chapters, https://www.netlib.org/lapack/lug/. registry ↩a ↩b ↩c