Invertibility of Gram Matrix - Proof

Question

I'm an undergrad that just got introduced to ordinary least squares and am trying to understand why a Gram matrix is invertible only if the column vectors are linearly independent. The thread below (3rd post ) uses the exact same proof as my lecturer. However, there is still something that is not clear for me which probably is something silly.

Gram matrix invertible iff set of vectors linearly independent

JasonMond's "only if" part is not as general as it should, because s/he assumes that AA is square. In the following, I complete the proof that holds whether AA is square or not.

Let $G=A^TA$. If the column vectors of $A$ are linearly dependent, there exists a vector $u≠0$ such that

$Au = 0$

It follows that

$0=A^TAu=Gu$

So i understand that if the column vectors of A are linearly dependent, then I can find a non-zero vector u such that $Au=0$. But how does this tell me that G is not invertible ? Because there are other vectors such that $Au\neq0$

For any square matrix G to be invertible, does it require the result of $Gu$ to be non-zero for all non-zero vectors $u$ ? If so, where can I read about this ?

Answer 1

Your question is related to the null space of a matrix. Suppose $A$ is a real $n\times n$ matrix, we define the null space of $A$, as $$Null(A)=\left\{ x \in R^n : Ax=0\right\}$$ If $A$ is invertible, it follows that $Null(A)=\{0\}$. This fact can be proven as follows. Suppose $x \in Null(A)$, then $Ax=0$. Multiply both sides by $A^{-1}$, we obtain $$A^{-1}Ax=0 \Rightarrow Ix=0 \Rightarrow x=0$$

Answer 2

So we know that $Gu=0$ for some non-zero vector $u$. Now assume for contradiction that $G$ is invertible. Then $G^{-1}Gu=G^{-1}0$ which simplifies to $u=0$. But this is a contradiction because we assumed $u$ is non-zero.

Therefore, if $Gu=0$ for some non-zero vector $u$, then $G$ is not invertible.