Prove that $X \succeq xx^T \iff \begin{bmatrix} X & x \\ x^T & 1\end{bmatrix} \succeq 0$

Question

I would like to prove the claim in the title:

$X \succeq xx^T \iff \begin{bmatrix} X & x \\ x^T & 1\end{bmatrix} \succeq 0$

The book I am reading ("Convex Optimization" by Stephen Boyd and Lieven Vandenberghe) states that this can be proven using Schur complement, but I can not figure out the proof by myself.

Answer 1

I will write it here because the comments are too impractical. The big matrix is p.sd if and only if for any vector $y$ and scalar $c$ we have

$$\left(\begin{array}{c}y\\ c\end{array}\right)^T\left(\begin{array}{cc}X & x\\ x^T& 1\end{array}\right)^T\left(\begin{array}{c}y\\ c\end{array}\right)\geq 0.$$

This is equivalent to

$$\sum_{ij}X_{ij}y_iy_j+2c\sum_ix_iy_i+c^2\geq 0.$$

If you look at it as a quadratic function of $c$, it is always nonnegative iff its discriminant is nonpositive, that is

$$4((\sum_ix_iy_i)^2-\sum_{ij}X_{ij}y_iy_j)\leq 0$$

and that in turn is equivalent to

$$y^T(X-xx^T)y\geq 0.$$

Answer 2

Let's prove it using the Schur complement, but in detail.

We compute $$ \underbrace{\pmatrix{I&-x\\0&1}\pmatrix{X & x\\x^T & 1}}\pmatrix{I&-x\\0&1}^T =\\ \pmatrix{X - xx^T & 0\\x^T & 1} \pmatrix{I&0\\-x^T&1} = \\ \pmatrix{X - xx^T& 0\\0& 1} $$ Thus, the matrix $\pmatrix{X & x\\x^T & 1}$ is positive semidefinite if and only if the matrix $\pmatrix{X - xx^T& 0\\0& 1}$ is positive semidefinite, which is true if and only if $X - xx^T \succeq 0$.