Schur decomposition

Not all matrices are diagonalizable. But all square matrices have a Schur decomposition:

$$A=QT{Q}^H$$

• $T$: triangular with eigenvalues on the diagonal
• $Q$: square complex unitary; $Q^{H}Q=I$.

Schur decompositions can be accurately computed because they rely on unitary matrices. This is one of the best decompositions to compute eigenvalues.

Proof of the existence of the Schur decomposition

We prove the result by induction on the size of the matrix. For $n=1$, the result is true.

Assume it is true for matrices of size less than $n$.

We know that all matrices have at least one eigenvalue. Denote $\lambda$ and $x$ the eigenvalue and eigenvector with $\Vert x{\Vert }_2=1$. We can define a unitary basis

$$Q_1=[x,x_1,\dots ,x_{n-1}]$$

We have

$$Q_1^{H}A{Q}_1=\left(\begin{array}{cc}\lambda & T_{12}\\ 0& T_{22}\end{array}\right)$$

By induction, we can find a unitary matrix $Q_2$ of size $n-1$ such that

$$Q_2^H{T}_{22}{Q}_2=T_{22}^{\ast }$$

where $T_{22}^{\ast }$ is upper triangular. Define the unitary matrix

$$Q_3=Q_1\left(\begin{array}{cc}1& \\ & Q_2\end{array}\right)$$

Then

$$Q_3^{H}A{Q}_3=\left(\begin{array}{cc}\lambda & \ast \\ 0& T_{22}^{\ast }\end{array}\right)$$

is upper triangular. $\square$

The computational cost of computing the Schur decomposition is $O(n^3)$. This will be covered in future sections.

Eigenvalues, Orthogonal matrix and projector, Hermitian and symmetric matrices