Schur Decomposition#

Theorem: Schur Decomposition

Every complex square matrix $A \in \mathbb{C}^{n \times n}$ is similar to an upper triangular matrix $R$ with a unitary transition matrix:

\[A = U R U^{\ast}\]

Definition: Schur Normal Form

We call $R$ the Schur normal form of $A$.

Proof

TODO

Algorithm: Schur Decomposition via Deflation Method

We want to find the Schur decomposition

\[A = URU^{\ast}\]

of a complex matrix square matrix $A \in \mathbb{C}^{n \times n}$.

Define $A_0 = A$.
For all $j \in \{0, 1, \cdots, n-2\}$:

Find an eigenvalue $\lambda_j$ of $A_j$ and a corresponding eigenvector $\mathbf{u}_j^{(1)}$ which is normalized with respect to the induced norm of the dot product.
Extend $\mathbf{u}_j^{(1)}$ to an orthonormal basis $\mathbf{u}_j^{(1)}, \mathbf{u}_j^{(2)}, \dotsc, \mathbf{u}_j^{(n-j)}$ of $\mathbb{C}^{n-j}$ and construct the unitary matrix $\hat{U}_j \in \mathbb{C}^{(n-j) \times (n-j)}$ whose columns are $\mathbf{u}_j^{(1)}, \mathbf{u}_j^{(2)}, \dotsc, \mathbf{u}_j^{(n-j)}$.

$$\hat{U}_j = \begin{bmatrix} \vert & \vert & \vert \\ \mathbf{u}_j^{(1)} & \cdots & \mathbf{u}_j^{(n-j)} \\ \vert & \vert & \vert\end{bmatrix}$$

Extend $\hat{U}_j$ to an $n\times n$ complex square matrix $U_j$ using the identity matrix $I_j$ as follows (We have $U_0 = \hat{U}_0$).

$$U_j = \begin{bmatrix} I_j & \mathbf{0} \\ \mathbf{0} & \hat{U}_j\end{bmatrix}$$

Define $A_{j+1}$ as the $(n - j - 1) \times (n - j -1)$ complex square matrix obtained by removing the first row and first column of the product $\hat{U}_j^{\ast} A_j \hat{U}_j$ (Skip this for the last $j = n - 2$).

$$\hat{U}_j^{\ast} A_j \hat{U}_j = \begin{bmatrix}\lambda_j & \ast \\ \mathbf{0} & A_{j+1}\end{bmatrix}$$

Compile the Schur decomposition $A = URU^{\ast}$:

The unitary matrix $U$ is the product of $U_0, U_1, \dotsc, U_{n-2}$.

$$U = U_0 U_1 \cdots U_{n-2}$$

The Schur normal form $R$ is the product $U^{\ast}AU$.

$$R = U^{\ast}AU$$

Example:

We want to find the Schur decomposition of the following complex square matrix $A = URU^{\ast}$:

\[A = \begin{bmatrix}3 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 0 & 2\end{bmatrix}\]

From the second column, we immediately see that $\begin{bmatrix}0 & 1 & 0\end{bmatrix}^{\mathsf{T}}$ is an eigenvector with eigenvalue $1$. We can easily extend it to the following orthonormal basis of $\mathbb{C}^3$:

\[\left\{ \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix}, \begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix}, \begin{bmatrix}0 \\ 0 \\ 1\end{bmatrix} \right\}\]

We thus have:

\[\hat{U}_0 = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]

Therefore:

\[U_0 = \hat{U}_0 = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]

Furthermore,

\[\hat{U}_0^{\ast} A_0 U_0 = \begin{bmatrix}1 & 1 & 2 \\ 0 & 3 & 0 \\ 0 & 1 & 2\end{bmatrix}\]

and so

\[A_1 = \begin{bmatrix}3 & 0 \\ 1 & 2\end{bmatrix}.\]

From the second column of $A_1$, we see that $\begin{bmatrix}0 & 1\end{bmatrix}^{\mathsf{T}}$ is an eigenvector with eigenvalue $2$. We can easily extend it to the following orthonormal basis of $\mathbb{C}^2$:

\[\left\{ \begin{bmatrix}0 \\ 1\end{bmatrix}, \begin{bmatrix}1 \\ 0\end{bmatrix} \right\}\]

We thus have:

\[\hat{U}_1 = \begin{bmatrix} 0 & 1 \\ 1 & 0\end{bmatrix}\]

Therefore:

\[U_1 = \begin{bmatrix} I_1 & \mathbf{0} \\ \mathbf{0} & \hat{U}_j\end{bmatrix} = \begin{bmatrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{bmatrix}\]

At last, we have:

\[U = U_0 U_1 = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{bmatrix} = \begin{bmatrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{bmatrix}\]

\[\begin{aligned} R & = U^{\ast}AU \\ & = \begin{bmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{bmatrix} \begin{bmatrix}3 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 0 & 2\end{bmatrix} \begin{bmatrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{bmatrix} \\ & = \begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & 1 \\ 0 & 0 & 3\end{bmatrix} \end{aligned}\]