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:


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).

  • 1
    $\begingroup$ 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). $\endgroup$ – Bernard Jun 30 '18 at 16:32
  • 3
    $\begingroup$ The boxed statement is false in general. However, it is true over the real field. $\endgroup$ – user1551 Jun 30 '18 at 16:53
  • $\begingroup$ I was not aware of how would this statement be true in other fields, but I'll update my answer. Thanks! $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – ShellRox Jun 30 '18 at 18:59
  • $\begingroup$ $\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. $\endgroup$ – James Yang Jun 30 '18 at 20:31
  • $\begingroup$ 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 $\endgroup$ – ShellRox Jun 30 '18 at 21:48
  • $\begingroup$ 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! $\endgroup$ – James Yang Jul 1 '18 at 2:06
  • $\begingroup$ Yes it indeed did, thank you! $\endgroup$ – 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.

  • $\begingroup$ $a_i$ is not necessarily in $\mathbf R^n$, unless you have a square matrix$. $\endgroup$ – Bernard Jun 30 '18 at 16:36
  • $\begingroup$ Right, I fixed it (I was implicitly assuming a square matrix since we're talking about invertibility). $\endgroup$ – paf Jun 30 '18 at 16:40
  • $\begingroup$ 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? $\endgroup$ – ShellRox Jun 30 '18 at 16:42
  • $\begingroup$ It's all about ${}^{\mathrm t\!}AA$, and this one is square. $\endgroup$ – Bernard Jun 30 '18 at 16:42
  • $\begingroup$ 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. $\endgroup$ – ShellRox Jun 30 '18 at 16:58

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.