2
$\begingroup$

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:

$A^TAx=0$

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

$\endgroup$
3
  • 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, 2018 at 16:32
  • 3
    $\begingroup$ The boxed statement is false in general. However, it is true over the real field. $\endgroup$
    – user1551
    Jun 30, 2018 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, 2018 at 17:04

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 2:06
  • $\begingroup$ Yes it indeed did, thank you! $\endgroup$
    – ShellRox
    Jul 1, 2018 at 9:20
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ $a_i$ is not necessarily in $\mathbf R^n$, unless you have a square matrix$. $\endgroup$
    – Bernard
    Jun 30, 2018 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, 2018 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, 2018 at 16:42
  • $\begingroup$ It's all about ${}^{\mathrm t\!}AA$, and this one is square. $\endgroup$
    – Bernard
    Jun 30, 2018 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, 2018 at 16:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .