12.4.4. Schur Decomposition

Although we do not generally use the determinant of the characteristic equation to find eigenvalues, considering the determinant gives us an insight into the quickest procedure for finding the eigenvalues. Because of the zeros in a triangular matrix, its determinant is the product of the elements on the diagonal. Likewise, the determinant of a triangular characteristic equation reveals the product of the characteristic factors. As first observed by Carl Jacobi, the eigenvalues may be taken directly from the diagonal of triangular matrices [1].

\[det(\mathbf{A} - \lambda\,\mathbf{I}) = 0\]

\[\begin{split}\begin{vmatrix} {a_{11} - \lambda} & a_{12} & {\cdots} & a_{1n} \\ 0 & {a_{22} - \lambda} & {\cdots} & a_{2n} \\ {\vdots} & {\vdots} & {} & {\vdots} \\ 0 & 0 & {\cdots} & {a_{nn} - \lambda} \end{vmatrix} = 0\end{split}\]

\[(a_{11} - \lambda_1)\,(a_{22} - \lambda_2)\cdots (a_{nn} - \lambda_n) = 0\]

Schur Triangularization Theorem

Theorem 12.2 (Schur Triangularization Theorem)

If \(\mathbf{A} \in \mathbb{C}^{n{\times}n}\), then there exists a unitary \(\mathbf{Q} \in \mathbb{C}^{n{\times}n}\) such that

\[\mathbf{A} = \mathbf{Q\,T\,Q}^H \quad \text{and} \quad \mathbf{T} = \mathbf{Q}^H \mathbf{A\,Q}\]

where \(\m{T}\) is upper triangular and similar to \(\m{A}\) with the eigenvalues on its diagonal. Further, if \(\bf{A}\) is Hermitian symmetric then \(\bf{T}\) is diagonal and the eigenvectors of \(\bf{A}\) are held in the columns of \(\bf{Q}\).

Proof. Matrix \(\m{T}\) is similar to \(\m{A}\) by the Similar Matrices Theorem. We show here that \(\mathbf{T_n} = \mathbf{Q}^H \mathbf{A\,Q}\) is upper triangular. The proof begins with the first eigenpair and the first column of \(\m{T}\). Then the other columns of \(\m{T}\) are considered sequentially, left to right, establishing the proof by induction.

Let \(\mathbf{Q}^H\) be a unitary matrix such that \(\mathbf{Q}_1^H \bm{x}_1 = k\,\bm{e}_1\). A Householder reflector for the eigenvector \(\bm{x}_1\) fits the requirement for \(\mathbf{Q}_1^H\).

(12.5)\[\begin{split} &\mathbf{A}\,\bm{x}_1 = \lambda_1\,\bm{x}_1 \\ &\mathbf{Q}_1^H \mathbf{A}\,\bm{x}_1 = \lambda_1\, \m{Q}_1^H \bm{x}_1 \\ &\mathbf{Q}_1^H \mathbf{A} \left(\m{Q}_1 \mathbf{Q}_1^H\right) \bm{x}_1 = \lambda_1\,\mathbf{Q}_1^H \bm{x}_1 \\ &\left(\m{Q}_1^H \m{A}\,\m{Q}_1\right) k\,\bm{e}_1 = \lambda_1\,k\, \bm{e}_1, \\ &\quad \text{which establishes the first column of } \m{T}_1. \\ &\mathbf{T}_1 = \mathbf{Q}_1^H \mathbf{A}\,\mathbf{Q}_1 = \begin{bmatrix} \lambda_1 & \text{*} \\ \mathbf{0} & \mathbf{B} \end{bmatrix}, \quad \text{where } \mathbf{B} \in \mathbb{C}^{(n-1){\times}(n-1)}.\end{split}\]

By similarity, \(\bf{A}\) and \(\mathbf{T}_1\) have the same eigenvalues, therefore the eigenvalues of \(\bf{B}\) are \(\lambda_2, \ldots, \lambda_n\). Next, repeating the steps outlined in equation (12.5) \(\mathbf{Q}_2\) and \(\mathbf{T}_2\) are found using \(\mathbf{B}\), instead of \(\bf{A}\).

\[\begin{split}\mathbf{Q}_2^H \mathbf{B}\,\mathbf{Q}_2 = \begin{bmatrix} \lambda_2 & \text{*} \\ \mathbf{0} & \mathbf{C} \end{bmatrix}, \quad \mathbf{C} \in \mathbb{C}^{(n-2){\times}(n-2)}\end{split}\]

We replace \(\bf{B}\) from \(\mathbf{T}_1\) with \(\mathbf{Q}_2^H \mathbf{B}\,\mathbf{Q}_2\) in \(\mathbf{T}_2\) .

\[\begin{split}\mathbf{T}_2 = \begin{bmatrix} \lambda_1 & \text{*} & \text{*} \\ 0 & \lambda_2 & \text{*} \\ \mathbf{0} & \mathbf{0} & \mathbf{C} \end{bmatrix}\end{split}\]

The procedure continues until the upper triangular \(\mathbf{T}_n\) is found.

\[\begin{split}\mathbf{T}_n = \begin{bmatrix} \lambda_1 & \text{*} & \text{*} & \text{*} \\ 0 & \lambda_2 & \text{*} & \text{*} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{bmatrix}\end{split}\]

\(\bf{Q}\) is the product of matrices formed from identity matrices and the unitary \(\mathbf{Q}_i\) matrices. Note that \(\mathbf{Q}_n\) is just 1.

