17.4  Deleting a Row and a Column

Proof. The map $\phi$ is linear, being given by deleting a coordinate, and it is bijective from $H$ to $F^{n-1}$ because inserting $0$ in position $m$ inverts it. Write $I=\{i_1<\cdots <i_{n-1}\}$, so that $\phi (\mathbf{x}{)}_r=x_{i_r}$ and $(\mathbf{B}{)}_{rs}=a_{i_r{i}_s}$ by Definition 7.7.1.

Let $\mathbf{x}\in H$. Expanding the inner product of $F^n$, which is linear in the first slot and conjugate-linear in the second, $$⟨\mathbf{A}\mathbf{x},\mathbf{x}⟩=\sum _{p=1}^n\sum _{q=1}^n{a}_{pq}{x}_q\overline{x_p}.$$ Every term with $p=m$ or $q=m$ vanishes, because $x_m=0$. The remaining terms are indexed by $p,q\in I$, say $p=i_r$ and $q=i_s$, and there the summand is $a_{i_r{i}_s}\phi (\mathbf{x}{)}_s\overline{\phi (\mathbf{x}{)}_r}=(\mathbf{B}{)}_{rs}\phi (\mathbf{x}{)}_s\overline{\phi (\mathbf{x}{)}_r}$. Summing over $r,s$ gives $⟨\mathbf{B}\phi (\mathbf{x}),\phi (\mathbf{x})⟩$. The same deletion of a zero coordinate gives ${\Vert \mathbf{x}\Vert }^2=\sum _{p\ne m}|x_p{|}^2={\Vert \phi (\mathbf{x})\Vert }^2$. Dividing the first identity by the second, which is positive when $\mathbf{x}\ne \mathbf{0}$, gives the statement about the Rayleigh quotients (Definition 17.1.1). This proves the lemma.

Proof. Let $m$ be the index not in $I$, and let $H$ and $\phi$ be as in Lemma 17.4.1, so that $R_{\mathbf{A}}(\mathbf{x})=R_{\mathbf{B}}(\phi (\mathbf{x}))$ for every non-zero $\mathbf{x}\in H$. Both $\mathbf{A}$ and $\mathbf{B}$ are Hermitian, so Theorem 17.2.3 applies to each, to $\mathbf{A}$ with $n$ and to $\mathbf{B}$ with $n-1$ in the role of the size. Fix $k$ with $1\le k\le n-1$.

$({\lambda }_k(\mathbf{B})\le {\lambda }_k(\mathbf{A}))$ By the max–min form of Theorem 17.2.3 for $\mathbf{B}$, there is a subspace $W^{\prime }\le F^{n-1}$ with $\dim W^{\prime }=k$ and $${\lambda }_k(\mathbf{B})=\underset{\mathbf{0}\ne \mathbf{y}\in W^{\prime }}{min}{R}_{\mathbf{B}}(\mathbf{y}).$$ Put $W={\phi }^{-1}(W^{\prime })\le H\le F^n$. Since $\phi$ is an isomorphism, $\dim W=k$, and $\phi$ carries the non-zero vectors of $W$ onto the non-zero vectors of $W^{\prime }$, so $$\underset{\mathbf{0}\ne \mathbf{x}\in W}{min}{R}_{\mathbf{A}}(\mathbf{x})=\underset{\mathbf{0}\ne \mathbf{y}\in W^{\prime }}{min}{R}_{\mathbf{B}}(\mathbf{y})={\lambda }_k(\mathbf{B}).$$ Now $W$ is one of the $k$-dimensional subspaces of $F^n$ over which the max–min form for $\mathbf{A}$ takes its maximum, so ${\lambda }_k(\mathbf{A})\ge {\lambda }_k(\mathbf{B})$.

