13 Linear Algebra

Published

February 19, 2026

(\lambda, x) eigenpair of A where A x = \lambda x and x \not= 0. Here, \lambda is an eigenvalue and x is an eigenvector,
we say x or (\lambda,x) is normalised if |x| = 1 (normally with respect to |\cdot| = |\cdot|_2),
\sigma(A) := \{ \lambda : \exists x \not= 0 \text{ s.t. } A x = \lambda x \}: spectrum of A,
\rho(A) := \max_{\lambda \in \sigma(A)} |\lambda|: spectral radius of A,
A^\star: conjugate transpose of A given by A^\star_{ij} = \overline{A_{ji}},
U is unitary if U^\star = U^{-1},

Definition 13.1 We say A is normal if A^\star A = A A^\star where A^\star is the conjugate transpose of A.

Exercise 13.1 Show that real symmetric matrices are normal.

Theorem 13.1 A is normal if and only if there exists a unitary matrix U (i.e. U^\star = U^{-1}) and a diagonal matrix \Lambda such that

\begin{align} A = U \Lambda U^\star. \end{align}

On defining \lambda_j := \Lambda_{jj} and u_j the j^\text{th} column of U, we have

\begin{align} A = \sum_{j=1}^n \lambda_j u_j u_j^\star \end{align}

where (\lambda_j, u_j) are orthonormal eigenpairs of A.

Proof.

If A = U \Lambda U^\star, then

\begin{align} A^\star A &= (U \Lambda U^\star)^\star U \Lambda U^\star \nonumber\\ % &= U \Lambda^\star (U^\star U) \Lambda U^\star \nonumber\\ % &= U \Lambda \Lambda^\star U^\star \nonumber\\ % &= U \Lambda U^\star U \Lambda^\star U^\star \nonumber\\ % &= (U \Lambda U^\star) (U \Lambda U^\star)^\star % = AA^\star . \end{align}

Here, we have used the fact that \Lambda^\star \Lambda = \Lambda\Lambda^\star because \Lambda is diagonal.

To prove the other direction, we will assume Schur’s decompostion: for a general matrix A there exists a unitary matrix U and upper triangular matrix T such that

\begin{align} A = U T U^\star. \end{align}

Schur decomposition

Schur decomposition is not too difficult to prove: there exists an eigenpair (\lambda_1,v_1) of A which can be extended to an orthonormal basis v_1,\dots,v_n. On defining U = [v_1 | \cdots | v_n], we have

\begin{align} U^\star A U = \begin{pmatrix} \lambda_1 & x^T \\ 0 & B \end{pmatrix} \end{align}

where x^T is some row vector and B is (n-1)\times (n-1). Writing the Schur decomposition of B as matrix B = V T V^\star, we have

\begin{align} A &= U\begin{pmatrix} 1 & 0\\ 0 & V \end{pmatrix} \begin{pmatrix} \lambda_1 & x^T \\ 0 & T \end{pmatrix} \begin{pmatrix} 1 & 0\\ 0 & V^\star \end{pmatrix} U^\star. \end{align}

The result follows by showing that this is a Schur decomposition of A.

Since A is normal,

\begin{align} U T T^\star U^\star &= U T U^\star (U T U^\star)^\star \nonumber\\ % &= AA^\star = A^\star A \nonumber\\ % &= (U T U^\star)^\star U T U^\star \nonumber % &= U T^\star T U^\star. \end{align}

As a result, T is normal (i.e. TT^\star = T^\star T). Since T is upper triangular,

\begin{align} \sum_{k} |T_{1k}|^2 &= (TT^\star)_{11} \nonumber\\ % &= (T^\star T)_{11} = \sum_k |T_{1k}|^2 \nonumber\\ % &= |T_{11}|^2 \end{align}

and so T_{1k} = 0 for all k\not=1. By applying the exact same argument on the remaining (n-1)\times(n-1) submatrix, we find that T is diagonal.

Let u be column j of U. Then

