Let $x \in \mathbb{R}^n$ be a unit vector, i.e., $\|x\|=1$. Show that the following matrix $A$ has at most one negative eigenvalue:
$$A:=(I-xx^\top)(I-3 \mathrm{Diag}(xx^\top))(I-xx^\top).$$
$\mathrm{Diag}(xx^\top)$ is the diagonal matrix whose $i$-th diagonal entry is $x_i^2$. ($\mathrm{Diag}$ extracts the diagonal of a matrix.)
Some of my thoughts/attempts:
- The inner matrix $I-3 \mathrm{Diag}(xx^\top)$ clearly has at most 2 negative eigenvalues, as $\|x\|^2=1$.
- The matrix $(I-xx^\top)$ is of course the orthogonal projector to the orthogonal complement of $x$. So we can add anything of the form $z x^\top + x z^\top$ to the inner matrix without changing $A$.
- I believe it suffices to show that there is some $y \in \mathbb{R}^n$ such that $A + y y^\top \succeq 0$ — see this MSE post. So it suffices to show that there exists a $y$ such that
$$z^\top (I-3 \mathrm{Diag}(xx^\top) + y y^\top) z \geq 0$$
for all $z$ orthogonal to $x$. - Maybe we can somehow appeal to Sylvester's law of inertia — also not clear though.
Best Answer
The claim in question is true. In the below, let $P=I-xx^T$ and $D=\operatorname{diag}(x_1^2,\ldots,x_n^2)$.
Lemma. Assume that $$ x\in\mathbb R^n,\quad\|x\|_2=1\quad\text{and}\quad x_1^2\ge x_2^2>\frac13> x_3^2\ge\cdots\ge x_n^2.\tag{$\ast$} $$ Then $x^T(I-3D)^{-1}x^T<0$.
Proof of the lemma. Let $s=\frac{1}{2}(x_1^2+x_2^2)$. Then $s>\frac13$. For each $i\ge3$, we have $1-3x_i^2\ge1-3(x_3^2+\cdots+x_n^2)=1-3(1-2s)=2(3s-1)>0$. Since $t\mapsto\frac{t}{1-3t}$ is concave on $(\frac13,1]$, we obtain $$ \begin{aligned} x^T(I-3D)^{-1}x^T =\sum_{i=1}^n\frac{x_i^2}{1-3x_i^2} &\le\frac{2s}{1-3s}+\sum_{i=3}^n\frac{x_i^2}{2(3s-1)}\\ &=\frac{2s}{1-3s}+\frac{1-2s}{2(3s-1)} =\frac{1-6s}{2(3s-1)}<0.\\ \end{aligned} $$
Proof of the claim in question. $I-3D$ can have at most two negative diagonal elements. If it has none or one, clearly $A$ has at most one negative eigenvalue. Now suppose that $I-3D$ has two negative diagonal elements. By a continuity argument, it suffices to prove the OP’s claim when $x_i^2\notin\{0,\frac13\}$ for every $i$, so that $x$ is entrywise nonzero and $I-3D$ is invertible. By relabelling the indices, we may further make the assumption $(\ast)$ stated in the lemma above.
Observe that for any negative eigenvalue $\lambda$ of $A$, if $y$ is a corresponding eigenvector, we must have $y\perp x$, because $x$ is an eigenvector of $A$ corresponding to a different eigenvalue (namely, zero). Therefore $\lambda y=Ay=P(I-3D)Py=P(I-3D)y$, meaning that $(I-3D)y=\lambda y+cx$ for some $c\in\mathbb R$, i.e., $$ (-\lambda+1-3D)y=cx\tag{1} $$ (where $-\lambda+1-3D$ means $(-\lambda+1)I-3D$, of course).
We now consider two cases:
Since $x_1=x_2$ in case 1 and $x_1\ne x_2$ in case 2, the two cases cannot both happen. In either case, $\lambda$ is simple and its value is uniquely determined. Therefore $A$ has at most one negative eigenvalue, counting multiplicity.