Schur Decomposition · aiwiki.page

The Schur decomposition is a matrix factorization that represents a square matrix in an orthonormal coordinate system where it is triangular, or block triangular when only real arithmetic is used. In its complex form, it expresses $A$ as $A=QTQ^*$ , where $Q$ is unitary and $T$ is upper triangular. The decomposition exposes the eigenvalues without requiring a basis of eigenvectors and is a fundamental tool in numerical linear algebra. (netlib.org)

Complex Schur decomposition

For every $A\in\mathbb C^{n\times n}$ , there exist a unitary matrix $Q$ and an upper triangular matrix $T$ such that

A=QTQ^*, \qquad Q^*AQ=T, \qquad Q^*Q=QQ^*=I.

Here $Q^*$ denotes the conjugate transpose, and $I$ is the identity matrix. The matrix $T$ is a Schur form of $A$ ; the columns of $Q$ are its Schur vectors. This is a similarity transformation, rather than merely a product factorization. (netlib.org)

The diagonal entries $t_{11},\ldots,t_{nn}$ are the eigenvalues of $A$ , counted with algebraic multiplicity. Consequently, its characteristic polynomial satisfies

\det(zI-A)=\prod_{j=1}^{n}(z-t_{jj}).

Unlike diagonalization, Schur triangularization exists even when $A$ has too few linearly independent eigenvectors to form a basis. Its upper-triangular entries retain information that a diagonal list of eigenvalues alone does not capture. (netlib.org)

Existence and proof

The existence theorem can be proved by induction on the matrix size. Choose a normalized eigenvector $q_1$ with eigenvalue $\lambda$ , and extend it to an orthonormal basis. Writing the resulting unitary matrix as $U=[q_1\ V]$ gives

U^*AU= \begin{pmatrix} \lambda & r\\ 0 & B \end{pmatrix}.

The lower-left block vanishes because $Aq_1=\lambda q_1$ . By the induction hypothesis, $B=W S W^*$ , with $W$ unitary and $S$ upper triangular. Thus

Q=U \begin{pmatrix} 1&0\\ 0&W \end{pmatrix}

makes $Q^*AQ$ upper triangular. The argument establishes existence without assuming that $A$ is diagonalizable. It is principally a theoretical proof, not the usual numerical procedure for finding the decomposition. (seas.ucla.edu)

Real Schur decomposition

For $A\in\mathbb R^{n\times n}$ , a decomposition using only real matrices always exists:

A=QTQ^{\mathsf T},

where $Q$ is an orthogonal matrix and $T$ is upper quasi-triangular. This means that $T$ is block upper triangular with diagonal blocks of size $1\times1$ or $2\times2$ . The scalar blocks represent real eigenvalues; the $2\times2$ blocks represent nonreal complex-conjugate pairs. (netlib.org)

A standard form for a nonreal pair is

\begin{pmatrix} a&b\\ c&a \end{pmatrix}, \qquad bc<0,

whose eigenvalues are

a\pm i\sqrt{-bc}.

The two off-diagonal entries need not be negatives of one another. (netlib.org)

For example,

A= \begin{pmatrix} 0&-1\\ 1&0 \end{pmatrix}

is already a real Schur form, with $Q=I$ . Direct calculation gives eigenvalues $i$ and $-i$ . It cannot be made upper triangular by a real similarity transformation: a real triangular matrix has real diagonal entries and therefore only real eigenvalues. The $2\times2$ block is what permits real arithmetic to represent this pair.

Schur vectors and invariant subspaces

Schur vectors are generally not individual eigenvectors. From $AQ=QT$ , the first Schur vector satisfies $Aq_1=t_{11}q_1$ , but later columns may be mapped into combinations of several preceding columns. Nevertheless, the first $k$ columns always span an invariant subspace in the complex Schur form:

A Q_k=Q_k T_k,

where $Q_k=[q_1,\ldots,q_k]$ and $T_k$ is the leading $k\times k$ block of $T$ . For a real Schur form, this statement applies at complete diagonal-block boundaries. (netlib.org)

The eigenvalues can be reordered so that a chosen group occupies the leading diagonal positions. The corresponding leading Schur vectors then provide an orthonormal basis for an invariant subspace associated with that group. This is useful when the subspace as a whole is more relevant than separate eigenvectors. (netlib.org)

The decomposition is not unique. For example, if $D$ is diagonal and unitary, then

A=(QD)(D^*TD)(QD)^*

is another Schur decomposition. Reordering eigenvalues introduces further alternatives; repeated eigenvalues can allow additional choices of basis within invariant subspaces. These transformations illustrate why a Schur form is not a unique canonical array of entries.

