NLA MT25, Schur decomposition

Suppose:

• $A \in \mathbb C^{n \times n}$

Then there exists a unitary matrix $U \in \mathbb C^{n \times n}$ and an upper triangular matrix $T$ such that

Pick an eigenvalue $\lambda _ 1$ of $A$ with a unit eigenvector $v _ 1$ (so $\|v _ 1\| _ 2 = 1$ and $A v _ 1 = \lambda _ 1 v _ 1$). Let $V _ \bot \in \mathbb C^{n \times (n-1)}$ have orthonormal columns spanning $\{v _ 1\}^\bot$ (e.g. via Gram-Schmidt), so $U _ 1 = [\,v _ 1 \mid V _ \bot\,]$ is unitary.

Step 1 (clear the first column): compute $U _ 1^\ast A U _ 1$ in blocks:

Using $A v _ 1 = \lambda _ 1 v _ 1$: the $(1,1)$ entry is $v _ 1^\ast A v _ 1 = \lambda _ 1\, v _ 1^\ast v _ 1 = \lambda _ 1$ (so the top-left entry is exactly $\lambda _ 1$, since $\|v _ 1\| _ 2 = 1$), and the rest of the first column is $V _ \bot^\ast A v _ 1 = \lambda _ 1\, V _ \bot^\ast v _ 1 = 0$ (the columns of $V _ \bot$ are orthogonal to $v _ 1$). The remaining blocks $w^\ast := v _ 1^\ast A V _ \bot \in \mathbb C^{1 \times (n-1)}$ and $A _ 2 := V _ \bot^\ast A V _ \bot \in \mathbb C^{(n-1) \times (n-1)}$ have no special structure. Hence

Equivalently, multiplying on the left by $U _ 1$ (using $U _ 1 U _ 1^\ast = I$) gives the form $A U _ 1 = U _ 1 \begin{bmatrix} \lambda _ 1 & w^\ast \\ 0 & A _ 2 \end{bmatrix}$.

Step 2 (recurse): apply Step 1 to the $(n-1) \times (n-1)$ block $A _ 2$, embedding the block-unitary $W$ that triangularises it as $\begin{bmatrix} I & 0 \\ 0 & W \end{bmatrix}$ so it fixes the already-cleared rows and columns. After $n-1$ steps,

is upper triangular. Since each $U _ k$ is unitary ($U _ k^{-1} = U _ k^\ast$), setting $U := U _ 1 U _ 2 \cdots U _ {n-1}$ (unitary, as a product of unitaries) gives

The successive top-left entries produced are the eigenvalues, so $\text{diag}(T) = (\lambda _ 1, \lambda _ 2, \ldots, \lambda _ n) = \text{eig}(A)$.

You have an orthogonal matrix $Q$ and a quasi-upper triangular matrix $T$ (i.e. almost triangular, but possibly with $2 \times 2$ blocks on the diagonal) such that

We have that $\text{eig}(A) = \text{eig}(T) = \text{diag}(T)$, so the diagonal elements of $T$ give the eigenvalues of $A$.

It involves only applying orthogonal transformations to $A$.

$T$ is diagonal iff $A$ is normal.

(Hence in this case, the Schur decomposition matches exactly the eigenvalue decomposition).

Backward direction ($T$ diagonal $\implies$ $A$ normal):

If $T = D$ is diagonal, then

Since $D$ is diagonal, $D^\ast D = D D^\ast$. Hence $A^\ast A = A A^\ast$.

Forward direction ($A$ normal $\implies$ $T$ diagonal):

We have the Schur decomposition $A = U T U^\ast$. Since $A$ is normal and $T$ is upper triangular, normality gives

so $T$ is normal. But then by ∆upper-triangular-normal-implies-diagonal, we must have $T$ diagonal.

You reduce $T$ further by solving the Sylvester equations, but this is not backward stable.

Eigenvalues: $\det(A - \lambda I) = \lambda^2 - 7\lambda + 10 = (\lambda - 5)(\lambda - 2)$; pick $\lambda _ 1 = 5$.

Unit eigenvector: $(A - 5I) = \begin{bmatrix} -1 & 1 \\ 2 & -2 \end{bmatrix} \Rightarrow v _ 1 = \tfrac{1}{\sqrt2}(1, 1)^\top$.