$({\lambda }_{k+1}(\mathbf{A})\le {\lambda }_k(\mathbf{B}))$ By the min–max form of Theorem 17.2.3 for $\mathbf{B}$, whose matrices have size $n-1$, there is a subspace $W^{\prime }\le F^{n-1}$ with $\dim W^{\prime }=(n-1)-k+1=n-k$ and $${\lambda }_k(\mathbf{B})=\underset{\mathbf{0}\ne \mathbf{y}\in W^{\prime }}{max}{R}_{\mathbf{B}}(\mathbf{y}).$$ Put $W={\phi }^{-1}(W^{\prime })\le F^n$, of dimension $n-k$. Since $1\le k+1\le n$ and $n-(k+1)+1=n-k=\dim W$, the subspace $W$ is admissible in the min–max form for ${\lambda }_{k+1}(\mathbf{A})$, and that form takes the minimum over all such subspaces. Hence $${\lambda }_{k+1}(\mathbf{A})\le \underset{\mathbf{0}\ne \mathbf{x}\in W}{max}{R}_{\mathbf{A}}(\mathbf{x})=\underset{\mathbf{0}\ne \mathbf{y}\in W^{\prime }}{max}{R}_{\mathbf{B}}(\mathbf{y})={\lambda }_k(\mathbf{B}).$$ This proves the theorem.

Proof. Induction on $m$. For $m=0$ we have $\mathbf{B}=\mathbf{A}$ and both inequalities are equalities.

Let $m\ge 1$ and suppose the statement holds for $m-1$, for every Hermitian matrix. Choose an index $j\notin I$ and put $I^{\prime }=I\cup \{j\}$, so $|I^{\prime }|=n-m+1$, and ${\mathbf{B}}^{\prime }={\mathbf{A}}_{I^{\prime },I^{\prime }}\in M_{n-m+1}(F)$, which is Hermitian. Since $I\subseteq I^{\prime }$, taking the principal submatrix on $I$ of ${\mathbf{B}}^{\prime }$ means keeping the rows and columns of $\mathbf{A}$ indexed by $I$, so $({\mathbf{B}}^{\prime }{)}_{I,I}=\mathbf{B}$ after relabeling the indices of $I$ inside $I^{\prime }$; and $|I|=|I^{\prime }|-1$.

Fix $i$ with $1\le i\le n-m$. By the inductive hypothesis applied to $\mathbf{A}$ and ${\mathbf{B}}^{\prime }$, $${\lambda }_i(\mathbf{A})\ge {\lambda }_i({\mathbf{B}}^{\prime })\ge {\lambda }_{i+m-1}(\mathbf{A}),$$ which is available because $i\le n-m<n-m+1$. By Theorem 17.4.2 applied to ${\mathbf{B}}^{\prime }$ and its principal submatrix $\mathbf{B}$, which is one size smaller, $${\lambda }_k({\mathbf{B}}^{\prime })\ge {\lambda }_k(\mathbf{B})\ge {\lambda }_{k+1}({\mathbf{B}}^{\prime })(1\le k\le n-m).$$ Combining, ${\lambda }_i(\mathbf{B})\le {\lambda }_i({\mathbf{B}}^{\prime })\le {\lambda }_i(\mathbf{A})$, which is the first inequality. For the second, take $k=i$ in the display above and then use the inductive hypothesis at the index $i+1$, legitimate since $i+1\le n-m+1$: $${\lambda }_i(\mathbf{B})\ge {\lambda }_{i+1}({\mathbf{B}}^{\prime })\ge {\lambda }_{(i+1)+m-1}(\mathbf{A})={\lambda }_{i+m}(\mathbf{A}).$$ This proves the corollary.