Normal matrices and diagonalization

A normal matrix satisfies $A^*A=AA^*$ . For such a matrix, its complex Schur form is diagonal: unitary similarity preserves normality, and an upper triangular normal matrix must be diagonal. Conversely, a matrix unitarily similar to a diagonal matrix is normal. This gives the finite-dimensional spectral theorem for complex normal matrices. (seas.ucla.edu)

An elementary example shows why triangularization is more general. Let

A= \begin{pmatrix} 1&1\\ 0&1 \end{pmatrix}.

Taking $Q=I$ and $T=A$ gives a Schur decomposition. However, solving $(A-I)x=0$ leaves only one independent eigenvector, so $A$ is not diagonalizable. The nonzero entry above the diagonal cannot simply be discarded without changing the represented linear transformation.

Numerical computation and stability

Standard dense algorithms first reduce $A$ to an upper Hessenberg matrix $H$ , which has zeros below its first subdiagonal. This is done through orthogonal or unitary similarity transformations, commonly implemented using Householder transformations. The QR algorithm then reduces $H$ to Schur form while accumulating the transformations needed to obtain $Q$ . Eigenvectors, if required, are computed separately from the triangular or Hessenberg problem. (netlib.org)

For dense matrices, the typical computational cost is $O(n^3)$ , although the operation count depends on convergence and on whether Schur vectors are accumulated. (wwwuser.gwdguser.de)

Well-designed Schur algorithms are backward stable: their computed result can be interpreted, up to rounding effects, as an exact factorization of a nearby matrix $A+E$ , with a small normwise perturbation $E$ . This form of numerical stability does not guarantee that every eigenvalue or eigenvector has small forward error. Sensitive spectral quantities may change substantially under a small perturbation, as measured by their condition numbers. (netlib.org)

The orthonormal Schur basis avoids the ill-conditioned change of coordinates that can occur with an eigenvector basis. It does not, however, remove the intrinsic sensitivity of eigenvalues, invariant subspaces, or subsequent computations. (netlib.org)

Applications

Eigenvalue problems. The diagonal entries or diagonal blocks of the Schur form supply the eigenvalues. Reordering the form also supports calculations involving selected invariant subspaces and their sensitivity. (netlib.org)

Matrix functions. For an appropriately defined matrix function, similarity gives

f(A)=Qf(T)Q^*.

Algorithms can therefore work with triangular $T$ instead of a general matrix. Schur-based methods are used for matrix exponentials, logarithms, square roots, and other functions. The triangular reduction is a starting point, not a guarantee that every subsequent recurrence is stable. (epubs.siam.org)

Matrix equations. For the Sylvester equation $AX+XB=C$ , write

A=USU^*,\qquad B=VTV^*.

The substitutions $Y=U^*XV$ and $D=U^*CV$ reduce the equation to

SY+YT=D.

The triangular or quasi-triangular structure permits systematic substitution. This reduction is central to the Bartels–Stewart method. (netlib.org)

Generalized Schur decomposition

The generalized Schur decomposition, also called the QZ decomposition, extends the construction to a pair of square matrices:

A=QSZ^*,\qquad B=QTZ^*,

with $Q,Z$ unitary and $S,T$ upper triangular in the complex case. Unlike ordinary Schur decomposition, it uses two generally different transformation matrices. (netlib.org)

For a regular matrix pencil $A-\lambda B$ , generalized eigenvalues are represented by diagonal pairs

(\alpha_j,\beta_j)=(s_{jj},t_{jj}).

When $\beta_j\ne0$ , the eigenvalue is $\alpha_j/\beta_j$ ; a nonzero $\alpha_j$ with $\beta_j=0$ represents an infinite eigenvalue. A pair $(0,0)$ signals a singular-pencil issue rather than an ordinary finite or infinite eigenvalue. The real version uses quasi-triangular blocks to retain real arithmetic for complex-conjugate pairs. (netlib.org)

References

Eigenvalues, Eigenvectors and Schur Factorizationnetlib.org
Schur decompositionseas.ucla.edu
LAPACK: dlanv2netlib.org
LAPACK, Handbook of Linear Algebranetlib.org
Introduction to Linear Algebra, 5th Editionmath.mit.edu
Invariant Subspaces and Condition Numbersnetlib.org
f08 – Least-squares and Eigenvalue Problems (LAPACK)wwwuser.gwdguser.de
LAPACK Working Note 13netlib.org
A Schur–Parlett Algorithm for Computing Matrix Functionseprints.maths.manchester.ac.uk
Eigenvalues, Eigenvectors and Generalized Schur Decompositionnetlib.org
LAPACK: sggesnetlib.org