\[\begin{split}\mathbf{Q} = \mathbf{Q}_1 \times \begin{bmatrix} 1 & \mathbf{0} \\ \mathbf{0} & \mathbf{Q}_2 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & \mathbf{0} \\ 0 & 1 & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{Q}_3 \end{bmatrix} \times \cdots \begin{bmatrix} 1 & 0 & 0 & \cdots & \mathbf{0} \\ 0 & 1 & 0 & \cdots & \mathbf{0} \\ 0 & 0 & 1 & \cdots & \mathbf{0} \\ \vdots & {} & {} & \ddots & \vdots \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{Q}_{n-1} \end{bmatrix}\end{split}\]

In the symmetric case, symmetry causes the transformations to produce the same results on the rows to the right of the diagonal as on the columns below the diagonal. Proofs relating to the Schur decomposition of symmetric matrices are given in Real Eigenvalues of a Symmetric Matrix and the Spectral Decomposition Theorem in Schur Decomposition of Symmetric Matrices.

\(\qed\)

You may have observed that the procedure in the proof shows a direct sequence of calculations for finding \(\mathbf{T}_n\) and \(\bf{Q}\). However, we required several eigenvalues and eigenvectors to complete the process. Converting a matrix from the upper Hessenberg form to the Schur triangular form requires an iterative algorithm.

A couple of corollaries to the Schur triangularization theorem give interesting properties about the eigenvalues of a matrix.

Sum of Eigenvalues

Corollary

The trace of a matrix (sum of the diagonal elements) is the sum of the eigenvalues. Further, similarity transformations preserve both the eigenvalues and the trace of a matrix.

Proof

There are two ways to prove this corollary. First, we will show the proof related to the Schur Triangularization Theorem. Then, the second proof derives from the determinant of the characteristic matrix.

1. By the Schur triangularization theorem, \(\m{A} = \m{Q\, T\, Q}^H\), where the matrices are the same as in the Schur Triangularization Theorem. Thus \(\m{A\, Q} = \m{Q\, T}\), and \(\mathrm{trace}(\m{A\, Q}) = \mathrm{trace}(\m{Q\, T})\). Due to the cyclic property of traces of matrix products, \(\mathrm{trace}(\m{A\, Q}) = \mathrm{trace}(\m{Q\, A}) = \mathrm{trace}(\m{Q\, T})\). So, \(\mathrm{trace}(\m{A}) = \mathrm{trace}(\m{T})\). Since the eigenvalues are on the diagonal of \(\m{T}\),

   \[\mathrm{trace}(\m{A}) = \mathrm{trace}(\m{T}) = \sum_{i = 1}^n \lambda_i.\]

2. An alternate expression of the characteristic equation is \(cp(t) = \det(t\m{I} - \m{A}) = t^n + c_{n-1}t^{n-1} + \cdots + c_1t + c_0\). The factoring of \(cp\) reveals the eigenvalues of \(\m{A}\).

   \[cp(t) = (t - \lambda_1)(t - \lambda_2)\ldots(t - \lambda_n)\]

   We find the \(c_{n-1}\) term of \(cp(t)\) by multiplying the factors, \(c_{n-1} = -(\lambda_1 + \lambda_2 + \cdots + \lambda_n)\). Then the Laplace expansion of \(\det(t\m{I} - \m{A})\) shows \(c_{n-1} = -(a_{11} + a_{22} + \cdots + a_{nn})\), which is the negative of the trace of \(\m{A}\). By equating terms, we have,

   \[\mathrm{trace}(\m{A}) = \sum_{i = 1}^n \lambda_i.\]

Likewise, if \(\m{C_T} = \m{T} - \m{\Lambda}\) is the characteristic matrix of \(\m{T}\), then \(\mathrm{trace}(\m{C_T}) = \mathrm{trace}(\m{T}) - \mathrm{trace}(\m{\Lambda}) = 0\) and \(\mathrm{trace}(\m{C_B}) = 0\), where \(\m{B}\) is any matrix that is similar to \(\m{T}\), which is a property of \(\m{C_B}\) being singular. The trace of all singular matrices is zero, but a trace of zero is insufficient proof that a matrix is singular.

\(\qed\)

Product of Eigenvalues

Corollary

The determinant of a matrix is the product of the eigenvalues. Further, similarity transformations preserve both the eigenvalues and the determinant of a matrix.

Proof

By the Schur triangularization theorem, \(\m{A} = \m{Q\, T\, Q}^H\), where the matrices are the same as in the Schur Triangularization Theorem. The determinant of \(\m{A}\) is the product of the determinants of its factors.

\[\det(\m{A}) = \det(\m{Q})\, \det(\m{T})\, \det(\m{Q}^H)\]

Because \(\m{Q}\) is unitary, \(\det(\m{Q})\) is either 1 or \(-1\), regardless, \(\det(\m{Q})\,\det(\m{Q}^H) = 1\). Therefore, \(\det(\m{A}) = \det(\m{T}) = \det(\m{B})\), where \(\m{B}\) is any matrix that is similar to \(\m{A}\) and \(\m{T}\). Since \(\m{T}\) is upper triangular, its determinant is the product of the eigenvalues.

\[\det(\m{A}) = \det(\m{T})= \prod_{i=1}^n \lambda_i\]

\(\qed\)

Footnotes:

[1]

The upper triangular form of a matrix is sometimes referred to as the Jacobi canonical form. Although that moniker is less common in current literature than it once was.