Eigenvalue Decomposition

Let $\lambda$ be an eigenvalue with eigenvector $\mathbf{v} \neq \mathbf{0}$, so $\mathbf{A}\mathbf{v} = \lambda \mathbf{v}$. Left-multiply both sides by $\mathbf{v}^H$: $$\mathbf{v}^H \mathbf{A} \mathbf{v} = \lambda \, \mathbf{v}^H \mathbf{v}.$$ Since $\mathbf{v} \neq \mathbf{0}$, we have $\mathbf{v}^H \mathbf{v} = \|\mathbf{v}\|^2 > 0$, so $$\lambda = \frac{\mathbf{v}^H \mathbf{A} \mathbf{v}}{\mathbf{v}^H \mathbf{v}}.$$ Now take the conjugate of both sides. Using $\mathbf{A}^H = \mathbf{A}$: $$\bar{\lambda} = \frac{(\mathbf{v}^H \mathbf{A} \mathbf{v})^*}{\mathbf{v}^H \mathbf{v}} = \frac{\mathbf{v}^H \mathbf{A}^H \mathbf{v}}{\mathbf{v}^H \mathbf{v}} = \frac{\mathbf{v}^H \mathbf{A} \mathbf{v}}{\mathbf{v}^H \mathbf{v}} = \lambda.$$ Hence $\lambda = \bar{\lambda}$, which means $\lambda \in \mathbb{R}$. $\blacksquare$

This was established in TEigenvalues of Hermitian Matrices Are Real. For completeness: if $\mathbf{A}\mathbf{v} = \lambda \mathbf{v}$ with $\mathbf{v} \neq \mathbf{0}$, then $$\lambda = \frac{\mathbf{v}^H \mathbf{A} \mathbf{v}}{\|\mathbf{v}\|^2} = \frac{(\mathbf{v}^H \mathbf{A} \mathbf{v})^*}{\|\mathbf{v}\|^2} = \bar{\lambda},$$ where the second equality uses $\mathbf{A}^H = \mathbf{A}$ and the scalar identity $(z^H w)^* = w^H z$. Hence $\lambda \in \mathbb{R}$.

Let $\mathbf{A}\mathbf{v}_1 = \lambda_1 \mathbf{v}_1$ and $\mathbf{A}\mathbf{v}_2 = \lambda_2 \mathbf{v}_2$ with $\lambda_1 \neq \lambda_2$. Compute: $$\lambda_1 \, \mathbf{v}_2^H \mathbf{v}_1 = \mathbf{v}_2^H (\mathbf{A}\mathbf{v}_1) = (\mathbf{A}^H \mathbf{v}_2)^H \mathbf{v}_1 = (\mathbf{A}\mathbf{v}_2)^H \mathbf{v}_1 = \overline{\lambda_2} \, \mathbf{v}_2^H \mathbf{v}_1 = \lambda_2 \, \mathbf{v}_2^H \mathbf{v}_1,$$ where the last equality uses $\lambda_2 \in \mathbb{R}$ (Step 1). Rearranging: $$(\lambda_1 - \lambda_2)\, \mathbf{v}_2^H \mathbf{v}_1 = 0.$$ Since $\lambda_1 \neq \lambda_2$, we conclude $\mathbf{v}_2^H \mathbf{v}_1 = 0$, i.e., $\mathbf{v}_1 \perp \mathbf{v}_2$.

We prove the full spectral decomposition by strong induction on $n$.

Base case ($n = 1$). A $1 \times 1$ Hermitian matrix $\mathbf{A} = [a]$ has $a \in \mathbb{R}$, and the decomposition is trivially $\mathbf{A} = [1]\,[a]\,[1]^H$.

Inductive step. Assume the theorem holds for all Hermitian matrices of size $(n-1) \times (n-1)$. Let $\mathbf{A} \in \mathbb{C}^{n \times n}$ be Hermitian.

Existence of an eigenvalue. The characteristic polynomial $\det(\mathbf{A} - \lambda \mathbf{I})$ has degree $n$ and therefore possesses at least one root $\lambda_1 \in \mathbb{C}$. By Step 1, $\lambda_1 \in \mathbb{R}$. Let $\mathbf{q}_1$ be a corresponding unit eigenvector: $\mathbf{A}\mathbf{q}_1 = \lambda_1 \mathbf{q}_1$, $\|\mathbf{q}_1\| = 1$.

Deflation. Extend $\mathbf{q}_1$ to an orthonormal basis $\{\mathbf{q}_1, \mathbf{u}_2, \ldots, \mathbf{u}_n\}$ of $\mathbb{C}^n$ (e.g., via Gram--Schmidt). Form the unitary matrix $\mathbf{U}_1 = [\mathbf{q}_1 \mid \mathbf{u}_2 \mid \cdots \mid \mathbf{u}_n]$. Then $$\mathbf{U}_1^H \mathbf{A} \mathbf{U}_1 = \begin{pmatrix} \lambda_1 & \mathbf{w}^H \\ \mathbf{w} & \mathbf{B} \end{pmatrix}$$ for some $\mathbf{w} \in \mathbb{C}^{n-1}$ and $\mathbf{B} \in \mathbb{C}^{(n-1)\times(n-1)}$.

