Consider the projection matrix in Linear Regression $P=X(X^TX)^{-1}X^T$. If we have $n$ points, $P$ is an $n$ x $n$ matrix. We also know it satisfies a number of properties, including that it's symmetric, idempotent, and if $X$ is $n$ x $r$, then $P$ has rank $r$. More here: https://en.wikipedia.org/wiki/Projection_matrix

Now consider the principle sub-matrix we get when removing any arbitrary $n-r$ rows and the corresponding columns. For example, if we remove row 1, 3, 5 we must also remove column 1, 3, 5. Call this new matrix $G$. We know $G$ is $r$ x $r$ and is symmetric.

We want to also show that $G$ has rank $r$. That is, by removing any arbitrary $n-r$ rows and the corresponding columns from $P$, the resulting principle sub-matrix has rank $r$.

I know if a matrix $A$ has rank $k$, than any sub-matrix of A must have rank $\leq k$. But that doesn't seem very helpful here for this proof. Intuitively, it seems that this statement should hold. I tried this out on Mathematica, and holds for $n=3$ and $n=4$ (with $r=2$). I'm not exactly sure how to proceed in trying to show this rigorously.

Edit: $X$ is the design matrix in regression, which always has a column of 1s at the end. So say we are in 2d, and we have the following $(x,y)$ points that we want to fit a line through: (2,1), (4,2), (5,9). Then the $X$ matrix looks like: $$ \begin{matrix} 2 & 1 \\ 4 & 1 \\ 5 & 1\\ \end{matrix} $$ In regression, we want to learn the equation of line (or hyperplane for higher dimension) which has a y-intercept term. Once we have such a $\beta$, our projection/regression is given by $X\beta$. The column of 1 is to account for the y-intercept term. Generally speaking $X$ has rank $r$.


I don't think what you want is true, unless you have further conditions on $X$. Let $$ X=\begin{bmatrix} 1&0\\0&1\\ 0&0\end{bmatrix}. $$ Then $n=3$, $r=2$, and $$ P=X(X^TX)^{-1}X=\begin{bmatrix} 1&0\\0&1\\ 0&0\end{bmatrix}\begin{bmatrix} 1&0\\0&1\end{bmatrix} \begin{bmatrix} 1&0&0\\0&1&0\end{bmatrix} =\begin{bmatrix} 1&0&0\\ 0&1&0\\0&0&0\end{bmatrix} $$ If you remove row and column 1, you get $$ \begin{bmatrix} 1&0\\0&0\end{bmatrix}, $$ with rank $1\ne 2=r$.

  • $\begingroup$ Right, I should have specified the conditions on X. I updated the question with the clear conditions on X. The example you mentioned, won't fit that condition. Thanks $\endgroup$ – Safwan Hossain Apr 4 at 1:51

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.