Prove or disprove a matrix inequality (positive semidefinite)

Question

I want to prove or find a counterexample that there exist constants $\mu>0, \rho>0$ such that the following inequality holds: \begin{align} (H + \mu M)^2 \succeq \rho M^2, \end{align} where $\mu>0, \rho>0$ are constants to be chosen, $H\in \mathbb{R}^{n\times n}$ is a fixed symmetric matrix with bounded eigenvalues $\lVert H\rVert\le \ell$, $M = I_n - Z \in \mathbb{R}^{n\times n}$ with $Z = \mathbb{1}_n\mathbb{1}_n^\top/n\in \mathbb{R}^{n\times n}$, $\mathbb{1}_n = (1, \dotsc, 1)^\top\in \mathbb{R}^{n}$, and $A \succeq B$ means that $A-B\succeq 0$ is a positive semidefinite matrix.

The matrix $M$ has some properties that might be helpful: (a) $M^2 = M$, (b) the eigenvalues of $M$ are $\lambda =1$ with multiplicity $n-1$ and $\lambda =0 $ with multiplicity $1$, (c) $M\mathbb{1}_n=0$.

Answer 1

This is true. Change coordinates so that $M$ is the projection to first $n-1$ coordinates: $Me_n=0$, $Me_i=e_i$ for $i<n$.

If $He_n=0$, then $H,M$ both have the same invariant orthogonal decomposition $e_n\oplus e_n^{\perp}$, they vanish on the first component and $M$ acts as ${\rm Id}$ on the second component, so large $\mu$ and $\rho=1$ work.

If $He_n\ne 0$, I claim that $H+\mu M$ is non-singular for certain $\mu$, and for such $\mu$ the appropriate $\rho$ of course exists. For proving this, we expand $\det(H+\mu M)$ as a polynomial in $\mu$. The coefficient of $\mu^{n-1}$ equals $H(n,n)$ (corresponding matrix element) and the coefficient of $\mu^{n-2}$ equals $-\sum_{k=1}^{n-1} H(k,n)^2+H(n,n)\times \text{something}$. At least one of these two coefficients is non-zero, thus the value of the determinant is non-zero for certain $\mu$.

Below goes the (negative) answer fo the uniform-in-$H$ version.

Let $n=2$. We change the coordinates so that $M=\begin{pmatrix}1&0\\0&0\end{pmatrix}$. Choose $H=\begin{pmatrix}1&1\\1&\frac1{1+\mu}\end{pmatrix}$ (such matrices are uniformly bounded for $\mu>0$, so your $\ell$ exists). Then $H+\mu M$ has a zero eigenvalue with an eigenvector $\begin{pmatrix}1\\-1-\mu\end{pmatrix}$ which is not an eigenvector of $M$. So the inequality $(H + \mu M)^2 \succeq \rho M^2$ does not hold for no $\rho$.