6
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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\}$.

$\endgroup$

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.