NLA MT25, Structured matrices
Flashcards
Symmetry and diagonalisability
@State a result about a characterisation of real symmetric matrices in terms of diagonalisability.
A real matrix $A \in \mathbb R^{n \times n}$ is symmetric iff it has real eigenvalues and is orthogonally diagonalisable.
@Prove that a real matrix $A \in \mathbb R^{n \times n}$ is symmetric iff it has real eigenvalues and is orthogonally diagonalisable.
Forward direction, symmetric $\implies$ real eigenvalues, orthogonally diagonalisable:
As $A$ is real and symmetric, $A^\top = A$. Then $A$ is normal, since $A^\ast A = A^2 = A A^\ast$.
By the Schur decomposition, there exists unitary $U$ and upper triangular $T$ such that $A = U T U^\ast$. Since $A$ is normal, by ∆diagonal-schur-iff-normal it follows that $T$ is diagonal and hence $A$ is unitarily diagonalisable with eigenvalues on the diagonal of $T$.
As $A^\ast = A$, we have $U D U^\ast = U D^\ast U^\ast$, hence $D = D^\ast$. Hence all eigenvalues are real.
It still remains to show that the eigenvectors are real so that $U$ can be taken orthogonal. Since $A$ is real and has real eigenvalues, each eigenspace $\text{ker}(A - \lambda I)$ is a real subspace of $\mathbb R^n$. Applying Gram-Schmidt within each eigenspace (over $\mathbb R$) gives an orthonormal basis of real eigenvectors.
Stacking these into a matrix $Q$ gives a real orthogonal matrix with $A = Q \Lambda Q^\top$.
Backward direction, real eigenvalues, orthogonally diagonalisable $\implies$ symmetric:
Suppose $A = Q \Lambda Q^\top$ with $Q$ orthogonal and $\Lambda$ real diagonal. Then
\[\begin{aligned} A^\top &= (Q \Lambda Q^\top)^\top \\ &= Q^{\top \top} \Lambda^\top Q^\top \\ &= Q \Lambda Q^\top \\ &= A \end{aligned}\]Unitarity and diagonalisability
@State a result about a characterisation of normal matrices in terms of diagonalisability.
A matrix $A \in \mathbb C^{n \times n}$ is normal (i.e. $A^\ast A = A A^\ast$) iff it is unitarily diagonalisable.
@Prove that a matrix $A \in \mathbb C^{n \times n}$ is normal (i.e. $A^\ast A = A A^\ast$) iff it is unitarily diagonalisable by appealing to another result.
Note that we have the Schur decomposition $A = U T U^\ast$. By ∆diagonal-schur-iff-normal, it follows that $A$ is normal iff $T$ is diagonal.
If $A$ is unitarily diagonalisable, then the Schur decomposition $U T U^\ast$ coincides with the eigenvalue decomposition and hence $A$ is normal.
If $A$ is normal, then $A = UTU^\ast$ has $T$ diagonal and hence $A$ is unitarily diagonalisable.
Normality and symmetry
@State a result about upper triangular matrices that are normal.
Suppose:
- $T \in \mathbb C^{n \times n}$
- $T$ is upper triangular
- $T$ is normal
Then:
- $T$ is diagonal
@Prove that if
- $T \in \mathbb C^{n \times n}$
- $T$ is upper triangular
- $T$ is normal
then:
- $T$ is diagonal
We induct on $n$.
Base case $(n = 1)$: Trivial.
Inductive step: Suppose the result is true for $(n-1) \times (n-1)$ matrices. As $T$ is normal, we have $T^\ast T = T T^\ast$. Since $T$ is upper-triangular, we have both that
\[\begin{aligned} (T^\ast T) _ {11} &= \vert T _ {11} \vert ^2 \\ (T T^\ast) _ {11} &= \sum^n _ {k=1} \vert T _ {1k} \vert ^2 = \vert T _ {11} \vert ^2 + \vert T _ {12} \vert ^2 + \cdots + \vert T _ {1n} \vert ^2 \end{aligned}\]Hence setting these equal implies
\[ \vert T _ {12} \vert ^2 + \cdots + \vert T _ {1n} \vert ^2 = 0\]and hence $T _ {1k} = 0$ for $k > 1$. Hence $T$ has block form
\[T = \begin{pmatrix} T _ {11} & 0 \\ 0 & T' \end{pmatrix}\]where $T'$ is upper-triangular. Since $T$ is block diagonal, we see that $T'$ must also be normal (compare $TT^\ast$ and $T^\ast T$). By the inductive hypothesis, $T'$ must also be diagonal, and hence the result holds.
Hessenberg matrices
@Define an upper Hessenberg matrix $A \in \mathbb C^{m \times n}$.
$A _ {ij} = 0$ if $i > j + 1$, i.e. all entries below the subdiagonal are zero.
Example:
\[A = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 0 & 9 & 10 & 11 \\ 0 & 0 & 12 & 13 \end{pmatrix}\]Bite-sized
A tridiagonal matrix has $A _ {ij} = 0$ whenever $ \vert i - j \vert > 1$ — only the diagonal and the first sub/super-diagonals can be nonzero.
Invariance properties: triangular structure is invariant under addition, multiplication, and inversion. Symmetric structure is invariant under addition and inversion, but not multiplication (the product of two symmetric matrices is generally not symmetric).
What is the difference between “orthogonal” and “orthonormal” as used in this course?
Orthogonal: typically a square $Q \in \mathbb R^{n \times n}$ with $Q^\top Q = Q Q^\top = I _ n$. Orthonormal: typically a tall rectangular $Q \in \mathbb R^{m \times n}$ with $m > n$ and $Q^\top Q = I _ n$ (columns orthonormal, but $Q Q^\top \ne I _ m$). This isn’t standard naming but it’s used consistently in the lecture notes; the rectangular case shows up everywhere in QR, SVD, Arnoldi/Lanczos bases.
For real matrices, “normal” means $A^\top A = A A^\top$. Symmetric, skew-symmetric, and orthogonal matrices are all special cases of normal — these are exactly the real matrices that admit a unitary diagonalisation.
Strategy for proving an upper triangular normal matrix is diagonal (∆upper-triangular-normal-implies-diagonal-proof).
Induct on $n$. The inductive step uses a 1-line entry comparison: in $T^\ast T = T T^\ast$, look at the $(1, 1)$ entry. By upper-triangularity, $(T^\ast T) _ {11} = \vert T _ {11} \vert ^2$ and $(T T^\ast) _ {11} = \sum _ {k} \vert T _ {1k} \vert ^2$. Equality forces $T _ {12} = \cdots = T _ {1n} = 0$, so the first row collapses to one nonzero entry and $T$ is block-diagonal with a $1 \times 1$ leading block and an $(n-1)\times(n-1)$ trailing block. The trailing block is normal (immediate from the block structure), so the inductive hypothesis closes the loop.
Strategy for proving $A$ symmetric (real) iff real eigenvalues + orthogonally diagonalisable (∆symmetric-iff-orthogonally-diagonalisable-proof).
- Easy direction ($\Lambda$ real, $Q$ real orthogonal ⇒ $A$ symmetric): just transpose the factorisation.
- Hard direction ($A$ symmetric ⇒ …): three sub-steps.
- Unitarily diagonalisable: $A$ symmetric ⇒ $A$ normal ⇒ Schur form is diagonal (∆diagonal-schur-iff-normal) ⇒ $A$ is unitarily diagonalisable.
- Eigenvalues are real: From $A = A^\ast$ on $A = UDU^\ast$, get $D = D^\ast$, so $D$ is real.
- Real $Q$: real symmetric $A$ with real eigenvalues has real eigenspaces $\ker(A - \lambda I) \subseteq \mathbb R^n$. Apply Gram-Schmidt within each eigenspace over $\mathbb R$ to get a real orthonormal basis.