# Proving that product of transpose matrix and the matrix is inversible

I need to prove that $A^T$$A is an invertible matrix.$$ A= \begin{bmatrix} \vec{a_1} & \vec{a_2} & \ldots & \vec{a_n} \\ \end{bmatrix} $$Can I prove this using a vector \vec{y} and numbers k_1, k_2, \ldots, k_n A^T$$A$$\vec{y} = k_1$$\vec{a_1}$ + $k_2$$\vec{a_2} + \ldots + k_n$$\vec{a_n}$

i.e. can I get a linear combination from $A$'s columns?

$A$ $=$ $M$x$N$ , $M$ $>$ $N$, and $A$ is not a $zero$ matrix.

• This need not be true. For example take $A$ to be the zero matrix. You need $A$ to be full rank. – Anurag A Jan 29 '16 at 11:04
• Moreover if $A$ is an $m \times n$ matrix one needs $m \geq n$, as $A^T A$ is an $n \times n$ matrix and $\operatorname{rank}(A^T A) \leq \min(\operatorname{rank} A^T, \operatorname{rank} A) = \operatorname{rank} A \leq \min(m, n)$. – Travis Willse Jan 29 '16 at 11:12
• A = MxN , M > N, and A is not a zero matrix. – Hydroxis Jan 29 '16 at 12:16
• If $A$ is not quadratic, you can't write $A^TAy$ as $k_1\vec{a}_1+...+k_n\vec{a_n}$ because of a dimension mismatch. – Gregor de Cillia Feb 1 '16 at 2:10

Your conditions with respect to the matrix $A$ are a little bit too vague to post a proper answer, but that might help. I will show, that a matrix $A^TA$ is invertible if and only if it $A$ has a trivial kernel, i.e if

$$Ax = \vec{0}\Rightarrow x = \vec{0},\ x\in R^n.$$

## Classical proof

Suppose $A^TAx$ is $\vec{0}$, then $$\vec{0} = A^TAx \Rightarrow 0 = x^TA^TAx = (Ax)^T(Ax) = \|Ax\|^2 \Rightarrow Ax = \vec{0}$$

On the contrary, if $Ax = \vec{0}$, it holds that $A^TAx = A^T\vec{0} = 0$.

## Proof using columns

To show the same result using columns, denote the columns as you did in the question with $a_1,...,a_n$. The following orthogonality can be shown.

$$A^TAx = [a_1|a_2|...|a_n]^TAx = 0\Rightarrow Ax\perp a_i,\ i= 1,...,n$$ Now, since the orthogonal space of $Ax$ is a linear space, we have that $$Ax \perp \text{span}\{a_i,i=1,...,n\}.$$ Since $\text{span}\{a_i,i=1,...,n\}$ is exactly the image set of $A$ (if we regard it as a map). $$Ax\in \text{span}\{a_i,i=1,...,n\}.$$ We can conclude $Ax=\vec{0}$. The contrary can be shown as above.

• Your comment answered my question. Thanks. – Hydroxis Feb 1 '16 at 15:12