hermitian matrix problem

Question

$A$ is a hermitian matrix with dimension $n$.

$x_i$ belongs to Orthonormal system $(1 < i \leq n)$, $X$　and their norm is $1$.

$\lambda_i$'s are the eigenvalues of $A$.

How to prove that $$\sum_{i=1}^q x_iAx_i^T \geq \sum_{i=1}^q\lambda_i $$

Answer 1

Let $X= \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}$

Let's consider the matrix $XAX^T$, in particular observe that the $i$-th diagonal entries can be written as $x_iAx_i^T$.

Hence $$\sum_{i=1}^n x_iAx_i^T =trace(XAX^T)=trace(AXX^T)$$

Can you complete the proof now?

Edit: (to handle $q$ and ordered eigenvalues)

Assuming that you are working with real matrices.

Let $A=UDU^T$, where $D=diag(\lambda_1, \ldots, \lambda_n)$.

Let $y_i = x_i U$, notice that $y_i$ is a new set of orthonormal system.

$$\sum_{i=1}^q x_iAx_i^T=\sum_{i=1}^q y_i Dy_i^T=\sum_{i=1}^q \sum_{j=1}^n\lambda_j y_{ij}^2=\sum_{j=1}^n\lambda_j\left(\sum_{i=1}^qy_{ij}^2 \right)$$

Let $z_j = \sum_{i=1}^q y_{ij}^2$, we have$$\sum_{i=1}^q x_iAx_i^T=\sum_{j=1}^n\lambda_jz_j$$

Since $\sum_{i=1}^n y_{ij}^2 = 1$, we have $0 \leq z_j \leq 1.$

Also, we have $\sum_{j=1}^nz_j=q$.

Hence a lower bound can be found by solving the following optimization problem:

$$\min_w \sum_{j=1}^n \lambda_jw_j$$

subject to

$$ 0 \leq w_j \leq 1$$ $$\sum_{j=1}^nw_j = q$$