Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Schur decomposition

by , PhD

For any given matrix, the Schur decomposition (or factorization) allows to find another matrix that is similar to the given one and is upper triangular. Moreover, the change-of-basis matrix used in the similarity transformation is unitary.

In other words, the Schur decomposition shows that each matrix is unitarily similar to an upper triangular matrix.

Table of Contents

Preliminaries

Let us revise some notions that are essential to understand the Schur decomposition.

We say that two square matrices A and $T$ are similar if and only if there exists an invertible $K	imes K$ matrix $Q$ such that[eq1]

The matrix $Q$ involved in the similarity transformation is called a change-of-basis matrix.

Two similar matrices have the same rank, trace, determinant and eigenvalues. Moreover, the algebraic and geometric multiplicities of their eigenvalues coincide.

We say that a square matrix $Q$ is unitary if and only if its columns have unit norm and are orthogonal to each other, in which case $Q$ has the property that[eq2]where $Q^{st }$ denotes the conjugate transpose of $Q$.

When $Q$ is unitary, the similarity transformation above becomes[eq3]and we say that A and $T$ are unitarily similar.

Householder matrices used in the proof

In the proof that any square matrix A is unitarily similar to an upper triangular matrix $T$ we are going to repeatedly use so-called Householder matrices.

Householder matrices are among the most powerful tools in modern linear algebra. We therefore recommend to study them in detail. However, here is a summary of what we need to know in order to understand the proof of the Schur decomposition:

The decomposition

We are now ready to present the Schur decomposition.

Proposition Let A be a square $K	imes K$ matrix. Then, A is unitarily similar to an upper triangular $K	imes K$ matrix $T$, that is,[eq7]where $Q$ is a $K	imes K$ unitary matrix.

Proof

Let $lambda _{1}$ be any eigenvalue of A and $x_{1}$ one of its associated eigenvectors (hence, $x_{1}
eq 0$). We can find a Householder matrix $R_{1}$ such that[eq8]where $c_{1}
eq 0$. Moreover,[eq9]Partition $R_{1}$ so as to form a block-matrix[eq10]where $s_{1}$ is the first column of $R_{1}$ and $T_{1}$ contains all the other columns. Since $s_{1}=R_{1}e_{1}$, we have[eq11]By using the rules for the multiplication of block matrices, we obtain[eq12]where in step $rame{A}$ we have used the fact that $x_{1}$ is an eigenvector of A. We can write[eq13]where 0 is a [eq14] vector of zeros, $st $ is a [eq15] vector of possibly non-zero entries (equal to the first row of $R_{1}AT_{1}$), and $A_{2}$ is a [eq16] matrix (containing all the rows of $R_{1}AT_{1}$ except the first one). This was the first step of the triangularization process. Let us now start the second step. Let $lambda _{2}$ be any eigenvalue of $A_{2}$ and $x_{2}$ one of its associated eigenvectors. We construct a Householder matrix $R_{2}$ such that[eq17]where $c_{2}
eq 0$. Note that $e_{1}$ is now shorter than in the previous step: its first entry is 1 and all its other entries are 0, but the number of 0s decreases by one unit. To be rigorous, we should change notation, but we keep the same notation for clarity's sake. As before, the symmetric equality[eq18]holds and, similarly to what we have demonstrated above, we have[eq19]We create a new block-matrix[eq20]The matrix $R_{2}$, being a Householder matrix, is unitary. The first column of $Q_{2}$ has unit norm and it is orthogonal to all the other columns. Thus, $Q_{2}$ is unitary. We can now compute the product[eq21]where we have denoted various new vectors of possibly non-zero entries by $st $. This ends the second step of the triangularization process. The successive steps are straightforward modifications of the second one. We keep doing Householder transformations until we obtain[eq22]Since the product of unitary matrices is unitary, the matrix[eq23]is unitary. Moreover,[eq24]because all the matrices involved in the product are derived from Householder matrices (which are Hermitian), possibly by adding blocks of zeros and ones which are unaffected by conjugate transposition. Therefore,[eq25]where $T$ is the upper triangular matrix above (with entries [eq26] on the main diagonal).

Uniqueness

The Schur decomposition is not unique. This can be seen easily from the algorithm used in the constructive proof above: at each step we choose an eigenvalue arbitrarily; as a consequence, there are different possible orderings of the eigenvalues of A on the main diagonal of $T$.

More in general, if [eq25]is a Schur decomposition of A, we can take any unitary matrix $P$ such that[eq28]is upper triangular, and use it to construct another Schur decomposition[eq29]

Eigenvalues

A triangular matrix has the property that its diagonal entries are equal to its eigenvalues. Moreover, two similar matrices have the same eigenvalues. Therefore, the Schur decomposition [eq30]allows to read the eigenvalues of A on the main diagonal of $T$, which is upper triangular and similar to A.

Comparison with diagonalization

We should compare the results derived here with those presented in the lecture on matrix diagonalization, where we have shown that if A has no defective eigenvalues, then it is similar to a diagonal matrix having the eigenvalues of A on the main diagonal.

Here are the similarity and differences:

Each of the two decompositions has its own strengths. As a consequence, they are useful in different situations.

Example

A simple example follows.

Example Define[eq31]Then, the Schur decomposition of A is[eq30]where[eq33]and[eq34]From $T$ we can read the eigenvalues of A, which are $lambda _{1}=1$ and $lambda _{2}=2$.

How to cite

Please cite as:

Taboga, Marco (2017). "Schur decomposition", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/Schur-decomposition.

The book

Most of the learning materials found on this website are now available in a traditional textbook format.