Proof. Step 1: diagonalize the corner. By the spectral theorem (Corollary 12.4.3 over $\mathbb{C}$, Corollary 12.5.2 over $\mathbb{R}$) write $\mathbf{B}=\mathbf{U}\mathbf{D}{\mathbf{U}}^{\ast }$ with $\mathbf{U}\in M_{n-1}(F)$ unitary and $\mathbf{D}=\mathrm{diag}({\mu }_1,\dots ,{\mu }_{n-1})$ carrying the eigenvalues of $\mathbf{B}$ in decreasing order, the columns ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_{n-1}$ of $\mathbf{U}$ being an orthonormal basis of eigenvectors. Let $\mathbf{V}=\left(\begin{array}{cc}\mathbf{U}& \mathbf{0}\\ {\mathbf{0}}^{\ast }& 1\end{array}\right)\in M_n(F)$, which is unitary because ${\mathbf{V}}^{\ast }\mathbf{V}={\mathbf{I}}_n$. Multiplying in blocks (Theorem 8.1.1) gives $${\mathbf{V}}^{\ast }\mathbf{A}\mathbf{V}=\left(\begin{array}{cc}\mathbf{D}& \tilde{\mathbf{b}}\\ {\tilde{\mathbf{b}}}^{\ast }& c\end{array}\right),\tilde{\mathbf{b}}={\mathbf{U}}^{\ast }\mathbf{b}.$$ Similar matrices have the same characteristic polynomial (Theorem 7.10.3), so we may compute with the right-hand side. Moreover ${\tilde{b}}_k=({\mathbf{U}}^{\ast }\mathbf{b}{)}_k=⟨\mathbf{b},{\mathbf{u}}_k⟩$, and the ${\mathbf{u}}_k$ with ${\mu }_k=\nu$ form an orthonormal basis of $E_{\nu }(\mathbf{B})$: they lie in it, and a vector $\mathbf{x}=\sum _k{c}_k{\mathbf{u}}_k$ with $\mathbf{B}\mathbf{x}=\nu \mathbf{x}$ has $({\mu }_k-\nu )c_k=0$ for every $k$, so $c_k=0$ unless ${\mu }_k=\nu$. Hence exactly $m_{\nu }$ of the ${\mu }_k$ equal $\nu$, and $$P_{\nu }\mathbf{b}=\sum _{k:{\mu }_k=\nu }⟨\mathbf{b},{\mathbf{u}}_k⟩{\mathbf{u}}_k\text{and}{\Vert P_{\nu }\mathbf{b}\Vert }^2=\sum _{k:{\mu }_k=\nu }|{\tilde{b}}_k{|}^2.$$ In particular $P_{\nu }\mathbf{b}=\mathbf{0}$ exactly when ${\tilde{b}}_k=0$ for every $k$ with ${\mu }_k=\nu$.

Step 2: the characteristic polynomial. We claim that, as polynomials in $x$,

Step 3: multiplicities. Let ${\nu }_1>\cdots >{\nu }_p$ be the distinct eigenvalues of $\mathbf{B}$, with multiplicities $m_1,\dots ,m_p$ summing to $n-1$, and put ${\beta }_t={\Vert P_{{\nu }_t}\mathbf{b}\Vert }^2$. Grouping equal ${\mu }_k$ in Eq. 17.4.1 — the product $\prod _{l\ne k}(x-{\mu }_l)$ is the same for all $k$ in one group, and the coefficients $|{\tilde{b}}_k{|}^2$ add up to ${\beta }_t$ by Step 1 — turns it into $$\begin{array}{rl}{p}_{\mathbf{A}}(x)& =(x-c)\prod _{t=1}^p(x-{\nu }_t{)}^{m_t}\\ & -\sum _{t=1}^p{\beta }_t(x-{\nu }_t{)}^{m_t-1}\prod _{s\ne t}(x-{\nu }_s{)}^{m_s}.\end{array}$$ Fix $t$. Every term on the right is divisible by $(x-{\nu }_t{)}^{m_t-1}$, so $p_{\mathbf{A}}(x)=(x-{\nu }_t{)}^{m_t-1}g(x)$ with $$\begin{array}{rl}g(x)& =(x-c)(x-{\nu }_t)\prod _{s\ne t}(x-{\nu }_s{)}^{m_s}-{\beta }_t\prod _{s\ne t}(x-{\nu }_s{)}^{m_s}\\ & -\sum _{u\ne t}{\beta }_u(x-{\nu }_t)(x-{\nu }_u{)}^{m_u-1}\prod _{s\ne u,t}(x-{\nu }_s{)}^{m_s}.\end{array}$$ Evaluate at $x={\nu }_t$. The first term vanishes because of its factor $(x-{\nu }_t)$, and so does every summand of the third, for the same reason. What is left is $$g({\nu }_t)=-{\beta }_t\prod _{s\ne t}({\nu }_t-{\nu }_s{)}^{m_s},$$ and the product is non-zero because the ${\nu }_s$ are distinct. So $g({\nu }_t)\ne 0$ exactly when ${\beta }_t\ne 0$, that is, exactly when $P_{{\nu }_t}\mathbf{b}\ne \mathbf{0}$. In that case ${\nu }_t$ is a root of $p_{\mathbf{A}}$ of multiplicity exactly $m_t-1$, which proves (a); in the other case $(x-{\nu }_t)$ divides $g$, so the multiplicity is at least $m_t$, which proves (b).

