How can I get a full rank symmetric submatrix of a symmetric matrix?

Question

Suppose $A= [a_{i,j}]$ is an $n \times n$ symmetric matrix with real entries such that it has precisely $m$ non-zero eigenvalues. I was thinking that it must be possible to pick $i_1, ..., i_m$ so that the $m \times m$ matrix $[a_{i_a,i_b}]$ is invertible (and all non-zero eigenvalues). I would appreciate if someone could show me how I can prove this. Thank you.

Answer 1

You may prove this by mathematical induction on the size of $A$. The base case where $n=1$ is trivial. In the inductive step, if $m=n$ (i.e. if $A$ is nonsingular), we simply choose the index set $\{1,2,\ldots,n\}$. If $m<n$ (i.e. $A$ is singular), some row of $A$ is a linear combination of the other rows. Without loss of generality, we may assume that the last row of $A$ is a linear combination of the first $n-1$ rows. Thus $\pmatrix{v^T&1}A=0$ for some $v\in\mathbb R^{n-1}$. Now let $$ A=\pmatrix{X&y\\ y^T&z},\ P=\pmatrix{I&v\\ 0&1} $$ where $A$ and $P$ have conforming partitions. Since $\pmatrix{v^T&1}A=0$, we have $v^TX+y^T=0$ and $v^Ty+z=0$. In turn, we also have $Xv+y=0$. It follows that $$ P^TAP =\pmatrix{I&0\\ v^T&1}\pmatrix{X&y\\ y^T&z}\pmatrix{I&v\\ 0&1} =\pmatrix{X&y\\ 0&0}\pmatrix{I&v\\ 0&1} =\pmatrix{X&0\\ 0&0}. $$ As $P$ is nonsingular, $m=\operatorname{rank}(A)=\operatorname{rank}(P^TAP)=\operatorname{rank}(X)$. Therefore, by induction assumption, $X$ has a nonsingular $m\times m$ principal submatrix. Now the result follows, because each principal submatrix is also a principal submatrix of $A$.