# Singular values and positive semi-definiteness

I have been working on the following question for a couple of days, and I am not getting anywhere. Suppose $A\in M_{n}$ with singular values $\sigma_{1}\geq \sigma_{2} \geq \cdots \sigma_n$. How can I show the following? $$\sigma_{1}\leq 1 \iff\begin{pmatrix}I_{n} & A \\ A^{*} & I_{n} \\ \end{pmatrix} \geq 0$$

(i) $\sigma_1 \leq 1 \implies B = \begin{pmatrix}I_{n} & A \\ A^{*} & I_{n} \\ \end{pmatrix} \geq 0$:

Consider any non-zero $x \in \mathbb{C}^{2n \times 1}$. Let $x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$ where $x_1,x_2 \in \mathbb{C}^{n \times 1}$. Then $$x^* Bx = \|x_1\|^2 + \|x_2\|^2 + x_1^*Ax_2 + x_2^*A^*x_1 = \|x_1\|^2 + \|x_2\|^2 + 2 \text{Re}(x_1^*Ax_2)$$ We have that $$|x_1^*Ax_2| \leq \|x_1\|\cdot\|Ax_2\| \leq \sigma_1 \|x_1\|\cdot\|x_2\|.$$ We also have that $$-|x_1^*Ax_2| \leq \text{Re}(x_1^*Ax_2) \leq |x_1^*Ax_2|.$$Hence, we get that $$x_1^*Ax_2 + x_2^*A^*x_1 = 2 \text{Re}(x_1^*Ax_2) \in \left[ -2 \sigma_1 \|x_1\|\cdot\|x_2\|,2 \sigma_1 \|x_1\|\cdot\|x_2\| \right].$$ Hence, $$x^* Bx \geq \|x_1\|^2 + \|x_2\|^2 - 2\sigma_1\|x_1\|\cdot\|x_2\| \geq 0 \qquad(\text{since }\sigma_1 \leq 1)$$

(ii) $B = \begin{pmatrix}I_{n} & A \\ A^{*} & I_{n} \\ \end{pmatrix} \geq 0 \implies \sigma_1 \leq 1$:

Since $B$ is given to be positive semi-definite, any non-zero $x \in \mathbb{C}^{2n \times 1}$ satisfies $x^*Bx \geq 0$. Consider $x = \begin{pmatrix} -u \\ v \end{pmatrix}$ where $u \in \mathbb{C}^{n \times 1}$ is the first left singular vector of $A$ and $v \in \mathbb{C}^{n \times 1}$ is the first right singular vector of $A$. Then $$0 \leq x^* Bx = \|u\|^2 + \|v\|^2 - u^*Av - v^*A^*u = 2 - 2 \sigma_1.$$ Hence, we get that $$\sigma_1 \leq 1.$$

This is a typical application the nonstrict Schur Complement Formula.

Basically the following are equivalent (two of them are trivially true): \begin{pmatrix} I &A\\ A^* &I \end{pmatrix} \succeq 0 \iff \begin{align} I &\succeq 0\\ I - A^* I A &\succeq 0\\ A(I-I) &= 0 \end{align} Hence, from the second condition we infer $I\succeq A^*A$, which is another version of the desired property.

• Nice demonstration. – user1551 Nov 30 '11 at 13:49