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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.