Prove that the matrix $(I-xx^\top)(I-3 \mathrm{Diag}(xx^\top))(I-xx^\top)$ has at most one negative eigenvalue, for $x$ a unit vector

Question

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:

1. The inner matrix $I-3 \mathrm{Diag}(xx^\top)$ clearly has at most 2 negative eigenvalues, as $\|x\|^2=1$.
2. 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$.
3. 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$.
4. Maybe we can somehow appeal to Sylvester's law of inertia -- also not clear though.

Answer 1

This is not a complete answer, but a sketch. (Thanks to @BenGrossmann for suggesting to look at the trace of $A$.)

We have $$tr(A) = tr(A(I-xx^\top)) = tr(I-xx^\top - 3\mathrm{Diag}(xx^\top) + 3 \mathrm{Diag}(xx^\top) x x^\top ) \\= n-4 + 3 x^\top \mathrm{Diag}(xx^\top) x.$$ Assume for contradiction that at at least two of the eigenvalues of $A$ are negative. We know that one eigenvalue of $A$ is zero, so we conclude that the largest $n-3$ eigenvalues of $A$ are strictly bigger than $tr(A)$.

As $B := I - 3\mathrm{Diag}(x x^\top)$ dominates $A$, we know that the eigenvalues of $B$ are at least as big as those of $A$ (see for example here). We conclude $$n-4 + 3 x^\top \mathrm{Diag}(xx^\top) x = tr(A) <\sum_{\ell=1}^{n-3} \lambda_{\ell}(B) = \sum_{\ell=1}^{n-3} \lambda_{\ell}(I - 3\mathrm{Diag}(x x^\top)) = n - 3 - 3S$$ where $S$ is the sum of the smallest $n-3$ entries of $(x_1^2, x_2^2, ..., x_n^2)$. Rearranging this gives $$x_1^4+x_2^2+...+x_n^4 + S= x^\top \mathrm{Diag}(xx^\top) x + S < 1/3.$$

On the other hand, it seems that $x^\top \mathrm{Diag}(xx^\top) x + S \geq 1/3$, which would give a contradiction. Indeed, one should be able to check that the minimum of $$\min a_1^2+ ... + a_n^2 + a_1 + ... +a_{n-3} \text{ subject to } a_1 + ... + a_n = 1 \text{ and } 0\leq a_1 \leq a_2 \leq ... \leq a_n$$ equals $1/3$ by writing out the KKT conditions (this is a convex optimization problem). (Note here I made a change of variables $a_i := x_i^2$ and WLOG assumed the $a_i$ are ordered.) I didn't do this explicitly, but Mathematica seems to confirm that the minimum of this problem is $1/3$, attained at $$a_1=...=a_{n-3}=0, a_{n-2}=a_{n-1}=a_n.$$

Answer 2

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:

1. $A$ has a negative eigenvalue $\lambda\in\left\{1-3x_1^2,\ 1-3x_2^2\right\}$. Then $-\lambda+1-3D$ has a zero diagonal element. Since $x$ is entrywise nonzero, $(1)$ shows that $c=0$ and in turn, $(-\lambda+1-3D)y=0$. However, the third up to the last diagonal elements of $-\lambda+1-3D$ are positive. Therefore $y_3=\cdots=y_n=0$. Since $x$ is entrywise nonzero and $x\perp y$, we see that $y$ is necessarily parallel to $(-x_2,x_1,0,\ldots,0)^T$, i.e., $\lambda$ is a simple eigenvalue. Moreover, since $(-\lambda+1-3D)y=0$ and $x\perp y$, we have $(I-3D)y=\lambda y$ and $$ 0=x^T(\lambda y)=x^T\left((I-3D)y\right)=-3x^TDy. $$ Hence $0=x^TD(-x_2,x_1,0,\ldots,0)^T=-x_1^3x_2+x_2^3x_1$. Since both $x_1$ and $x_2$ are negative, we must have $x_1=x_2$. Therefore the value of $\lambda$ is uniquely determined (as $1-3x_1^2$).
2. $A$ has a negative eigenvalue $\lambda\not\in\left\{1-3x_1^2,\ 1-3x_2^2\right\}$. Then $-\lambda+1-3D$ is nonsingular. It follows that $c\ne0$ in $(1)$ and $y=c(-\lambda+1-3D)^{-1}x$. In turn, $x^T(-\lambda+1-3D)^{-1}x=\frac{1}{c}x^Ty=0$, i.e. $-\lambda$ is a zero of the function $g:[0,\infty)\to\mathbb R$ defined by $$ g(t)=x^T(t+1-3D)^{-1}x=\sum_{i=1}^n\frac{x_i^2}{t+1+3x_i^2}. $$ By our lemma, we have $g(0)<0$. Also, for each $i$, the graph of $t\mapsto\frac{x_i^2}{t+1+3x_i^2}$ is a hyperbola. If we superimpose these graphs one on the other to obtain a graph of $g$, we see that $g$ has no zero when $x_1=x_2$ and it has a unique zero when $x_1\ne x_2$. Therefore $x_1\ne x_2$ and the value of $\lambda$ is uniquely determined. In addition, $(1)$ shows that the eigenspace for $\lambda$ is one-dimensional and is spanned by $(-\lambda+1-3D)^{-1}x$. Hence $\lambda$ is a simple eigenvalue.

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.