## Subsection9.2.5The Schur and spectral decompositions

###### Definition9.2.5.1.

Matrices $A$ and $B$ are said to be similar if there exists a nonsingular matrix $Y$ such that $B = Y^{-1} A Y \text{.}$

###### Definition9.2.5.2.

Given a nonsingular matrix $Y$ the transformation $Y^{-1} A Y$ is called a similarity transformation (applied to matrix $A$).

Let $\lambda \in \Lambda( A )$ and $x$ be an associated eigenvector. Then $A x = \lambda x$ if and only if $Y^{-1} A Y Y^{-1} x = Y^{-1} \lambda x$ if and only if $B ( Y^{-1} x ) = \lambda ( Y^{-1} x ) \text{.}$

The observation is that the eigenvalues of a matrix are invariant under a similarity transformation>

It is not hard to expand the last proof to show that if $A$ is similar to $B$ and $\lambda \in \Lambda( A )$ has algebraic multiplicity $k$ then $\lambda \in \Lambda( B )$ has algebraic multiplicity $k\text{.}$

In (((Unresolved xref, reference ""; check spelling or use "provisional" attribute))) , we argued that the application of unitary matrices is desirable, since they preserve length and hence don't amplify error. For this reason, unitary similarity transformations are our weapon of choice when designing algorithms for computing eigenvalues and eigenvectors.

###### Definition9.2.5.4.

Given a nonsingular matrix $Q$ the transformation $Q^H A Q$ is called a unitary similarity transformation (applied to matrix $A$).

The following is the fundamental theorem for the algebraic eigenvalue problem:

We will outline how to construct $Q$ so that $Q^H A Q = U \text{,}$ an upper triangular matrix.

Since a polynomial of degree $m$ has at least one root, matrix $A$ has at least one eigenvalue, $\lambda_1\text{,}$ and corresponding eigenvector $q_1 \text{,}$ where we normalize this eigenvector to have length one. Thus $A q_1 = \lambda_1 q_1 \text{.}$ Choose $Q_2$ so that $Q = \left( \begin{array}{ c|c} q_1 \amp Q_1 \end{array} \right)$ is unitary. Then

\begin{equation*} \begin{array}{l} Q^H A Q \\ ~~~=~~~~ \\ \left( \begin{array}{ c|c} q_1 \amp Q_2 \end{array} \right)^H A \left( \begin{array}{ c|c} q_1 \amp Q_2 \end{array} \right) \\ ~~~=~~~~ \\ \left( \begin{array}{ c|c} q_1^H A q_1 \amp q_1^H A Q_2 \\ \hline Q_2^H A q_1 \amp Q_2^H A Q_2 \end{array} \right) \\ ~~~=~~~~ \\ \left( \begin{array}{ c|c} \lambda_1 \amp q_1^H A Q_2 \\ \hline \lambda Q_2^H q_1 \amp Q_2^H A Q_2 \end{array} \right) \\ ~~~=~~~~ \\ \left( \begin{array}{ c|c} \lambda_1 \amp w^T \\ \hline 0 \amp B \end{array} \right), \end{array} \end{equation*}

where $w^T = q_1^H A Q_2$ and $B = Q_2^H A Q_2 \text{.}$ This insight can be used to construct an inductive proof.

In other words: Given matrix $A \text{,}$ there exists a unitary matrix $Q$ such that applying the unitary similarity transformation $Q^H A Q$ yields an upper triangular matrix $U \text{.}$ Since then $\Lambda( A ) = \Lambda( U ) \text{,}$ the eigenvalues of $A$ can be found on the diagonal of $U \text{.}$

One should not mistake the above theorem and its proof for a constructive way to compute the Schur decomposition: finding an eigenvalue, $\lambda_1$ and/or the eigenvector associated with, $q_1 \text{,}$ is difficult. Also, completing the unitary matrix $\left( \begin{array}{c | c } q_1 \amp Q_2 \end{array} \right)$ is expensive (essentially requiring the equivalent of a QR factorization).

