# Prove that $X$ is PSD $\iff$ the principal submatrix of $X$ with all maximally linearly independent columns (and corresponding rows) left is PD.

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.

• another snazzy way to show $\bar{X} \text{ is PD} \longrightarrow X \text{ is PSD}$ is via Cauchy Eigenvalue Interlacing... Mar 6 '20 at 21:13

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.