Schur decomposition

From Wikipedia, the free encyclopedia

In the mathematical discipline of linear algebra, the Schur decomposition or Schur triangulation (named after Issai Schur) is an important matrix decomposition.

Contents

[edit] Statement

The Schur decomposition reads as follows: if A is a n × n square matrix with complex entries, then A can be expressed as

A = Q U Q^{-1}\,

where Q is a unitary matrix (so that its inverse Q−1 is also the conjugate transpose Q* of Q), and U is an upper triangular matrix, which is called a Schur form of A. Since U is similar to A, it has the same multiset of eigenvalues, and since it is triangular, those eigenvalues are the diagonal entries of U.

The Schur decomposition implies that there exist a nested sequence of A-invariant subspaces {0} = V0 ⊂ V1 ⊂ ... ⊂ Vn = Cn, and that there exists an ordered orthonormal basis (for the standard Hermitian form of Cn) such that the first i basis vectors span Vi for each i. Phrased somewhat differently, the first part says that an operator T on a complex finite-dimensional vector space stabilizes a complete flag (V1,...,Vn).

[edit] Proof

A constructive proof for the Schur decomposition is as follows: every operator A on a complex finite-dimensional vector space has an eigenvalue λ, corresponding to some eigenspace Vλ. Let Vλ⊥ be its orthogonal complement. It is clear that, with respect to this orthogonal decomposition, A has matrix representation (one can pick here any orthonormal bases spanning Vλ and Vλ⊥ respectively)

A = \begin{bmatrix} \lambda \, I_{\lambda} & A_{12} \\ 0 & A_{22} \end{bmatrix}: \begin{matrix} V_{\lambda} \\ \oplus \\ V_{\lambda}^{\perp} \end{matrix} \rightarrow \begin{matrix} V_{\lambda} \\ \oplus \\ V_{\lambda}^{\perp} \end{matrix}

where Iλ is the identity operator on Vλ. The above matrix would be upper-triangular except for the A22 block. But exactly the same procedure can be applied to the sub-matrix A22, viewed as an operator on Vλ⊥, and its submatrices. Continue this way until we exhaust the space Cn gives the desired result.

The above argument can be slightly restated as follows: let λ be an eigenvalue of A, corresponding to some eigenspace Vλ. A induces an operator T on the quotient space Cn modulo Vλ. This operator is precisely the A22 submatrix from above. As before, T would have an eigenspace, say Wμ ⊂ Cn modulo Vλ. Notice the preimage of Wμ under the quotient map is an invariant subspace of A that contains Vλ. Continue this way until the resulting quotient space has dimension 0. Then the successive preimages of the eigenspaces found at each step form a flag that A stabilizes.

[edit] Notes

Although every square matrix has a Schur decomposition, in general this decomposition is not unique. For example, the eigenspace Vλ can have dimension > 1, in which case any orthonormal basis for Vλ would lead to the desired result.

Write the triangular matrix U as U = D + N, where D is diagonal and N is strictly upper triangular (and thus nilpotent). The diagonal matrix D contains the eigenvalues of A in arbitrary order (hence its Frobenius norm, squared, is the sum of the squared moduli of the eigenvalues of A, while the Frobenius norm of A, squared, is the sum of the squared singular values of A). The nilpotent part N is generally not unique either, but its Frobenius norm is uniquely determined by A (just because the Frobenius norm of A is equal to the Frobenius norm of U = D + N).

It is clear that if A is a normal matrix, then U from its Schur decomposition must be a diagonal matrix and the column vectors of Q are the eigenvectors of A. Therefore, the Schur decomposition extends the spectral decomposition. In particular, if A is positive definite, the Schur decomposition of A, its spectral decomposition, and its singular value decomposition coincide.

A commuting family {Ai} of matrices can be simultaneously triangularized, i.e. there exists a unitary matrix Q such that, for every Ai in the given family, Q Ai Q* is upper triangular. This can be readily deduced from the above proof. Take element A from {Ai} and again consider a eigenspace VA. Then VA is invariant under all matrices in {Ai}. Therefore all matrices in {Ai} must share one common eigenvector in VA. Induction then proves the claim. As a corollary, we have that every commuting family of normal matrices can be simultaneously diagonalized.

In the infinite dimensional setting, not every bounded operator on a Banach space has an invariant subspace. However, the upper-triangularization of an arbitrary square matrix does generalize to compact operators. Every compact operator on a complex Banach space has a nest of closed invariant subspaces.

[edit] Applications

Lie theory applications include:

[edit] Generalized Schur decomposition

Given square matrices A and B, the generalized Schur decomposition factorizes both matrices as A = QSZ * and B = QTZ * , where Q and Z are unitary, and S and T are upper triangular. The generalized Schur decomposition is also sometimes called the QZ decomposition. (See Golub and van Loan, 1996, sec. 7.7.)

The generalized eigenvalues λ that solve the generalized eigenvalue problem Ax = λBx (where x is an unknown nonzero vector) can be calculated as the ratio of the diagonal elements of S to those of T. That is, using subscripts to denote matrix elements, the ith generalized eigenvalue λi satisfies λi = Sii / Tii.

[edit] See also

[edit] References

  • Roger A. Horn and Charles R. Johnson, Matrix Analysis, Sections 2.3 and further, Cambridge University Press, 1985. ISBN 0-521-38632-2.
  • Gene H. Golub and Charles F. van Loan, Matrix Computations, 3rd ed., Section 7.7, Johns Hopkins University Press, 1996. ISBN 0801854148.