If $A^TA$ is invertible, then $A$ has linearly independent column vectors

Question

Question: Prove that for a $m \times n$ matrix $A$, if $A^TA$ is invertible, then $A$ has linearly independent column vectors.

I am hitting a complete blank with this proof, I have the following jotted down so far about stuff that I know.

What I know so far:

Let $A$ be an $m \times n$ matrix and suppose $A^TA$ is invertible.

We know $A^T$ is an $n\times m$ matrix, hence $A^TA$ is an $n\times n$ square matrix with nonzero determinant.

We also know that $A^TA\bar{x}=\bar{0}$ has only the trivial solution and $A^TA = \bar{b}$ is consistent and has exactly one solution.

The column and row vectors of $A^TA$ are linearly independent.

How can I use some of the above to show that $A$ has linearly independent column vectors?

Answer 1

For each $i$, let $A_i$ be the $i$th column of $A$. Let $A_1 x_1 + \cdots + A_n x_n = 0$ be a linear dependence relation. Then $Ax = 0$, where $x$ is the column vector $(x_1\cdots x_n)^T$. So $A^TAx = 0$. Invertibility of $A^T A$ implies $x = 0$. Thus $x_1 = \cdots = x_n = 0$, showing that $\{A_1,\ldots, A_n\}$ is linearly independent, as desired.

Answer 2

We have a theorem: $rank(AB) \leq min(rank(A),rank(B))$

In our case, we have $rank(A^TA) \leq min(rank(A^T),rank(A))$

Since row rank is equal to column rank, we can infer that $rank(A^T)=rank(A)$, and so $rank(A^TA) \leq rank(A)$.

But we also know that $A^TA$ is invertible, so it has full rank, so $rank(A^TA)=n$.

So we have $rank(A) \geq n$. but $A$ only has $n$ columns, so the rank can't possibly be more than $n$, overall we have $rank(A)=n$. so $A$ has $n$ independent column (and row) vectors.

Answer 3

Since $A^TA$ is invertible you have $(A^TA)^{-1} A^TA = I_n$.

Consider the space generated by the columns of $A$ in $\mathbb{R}^m$. Then the equality above show that the image of that space under the linear map induced by $(A^TA)^{-1} A^T$ is $\mathbb{R}^n$. As a consequence the dimension of that space is at least $n$ and thus the $n$ columns must be independent.

Answer 4

Well, suppose $A$ does not have independent column vectors and denote by $A^i$ the $i$-th column of $A$.

Then, there exist $v_1,\ldots, v_n\in\mathbb{R}$ not all zero such that $$\sum v_i A^i=0$$ i.e. the vector $v=(v_1,\ldots, v_n)^t$ is a solution of $Ax=0$, i.e. $v$ belongs to $\ker A$ and $v\neq 0$.

Now, $A^TAv=A^T(Av)=A^T0=0$. Hence $v\in \ker(A^TA)$, hence $A^TA$ is not invertible.

More generally, $\ker(A)\subseteq\ker(A^TA)$. So if you suppose that the bigger one is just $\{0\}$, also the smaller has to be $\{0\}$.