How to prove this result about the interlacing of eigenvalues.

Question

Let $A$ be a real symmetric matrix of order $n$ with eigenvalues $\mu_1\ge \mu_2,\ldots, \mu_{n}$. $B=\begin{bmatrix} x&x&x&x&x \end{bmatrix}$, where $x$ is non zero column vector in $R^n$. Construct a new matrix: $$C=\begin{bmatrix} A&B\\B^T &0 \end{bmatrix}$$ Removing four zeros of $C$ (due to identical columns) arrange the remaining eigenvalues as $\lambda_1\ge \lambda_2,\ldots, \lambda_{n+1}$.

How to show that $\lambda_i\ge\mu_i\ge\lambda_{i+1}$ for $i=1,2,\ldots,n$.

I know that removing $4$ identical columns, we are left with matrix of order $n+1$ and there this result hold due to interlacing. But eigenvalues of that matrix and of matrix $C$ are different. So , how can I conclude here?

Answer 1

You almost solved your problem. The only thing that you forgot to do was a change a basis.

Let $e_1,e_2,\ldots,e_{n+5}$ denote the canonical basis of ${\mathbb R}^{n+5}$. The identical columns in $C$ force the subspace $Z$ spanned by $e_{k}-e_{n+1} (n+2\leq k \leq n+5)$ to be included in the kernel of $C$. We construct an orthonormal basis in which $Z$ will be spanned by the last, rightmost vectors (so we can concentrate on the interesting leftmost part).

Formally, define a new basis $F=(f_1,f_2,\ldots,f_{n+5})$ by $f_k=e_k$ for $k\leq n$, and

$$ \begin{array}{lcl} f_{n+1} &=& \frac{e_{n+1}+e_{n+2}+e_{n+3}+e_{n+4}+e_{n+5}}{\sqrt{5}} \\ f_{n+2} &=& \frac{e_{n+1}+e_{n+2}+e_{n+3}+e_{n+4}-4e_{n+5}}{\sqrt{20}} \\ f_{n+3} &=& \frac{e_{n+1}+e_{n+2}+e_{n+3}-3e_{n+4}}{\sqrt{12}} \\ f_{n+4} &=& \frac{e_{n+1}+e_{n+2}-2e_{n+3}}{\sqrt{6}} \\ f_{n+5} &=& \frac{e_{n+1}-e_{n+2}}{\sqrt{2}} \\ \end{array} $$

Then $F$ is orthonormal. In this new basis, $A$ has not changed while $C$ has become

$$ C'=\begin{bmatrix} D&0\\0 &0 \end{bmatrix} $$

where $D$ is the $(n+1)\times(n+1)$ matrix

$$ D=\begin{bmatrix} A&\sqrt{5}x\\\sqrt{5}x &0 \end{bmatrix} $$

The eigenvalues of $D$ are exactly the $\lambda_1\ge \lambda_2,\ldots \geq \lambda_{n+1}$. Then the usual interlacing property you mention in your post applies.