Proof that $\textbf{Q} = \textbf{I}_n - \textbf{X}(\textbf{X}^T\textbf{X})^{-1}\textbf{X}^T$ is of rank $n-k-1$.

Question

Let $n > k$. Let $\textbf{Q} = \textbf{I}_n - \textbf{X}(\textbf{X}^T\textbf{X})^{-1}\textbf{X}^T$ where $\textbf{I}_n$ is an $n \times n$ identity matrix, $\textbf{X}$ is a $n \times (k+1)$ matrix with rank $k+1$ and the first column of $\textbf{X}$ contains only of $1$'s. I would like to show that $\textbf{Q}$ has rank $n-k-1$.

First note that $\textbf{Q}\textbf{X} = \boldsymbol{0}$ and $\textbf{Q}$ is an $n \times n$ matrix. Because $\textbf{Q}\textbf{X} = \boldsymbol{0}$, the rows of $\textbf{Q}$ satisfy the following $k + 1$ constraints: \begin{align*} \sum_{j=1}^nq_{ji} &= 0, \ j = 1, \dotsc, n;\\ \sum_{j=1}^nq_{ji}x_{i1} &= 0, \ j = 1, \dotsc, n;\\ &\vdots\\ \sum_{j=1}^nq_{ji}x_{ik} &= 0, \ j = 1, \dotsc, n. \end{align*}

I feel like I am almost there, but I can't seem to explain why the rank of $\textbf{Q}$ is $n-k-1$ using these constrains.

Answer 1

The matrix $\ X\ $ has $\ k+1\ $ linearly independent columns. Let $\ S\ $ be the set of row vectors orthogonal to the column space of $\ X\ $. Then $\ S\ $ has dimension $\ n-k-1\ $, and for any $\ v\in S\ $, \begin{align} vQ&=v-vX\big(X^TX\big)^{-1}X^T\\ &=v\ , \end{align} so $\ v\ $ is in the row space of $\ Q_\ $. Therefore, the dimension of the row space, and hence the rank of $\ Q\ $ is at least $\ n-k-1\ $.

But $\ QX=0\ $, so the kernel of $\ Q\ $ contains the column space of $\ X\ $ and therefore has dimension at least $\ k+1\ $. By the rank-nullity theorem, therefore, $$ k+1\le\dim\ker Q=n-\text{rank}\,Q\ , $$ giving $\ \text{rank}\,Q\le n-k-1\ $, and hence $\ \text{rank}\,Q= n-k-1\ $.

Answer 2

Denote the rank of $A$ by $r(A)$.

Denote $Y = X(X^\mathsf{T} X)^{-1}X^{\mathsf{T}}$. We have $r(Y) = k + 1$.

Using $r(A + B) \le r(A) + r(B)$, we have $$r(Q + Y) \le r(Q) + r(Y)$$ which results in $$r(Q) \ge n - (k + 1).$$

Using $r(AB) \ge r(A) + r(B) - n$, we have $$r(QX) \ge r(Q) + r(X) - n$$ which results in (using $QX = 0$) $$r(Q) \le n - (k + 1).$$

Thus, $r(Q) = n - (k + 1)$.