Let $\lambda \in \mathbb C, \ell \in \mathbb R, x \in \mathbb C^{n},$ and $$\mathcal H=\begin{pmatrix}\lambda I_n & x\\ x^{\ast} &\ell\end{pmatrix}.$$ Prove that $\lambda$ is an eigenvalue of $\mathcal H$ with multiplicity at least $n − 1$. What are the other two eigenvalues?
Attempt: I tried to use Cauchy Interlacing Theorem but I'm getting nowhere. Any hint and help would be much appreciated!
The Cauchy interlacing theorem is exactly the right way to go. In this case, the theorem guarantees that the eigenvalues $\lambda_1 \leq \cdots \leq \lambda_{n+1}$ of $\mathcal H$ satisfy $$ \lambda_1 \leq \lambda \leq \lambda_2 \leq \lambda \leq \cdots \leq \lambda \leq \lambda_n \leq \lambda \leq \lambda_{n+1}, $$ which implies that we have $\lambda_2 = \cdots = \lambda_n = \lambda$.
Now, the only step left is to compute the other two eigenvalues. One way to do this is as follows: it is equivalent to consider the eigenvalues of the matrix $$ A = \mathcal H - \lambda I_{n+1} = \pmatrix{0&x\\ x^* & \ell - \lambda}. $$ Note that $\mu$ is an eigenvalue of $A$ if and only if $\mu + \lambda$ is an eigenvalue of $\mathcal H$. Notably, $A$ is a rank-2 matrix. With that in mind, there are two nice strategies that you can use here to compute the non-zero eigenvalues:
Option 1: Calculate $\operatorname{tr}(A)$ and $\operatorname{tr}(A^2)$, then use the relationship between the trace of a matrix and the matrix's eigenvalues to solve for the two non-zero eigenvalues of $A$. We find that $$ \operatorname{tr}(A) = \ell - \lambda, \quad \operatorname{tr}(A^2) = (\ell - \lambda)^2 + 2\|x\|^2. $$
Option 2: Compute a "rank-factorization" $A = BC$, i.e. a factorization in which $B,C$ have sizes $(n+1) \times 2, 2 \times (n + 1)$. Then, note that the non-zero eigenvalues of $A$ are equal to the non-zero eigenvalues of the $2 \times 2$ matrix $CB$. One such factorization is given by $$ B = \pmatrix{x & 0\\0 & 1}, \quad C = \pmatrix{0_{1 \times n} & 1\\ x^* & \ell - \lambda}. $$