Because $\mathbf{A}$ is Hermitian, so is $\mathbf{U}_1^H \mathbf{A} \mathbf{U}_1$ (since $(\mathbf{U}_1^H \mathbf{A} \mathbf{U}_1)^H = \mathbf{U}_1^H \mathbf{A}^H \mathbf{U}_1 = \mathbf{U}_1^H \mathbf{A} \mathbf{U}_1$). The Hermitian property forces $\lambda_1 \in \mathbb{R}$ (already known) and $\mathbf{B}^H = \mathbf{B}$. It also forces $\mathbf{w}^H$ to equal the conjugate transpose of $\mathbf{w}$, which is automatically satisfied. However, a sharper constraint comes from the first column: $$\mathbf{U}_1^H \mathbf{A} \mathbf{U}_1 \mathbf{e}_1 = \mathbf{U}_1^H \mathbf{A} \mathbf{q}_1 = \lambda_1 \mathbf{U}_1^H \mathbf{q}_1 = \lambda_1 \mathbf{e}_1 = \begin{pmatrix} \lambda_1 \\ \mathbf{0} \end{pmatrix}.$$ Comparing with the first column of the block form gives $\mathbf{w} = \mathbf{0}$. Therefore $$\mathbf{U}_1^H \mathbf{A} \mathbf{U}_1 = \begin{pmatrix} \lambda_1 & \mathbf{0}^H \\ \mathbf{0} & \mathbf{B} \end{pmatrix}.$$

Apply the inductive hypothesis. Since $\mathbf{B}$ is an $(n-1) \times (n-1)$ Hermitian matrix, by the induction hypothesis there exists a unitary $\mathbf{Q}_{n-1}$ and a real diagonal $\mathbf{\Lambda}_{n-1}$ such that $\mathbf{B} = \mathbf{Q}_{n-1} \mathbf{\Lambda}_{n-1} \mathbf{Q}_{n-1}^H$.

Define $$\mathbf{U}_2 = \begin{pmatrix} 1 & \mathbf{0}^H \\ \mathbf{0} & \mathbf{Q}_{n-1} \end{pmatrix}.$$ Then $\mathbf{U}_2$ is unitary and $$\mathbf{U}_2^H (\mathbf{U}_1^H \mathbf{A} \mathbf{U}_1) \mathbf{U}_2 = \begin{pmatrix} \lambda_1 & \mathbf{0}^H \\ \mathbf{0} & \mathbf{\Lambda}_{n-1} \end{pmatrix} = \mathbf{\Lambda},$$ which is real and diagonal.

Setting $\mathbf{Q} = \mathbf{U}_1 \mathbf{U}_2$ (a product of unitary matrices, hence unitary), we obtain $$\mathbf{Q}^H \mathbf{A} \mathbf{Q} = \mathbf{\Lambda} \quad \Longleftrightarrow \quad \mathbf{A} = \mathbf{Q} \mathbf{\Lambda} \mathbf{Q}^H.$$

Writing $\mathbf{Q} = [\mathbf{q}_1 \mid \cdots \mid \mathbf{q}_n]$, this becomes $$\mathbf{A} = \sum_{i=1}^{n} \lambda_i \, \mathbf{q}_i \mathbf{q}_i^H,$$ which completes the proof. $\blacksquare$

The induction above does not assume that eigenvalues are distinct. If $\lambda_1$ has algebraic multiplicity $m > 1$, then the deflated matrix $\mathbf{B}$ still has $\lambda_1$ as an eigenvalue (with multiplicity $m - 1$), and the inductive hypothesis produces orthonormal eigenvectors for it.

In the case of a repeated eigenvalue, the eigenspace $\mathcal{E}_{\lambda_1} = \mathcal{N}(\mathbf{A} - \lambda_1 \mathbf{I})$ has dimension equal to the algebraic multiplicity (for Hermitian matrices, geometric and algebraic multiplicities always coincide). Any orthonormal basis of $\mathcal{E}_{\lambda_1}$ serves as a valid set of eigenvectors.

This non-uniqueness of eigenvectors within a repeated eigenspace is a feature, not a deficiency: it grants freedom in choosing convenient bases — a freedom exploited, for instance, when jointly diagonalizing commuting Hermitian matrices.

By the spectral theorem (TSpectral Theorem for Hermitian Matrices), write $\mathbf{A} = \mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^H$. Any nonzero $\mathbf{x} \in \mathbb{C}^n$ can be expressed as $\mathbf{x} = \sum_{i=1}^{n} c_i \mathbf{q}_i$ where $c_i = \mathbf{q}_i^H \mathbf{x}$. Define $\mathbf{c} = \mathbf{Q}^H \mathbf{x} = (c_1, \ldots, c_n)^T$.

Since $\mathbf{Q}$ is unitary, $\|\mathbf{x}\|^2 = \|\mathbf{c}\|^2 = \sum_{i=1}^{n} |c_i|^2 > 0$.

