# How to extract a positive definite submatrix from a PSD matrix?

Let $$M$$ be a real symmetric positive semi-definite matrix s.t. there is only one zero eigenvalue.

Question: Is it true that there is a unique principal submatrix that is positive definite? If so, how to determine this submatrix?

First trial: Let the eigenvector corresponding to the zero eigenvalue be $$v$$. We can represent $$M$$ as $$$$M=Q'DQ,\tag{*}$$$$ where $$Q'Q=I$$ and $$D$$ is a diagonal matrix. Suppose for certainty that the last element of D is equal to $$0$$, i.e., $$d_{nn}=0$$. This means that the last column of $$Q$$ is equal to $$v$$.

Now let's write $$D=\begin{bmatrix}D_1& 0\\0& 0\end{bmatrix}$$ and $$Q=\begin{bmatrix}\tilde Q& q_1\\q_2'& x\end{bmatrix}$$, where $$D_1$$ is a PD diagonal matrix, $$\tilde Q$$ is an $$[n-1,n-1]$$ matrix, $$q_1$$ and $$q_2$$ are vectors, and $$x$$ is a scalar.

With this, we rewrite (*) as $$M=\begin{bmatrix}\tilde Q'& q_2\\q_1'& x\end{bmatrix}\begin{bmatrix}D_1& 0\\0& 0\end{bmatrix}\begin{bmatrix}\tilde Q& q_1\\q_2'& x\end{bmatrix}= \begin{bmatrix}\tilde Q'D_1& 0\\q_1'D_1& 0\end{bmatrix}\begin{bmatrix}\tilde Q& q_1\\q_2'& x\end{bmatrix}= \begin{bmatrix}\tilde Q'D_1\tilde Q& \tilde Q'D_1q_1\\q_1'D_1\tilde Q& q_1'D_1q_1\end{bmatrix}$$

Here, $$\tilde Q'D_1\tilde Q$$ is the $$(n,n)$$-principal submatrix of $$M$$, which is positive definite if $$\tilde Q$$ is non-singular. Thus the problem boils down to deternining non-singular principal submatrices of $$Q$$. However, I'm not sure is this makes the problem any simpler..

Solution (?): The number of PD principal submatrices id equal to the number of non-zero elements in the eigenvector $$v$$. If $$v_i\neq 0$$, $$M[i]$$ is PD.

I will post the proof in a day or so.

• You can extract principal submatrices using "elimination matrices" – Bertrand Jan 11 at 14:54
• @Bertrand, I know how to extract submatrices. The question is rather which one is to extract? – Dmitry Jan 11 at 15:02

Here is a counter-example to your conjecture: the matrix $$M=\left( \begin{array}{rrr} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{array} \right)$$ is positive semi-definite and has rank $$2$$, but any matrix extracted by eliminating the $$i^{th}$$ row and column is positive definite.
• You are right. I've already recognized that. Please see the last lines in my answer. There, $v$ is the eigenvector corresponding to the zero eigenvalue. That result agrees with your observation: $v=[1,1,1]$ hence, all principal submatrices will be PD. – Dmitry Jan 28 at 11:46
Lemma. Let $$S$$ be an $$n \times n$$ symmetric matrix that satisfies $$Sp = 0$$, where $$p \ne 0$$, and let $$\tilde{S}$$ be an $$(n-1) \times (n-1)$$ matrix obtained from $$S$$ by deleting any one row and the corresponding column. Then a necessary and sufficient condition for $$S$$ to be negative semidefinite is that $$\tilde{S}$$ is negative semidefinite.
• Shouldn't it read: "... is that $\tilde S$ is negative definite"? Otherwise I'm not sure that this statement is true. Anyway, this does not solve my problem. – Dmitry Jan 11 at 15:17
• It is negative semidefinite, and not negative definite. The reason is clear in the proof. The lemma does not apply to diagonal matrices, as diagonal matrices do not satisfy $Sp = 0$ for $p \ne 0$. – Bertrand Jan 11 at 16:38