Boyd & Vandenberghe, example 3.4 — question on Schur complements and LMIs

Question

In example 3.4 of Boyd & Vandenberghe's Convex Optimization, we have following inequality $$t-\mathbf{x^TY^{-1}x}\geq 0$$ which can be equivalently written in matrix form as follows $$\left[ {\begin{array}{cc} \mathbf{x^T} & 1 \\ \end{array} } \right]\left[ {\begin{array}{cc} \mathbf{-Y^{-1} ~~~~0\\ ~~~~0~~~~~~~~~~ t} \end{array} } \right]\left[ {\begin{array}{c} \mathbf{x} \\ 1 \\ \end{array} } \right] \geq 0$$ I want to know how this condition transforms into $$\left[ {\begin{array}{cc} \mathbf{Y} & \mathbf{x} \\ \mathbf{x^T} & t \\ \end{array} } \right]\succeq 0.$$Any help in this regard will be much appreciated. Thanks in advance.

Answer 1

I guess what you're looking for is a derivation of the Schur complement, or at least a proof that doesn't directly invoke it. So here we go. Let's assume that $Y$ is nonsingular. Then it is the case that $$\begin{bmatrix} Y & x \\ x^T & t \end{bmatrix} = \begin{bmatrix} I & 0 \\ x^T Y^{-1} & 1 \end{bmatrix} \begin{bmatrix} Y & 0 \\ 0 & t - x^TY^{-1} x \end{bmatrix} \begin{bmatrix} I & Y^{-1} x \\ 0 & 1 \end{bmatrix} $$ If you don't see that this is true, just multiply it out.

Now, for any symmetric $Q$ and any nonsingular $P$ of the same size, $Q\succeq 0$ if and only if $PQP^T\succeq 0$. Let's choose $$Q=\begin{bmatrix} Y & x \\ x^T & t \end{bmatrix} \quad P=\begin{bmatrix} I & 0 \\ x^TY^{-1} & 1 \end{bmatrix}^{-1}$$ Therefore, $$\begin{bmatrix} Y & x \\ x^T & t \end{bmatrix} \succeq 0 \quad\Longleftrightarrow\quad \begin{bmatrix} Y & 0 \\ 0 & t - x^T Y^{-1} x \end{bmatrix} \succeq 0 \quad\Longleftrightarrow\quad Y\succ 0, ~ t - x^TY^{-1}x \geq 0.$$ Note that the $(1,1)$ block of the second inequality implies only that $Y\succeq 0$. But combined with the assumption that $Y$ is nonsingular, implied by the presence of the inverse in the $(2,2)$ term, you get that $Y\succ 0$.