\begin{align} (A u)_i &= \sum_{km} U_{ik} \Lambda_{kk} U^\star_{km} u_{m} \nonumber\\ % &= \sum_{km} U_{ik} \Lambda_{kk} U^\star_{km} U_{mj} \nonumber\\ % &= U_{ij} \Lambda_{jj} % = \Lambda_{jj} u_i. \end{align}

Finally, we have

\begin{align} A_{ij} &= \sum_{k} \Lambda_{kk} U_{ik} U_{kj}^\star \nonumber\\ % &= \sum_{k} \Lambda_{kk} (u_k)_i \overline{(u_k)_j} \end{align}

where u_k is the k^\text{th} column of U.

Theorem 13.2 If A is normal, then \rho(A) = \|A\|_2.

Proof.

By the previous theorem, we can write

\begin{align} A = U \Lambda U^\star = \sum_j \lambda_j u_j u_j^\star \end{align}

where (\lambda_j,u_j) are normalised eigenpairs of A. Moreover, since U = [u_1|\dots|u_n] is unitary, we have u_{i}^\star u_j = \sum_k \overline{(u_i)_k} (u_j)_k = \delta_{ij}.

Write x = \alpha_1 u_1 + \dots + \alpha_n u_n where |x|_2 = 1. We have

\begin{align} 1 &= |x|_2^2 = \sum_k \overline{x_k} x_k \nonumber\\ &= \sum_k \overline{(\alpha_1 u_1 + \cdots + \alpha_n u_n)_k} (\alpha_1 u_1 + \cdots + \alpha_n u_n)_k \nonumber\\ % &= |\alpha_1|^2 + \cdots + |\alpha_n|^2 \end{align}

and

\begin{align} | Ax |_2^2 % &= \sum_k \overline{(Ax)_k} (Ax)_k \nonumber\\ % &= |\alpha_1 \lambda_1|^2 + \cdots + |\alpha_n \lambda_n|^2. \end{align}

Lemma 13.1 \rho(A) \leq \|A\| for every submultiplicative matrix norm.

Proof.

In Lecture 8 we proved this for any induced matrix norm. Here, we take any submultiplicative matrix norm \|\cdot\|.

Let (\lambda, x) be an eigenpair of A and notice that B := xx^T satisies

\begin{align} AB = (Ax) x^T = (\lambda x) x^T = \lambda B . \end{align}

As a result, since \|\cdot\| is submultiplicative, we have |\lambda| \| B\| = \| A B \| \leq \|A\| \|B\|. Dividing by \|B\| gives |\lambda| \leq \|A\|.

Theorem 13.3 For fixed A and \epsilon > 0, there exists a submultiplicative matrix norm \| \cdot \|_\epsilon such that

\begin{align} \rho(A) \leq \| A \|_{\epsilon} \leq \rho(A) + \epsilon. \end{align}

Proof.

We have already seen \rho(A) \leq \| A \|_{\epsilon} for all submultiplicative matrix norms \| \cdot \|_\epsilon.

We use the Schur decomposition of A to write A = U TU^\star with U unitary and T upper triangular and let

\begin{align} D := \begin{pmatrix} \delta & \\ & \delta^2 \\ & & \delta^3 \\ & & & \ddots \\ & & & & \delta^{n} \end{pmatrix}. \end{align}

Then, \|B\|' := \| D^{-1} U^\star B U D \|_{\infty} is a submultiplicative matrix norm with

\begin{align} \|A\|' &= \| D^{-1} U^\star A U D \|_{\infty} \nonumber\\ % &= \| D^{-1} T D \|_{\infty} \nonumber\\ % &= \max_{i} \sum_j | [D^{-1} T D]_{ij} | \nonumber\\ % &= \max_i \sum_j \delta^{j-i} |T_{ij}| \nonumber\\ % &= \max_i \big[ |\lambda_i| + \sum_{j>i} \delta^{j-i} |T_{ij}|\big] . \end{align}

Choosing \delta sufficiently small, we can make \sum_{j>i} \delta^{j-i} |T_{ij}| \leq \epsilon and define \| \cdot \|_{\epsilon} := \|\cdot\|' for this choice of \delta.

Other Links