29
$\begingroup$

How can I understand that $A^TA$ is invertible if $A$ has independent columns? I found a similar question, phrased the other way around, so I tried to use the theorem

$$ rank(A^TA) \le min(rank(A^T),rank(A)) $$

Given $rank(A) = rank(A^T) = n$ and $A^TA$ produces an $n\times n$ matrix, I can't seem to prove that $rank(A^TA)$ is actually $n$.

I also tried to look at the question another way with the matrices

$$ A^TA = \begin{bmatrix}a_1^T \\ a_2^T \\ \ldots \\ a_n^T \end{bmatrix} \begin{bmatrix}a_1 a_2 \ldots a_n \end{bmatrix} = \begin{bmatrix}A^Ta_1 A^Ta^2 \ldots A^Ta_n\end{bmatrix} $$

But I still can't seem to show that $A^TA$ is invertible. So, how should I get a better understanding of why $A^TA$ is invertible if $A$ has independent columns?

$\endgroup$
24
$\begingroup$

Consider the following: $$A^TAx=\mathbf 0$$ Here, $Ax$, an element in the range of $A$, is in the null space of $A^T$. However, the null space of $A^T$ and the range of $A$ are orthogonal complements, so $Ax=\mathbf 0$.

If $A$ has linearly independent columns, then $Ax=\mathbf 0 \implies x=\mathbf 0$, so the null space of $A^TA=\{\mathbf 0\}$. Since $A^TA$ is a square matrix, this means $A^TA$ is invertible.

$\endgroup$
  • $\begingroup$ This answer uses vocabulary that is much more familiar than the other answer you linked in the comments. Thanks! $\endgroup$ – Chewers Jingoist Jun 26 '16 at 23:54
  • 2
    $\begingroup$ I liked @littleO's elegant proof but, going against popular votes, I'm accepting this answer because it gave me a better understanding. $\endgroup$ – Chewers Jingoist Jun 27 '16 at 0:16
  • 2
    $\begingroup$ @CharlieParker I am pretty sure your proof is flawed. You do not consider the case where $Ax \neq 0$, but $A^TAx=0$ because $Ax$ is in the null space of $A^T$. In order to show this can't happen, I made an argument using the null space of $A^T$ to show $Ax$ must equal $0$. $\endgroup$ – Noble Mushtak Oct 18 '17 at 21:54
  • 3
    $\begingroup$ @CharlieParker Sorry for the late response. $Ax \in N(A^T)$ because we have $A^T(Ax)=0$. Also, $Ax \in C(A)$, as you said. Therefore, $Ax$ is in both $N(A^T)$ and $C(A)$. However, the only vector that can be in both a subspace and the orthogonal complement of its subspace is the zero vector. Thus, $Ax$ must be the zero vector. $\endgroup$ – Noble Mushtak Nov 5 '17 at 14:50
  • 2
19
$\begingroup$

If $A $ is a real $m \times n $ matrix then $A $ and $A^T A $ have the same null space. Proof: $A^TA x =0\implies x^T A^T Ax =0 \implies (Ax)^TAx=0 \implies \|Ax\|^2 = 0 \implies Ax = 0 $.

$\endgroup$
  • 1
    $\begingroup$ I was also wondering why $N(A^TA) = N(A)$ but I didn't think that would be related to my question. Thanks! $\endgroup$ – Chewers Jingoist Jun 27 '16 at 0:03
  • 1
    $\begingroup$ Is it true that anything multiplied on the left leaves the null space unaffected? i.e. $N(CA) = N(A)$ for all $C$? $\endgroup$ – Charlie Parker Oct 18 '17 at 21:09
  • 1
    $\begingroup$ Also, at what point are you using that the matrix $A$ has column rank $r$? I'm curious because your proof seems a lot less intuitive than what the simpler argument than: If we want $A^TAx=0$ only with the zero vector then its obvious thats the case by definition because $A$ has independent columns, so only $Ax=0$ and thats true too for $A^T A $. $\endgroup$ – Charlie Parker Oct 18 '17 at 21:11
  • 3
    $\begingroup$ @CharlieParker Also, in this answer, littleO only showed that $A$ and $A^TA$ had the same null space. However, the full proof is a bit more intricate than this: Since $A$ has column rank $r$ (i.e. independent columns), it has a trivial null space. Thus, by the above, $A^TA$ also has a trivial null space. Therefore, since $A^TA$ is a square matrix and has a trivial null space, it is invertible. $\endgroup$ – Noble Mushtak Oct 18 '17 at 21:58
  • 1
    $\begingroup$ @CharlieParker Yes, an invertible $C$ would not change the null space. However, it is not the only type of matrix that works. As littleO showed, $A^T$ also works, even if $A$ does not have independent columns. $\endgroup$ – Noble Mushtak Oct 18 '17 at 22:10
4
$\begingroup$

Let $A \in \mathbb R^{m \times n}$. Note that

$$f (x) := x^T A^T A x = \|A x\|_2^2$$

is positive semidefinite. Function $f$ vanishes when $A x = 0_m$. If $A$ has full column rank, i.e., if its $n$ columns are linearly independent, then $A x =0_m$ implies that $x = 0_n$, i.e., $f$ is positive definite and, hence, $A^T A$ is positive definite and, thus, invertible.

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