I'm trying to find a snazzy proof of the following theorem:
Let $B \subseteq \{1,\dots n\}$ be a set of indices corresponding to a maximal linearly independent set of columns of $X$. Let $\tilde{X}$ be the principal submatrix of $X$ with rows and columns given by $B$. Prove that $X$ is positive semidefinite if and only if $\tilde{X}$ is positive definite.
I'm not sure what theory I should use because I don't seem to have any theorems that clearly apply to this except that all principal minors of a PSD matrix are positive.
Best Answer
One approach of arguable snazziness is as follows. The $\implies$ direction is straightforward. For the $\Longleftarrow$ direction, suppose without loss of generality that $X$ is symmetric and that $\tilde X$ is the leading $r \times r$ principal submatrix. We have $$ X = \pmatrix{\tilde X&B\\B^T&C}. $$ We note that $X$ is positive semidefinite if both $\tilde X$ and $X/\tilde X$ are positive semidefinite, where $X/\tilde X$ is the Schur complement. That is, $$ X/\tilde X = C - B^T \tilde X^{-1}B. $$ On the other hand, the rank of $X$ must be $r$, so we have $$ r = \operatorname{rank}(X) = \operatorname{rank}(\tilde X) + \operatorname{rank}(X/\tilde X) = r + \operatorname{rank}(X/\tilde X). $$ Thus, $X/\tilde X = 0$, which means that $X/\tilde X$ is positive semidefinite. We conclude that $X$ is indeed positive semidefinite.
The $\implies$ direction in detail: suppose without loss of generality that the first $r$ columns of $X$ form the maximal linearly independent set in question. That is, $Xv \neq 0$ for all $v$ in the span of $\{e_1,\dots,e_r\}$ (where $e_j$ is the $j$th canonical basis vector). It follows that $v^TXv \neq 0$ for all $v$ in the span of $\{e_1,\dots,e_r\}$. From this, we conclude that the leading $r \times r$ submatrix $\tilde X$ is positive definite, as desired.