NLA MT25, Schur decomposition
Flashcards
@State the Schur decomposition theorem for matrices over $\mathbb C$.
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
\[A = U T U^\ast\]@Prove the existence of the ∆schur-decomposition, i.e. that if:
- $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
\[A = U T U^\ast\]
Pick some eigenvalue $\lambda _ 1$ of $A$ with corresponding eigenvector $v _ 1$, so that $A v _ 1 = \lambda _ 1 v _ 1$. Let $U _ 1 = [v _ 1 \mid V _ \bot]$ where $V _ \bot$ is orthogonal to $v _ 1$ (e.g. found via Gram-Schmidt). Then $U _ 1$ is unitary,
\[AU _ 1 = U _ 1 \begin{bmatrix} \ast & \ast & \cdots & \ast \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \\ \end{bmatrix}\]Hence
\[U _ 1^\ast A U _ 1 = \begin{bmatrix} \ast & \ast & \cdots & \ast \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \\ \end{bmatrix}\]Repeating this process on the lower $(n-1) \times (n-1)$ block iteratively yields
\[U _ {n-1}^\ast U^\ast _ {n-2} \cdots U _ 1 A U _ 1 \cdots U _ {n-2} U _ {n-2} = T\]and hence
\[A = U _ 1 \cdots U _ {n-1} U _ {n-2} T U _ {n-1}^\ast U _ {n-2}^\ast \cdots U _ 1\]The ∆schur-decomposition decomposes $A \in \mathbb C^{n \times n}$ into $A = U T U^\ast$ where $U$ is unitary and $T$ is upper triangular. What happens when $A \in \mathbb R^{n \times n}$?
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
\[A = Q T Q^\top\]The ∆schur-decomposition states that if $A \in \mathbb C^{n \times n}$, then there exists a unitary matrix $U \in \mathbb C^{n \times n}$ and upper-triangular $T$ such that
\[A = U T U^\ast\]
Why is this useful in terms of computing the eigenvalues?
We have that $\text{eig}(A) = \text{eig}(T) = \text{diag}(T)$, so the diagonal elements of $T$ give the eigenvalues of $A$.
The ∆schur-decomposition states that if $A \in \mathbb C^{n \times n}$, then there exists a unitary matrix $U \in \mathbb C^{n \times n}$ and upper-triangular $T$ such that
\[A = U T U^\ast\]
What is the intuitive reason that this can be computed in a backward stable manner?
It involves only applying orthogonal transformations to $A$.
The ∆schur-decomposition states that if $A \in \mathbb C^{n \times n}$, then there exists a unitary matrix $U \in \mathbb C^{n \times n}$ and upper-triangular $T$ such that
\[A = U T U^\ast\]
@State a theorem about when $A$ is normal.
$T$ is diagonal iff $A$ is normal.
(Hence in this case, the Schur decomposition matches exactly the eigenvalue decomposition).
The ∆schur-decomposition states that if $A \in \mathbb C^{n \times n}$, then there exists a unitary matrix $U \in \mathbb C^{n \times n}$ and upper-triangular $T$ such that
\[A = U T U^\ast\]
We have the further result that $T$ is diagonal iff $A$ is normal, so that the Schur decomposition gives the eigenvalue decomposition.
Suppose $A$ is not normal and we want $A = X \Lambda X^{-1}$. How can you do this? Why is it not so useful?
You reduce $T$ further by solving the Sylvester equations, but this is not backward stable.
@nonexaminable~