Eigenvalues of Hermitian Matrices

Throughout, the eigenvalues of a Hermitian $A \in M_n$ are ordered $\lambda_1 \le \lambda_2 \le \cdots \le \lambda_n$.

Field of Values

For $A \in M_n$,

$$F(A) = \left\{\frac{x^*Ax}{x^*x} : x \in \mathbb{C}^n, x \neq 0\right\} = \{x^*Ax : x \in \mathbb{C}^n, \|x\|_2 = 1\}$$

If $A$ is normal, $F(A) = \mathrm{Co}(\sigma(A))$, the convex hull of the eigenvalues.

Proof Let $\mathbb{S}$ be the unit sphere and $A = UDU^*$. Since $U^*$ maps $\mathbb{S}$ onto $\mathbb{S}$,

$$F(A) = \{x^*UDU^*x : x \in \mathbb{S}\} = \{y^*Dy : y \in \mathbb{S}\} = \Big\{\sum_{i=1}^{n} |y_i|^2 d_{ii} : \sum_{i=1}^{n} |y_i|^2 = 1\Big\}$$

which are exactly the convex combinations of the eigenvalues.

Rayleigh-Ritz

$A \in M_n$ Hermitian is PSD if $x^*Ax \ge 0$ for all $x \in \mathbb{C}^n$.

For $A \in M_n$ Hermitian,

$$\min_{x \neq 0} \frac{x^*Ax}{x^*x} = \lambda_1(A), \qquad \max_{x \neq 0} \frac{x^*Ax}{x^*x} = \lambda_n(A)$$

More generally, let $A$ have orthonormal eigenvectors $\mu_1, \ldots, \mu_n$ with eigenvalues $\lambda_1 \le \cdots \le \lambda_n$. For all $k = 1, \ldots, n$

$$\min_{\substack{x \neq 0 \\ x \perp \mu_1, \ldots, \mu_{k-1}}} \frac{x^*Ax}{x^*x} = \lambda_k, \qquad \max_{\substack{x \neq 0 \\ x \perp \mu_{k+1}, \ldots, \mu_n}} \frac{x^*Ax}{x^*x} = \lambda_k$$

Proof Let $A = UDU^*$ with $U = [\mu_1 | \cdots | \mu_n]$ and $D = \mathrm{diag}(\lambda_1, \ldots, \lambda_n)$. $x \perp \mu_1, \ldots, \mu_{k-1}$ iff $x \in \mathrm{Span}\{\mu_k, \ldots, \mu_n\}$, i.e. $x = \sum_{i=k}^{n} \delta_i \mu_i$ with $\delta_i$ not all 0. Then

$$\frac{x^*Ax}{x^*x} = \frac{\sum_{i=k}^{n} \bar{\delta}_i \delta_i \lambda_i}{\sum_{i=k}^{n} \bar{\delta}_i \delta_i} = \sum_{j=k}^{n} \alpha_j \lambda_j, \qquad \alpha_j = \frac{|\delta_j|^2}{\sum_{i=k}^{n} |\delta_i|^2}$$

with $\alpha_j \ge 0$ and $\sum \alpha_j = 1$. This is a convex combination of $\lambda_k, \ldots, \lambda_n$, so the minimum is $\min \mathrm{Co}(\lambda_k, \ldots, \lambda_n) = \lambda_k$, attained at $x = \mu_k$. The max is the same argument.

Courant-Fisher

For $A \in M_n$ Hermitian and all $k = 1, \ldots, n$,

$$\max_{y_1, \ldots, y_{k-1} \in \mathbb{C}^n} \left( \min_{\substack{x \neq 0 \\ x \perp y_1, \ldots, y_{k-1}}} \frac{x^*Ax}{x^*x} \right) = \lambda_k, \qquad \min_{y_{k+1}, \ldots, y_n \in \mathbb{C}^n} \left( \max_{\substack{x \neq 0 \\ x \perp y_{k+1}, \ldots, y_n}} \frac{x^*Ax}{x^*x} \right) = \lambda_k$$

Proof

1. For any $y_1, \ldots, y_{k-1}$, $\mathrm{Span}\{\mu_1, \ldots, \mu_k\}$ has dimension $k$ and $\mathrm{Span}\{y_1, \ldots, y_{k-1}\}^\perp$ has dimension $\ge n - k + 1$, so their intersection is not $\{\vec{0}\}$.
2. Let $\omega \neq 0$ be in the intersection. $\frac{\omega^*A\omega}{\omega^*\omega}$ is a convex combination of $\lambda_1, \ldots, \lambda_k$, so it is $\le \lambda_k$.
3. So the inner min is $\le \lambda_k$ for every choice of $y$'s, with equality at $y_i = \mu_i$ by Rayleigh-Ritz.

