Majorization

Majorization

Let $x, y \in \mathbb{R}^n$ and order their entries increasingly, $x_{\ell_1} \le x_{\ell_2} \le \cdots \le x_{\ell_n}$ and $y_{m_1} \le y_{m_2} \le \cdots \le y_{m_n}$. $x$ majorizes $y$ when for all $k = 1, \ldots, n$

$$\sum_{i=1}^{k} x_{\ell_i} \ge \sum_{i=1}^{k} y_{m_i}$$

with equality at $k = n$.

Note this is stated with increasing order. Many references order decreasingly instead, which reverses the direction of every statement below (e.g. they say $\lambda(A)$ majorizes $\mathrm{diag}(A)$).

Diagonal and Eigenvalues

For $A \in M_n$ Hermitian, $\mathrm{diag}(A) = (a_{11}, \ldots, a_{nn})$ majorizes $\lambda(A) = (\lambda_1(A), \ldots, \lambda_n(A))$.

Proof By induction, $n = 1$ is trivial. Assume it holds for $n - 1$. Order the diagonal $a_{\ell_1 \ell_1} \le \cdots \le a_{\ell_n \ell_n}$ and let $B$ be the submatrix from deleting row and column $\ell_n$. Then $\mathrm{diag}(B)$ is the $n - 1$ smallest diagonal entries of $A$, and for all $k = 1, \ldots, n - 1$, by interlacing and then induction,

$$\sum_{i=1}^{k} \lambda_i(A) \le \sum_{i=1}^{k} \lambda_i(B) \le \sum_{i=1}^{k} a_{\ell_i \ell_i}$$

For $k = n$, $\sum_{i=1}^{n} \lambda_i(A) = \mathrm{tr}(A) = \sum_{i=1}^{n} a_{\ell_i \ell_i}$.

Eigenvalue Sums as Traces

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

$$\sum_{k=1}^{r} \lambda_k(A) = \min_{\substack{U \in M_{n,r} \\ \text{orthonormal cols}}} \mathrm{tr}(U^*AU), \qquad \sum_{k=0}^{r-1} \lambda_{n-k}(A) = \max_{\substack{U \in M_{n,r} \\ \text{orthonormal cols}}} \mathrm{tr}(U^*AU)$$

Proof

1. For any $U \in M_{n,r}$ with orthonormal columns, there is a unitary $V = [\, U \mid * \,] \in M_n$ by Gram-Schmidt.
2. $U^*AU$ is the leading $r \times r$ principal submatrix of $V^*AV$.
3. So $\lambda_k(A) = \lambda_k(V^*AV) \le \lambda_k(U^*AU)$ by interlacing.
4. Summing over $k$, $\sum_{k=1}^{r} \lambda_k(A) \le \sum_{k=1}^{r} \lambda_k(U^*AU) = \mathrm{tr}(U^*AU)$, so we just need a $U$ attaining the min.
5. Let $W = [w_1 | \cdots | w_r]$ with $w_i$ orthonormal eigenvectors of $\lambda_1, \ldots, \lambda_r$. Then $W^*AW = \mathrm{diag}(\lambda_1, \ldots, \lambda_r)$ and $\mathrm{tr}(W^*AW) = \sum_{k=1}^{r} \lambda_k(A)$.

Eigenvalues of a Sum

For $A, B$ Hermitian, $\lambda(A + B)$ majorizes $\lambda(A) + \lambda(B)$.

Proof For all $k = 1, \ldots, n$,

$$\begin{aligned} \sum_{i=1}^{k} \lambda_i(A + B) &= \min_{\substack{U \in M_{n,k} \\ \text{orthonormal cols}}} \mathrm{tr}(U^*(A + B)U) = \min \big(\mathrm{tr}(U^*AU) + \mathrm{tr}(U^*BU)\big) \\ &\ge \min \mathrm{tr}(U^*AU) + \min \mathrm{tr}(U^*BU) = \sum_{i=1}^{k} \lambda_i(A) + \sum_{i=1}^{k} \lambda_i(B) \end{aligned}$$

with equality at $k = n$ since both sides are $\mathrm{tr}(A + B)$.

Hadamard's Inequality

Let $A \in M_n$ be PSD. Then

$$\det A \le \prod_{i=1}^{n} a_{ii}$$

Proof For all $i$, $0 \le \lambda_1(A) \le a_{ii}$ by PSD and interlacing, so $\prod_i a_{ii} \ge 0$. If $A$ is singular, $\det A = 0$ and we are done.

Else $A$ is PD, so $0 < \lambda_1(A) \le a_{ii}$. Let $D = \mathrm{diag}(1/\sqrt{a_{11}}, \ldots, 1/\sqrt{a_{nn}})$. $DAD$ is Hermitian PD with ones on the diagonal, so by AM-GM

$$\frac{\det A}{\prod_{i=1}^{n} a_{ii}} = \det D^2 \det A = \det(DAD) = \prod_{i=1}^{n} \lambda_i(DAD) \le \Big(\frac{1}{n} \sum_{i=1}^{n} \lambda_i(DAD)\Big)^n = \Big(\frac{1}{n} \mathrm{tr}(DAD)\Big)^n = \Big(\frac{n}{n}\Big)^n = 1$$