Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let A be an $m \times n$ matrix such that $A^t A$ is invertible. Show that the columns of A are linear independent.

Proof

Assume that $A^t A$ is invertible and the columns of A denoted by $a_1,\dots,a_n$ are linear dependent and there exists scalrs $x_1,x_2,\ldots,x_n$, not all are zero such that $$x_1a_1 + x_2a_2 + \cdots + x_n a_n=0.$$

In matrix form we have $Ax = 0$ $$\begin{align*} Ax &= 0\\ A^t Ax &= A^t 0 = 0\\ (A^t A)^{-1} (A^t A)x &= (A^t A)^{-1} 0 = 0\\ x &= 0 \end{align*}$$

But this is a contradiction, hence the columns of A must be linearly independent.

Question

Doesn't make sense to me, we showed that all the scalars $x$ are 0s, but then we have $$0a_1 + 0a_2 + \cdots + 0a_n = 0$$

How do know that the columns are not 0? The columns are technically "free" and it would make the columns linearly dependent.

share|improve this question
    
You don't need to argue by contradiction: simply assume that $x_1,\ldots,x_n$ are scalars such that $x_1a_1+\cdots+x_na_n=0$; your argument shows that in that case, $x_1=\cdots=x_n=0$. This is the definition of linear independence. You have a fake "proof by contradiction". –  Arturo Magidin Mar 12 '12 at 16:01

3 Answers 3

up vote 4 down vote accepted

The columns are not "free" to be anything; they must be such that $A^tA$ is invertible after all.

If $a_i$ (the $i$th column of $A$) were the zero vector, then the $i$th column of $A^tA$ would also be the zero vector, which would ensure $\det(A^tA)=0$ and thus that $A^tA$ was not invertible, a contradiction.

share|improve this answer
    
Ohhh okay,that explains alot. –  sidht Mar 12 '12 at 5:23

You showed that the hypothesis $x_1a_1 + x_2a_2 + \cdots + x_n a_n=0$ implies $x_1=x_2=\cdots=x_n=0$ and this is precisely the property that by definition says that the columns $a_1,\ldots,a_n$ are linearly independent.

The converse statement, that $x_1=x_2=\cdots=x_n=0$ implies $x_1a_1 + x_2a_2 + \cdots + x_n a_n=0$, in other words that $0a_1 + 0a_2 + ... + 0a_n = 0$, is irrelevant to the question. In fact this converse statement is absolutely uninteresting, since it always holds, whether $a_1,\ldots,a_n$ are linearly dependent or not.

share|improve this answer

Here's an alternative way:

If $A^TA$ is invertible, then here exists a matrix $M$ such that $M(A^TA)=I$; hence, $(MA^T)A = I$.

Viewing the matrices as linear transformations, we have that $A$ is left invertible, hence $A$ must be one-to-one. Thus, the nullspace of $A$ is trivial. Therefore, the columns of $A$ must be linearly independent.

Note that this generalizes easily (as does your own argument) to the following:

If $A$ is an $m\times n$ matrix for which there exists a matrix $B$ with $BA$ invertible, then the columns of $A$ are linearly independent.

In other words, there was nothing special about using $A^T$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.