Schur Decomposition Calculator

What is Schur Decomposition?

Schur decomposition is a fundamental matrix factorization that expresses any square matrix A as the product A = QTQ^T (or A = QTQ^* in the complex case), where Q is a unitary (orthogonal, in the real case) matrix and T is an upper triangular matrix. Named after the German mathematician Issai Schur who proved its existence in 1909, the Schur decomposition reveals the eigenvalues of A along the diagonal of T while maintaining perfect numerical stability through orthogonal transformations.

Unlike eigendecomposition, which requires a matrix to have a full set of linearly independent eigenvectors, the Schur decomposition exists for every square matrix without exception. This universality makes it one of the most reliable tools in numerical linear algebra.

In this factorization, Q is an orthogonal matrix (Q^TQ = I), meaning its columns form an orthonormal basis, and T is an upper triangular matrix whose diagonal entries are the eigenvalues of A (for matrices with real eigenvalues) or whose diagonal contains 1×1 and 2×2 blocks encoding real and complex conjugate eigenvalue pairs (in the real Schur form).

Why Schur Decomposition Matters

The Schur decomposition occupies a central position in computational linear algebra because it provides a numerically stable way to compute eigenvalues. Direct computation of eigenvalues by finding roots of the characteristic polynomial is notoriously ill-conditioned: small perturbations in the matrix entries can lead to large errors in the computed eigenvalues when working through the polynomial. The Schur decomposition avoids the characteristic polynomial entirely, instead relying on orthogonal similarity transformations that preserve the 2-norm of the matrix and do not amplify rounding errors.

Every major numerical linear algebra library, including LAPACK, MATLAB, NumPy, and Julia's LinearAlgebra module, computes eigenvalues by first reducing the matrix to Schur form. The eigenvalues then simply appear on the diagonal of the triangular factor T. This approach is both more stable and more efficient than alternative methods for general matrices.

The Schur Decomposition Theorem

The existence of the Schur decomposition is guaranteed by a fundamental theorem in matrix analysis:

Theorem (Schur, 1909): For every square matrix A in C^n×n, there exists a unitary matrix Q and an upper triangular matrix T such that A = QTQ^*. The diagonal entries of T are the eigenvalues of A (in any prescribed order).

The proof proceeds by induction on the matrix dimension. For a 1×1 matrix, the result is trivial. For an n×n matrix, one takes any eigenvalue λ with corresponding unit eigenvector q₁, extends q₁ to an orthonormal basis, and forms the unitary matrix U = [q₁ | U₂]. Then U^*AU has λ in the (1,1) position and zeros below it in the first column. The remaining (n-1)×(n-1) submatrix can be decomposed by the inductive hypothesis, completing the construction.

This theorem is remarkable because it imposes no conditions on A whatsoever: the matrix need not be symmetric, normal, diagonalizable, or even invertible. Every square matrix has a Schur decomposition.

Real Schur Form vs. Complex Schur Form

When working with real matrices (entries in R rather than C), the eigenvalues may include complex conjugate pairs. Since the Schur decomposition aims to produce an upper triangular matrix with eigenvalues on the diagonal, the complex Schur form requires complex arithmetic even when the input matrix is real.

The real Schur form addresses this by allowing T to be quasi-upper triangular rather than strictly upper triangular. In the real Schur decomposition A = QTQ^T, the matrix Q is real orthogonal and T is block upper triangular with 1×1 blocks for real eigenvalues and 2×2 blocks for complex conjugate pairs. Each 2×2 diagonal block has the form:

The real Schur form is preferred in practice because it avoids complex arithmetic entirely while still revealing all the eigenvalue information. The 2×2 diagonal blocks encode complex conjugate eigenvalue pairs, and all eigenvalues can be extracted from T without ever leaving real arithmetic.

Connection to Eigenvalues

The relationship between the Schur decomposition and eigenvalues is direct and elegant. Since A = QTQ^T is a similarity transformation (A and T are similar matrices), they share the same eigenvalues. For the triangular matrix T, the eigenvalues are simply the diagonal entries. This gives us an immediate and computationally stable way to read off eigenvalues.

For normal matrices (matrices satisfying AA^T = A^TA, which includes symmetric, orthogonal, and skew-symmetric matrices), the Schur form T is actually diagonal. This means the Schur decomposition of a normal matrix coincides with its eigendecomposition, and the columns of Q are the eigenvectors. For non-normal matrices, the off-diagonal entries of T encode information about the defectiveness of eigenvalues and the sensitivity of the eigenvalue problem.

The departure from normality, often measured by the Frobenius norm of the strictly upper triangular part of T, quantifies how far a matrix is from being diagonalizable by a unitary transformation. This measure is important in perturbation theory and the analysis of non-normal operators.

The QR Algorithm Connection

The standard computational method for finding the Schur decomposition is the QR algorithm, one of the most important algorithms in numerical analysis. The basic QR algorithm works as follows:

1. Initialize: Set A₀ = A.
2. Iterate: At each step k, compute the QR factorization A_k = Q_kR_k, then form A_k+1 = R_kQ_k.
3. Converge: Under suitable conditions, the sequence A_k converges to an upper triangular matrix T (the Schur form).

