# Proof that columns of an invertible matrix are linearly independent

Explain why the columns of an $n \times n$ matrix $A$ are linearly independent when $A$ is invertible.

The proof that I thought of was:

If $A$ is invertible, then $A \sim I$ ($A$ is row equivalent to the identity matrix). Therefore, $A$ has $n$ pivots, one in each column, which means that the columns of $A$ are linearly independent.

The proof that was provided was:

Suppose $A$ is invertible. Therefore the equation $Ax = 0$ has only one solution, namely, the zero solution. This means that the columns of $A$ are linearly independent.

I am not sure whether or not my proof is correct. If it is, would there be a reason to prefer one proof over the other?

As seen in the Wikipedia article and in Linear Algebra and Its Applications, $\sim$ indicates row equivalence between matrices.

• What is a pivot? What does $A \sim I$ mean? Your proof seems incomplete and complicated, while the provided proof is a straightforward consequence of definitions. – Crostul Sep 13 '16 at 11:11
• Your proof seems to omit some details. What does $A \sim I$ mean? Are your "pivots" a reference to row reduction? – hardmath Sep 13 '16 at 11:11
• While the other comments do have done truth in them, I think they miss the main point: Yes, the proposed solution is different, but your approach does also work out in the end. – Arthur Sep 13 '16 at 11:43
• Many linear algebra texts have somewhere a long list of conditions equivalent to $A$ being invertible. With such a list, you have a lot of ways to prove that Condition X is equivalent to $A$ being invertible: you can say, Condition X is equivalent to Condition Y, and Condition Y is equivalent to $A$ being invertible, QED. It all depends on what facts you're allowed to assume as known. – Gerry Myerson Sep 13 '16 at 11:46
• @Arthur thanks, I was only unsure about the part where due to the invertible nature of A, I take that it has a pivot in each column. The idea that having a pivot in each column ensures their linear independence is clearer for me. – Bernardo Sulzbach Sep 13 '16 at 11:49

I would say that the textbook's proof is better because it proves what needs to be proven without using facts about row-operations along the way. To see that this is the case, it may help to write out all of the definitions at work here, and all the facts that get used along the way.

## Definitions:

• $A$ is invertible if there exists a matrix $A^{-1}$ such that $AA^{-1} = A^{-1}A = I$
• The vectors $v_1,\dots,v_n$ are linearly independent if the only solution to $x_1v_1 + \cdots + x_n v_n = 0$ (with $x_i \in \Bbb R$) is $x_1 = \cdots = x_n = 0$.

## Textbook Proof:

Fact: With $v_1,\dots,v_n$ referring to the columns of $A$, the equation $x_1v_1 + \cdots + x_n v_n = 0$ can be rewritten as $Ax = 0$. (This is true by definition of matrix multiplication)

