Proof of Inverse Existence for A^TA

Theorem 6.4.3

If $ A $ is an $ m \times n $ matrix, then the following are equivalent.

(a) The column vectors of $ A $ are linearly independent.

(b) $ A^TA $ is invertible.

Proof

We will prove both directions.

(a) ⇒ (b)

Assume that the column vectors of $ A $ are linearly independent.

The matrix $ A^TA $ has size $ n \times n $.

To prove that $ A^TA $ is invertible, show that $ A^TA\vec{x} = \vec{0} $ has only the trivial solution.

If $ \vec{x} $ is a solution of $ A^TA\vec{x} = \vec{0} $, then $ A\vec{x} $ is in the null space of $ A^T $ and also in the column space of $ A $.

By Theorem 4.8.7(b), the null space of $ A^T $ and the column space of $ A $ are orthogonal complements.

Due to orthogonality, part (b) of Theorem 6.2.4 implies $ A\vec{x} = \vec{0} $.

Since $ A $ is assumed to have linearly independent column vectors, the only solution to $ A\vec{x} = \vec{0} $ is $ \vec{x} = \vec{0} $.

(b) ⇒ (a)

Assume that $ A^TA $ is invertible. We want to show that the column vectors of $ A $ are linearly independent.

Consider the linear combination $ c_1\vec{a}_1 + c_2\vec{a}_2 + \ldots + c_n\vec{a}_n = \vec{0} $, where $ \vec{a}_i $ is the $i$-th column vector of $ A $ and $ c_i $ are scalars.

Multiply both sides by $ A^T $ from the left:

\[A^T(c_1\vec{a_1}+ c_2\vec{a_2} + \ldots + c_n\vec{a_n}) = A^T\vec{0}\]

Using properties of transpose and the fact that $ A^TA $ is invertible, we get:

\[c_1A^T\vec{a_1}\ + c_2A^T\vec{a_2}\ + \ldots + c_nA^T\vec{a_n}\ = \vec{0}\]

Since $ A^TA $ is invertible, its null space contains only the zero vector. This implies that the above equation can only be true if $ c_1 = c_2 = \ldots = c_n = 0 $, showing that the column vectors of $ A $ are linearly independent.

Therefore, we have shown both (a) ⇒ (b) and (b) ⇒ (a), and the two statements are equivalent.

Theorem 4.8.7(b):

If $A$ is a matrix, then the null space of $A^T$ and the column space of $A$ are orthogonal complements.

Proof: Let $\vec{v}$ be a vector in the null space of $A^T$, i.e., $A^T \vec{v} = \vec{0}$. This means that $\vec{v}$ is orthogonal to every row vector of $A^T$.

Since the rows of $A^T$ are the columns of $A$, $\vec{v}$ is orthogonal to every column vector of $A$. Thus, $\vec{v}$ is in the orthogonal complement of the column space of $A$.

Conversely, let $\vec{w}$ be in the orthogonal complement of the column space of $A$. This means that $\vec{w}$ is orthogonal to every column vector of $A$.

Since the columns of $A$ are the rows of $A^T$, $\vec{w}$ is orthogonal to every row vector of $A^T$. Hence, $\vec{w}$ is in the null space of $A^T$.

Therefore, the null space of $A^T$ and the column space of $A$ are orthogonal complements.

Theorem 6.2.4(b)

If $A$ is a matrix and $A\vec{x} = \vec{0}$ has only the trivial solution, then the columns of $A$ are linearly independent.

Proof: Assume that $A\vec{x} = \vec{0}$ has only the trivial solution. Suppose $c_1 \vec{v}_1 + c_2 \vec{v}_2 + \ldots + c_n \vec{v}_n = \vec{0}$, where $\vec{v_i}$ are the columns of $A$ and $c_i$ are scalars.

Let $A$ be an $m \times n$ matrix, and $\vec{v_i}$ be the $i$-th column vector of $A$. Then, $A\vec{x} = c_1 \vec{v}_1 + c_2 \vec{v}_2 + \ldots + c_n \vec{v}_n = \vec{0}$.

Since $A\vec{x} = \vec{0}$ has only the trivial solution, we must have $c_1 = c_2 = \ldots = c_n = 0$. Thus, the columns of $A$ are linearly independent.