Step 4: strictness. $(\Leftarrow )$ Suppose $\mathbf{B}$ has $n-1$ distinct eigenvalues, so every $m_t=1$, and $P_{\nu }\mathbf{b}\ne \mathbf{0}$ for each of them. By (a), no eigenvalue of $\mathbf{B}$ is an eigenvalue of $\mathbf{A}$. Theorem 17.4.2 gives ${\lambda }_k(\mathbf{A})\ge {\lambda }_k(\mathbf{B})\ge {\lambda }_{k+1}(\mathbf{A})$ for each $k$; since ${\lambda }_k(\mathbf{B})$ is an eigenvalue of $\mathbf{B}$ and ${\lambda }_k(\mathbf{A})$, ${\lambda }_{k+1}(\mathbf{A})$ are eigenvalues of $\mathbf{A}$, neither inequality can be an equality. So all $2(n-1)$ of them are strict.

$(\Rightarrow )$ Suppose all of them are strict, that is, $${\lambda }_1(\mathbf{A})>{\lambda }_1(\mathbf{B})>{\lambda }_2(\mathbf{A})>\cdots >{\lambda }_{n-1}(\mathbf{B})>{\lambda }_n(\mathbf{A}).$$ Reading two steps at a time gives ${\lambda }_k(\mathbf{B})>{\lambda }_{k+1}(\mathbf{A})>{\lambda }_{k+1}(\mathbf{B})$ for $1\le k\le n-2$, so the eigenvalues of $\mathbf{B}$ are distinct. And the displayed chain is strictly decreasing, so its $2n-1$ entries are pairwise distinct; in particular no eigenvalue of $\mathbf{B}$ is an eigenvalue of $\mathbf{A}$. By (b), read as a contrapositive, $P_{\nu }\mathbf{b}\ne \mathbf{0}$ for every eigenvalue $\nu$ of $\mathbf{B}$. This proves the theorem.

Proof. Let $\mathbf{T}\mathbf{u}=\nu \mathbf{u}$ and suppose $u_k=0$; we show $\mathbf{u}=\mathbf{0}$. If $k=1$ this is immediate. Otherwise row $k$ of $\mathbf{T}\mathbf{u}=\nu \mathbf{u}$ reads $t_{k,k-1}{u}_{k-1}+t_{kk}{u}_k=\nu u_k$, so $t_{k,k-1}{u}_{k-1}=0$ and $u_{k-1}=0$, since $t_{k,k-1}\ne 0$. Now suppose $u_i=u_{i+1}=0$ for some $2\le i\le k-1$. Row $i$ reads $t_{i,i-1}{u}_{i-1}+t_{ii}{u}_i+t_{i,i+1}{u}_{i+1}=\nu u_i$, so $t_{i,i-1}{u}_{i-1}=0$ and $u_{i-1}=0$. Walking up from $i=k-1$ to $i=2$ gives $u_{k-2}=\cdots =u_1=0$, so $\mathbf{u}=\mathbf{0}$, and $\mathbf{u}$ is not an eigenvector.

If some eigenspace $E_{\nu }(\mathbf{T})$ contained two independent vectors $\mathbf{u},{\mathbf{u}}^{\prime }$, then $u_k^{\prime }\mathbf{u}-u_k{\mathbf{u}}^{\prime }$ would be a non-zero vector of $E_{\nu }(\mathbf{T})$ — non-zero by independence, since $u_k\ne 0$ — with last coordinate $0$, which we have just excluded. So each eigenspace is a line. Since $\mathbf{T}$ is real symmetric, its eigenspaces have dimensions adding up to $k$ (Corollary 12.5.2), so there are $k$ of them, that is, $k$ distinct eigenvalues. This proves the lemma.

Proof.