Relationship between rank and positive semidefiniteness

Question

I am reading this paper$^\color{magenta}{\dagger}$ on solving minimum rank problems. On page 475, the authors state the following:

The rank of a block symmetric matrix is equal to the rank of a diagonal block plus the rank of its Schur complement (see, e.g., [Horn and Johnson, Matrix Analysis, section 2.2]). Given a function $f$ that maps matrices into $q \times q$ symmetric matrices, the condition that $f(X)$ is positive semidefinite can be equivalently expressed through a rank constraint as $$ f(X) \succeq 0 \iff \operatorname{rank}\begin{pmatrix} I_q & B \\ B' & f(X) \end{pmatrix} \leq q $$ for some $B \in \mathbb{R}^{q\times q}$. That is, if there exists a matrix $B$ satisfying the inequality above, then $f(X) = B'B \succeq 0$.

---

My questions are:

1. I don't have Horn and Johnson's book, so I would appreciate if someone could point me to the proof of this statement.

2. Assuming the statement about ranks is true, how does this translate to the relationship between $f(X) \succeq 0 $ and the rank of the block matrix ?

3. And, assuming 2) to be true, how does the author get $f(X) = B'B$, ie the Schur complement of the block matrix ?

---

$\color{magenta}{\dagger}$ Benjamin Recht, Maryam Fazel, Pablo A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, Volume 52, Issue 3, 2010.

Answer 1

1. Consider a block matrix $$ M=\left[\matrix{A & B\\C & D}\right] $$ and assume $A$ is invertible. Then we can block-diagonalize $M$ as $$ \underbrace{\left[\matrix{I & 0\\-CA^{-1} & I}\right]}_{L}\left[\matrix{A & B\\C & D}\right] \underbrace{\left[\matrix{I & -A^{-1}B\\0 & I}\right]}_{R}=\left[\matrix{A & 0\\0 & M/A}\right] $$ where $M/A=D-CA^{-1}B$ is the Schur complement (wrt $A$). Since the transformation matrices $L$ and $R$ are invertible, we have $\text{rank}(M)=\text{rank}(LMR)$, and the statement follows.

2. Using the result above for the matrix $$ M_f=\left[ \matrix{ I_q & B \\ B^T & f(X) } \right] $$ we get $\text{rank}M_q=\underbrace{\text{rank}I_q}_{=q}+\text{rank}(f(X)-B^TB)= q+\text{rank}(f(X)-B^TB)\ge q$. To have $\text{rank}M_f\le q$ is possible iff $\text{rank}(f(X)-B^TB)=0$ iff $f(X)-B^TB=0$ (the zero matrix).

3. Clear from 2.