Why is the matrix invertible if its null space is zero?

I'm trying to understand the proof of the following statement:

If $A$ has independent columns then $A^TA$ is invertible.

Please keep in mind that these structured are based on real field.

The proof starts with following equation:

$A^TAx=0$

Then it is stated, that for $A^TA$ to be invertible, $x$ must be the zero vector.

In other words, for $A^TA$ to be invertible, it's null space must be the zero vector.

I found this answer, but I couldn't completely understand it. The author of the answer defined variables: $A$ being a matrix containing columns of $a_n$, $x$ being a vector containing columns of $(x_n)^T$, and $Ax$ being equal to $0$.

Then it's obvious that $x_na_n=0$, but author states that unless $x_n=0$, the columns will not be linearly independent.

I couldn't understand this. If $A$ has linearly independent columns, then how will it change at all when being multiplied by $x$? Maybe they mean $Ax$, but still even if $x$ is zero vector, isn't $Ax$ just a simple linear combination of $A$ and $x$? (And if that is true then it's definitely not linearly independent).

• If $x$ is the zero vecto in, say $K^n$ and $A$ is an $m\times n$ matrix, $Ax$ is the zero vector in $K^m$ ($K$ being the base field). – Bernard Jun 30 '18 at 16:32
• The boxed statement is false in general. However, it is true over the real field. – user1551 Jun 30 '18 at 16:53
• I was not aware of how would this statement be true in other fields, but I'll update my answer. Thanks! – ShellRox Jun 30 '18 at 17:04

As stated in the comments, this does not hold in general, but holds if $A$ is a real matrix.

Claim 1: $ker(A) = ker(A^TA)$

$\subseteq$ is clear. To prove the other, let $v \in ker(A^TA)$. Then $0 = \langle v, A^TAv \rangle = ||Av||^2 \iff Av = 0 \iff v \in ker(A)$.

Claim 2: matrix $A$ is invertible iff injective (as a linear map given bases in domain and codomain). Note that for a linear map, or a matrix, $A$, it is injective iff $ker(A) = \{0\}$, i.e. trivial.

So since $ker(A)$ is trivial as A has independent column vectors, $A^TA$ is invertible by claims 1 and 2.

• Hello, thanks for your answer. Could you please explain what is meant by $0=⟨v,ATAv⟩$? I understand that $A^TAv$ must be zero due to $v$ being in null space but why $v$? Also isn't $A$ basis of the column space itself? Thanks you again. – ShellRox Jun 30 '18 at 18:59
• $\langle u, v\rangle$ is an inner product on u and v. In $\mathbb{R}^n$, we typically use dot product. So in this case you can just read that as dot product. I used inner product because it is more general than dot product. The next equality follows from definition of adjoint of a matrix. Note that I’m assuming A is a real matrix. For your second question, the column vectors of A form a basis of column space iff A is square because you assumed they are linearly independent. – James Yang Jun 30 '18 at 20:31
• Yes I understand the conception of inner products but unfortunately I wasn't familiar with the notation. I almost understood your answer but is it possible to display injective relatiom? You mentioned these function mapping was performed between basis of the functions, for what should $A$ be injective for? I'm assuming null space? Thanks – ShellRox Jun 30 '18 at 21:48
• I am not sure if I understand your question, but I'll try to answer. Since $A$ is linear, $A$ is injective iff $Av = 0 \implies v = 0$, or identically, $ker(A) = \{0\}$. $A$ is just a matrix representation of a linear map from $\mathbb{R}^n \to \mathbb{R}^m$. It is uniquely determined by how it maps the basis vectors. The column vectors of $A$ are precisely the mapped basis vectors. If the column vectors of $A$ are linearly independent, then $A$ is injective: let $v=\sum a_ie_i$. Then $Av=0 \implies \sum a_iA(e_i) =0 \implies a_i = 0\, \forall i$ because $A(e_i)$ indep. Hope that clears it up! – James Yang Jul 1 '18 at 2:06
• Yes it indeed did, thank you! – ShellRox Jul 1 '18 at 9:20

Then it's obvious that $x_na_n=0$, but author states that unless $x_n=0$, the columns will not be linearly independent.

That's not what the author says. He explains that if $a_1,\dots,a_n$ are the columns of $A$ (thus each $a_i$ is a vector in $\Bbb R^m$ - where $m$ is the number of rows of $A$) and if $x = \begin{bmatrix}x_1 & \dots & x_n\end{bmatrix}^T$ (thus each $x_i$ is a scalar), then $\displaystyle Ax = \sum_{i=1}^n x_ia_i$ is a linear combination of the vectors $a_1,\dots,a_n$. Thus, if at least one of the $x_i$ is non-zero, the definition of linear dependence tells us that $a_1,\dots,a_n$ are linearly dependent. But if the only $x$ giving $Ax=0$ is the zero vector, then the columns $a_1,\dots,a_n$ are linearly independent.

• $a_i$ is not necessarily in $\mathbf R^n$, unless you have a square matrix$. – Bernard Jun 30 '18 at 16:36 • Right, I fixed it (I was implicitly assuming a square matrix since we're talking about invertibility). – paf Jun 30 '18 at 16:40 • Apologies for my confusion, how is the vector$a_1,...,a_n$affected by scalar$x_n$before they are combined into$Ax$? Is it$Ax$that becomes linearly dependent when$x$is not a zero vector? – ShellRox Jun 30 '18 at 16:42 • It's all about${}^{\mathrm t\!}AA$, and this one is square. – Bernard Jun 30 '18 at 16:42 • Apologies if this is ignorant question but is$Ax$still a linear combination of$A$and$x$if$x$is a zero vector? I can't understand how is$A$matrix related in any way to$x\$ before they are combined. – ShellRox Jun 30 '18 at 16:58