The accumulated product Q = Q₀Q₁Q₂... gives the orthogonal factor in the Schur decomposition. In practice, the algorithm is enhanced with several critical optimizations:

• Preliminary Hessenberg reduction: The matrix is first reduced to upper Hessenberg form (upper triangular plus one subdiagonal) using Householder reflections. This reduces the cost of each QR iteration from O(n³) to O(n²).
• Shifted QR iterations: Instead of factoring A_k directly, the algorithm factors A_k - σ_kI where the shift σ_k is chosen to accelerate convergence. The Wilkinson shift (the eigenvalue of the trailing 2×2 submatrix closest to the bottom-right entry) provides cubic convergence in practice.
• Implicit shifts (Francis double shift): To keep all arithmetic real when processing real matrices with complex eigenvalue pairs, the Francis QR step applies two shifts simultaneously (a complex conjugate pair) while performing only real operations. This is the basis of the implicit double-shift QR algorithm used in LAPACK.
• Deflation: When a subdiagonal entry becomes negligibly small, the matrix decouples into independent smaller problems, accelerating convergence.

Applications of Schur Decomposition

The Schur decomposition appears throughout scientific computing and engineering:

• Eigenvalue computation: As discussed, the Schur decomposition is the backbone of virtually all practical eigenvalue algorithms. Libraries such as LAPACK, MATLAB, and NumPy compute eigenvalues by first reducing to Schur form.
• Matrix functions: Computing functions of matrices, such as the matrix exponential e^A, matrix logarithm, or matrix square root, is greatly simplified in Schur form. Since f(A) = Qf(T)Q^T, and T is triangular, the matrix function f(T) can be computed column by column using the Parlett recurrence. This is the approach used by MATLAB's expm, logm, and sqrtm functions.
• Control theory: In control systems, the Schur decomposition is essential for solving Lyapunov equations (AX + XA^T = -C), Sylvester equations (AX + XB = C), and algebraic Riccati equations. The Bartels-Stewart algorithm solves Sylvester equations by first computing the Schur decompositions of A and B, transforming the equation into triangular form, and solving by back substitution.
• Stability analysis: The eigenvalues revealed by the Schur decomposition determine the stability of dynamical systems. A continuous-time linear system x' = Ax is stable if and only if all eigenvalues have negative real parts. The Schur form provides a numerically reliable way to check this condition and to separate stable and unstable invariant subspaces.
• Model reduction: In large-scale systems, the ordered Schur decomposition is used to identify dominant modes and perform balanced truncation for model order reduction.
• Computing invariant subspaces: The ordered real Schur form allows extraction of invariant subspaces corresponding to selected eigenvalues. By reordering the diagonal blocks of T, one can move eigenvalues of interest to the top-left corner and read off the corresponding invariant subspace from the leading columns of Q.

Computational Complexity

The full Schur decomposition of an n×n matrix requires the following computational effort:

• Hessenberg reduction: The initial reduction to upper Hessenberg form using Householder reflections costs approximately 10n³/3 floating-point operations.
• QR iterations: Each Francis double-shift QR step on a Hessenberg matrix costs O(n²) operations. In practice, the total number of QR steps scales linearly with n, so the total cost of the iterative phase is approximately O(n³).
• Accumulating Q: If the orthogonal factor Q is needed (not just the eigenvalues), accumulating the transformations adds roughly 4n³/3 to the cost.

The overall cost is approximately 25n³ floating-point operations when both Q and T are computed, or about 10n³ when only eigenvalues are needed. This makes the Schur decomposition more expensive than LU factorization (2n³/3) but comparable to the full SVD.

Comparison with Eigendecomposition

The Schur decomposition and eigendecomposition are closely related but differ in important ways:

• Existence: The Schur decomposition exists for every square matrix. Eigendecomposition (A = XΛX^-1) requires A to have n linearly independent eigenvectors, which fails for defective matrices. For example, the matrix [[0, 1], [0, 0]] has a Schur decomposition but no eigendecomposition.
• Numerical stability: The Schur decomposition uses orthogonal transformations (condition number 1), so it is inherently well-conditioned. Eigendecomposition involves the eigenvector matrix X, which can be extremely ill-conditioned for non-normal matrices, leading to unreliable results.
• Information content: Eigendecomposition provides eigenvectors directly, which the Schur decomposition does not (except for normal matrices). However, the Schur vectors (columns of Q) span the same invariant subspaces and are always orthonormal.
• Computation: In practice, eigendecomposition is computed by first finding the Schur form and then solving for eigenvectors from the triangular system. The Schur decomposition is therefore always an intermediate step in eigendecomposition.

When to Use Schur Decomposition

• You need to compute eigenvalues of a general (possibly non-symmetric) square matrix in a numerically stable way
• You need to evaluate matrix functions such as the matrix exponential, logarithm, or square root
• You are solving Sylvester or Lyapunov equations in control theory applications
• You need to analyze the stability of a dynamical system by examining eigenvalue locations
• You want to compute invariant subspaces corresponding to selected groups of eigenvalues
• The matrix may be defective (lacking a full set of eigenvectors), making eigendecomposition impossible
• You need an orthonormal basis for an invariant subspace rather than individual eigenvectors