Now, suppose that $A$ is invertible. We want to show that the only solution to $Ax = 0$ is $x = 0$ (and by the above fact, we'll have proven the statement).

Multiplying both sides by $A^{-1}$ gives us $$Ax = 0 \implies A^{-1}Ax = A^{-1}0 \implies x = 0$$ So, we may indeed state that the only $x$ with $Ax = 0$ is the vector $x = 0$.

Fact: With $v_1,\dots,v_n$ referring to the columns of $A$, the equation $x_1v_1 + \cdots + x_n v_n = 0$ can be rewritten as $Ax = 0$. (This is true by definition of matrix multiplication)

Fact: If $A$ is invertible, then $A$ is row-equivalent to the identity matrix.

Fact: If $R$ is the row-reduced version of $A$, then $R$ and $A$ have the same nullspace. That is, $Rx = 0$ and $Ax = 0$ have the same solutions

From the above facts, we conclude that if $A$ is invertible, then $A$ is row-equivalent to $I$. Since the columns of $I$ are linearly independent, the columns of $A$ must be linearly independent.

It might be worth pointing out a fascinating proof in the book Algebra by Michael Artin that

The columns of a square matrix $A$ are linearly independent if and only if $A$ is invertible.

The proof proceeds by circularly proving the following chain of implications: (a) $\implies$ (b) $\implies$ (c) $\implies$ (d) $\implies$ (a). All four conditions from (a) to (d) are therefore equivalent.

(a) $A$ can be reduced to the identity by a sequence of elementary row operations.

(b) $A$ is a product of elementary matrices.

(c) $A$ is invertible.

(d) $AX = 0$ has only the trivial solution $X = 0$.

we want to proove that A is invertible if the column vectors of A are linearly independent. we know that if A is invertible than rref of A is an identity matrix so the row vectors of A are linearly independent.

And we also know that if A is invertible than transpose of A is also invertible that means that the row vectors of transpose of A are linearly independent so the column vectors of A are linearly independent.

I would put it concisely as follows \eqalign{ & {\bf A}\,{\rm invertible}\quad \Leftrightarrow \quad \det \left( {\bf A} \right) \ne 0\quad \Leftrightarrow \cr & \left( \matrix{ \Leftrightarrow \quad \,{\bf x}^T {\bf A} = {\bf 0}\; \Rightarrow \;{\bf x}^T = {\bf 0}\quad \Leftrightarrow \hfill \cr \Leftrightarrow \quad {\bf A}\,{\bf x} = {\bf 0}\; \Rightarrow \;{\bf x} = {\bf 0}\quad \Leftrightarrow \hfill \cr} \right) \cr & \Leftrightarrow \quad {\rm columns}\,{\rm (and}\,{\rm rows)}\,{\rm of}\,{\bf A}\,{\rm linearly}\,{\rm independent} \cr}

If the columns of $$A$$ ,i.e $$C_i$$ are linearly independent for $$i = 1, \ldots, n$$. Thus,{$$C_1$$,$$C_2$$,..,$$C_n$$} is a basis of $$R^n$$. If $$E_i$$ for $$i=1, \ldots, n$$ are the standard basis for $$R^n$$ then we can say that $$E_i=C_1 B_{1i} + C_2 B_{2i} +\ldots + C_n B_{ni} ; \tag A$$ for a unique set of constants $$B_{ji}$$ for $$j = 1, \ldots, n$$. (In short, any standard basis of $$R^n$$ is a unique linear combination of the basis vectors $$C_1$$,$$C_2$$,..,$$C_n$$ of $$R^n$$.)

Using the standard basis of $$R^n$$ and elements $$A_{ij}$$ of matrix $$A$$, we know that any column of matrix $$A$$ can be written as $$C_i = A_{1i} E_1 + A_{2i} E_2 + \ldots + A_{ni} E_n ;\tag B$$ therefore substituting (B) in (A);

$$E_i = (A_{11}E_1 + \ldots + A_{n1}E_n)B_{1i} + (A_{12}E_1 + \ldots + A_{n2}E_n)B_{2i} +\ldots + (A_{1n}E_1 + \ldots + A_{nn}E_n) B_{ni}$$

$$E_i = (A_{11}B_{1i} +\ldots + A_{1n}B_{ni})E_1 +\ldots +(A_{i1}B_{1i} +\ldots+ A_{in}B_{ni})E_i +\ldots +(A_{n1}B_{1i} +\ldots + A_{nn}B_{ni}) E_n \tag{C}$$

Comparing LHS and RHS its evident that

$$(A_{i1}B_{1i} +\ldots + A_{in}B_{ni})=1 \text{ for } i = 1, \ldots, n. \tag{D}$$

whereas

$$(A_{j1}B_{1i} +\ldots + A_{jn}B_{ni})=0 \text{ for } j \ne i \tag{E}$$

If $$B=(B_{ij})$$ is a matrix then from $$(B),(D),(E)$$ we have $$AB=I$$ and hence $$B$$ is the inverse of $$A$$.

(note: this proof uses no assumptions of row or column transformations or determinants as well but uses the only one simple fact of linear independence between the basis vectors and standard basis vectors. )

• Please use MathJax – Aqua Jul 8 '19 at 13:23

I’ll use rows instead of columns, but the argument for columns holds similarly. Suppose a square matrix A is invertible that means it is row equivalent to the identity matrix. Now, observing that the rows of the identity are linearly independent, you can reapply the reverse operations on the rows of the identity to get the rows of A, this shows that the rows of A are linearly independent.

Suppose the rows of A are linearly independent. Applying row operations on the rows of A until you have a reduced echelon matrix, will give you a matrix with no zero rows and hence it must be the identity. Therefore A is row equivalent to the identity and so A is invertible.