# Eigenvalues of $MA$ versus eigenvalues of $A$ for orthogonal projection $M$

Suppose that $M$ is symmetric idempotent $n\times n$ and has rank $n-k$. Suppose that $A$ is $n\times n$ and positive definite. Let $0<\nu_1\leq\nu_2\leq\ldots\nu_{n-k}$ be the nonzero eigenvalues of $MA$ and $0<\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n$ be the eigenvalues of $A$. I'm trying to show that $$\forall i=1,\ldots,n-k:\quad 0<\lambda_i\leq\nu_i\leq\lambda_{i+k}\tag{*}$$ There will be a 300 bounty for the accepted answer. Can someone also please make all the (attempted) proofs below as spoilers? I can only do that for the first proof.

Attempt: I have an attempt here using Durbin and Watson (1950) but I don't fully understand the authors' argument so the attempt is incomplete. Nonetheless, I'll present the attempt here. Step 3 below is where I am stuck.

Step 1: One can write $M$ as $M_kM_{k-1}\cdots M_1$ where $M_i=I_n-p_ip_i'$ and $\{p_1,\ldots,p_k\}$ is a set of $n\times 1$ mutually orthogonal vectors s.t. $||p_i||=1$.

Proof. $M$, by assumption, can be written as $M=I_n-X(X'X)^{-1}X'$ where $X$ is $n\times k$ with full column rank. Let $P=(p_1,\ldots,p_k)$ (dimension $n\times k$) be the $Q$ bit of the QR decomposition of $X$.

Step 2: Let $T=(T_1,\ldots,T_n)$ be an $n\times n$ matrix of orthonormal eigenvectors of $A$ that corresponds to eigenvalues $\lambda_1,\ldots,\lambda_n$. Let $l_{1i}=T_i'p_1$. Then any nonzero eigenvalue $\theta$ of $M_1A$ satisfies $$\sum_{i=1}^nl_{1i}^2\prod_{j\neq i}(\theta-\lambda_j)=0.\tag{**}$$

Proof. For any eigenvalue (possibly $0$) $\theta$ of $M_1A$, we have $$0=|I_n\theta-M_1A|=|I_n\theta-(I_n-p_1p_1')A|=|I_n\theta-(I_n-l_1l_1')\Lambda|$$ Here, $l_1$ is the $n\times 1$ column vector with entries $l_{1i}$ and $\Lambda=\text{diag}(\lambda_1,\ldots,\lambda_n)$. Write out $I_n\theta-(I_n-l_1l_1')\Lambda$ in full. Subtract $l_2/l_1$ times the first row from the second row, $l_3/l_1$ times the first row from the third row, and so on, and then execute the Laplace expansion along the first row. The result is $$0=|I_n\theta-(I_n-l_1l_1')\Lambda|=\prod_{j=1}^n(\theta-\lambda_j)+\sum_{i=1}^nl_{1i}^2\lambda_{i}\prod_{j\neq i}(\theta-\lambda_j).$$ Plugging $\theta=0$ in the rightmost expression above gives $\sum_{i=1}^2l_{1i}^2=1$. Thus, \begin{align*} 0&=\sum_{i=1}^nl_{1i}^2\prod_{j=1}^n(\theta-\lambda_j)+\sum_{i=1}^nl_i^2\lambda_{i}\prod_{j\neq i}(\theta-\lambda_j)\\ &=\sum_{i=1}^nl_{1i}^2(\theta-\lambda_i)\prod_{j\neq i}(\theta-\lambda_j)+\sum_{i=1}^nl_i^2\lambda_{i}\prod_{j\neq i}(\theta-\lambda_j) \end{align*} which can be simplified and, for $\theta\neq 0$, divided by $\theta$ to get ($**$).

Step 3: Let $0=\cdots =0<\theta_1^{(s)}\leq \theta_2^{(s)}\leq \theta_{n-s}^{(s)}$ be the eigenvalues of $M_sM_{s-1}\cdots M_1A$. Then, $$\forall s=1,\ldots,k:\quad \theta_i^{(s-1)}\leq\theta_i^{(s)}\leq \theta_{i+1}^{(s-1)},\quad i=1,\ldots,n-s.\tag{***}$$ Here the $\lambda_i$'s are taken to be the $\theta_i^{(0)}$'s.

Proof. Let's build the first step for the case $s=1$. Consider $$f(\theta)=\sum_{i=1}^nl_{1i}^2\prod_{j\neq i}(\theta-\lambda_j)$$ and consider $[\lambda_r,\lambda_{r+1}]$ for $r=1,\ldots,n-1$. Either $f(\lambda_r)=0$ or $f(\lambda_{r+1})=0$ or $f(\lambda_r)f(\lambda_{r+1})\neq 0$. It's easy to show that in general $f(\lambda_r)f(\lambda_{r+1})\leq 0$ and so if $f(\lambda_r)f(\lambda_{r+1})\neq 0$ then $f(\lambda_r)f(\lambda_{r+1})< 0$ and so by the Intermediate Value Theorem, there is an zero of $f$ between $(\lambda_r,\lambda_{r+1})$. In sum, there is a zero of $f$ in each $[\lambda_r,\lambda_{r+1}]$ for each $r=1,\ldots,n-1$. It follows that $$0<\lambda_1\leq\theta_1^{(1)}\leq\lambda_2\leq \theta_2^{(1)}\leq\cdots\leq \theta_{n-1}^{(1)}\leq\lambda_n.$$ This proves ($***$) for $s=1$. Proceed with $M_2M_1A$ as $M_2(M_1A)$ to get ($***$) for $s=2$. And so on.

Step 4: ($*$) holds.

Proof. By Step 3, for $i=1,\ldots,n-k$, $$\nu_i=\theta_i^{(k)}\geq \theta_i^{(k-1)}\geq \cdots \geq \theta_i^{(1)} \geq \theta_i^{(0)}=\lambda_i.$$ Similarly, $$\nu_i=\theta_i^{(k)}\geq \theta_{i+1}^{(k-1)}\geq \cdots \geq \theta_{i+k-1}^{(1)} \geq \theta_{i+k}^{(0)}=\lambda_{i+k}.$$

Problem with Step 3. The case for $s=1$ and $M_1A$ relies on $A$ being diagonalizable. I don't think the same argument works for $M_2(M_1A)$ because we don't know the diagonalizability of $M_1A$. So I don't think the induction step in Step 3 works (Durbin and Watson (1950) claim it does.). Moreover, while I'm confident in the Intermediate Value Theorem argument, I'm not confident about the subsequent claim:

It follows that $$0<\lambda_1\leq\theta_1^{(1)}\leq\lambda_2\leq \theta_2^{(1)}\leq\cdots\leq \theta_{n-1}^{(1)}\leq\lambda_n.$$

As $M$ is symmetric idempotent, with respect to its orthonormal eigenbasis, you may assume that $M=I_{n-k}\oplus0$. Then the eigenvalues of $MA$ are just the eigenvalues of the leading principal $(n-k)\times(n-k)$ submatrix of $A$. So, essentially, the inequality in question relates the eigenvalues of a positive definite matrix $A$ to the eigenvalues of its principal submatrix. This actually is a well-known result that is not only true for positive definite matrices, but for all Hermitian matrices. See, e.g. theorem 4.3.15 (p.189) of Horn and Johnson, Matrix Analysis, 1/e, Cambridge University Press, 1985.