How the principal submatrix of a PSD matrix could be positive definite?

Question

Assuming $A \in R^{n \times n}$ and is PSD and hermitian, so it has $k$ non-zero eigenvalues and $k<n$. Also its entries are all non-zero values.

Then i create $B$ as the principal submatrix of $A$ obtained by selecting same rows and columns of $A$ indicated by $I$, a subset of $\{1,2,...n\}$.

I noticed for a wide range of random matrices of $A$, as long as having $size(I)<k$ the resulted $B$ will be positive-definite meaning it has only positive eigenvalues. To generate $A$ i chose each entry as a random number in the range [-100 100] and doing $A^T*A$ and afterwards making some of the eigenvalues equal to zero using eigenvalue decomposition of $A$.

So although it is possible to create specific matrices $A$ which don't obey the above rule, i think there should be some pre-conditions on $A$ to let the above happens! and i like to find the mathematical way to explain that!

Answer 1

It is not true.

Let $A = \begin{bmatrix}1 & 0 \\ 0 & 0 \end{bmatrix}$, then $k=1$, $n=2$.

Let $I=\{2\}$, then $B=0$ which is not positive definite.

Edit:

Let $A = \begin{bmatrix} 8 & 0.1 & 0.1 & 0.1 \\ 0.1 & 6 & 0.1 & 0.1 \\ 0.1 & 0.1 & 0.1 & 0.1 \\ 0.1 & 0.1 & 0.1 & 0.1\end{bmatrix}$. It has $k=3$ non-zero eigenvalues. Let $I = \{ 3,4\}$, the matrix $B$ is singular.

Answer 2

Two facts :

1) By the Cauchy interlacing theorem, the eigenvalues of any principal submatrix $((n-1) \times (n-1))$ $B$ of a Hermitian matrix $(n \times n)$ $A$ interlace those of $A$ (obtained by deleting a single row and a single column, with the same index). It means that if we are with a matrix $A$, the smallest eigenvalue of $B$ is $\geq$ to the smallest eigenvalue of initial matrix $A$. Continuing in this way, by an immediate recurrence, the smallest eigenvalue of a matrix of the type you consider (deleting the same $p$ rows and $p$ columns) will generate a smallest eigenvalue $\geq$ to the smallest eigenvalue of initial matrix $A$.

2) the determinant is the product of eigenvalues ; having no eigenvalue equal to $0$ is equivalent to $\det(A)\neq 0$.

Thus, as a consequence of 1) and 2), we just have to prove that :

$$\text{measure}(\{A \ | \ \det(A)\neq 0\})=1$$

(replace "measure" with "probability" ; it is the same meaning).

But, seen in $\mathbb{R^{n \times n}}$, the set of all $A$ such that $\det(A)=0$ is a hypersurface, thus with measure equal to 0. That's all.

---

An example: consider

• the set $\frak{E}$ of $2 \times 2$ symmetric definite positive matrices

$$\begin{bmatrix}a & b\\ b & c \end{bmatrix}$$ (assimilable to $\mathbb{R}^3$) are defined by $a>0$ and $\det(A)=ac-b^2>0$.

• the set $\frak{F}$ of semi-definite positive matrices are defined by condition $\det(A)=ac-b^2=0$. It is the equation of a surface (which has a conical aspect, considered in $\mathbb{R}^3$).

$\frak{F}$ has measure 0 in $\frak{E}\cup\frak{F}$ (it is its frontier).

Look at the Matlab program below and its resulting image:

clear all;close all;hold on;
for k=1:2000;
   A=rand(2);A=A*A';
   S(:,k)=[A(1,1);A(2,1);A(2,2)];
end
plot3(S(1,:),S(2,:),S(3,:),'.b');
[a,c]=meshgrid(0:0.02:2,0:0.02:2);
surf(a,sqrt(a.*c),c,'edgecolor','none');alpha(0.3);
view([131,40])