Weyl's Inequality

For any $A, B \in M_n$ Hermitian and all $k = 1, \ldots, n$,

$$\lambda_k(A) + \lambda_1(B) \le \lambda_k(A + B) \le \lambda_k(A) + \lambda_n(B)$$

Proof Using the min-max form of Courant-Fisher and Rayleigh-Ritz on $B$,

$$\lambda_k(A + B) = \min_{y} \max_{x \perp y} \left(\frac{x^*Ax}{x^*x} + \frac{x^*Bx}{x^*x}\right) \le \min_{y} \max_{x \perp y} \left(\frac{x^*Ax}{x^*x} + \lambda_n(B)\right) = \lambda_k(A) + \lambda_n(B)$$

The lower bound is the same with $\frac{x^*Bx}{x^*x} \ge \lambda_1(B)$.

If $B$ is also PSD, then $\lambda_1(B) \ge 0$, so for all $k$

$$\lambda_k(A) \le \lambda_k(A) + \lambda_1(B) \le \lambda_k(A + B)$$

Interlacing Theorem I

For $A \in M_n$ Hermitian, $a \in \mathbb{R}$, $z \in \mathbb{C}^n$ and all $k = 1, \ldots, n - 1$,

$$\lambda_k(A + azz^*) \le \lambda_{k+1}(A)$$

Proof Adding the constraint $x \perp z$ can only decrease the inner min, and on $x \perp z$ the term $azz^*$ vanishes,

$$\begin{aligned} \lambda_k(A + azz^*) &= \max_{y_1, \ldots, y_{k-1}} \min_{\substack{x \neq 0 \\ x \perp y_1, \ldots, y_{k-1}}} \frac{x^*(A + azz^*)x}{x^*x} \le \max_{y_1, \ldots, y_{k-1}} \min_{\substack{x \neq 0 \\ x \perp y_1, \ldots, y_{k-1}, z}} \frac{x^*Ax}{x^*x} \\ &\le \max_{y_1, \ldots, y_k} \min_{\substack{x \neq 0 \\ x \perp y_1, \ldots, y_k}} \frac{x^*Ax}{x^*x} = \lambda_{k+1}(A) \end{aligned}$$

Corollary For $A, B \in M_n$ Hermitian with $\mathrm{rank}(B) = r$, and all $k$ for which the indices make sense,

$$\lambda_k(A + B) \le \lambda_{k+r}(A)$$

Write $B = U \mathrm{diag}(d_{11}, \ldots, d_{rr}, 0, \ldots, 0) U^*$, so $B = \sum_{i=1}^{r} d_{ii} U_i U_i^*$ is a sum of $r$ terms of the form $azz^*$. The rest follows by induction.

Applying this to $A + B$ and $-B$ (also rank $r$) gives both directions,

$$\lambda_{k-r}(A) \le \lambda_k(A + B) \le \lambda_{k+r}(A), \qquad \lambda_{k-r}(A + B) \le \lambda_k(A) \le \lambda_{k+r}(A + B)$$

Interlacing Theorem II

Let $A \in M_n$ be Hermitian and $B$ an $r \times r$ principal submatrix of $A$, which is Hermitian by default. For all $k = 1, \ldots, r$,

$$\lambda_k(A) \le \lambda_k(B) \le \lambda_{k+n-r}(A)$$

Proof Let the deleted rows and columns be indexed by $i_1, \ldots, i_{n-r}$. Adding constraints can only increase the inner min, so

$$\begin{aligned} \lambda_k(A) &= \max_{y_1, \ldots, y_{k-1} \in \mathbb{C}^n} \min_{\substack{x \neq 0 \\ x \perp y_1, \ldots, y_{k-1}}} \frac{x^*Ax}{x^*x} \le \max_{y_1, \ldots, y_{k-1} \in \mathbb{C}^n} \min_{\substack{x \neq 0 \\ x \perp y_1, \ldots, y_{k-1} \\ x \perp e_{i_1}, \ldots, e_{i_{n-r}}}} \frac{x^*Ax}{x^*x} \\ &= \max_{v_1, \ldots, v_{k-1} \in \mathbb{C}^r} \min_{\substack{z \neq 0 \\ z \perp v_1, \ldots, v_{k-1}}} \frac{z^*Bz}{z^*z} = \lambda_k(B) \end{aligned}$$

The upper bound is the same argument with the min-max form.

Corollary Taking $r = 1$, for all $k$

$$\lambda_1(A) \le a_{kk} \le \lambda_n(A)$$