2
$\begingroup$

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.

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

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.

$\endgroup$
3
  • $\begingroup$ fantastic! thank you! $\endgroup$
    – Britta
    Mar 6 '20 at 11:46
  • $\begingroup$ also, snazziness is sufficiently on point! $\endgroup$
    – Britta
    Mar 6 '20 at 12:00
  • 1
    $\begingroup$ @Britta You're welcome, and glad to hear it! $\endgroup$ Mar 6 '20 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.