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$
Singular values and positive semi-definiteness
2 Answers
(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.
-
0Nice demonstration. – 2011-11-30