Extend to a unitary $U _ 1 = [\,v _ 1 \mid v _ 1^\perp\,] = \tfrac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$ (orthogonal and symmetric).

Clear the first column:

For $n = 2$ this single deflation step finishes: $A = U T U^\top$ with $U = U _ 1$. The eigenvalues $5, 2$ sit on $\mathrm{diag}(T)$; the strictly-upper entry $T _ {12} = 1 \ne 0$ because $A$ is not normal ($A^\top A \ne A A^\top$) — for normal $A$, $T$ would be diagonal (∆diagonal-schur-iff-normal).

Only the first column $u _ 1$ is always an eigenvector (with eigenvalue $T _ {11}$). The remaining $u _ k$ ($k \ge 2$) are generally not eigenvectors: what is $A$-invariant is each nested span $\mathrm{span}(u _ 1, \ldots, u _ k)$ (the Schur invariant subspaces, ∆bite-schur-invariant-subspaces), not the individual columns. To recover eigenvectors you’d further reduce $T$ to diagonal form (via Sylvester equations) — but that step is not backward stable for non-normal $A$.

For each $k$, the span of the first $k$ columns, $\mathcal S _ k := \mathrm{span}(u _ 1, \ldots, u _ k)$, is an $A$-invariant subspace. From $A U = U T$, column $j$ reads $A u _ j = \sum _ {i=1}^{j} T _ {ij}\, u _ i \in \mathrm{span}(u _ 1, \ldots, u _ j)$ (the sum stops at $i = j$ because $T$ is upper triangular), so $A \mathcal S _ k \subseteq \mathcal S _ k$ for every $k$.

These form a nested chain (a complete flag) $\mathcal S _ 1 \subset \mathcal S _ 2 \subset \cdots \subset \mathcal S _ n = \mathbb C^n$ with $\dim \mathcal S _ k = k$, and the eigenvalues of the restriction $A \vert _ {\mathcal S _ k}$ are the leading diagonal entries $T _ {11}, \ldots, T _ {kk}$. So the Schur form is precisely an orthonormal basis adapted to a complete flag of $A$-invariant subspaces. Only $\mathcal S _ 1 = \mathrm{span}(u _ 1)$ is $1$-dimensional, so only $u _ 1$ is itself an eigenvector (cf. ∆bite-schur-U-columns-not-eigenvectors).

The Schur form can be computed in a backward stable way: it involves only unitary similarity transformations of $A$. A full eigenvalue decomposition for non-normal $A$ requires solving Sylvester equations, which involves non-unitary transformations and is not backward stable. Since eigenvalues can be read off as $\mathrm{diag}(T)$, the Schur form gives the spectrum directly — for most purposes there’s no need to push on to a diagonal form.

• Pick any eigenvalue $\lambda _ 1$ of $A$ and corresponding unit eigenvector $v _ 1$. Extend to a unitary $U _ 1 = [v _ 1 \mid V _ \bot]$.
• Conjugating: $U _ 1^\ast A U _ 1$ has the form $[\lambda _ 1, *; 0, B]$ — first column matches the eigenvector relation $Av _ 1 = \lambda _ 1 v _ 1$.
• Apply the inductive hypothesis to the $(n-1) \times (n-1)$ block $B$ to get its Schur decomposition.
• Embed and concatenate: $U = U _ 1 \cdot \mathrm{diag}(1, U _ B)$ is unitary, and $U^\ast A U$ is upper triangular.

The proof is non-constructive: you need to “pick an eigenvalue”, which only exists abstractly (roots of $\chi _ A$) — there is no finite-step algorithm for this. The QR algorithm produces a numerical Schur form iteratively.

• Easy direction ($T$ diagonal $\implies$ $A$ normal): compute both $A^\ast A$ and $A A^\ast$ as $U \cdot (\text{diagonal-diagonal product}) \cdot U^\ast$; the two diagonals commute trivially.
• Hard direction ($A$ normal $\implies$ $T$ diagonal): $A^\ast A = AA^\ast \implies T^\ast T = T T^\ast$ (cancelling $U, U^\ast$). Apply ∆upper-triangular-normal-implies-diagonal: an upper triangular normal matrix must be diagonal.

The hard direction outsources its real work to the upper-triangular-normal lemma, which uses an inductive argument on $n$ counting first-row entries.