Let $A = Q U Q^H$ be the Schur decomposition of $A \text{.}$ Then $U = Q^H A Q \text{.}$ Since $A$ is Hermitian, so is $U$ since $U^H = ( Q^H A Q )^H = Q^H A^H Q = Q^H A Q = U \text{.}$ A triangular matrix that is Hermitian is diagonal. Any Hermitian matrix has a real valued diagonal and hence $D$ has real valued on its diagonal.

###### Homework9.2.5.1.

Prove Lemma~\ref{lemma:eigpart}. Then generalize it to a result for block upper triangular matrices:

\begin{equation*} A = \left( \begin{array}{c | c | c | c } A_{0,0} \amp A_{0,1} \amp \cdots \amp A_{0,N-1} \\ \hline 0\amp A_{1,1} \amp \cdots \amp A_{1,N-1} \\ \hline 0 \amp 0 \amp \ddots \amp \vdots \\ \hline 0 \amp 0 \amp \cdots \amp A_{N-1,N-1} \end{array} \right). \end{equation*}

{\bf Lemma~\ref{lemma:eigpart}} Let $A \in \C^{m \times m}$ be of form $A = \FlaTwoByTwo{ A_{TL} }{ A_{TR} }{ 0 }{ A_{BR} } \text{.}$ Assume that $Q_{TL}$ and $Q_{BR}$ are unitary of appropriate size''. Then

\begin{equation*} A = \FlaTwoByTwo{ Q_{TL} }{ 0 }{ 0 }{ Q_{BR} }^H \FlaTwoByTwo{ Q_{TL} A_{TL} Q_{TL}^H }{ Q_{TL} A_{TR} Q_{BR}^H }{ 0 }{ Q_{BR} A_{BR} Q_{BR}^H } \FlaTwoByTwo{ Q_{TL} }{ 0 }{ 0 }{ Q_{BR} }. \end{equation*}
\begin{equation*} \begin{array}{rcl} \lefteqn{\FlaTwoByTwo{ Q_{TL} }{ 0 }{ 0 }{ Q_{BR} }^H \FlaTwoByTwo{ Q_{TL} A_{TL} Q_{TL}^H }{ Q_{TL} A_{TR} Q_{BR}^H }{ 0 }{ Q_{BR} A_{BR} Q_{BR}^H } \FlaTwoByTwo{ Q_{TL} }{ 0 }{ 0 }{ Q_{BR} } \hspace{0.75in}} \\ \amp=\amp \FlaTwoByTwo{ Q_{TL}^H Q_{TL} A_{TL} Q_{TL}^H Q_{TL}}{ Q_{TL}^H Q_{TL} A_{TR} Q_{BR}^H Q_{BR}}{ 0 }{ Q_{BR}^H Q_{BR} A_{BR} Q_{BR}^H Q_{BR}} \\ \amp=\amp \FlaTwoByTwo{ A_{TL} }{ A_{TR} }{ 0 }{ A_{BR} } = A. \end{array} \end{equation*}

By simple extension $A = Q^H B Q$ where

\begin{equation*} \begin{array}{rcl} Q = \left( \begin{array}{c | c | c | c } Q_{0,0} \amp 0 \amp \cdots \amp 0 \\ \hline 0\amp Q_{1,1} \amp \cdots \amp 0 \\ \hline 0 \amp 0 \amp \ddots \amp \vdots \\ \hline 0 \amp 0 \amp \cdots \amp Q_{N-1,N-1} \end{array} \right) \end{array} \end{equation*}

and

\begin{equation*} \begin{array}{rcl} B = \left( \begin{array}{c | c | c | c } Q_{0,0} A_{0,0} Q_{0,0}^H \amp Q_{0,0} A_{0,1} Q_{1,1}^H\amp \cdots \amp Q_{0,0} A_{0,N-1} Q_{N-1,N-1}^H\\ \hline 0\amp Q_{1,1} A_{1,1} Q_{1,1}^H \amp \cdots \amp Q_{1,1} A_{1,N-1} Q_{N-1,N-1}^H\\ \hline 0 \amp 0 \amp \ddots \amp \vdots \\ \hline 0 \amp 0 \amp \cdots \amp Q_{N-1,N-1} A_{N-1,N-1} Q_{N-1,N-11}^H \end{array} \right) . \end{array} \end{equation*}