Compute: $$\mathbf{x}^H \mathbf{A} \mathbf{x} = \mathbf{c}^H \mathbf{Q}^H \mathbf{A} \mathbf{Q} \mathbf{c} = \mathbf{c}^H \mathbf{\Lambda} \mathbf{c} = \sum_{i=1}^{n} \lambda_i |c_i|^2.$$ Therefore $$R(\mathbf{A}, \mathbf{x}) = \frac{\sum_{i=1}^{n} \lambda_i |c_i|^2}{\sum_{i=1}^{n} |c_i|^2}.$$ Define weights $w_i = |c_i|^2 / \|\mathbf{c}\|^2 \geq 0$ with $\sum_i w_i = 1$. Then $R(\mathbf{A}, \mathbf{x}) = \sum_{i=1}^n w_i \lambda_i$.

Since $w_i \geq 0$ and $\sum_i w_i = 1$, the Rayleigh quotient is a convex combination of the eigenvalues. Therefore: $$R(\mathbf{A}, \mathbf{x}) = \sum_{i=1}^{n} w_i \lambda_i \leq \lambda_1 \sum_{i=1}^{n} w_i = \lambda_1,$$ and similarly $$R(\mathbf{A}, \mathbf{x}) = \sum_{i=1}^{n} w_i \lambda_i \geq \lambda_n \sum_{i=1}^{n} w_i = \lambda_n.$$

For $\mathbf{x} = \mathbf{q}_1$: $c_1 = 1$, $c_i = 0$ for $i \geq 2$, giving $R(\mathbf{A}, \mathbf{q}_1) = \lambda_1$.

For $\mathbf{x} = \mathbf{q}_n$: $c_n = 1$, $c_i = 0$ for $i \leq n - 1$, giving $R(\mathbf{A}, \mathbf{q}_n) = \lambda_n$.

Hence the upper and lower bounds are both achieved. $\blacksquare$

Let $\mathcal{V}_k = \operatorname{span}\{\mathbf{q}_1, \ldots, \mathbf{q}_k\}$. For any $\mathbf{x} = \sum_{i=1}^k c_i \mathbf{q}_i \in \mathcal{V}_k$ with $\mathbf{x} \neq \mathbf{0}$: $$R(\mathbf{A}, \mathbf{x}) = \frac{\sum_{i=1}^k \lambda_i |c_i|^2}{\sum_{i=1}^k |c_i|^2} \geq \lambda_k,$$ since $\lambda_i \geq \lambda_k$ for $i \leq k$. Thus $\min_{\mathbf{x} \in \mathcal{V}_k \setminus \{\mathbf{0}\}} R(\mathbf{A}, \mathbf{x}) \geq \lambda_k$, and equality is achieved at $\mathbf{x} = \mathbf{q}_k$. This gives $$\max_{\dim \mathcal{V} = k} \min_{\mathbf{x} \in \mathcal{V}} R(\mathbf{A}, \mathbf{x}) \geq \lambda_k.$$

Let $\mathcal{V}$ be any $k$-dimensional subspace. Define $\mathcal{W}_{n-k+1} = \operatorname{span}\{\mathbf{q}_k, \mathbf{q}_{k+1}, \ldots, \mathbf{q}_n\}$, which has dimension $n - k + 1$. By a dimension argument: $$\dim(\mathcal{V}) + \dim(\mathcal{W}_{n-k+1}) = k + (n - k + 1) = n + 1 > n,$$ so $\mathcal{V} \cap \mathcal{W}_{n-k+1}$ contains a nonzero vector $\mathbf{z}$.

Since $\mathbf{z} \in \mathcal{W}_{n-k+1}$, write $\mathbf{z} = \sum_{i=k}^{n} c_i \mathbf{q}_i$. Then $$R(\mathbf{A}, \mathbf{z}) = \frac{\sum_{i=k}^{n} \lambda_i |c_i|^2}{\sum_{i=k}^{n} |c_i|^2} \leq \lambda_k,$$ since $\lambda_i \leq \lambda_k$ for $i \geq k$.

Since $\mathbf{z} \in \mathcal{V}$, we have $\min_{\mathbf{x} \in \mathcal{V}} R(\mathbf{A}, \mathbf{x}) \leq R(\mathbf{A}, \mathbf{z}) \leq \lambda_k$.

As this holds for every $k$-dimensional $\mathcal{V}$: $$\max_{\dim \mathcal{V} = k} \min_{\mathbf{x} \in \mathcal{V}} R(\mathbf{A}, \mathbf{x}) \leq \lambda_k.$$

Combining Steps 1 and 2: $$\lambda_k = \max_{\substack{\mathcal{V} \subseteq \mathbb{C}^n \\ \dim \mathcal{V} = k}} \;\min_{\substack{\mathbf{x} \in \mathcal{V} \\ \mathbf{x} \neq \mathbf{0}}} R(\mathbf{A}, \mathbf{x}).$$ The dual (min-max) characterization follows by applying the max-min result to $-\mathbf{A}$ (whose eigenvalues are $-\lambda_n \geq \cdots \geq -\lambda_1$) and substituting $k' = n - k + 1$. $\blacksquare$