# Eigenvalue of PSD matrices by constrained SDP program

Given Lemma 1, I want to prove the following corollary.

lemma 1 (Rayleigh Quotient): Given matrix $$A \succeq 0$$, $$$$\lambda_{\min} (A) = \min_{x \in \mathbb R^n}\frac{x^\top A x}{x^\top x}.$$$$

Corollary: Given matrix $$A \succeq 0$$, $$$$\lambda_{\min}(A) = \underset{U \in \Delta_{n \times n}}{\min} \langle A,U \rangle.$$$$ where $$\Delta_{n \times n} \overset{\operatorname{def}}{=} \{M \in \mathbb R^{n \times n}~:~M \succeq 0,~\mathrm{Trace}(M) = 1 \}$$, and $$\langle X, Y\rangle = \mathrm{Trace}(XY)$$ denotes the inner product between two symmetric matrices.

I found the following proof in the net, but I cannot totally understand it.

Proof: Let $$\begin{equation*} U^* = \underset{U \in \Delta_{n \times n}}{\arg\min} \langle A, U\rangle. \end{equation*}$$ We take the SVD $$A = \sum_{i=1}^{n} \lambda_i u_i u_i^\top$$ and $$\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$$. It is clear that $$\langle A, U^* \rangle \leq \langle A, u_1 u_1^\top \rangle$$ $$= \lambda_{\min}(A)$$. Next, we need to show $$\lambda_{\min}(A) \leq \langle A, U^* \rangle$$.

The SVD of $$U^* = \sum_{i=1}^{n} \sigma_i v_i v_i^\top$$. If $$\lambda_{\min}(A) > \langle A, U^* \rangle$$, then $$\lambda_{\min}(A) > \sum_{i=1}^{n} \sigma_i v_i^\top A v_i$$. Since $$\sum \sigma_i = 1$$, there exists $$k$$ such that $$\lambda_{\min}(A) > v_k^\top A v_k$$ which contradicts Lemma 1.

The parts of the proof I do not understand well are:

• Why $$\langle A, U^* \rangle \leq \langle A, u_1 u_1^\top \rangle$$ is clear?
• Why?

there exists $$k$$ such that $$\lambda_{\min}(A) > v_k^\top A v_k$$ which contradicts Lemma 1

I will be very grateful if you could help me to understand these parts.

The first inequality follows because $$u_1 u_1^{\mathsf{T}} \in \Delta_{n \times n}$$, and $$U^{\ast}$$ is the minimizer over that set:
$$\langle U^{\ast}, A \rangle = \min_{U \in \Delta_{n \times n}} \langle U, A \rangle \leq \langle u_1 u_1^{\mathsf{T}}, A \rangle.$$
Indeed, you can verify that $$u_1 u_1^{\mathsf{T}} \succeq 0$$ and its trace is equal to $$\mathsf{tr}(u_1 u_1^{\mathsf{T}}) = \mathsf{tr}(u_1^{\mathsf{T}} u_1) = \|u_1\|^2 = 1.$$
The second part follows because $$\sum_{i = 1}^n \sigma_i v_i^{\mathsf{T}} A v_i \geq \underbrace{\left( \sum_{i = 1}^n \sigma_i \right)}_{= 1} \cdot \min_{i = 1, \dots, n} \left( v_i^{\mathsf{T}} A v_i \right).$$
In particular, the minimum is attained for some index $$k$$.