I was going through the solution for least square linear regression that comes out to be
$$ w_{ls} = {(X^TX)}^{-1} X^Ty $$
Now, this exist when ${(X^TX)}^{-1}$ exist, which means ${(X^TX)}$ is invertible.
Now I know that a matrix is invertible when its full rank or its determinant is non zero.
Intuitively speaking it exists when the matrix M is not squishing the space into lower dimension.
Now the derivation i am going through claims that ${(X^TX)}$ is full rank when, when the $n * d$ matrix X, has at least d linearly independent rows?
I know ${(X^TX)}$ should have all linearly independent columns for the inverse to exist , but how do we proceed to show that X should have at least d linearly independent rows?
Best Answer
You know that if $A$ is an $m\times n$ matrix, $$\text{rank}(A)+\text{nullity}(A)=n\tag{1}$$(Rank-nullity theorem).
If $\underset{m\times n}{A}$ is an $m\times n$ matrix, then $\underset{n\times m}{A^T}\;\underset{m\times n}{A}$ is an $n\times n$ matrix, i.e. $A$ and $A^TA$ have the same number of columns.
$Ax=0 \Rightarrow A^TAx=0$, and $A^TAx=0 \Rightarrow x^TA^TAX=0\Rightarrow Ax=0$, hence the nullspaces of $A$ and $A^TA$ are the same. Since they have the same number of columns, it follows from $(1)$ that $$\text{rank}(A)=\text{rank}(A^TA)$$See Seber & Lee, Linear Regression Analysis, John Wiley & Sons, 2003, pp. 458-459.
If your model matrix $X$ is an $n\times d$ matrix and $\text{rank}(X)=d$, then $X^TX$ is a square $d\times d$ matrix and its rank is $d$, i.e. it is full rank. And if $\text{rank}\left(\underset{d\times n}{X^T}\,\underset{n\times d}{X}\right)=d$, then $\text{rank}(X)=d$.