Eigenvalues of principal minors Vs. eigenvalues of the matrix

Say I have a positive semi-definite matrix with least positive eigenvalue x. Are there always principal minors of this matrix with eigenvalue less than x?

(Here "semidefinite" can not be taken to include the case "definite" -- there should be a zero eigenvalue.)

-

A counterexample (to the unedited question): $$A = \begin{pmatrix}1+x&1\\\1&1+x\end{pmatrix}.$$ Eigenvalues of $A$ are $2+x$ and $x$, principal minors have one eigenvalue $1+x$.

Voting to close.

-
The poster clearly left out the condition that the matrix should be semidefinite and not definite (or else the interlacing inequalities make the condition impossible). – Allen Knutson Mar 5 '13 at 2:25

No, it is not true; Consider the matrix

$$A= \begin{pmatrix} \frac{9}{2} & \frac{9}{20} & \frac{21}{20} & -\frac{3}{2}\\ -\frac{79}{11} & -\frac{3}{110} & \frac{23}{110} & \frac{31}{11}\\ \frac{6}{11} & \frac{21}{55} & \frac{114}{55} & \frac{6}{11}\\ \frac{16}{11} & \frac{12}{55} & \frac{128}{55} & \frac{5}{11} \end{pmatrix}$$ which has eigenvalues 0,1,2,3 (so it is positive semi-definite, but not definite.) The four principal minors are $$\frac{27}{22},\frac{189}{110},\frac{153}{55},\frac{36}{11}$$ sorted in increasing order. This should give a definite negative answer to your question.

-
On the other hand, if the matrix is assumed to be real symmetric (or Hermitian), the claim is true (because one can find a linear combination of the two eigenvectors corresponding to zero and the least positive eigenvalue respectively which are supported on only n-1 of the n coordinates). It may be that this is another hypothesis that was omitted by the OP. – Terry Tao Mar 5 '13 at 16:40
Terry Tao: Right, that is a possibility, but I can see why the poster believed that the current version was true; I did some quick numerics (that is how I got the example), and the counterexamples are quite rare, (with appropriate definition on "rare"). – Per Alexandersson Mar 5 '13 at 17:26

Say the matrix $S$ has unitary orthonormal eigenvectors $u_1,u_2,\dots u_n$ with eigenvalues $$\lambda_1\leq \lambda_2\leq \dots \leq \lambda_{n-1}\leq \lambda_n$$ I think the smallest (resp. largest) eigenvalue of a principal minor is $\leq \lambda_2$ (resp. strictly $\geq \lambda_{n-1}$).

A sufficient condition for this is to have ortho-normal eigenvectors in $S$ and in its minors (true in a positive definite world with symmetric matrices).

For any chosen coordinate $i$, the idea is to consider a linear combination of $v=au_1+bu_2$ such that $v_i=0$ as suggested above (if I understood well the comment of T. Tao). I think one can prove that $\frac{|Sv|}{|v|}\in [\lambda_1,\lambda_2]$, where $|v|^2=a^2+b^2$ (to verify it, write $Sv=a\lambda_1 u_1+b\lambda_2 u2$ and observe $|Sv|^2= \lambda_1^2a^2 + \lambda_2^2b^2$. In other words, the multiplication by $S$ ''stretches'' $v$ by something between $\lambda_1$ and $\lambda_2$. Now, we can see how the minor $S^i$ ($S$ without line and column $i$) acts on $v^i$ ($v$ without position $i$). Column $i$ does nothing to $v$ in the calculation of $Sv$, and so, $S^iv^i$ is the same as vector $Sv$ but without the (non-zero) value of $Sv$ at coordinate $i$. By forgetting this coordinate, $S^iv^i$ has an even smaller 2-norm than $Sv$. Vector $v^i$ is stretched'' via the $S^i$ multiplication by something $\leq \lambda_2$. As such, $S^i$ can not have all eigenvalues larger than $\lambda_2$, this would mean that it ''stretches'' any $(n-1)-$dimensional vector (including $v^i$) by more than $\lambda_2$.

Finally, the inequalities are not strict because $a$ or $b$ above can be zero. The very basic matrix $\begin{pmatrix} 1 & 0 \\ 0 & 0 \\ \end{pmatrix}$ has eigenvalues 0 and 1 but the right-left minor has eigenvalue 1.

-