# Why is this true for matrices? Linearly dependent columns $\implies$ not invertible

If $A$ is a square matrix with linearly dependent columns, then $A$ is not invertible.

Why is this true for matrices?

• As a very simple example to further convince yourself, take $A$ to be a $2 \times 2$ matrix of all $1$'s. Then notice if you move along the line $x+y = d = \text{const}$, $A$ sends every point on this line to the same point, $(d,d)$. – Chester Aug 17 '15 at 23:04

You should know that elementary column operations preserve a zero/nonzero determinant. You should also know that if a column is all zeros, then the determinant is zero. All that remains is to convince yourself that if the columns are linearly dependent, then you can make one column all zeros from a sequence of elementary column operators.

• Nice answer. +1 – James K Aug 17 '15 at 22:54
• The first sentence is not true; see math.stackexchange.com/questions/1991807/…. However, the -1 from a single column exchange will not change a determinant equal to 0. – sunspots Jun 17 '19 at 9:55
• @sunspots good catch, corrected. – Jahan Claes Jun 17 '19 at 12:47
• is the opposite direction (of the question) also true ? – Xhero39 May 1 '20 at 18:59
• Yes! Every step in the proof I outlined goes in both directions. – Jahan Claes May 1 '20 at 19:12

Let $A_1, \ldots, A_n$ be the columns of $A$. If they're linearly dependent, then there are constants $c_i$ (not all zero) such that $$c_1\,A_1 + \cdots + c_n \,A_n=\vec0.$$ The trick is to note that if $\vec c = \left[\begin{array}{c} c_1\\ \vdots\\ c_n\end{array}\right]$, then the above equation says precisely that $A\vec c = \vec 0$, with $\vec c \not=\vec0$. (In general, $x_1\,A_1 + \cdots + x_n \,A_n=A\vec x$, for any vector $\vec x$.)

Now you use the fact that if $A$ is invertible, then the only solution to $A\vec x = \vec0$ is $\vec x = \vec0$. So $A$ can't be invertible. $~\square$

• The fact you use at the end ("if $A$ is invertible, then the only solution to $A\vec x = \vec0$ is $\vec x = \vec0$") seems like simply restating the problem to me. How do we know (or how can we prove) that this is true? – Joe Strout Sep 14 '19 at 4:27
• is the opposite direction (of the question) also true ? – Xhero39 May 1 '20 at 18:57

If the columns of A are linearly dependent,

then $a_1\vec{c_1}+\cdots+a_n\vec{c_n}=\vec{0}$ for some scalars $a_1,\cdots, a_n$ (not all 0).

Then $Av=\vec{0}$ where $v=\begin{pmatrix}a_1\\\vdots\\a_n\end{pmatrix}\ne\vec{0}$, so A is not invertible

(since otherwise, multiplying by $A^{-1}$ would give a contradiction).

• For future searchers: this answer is closest to being complete, rather than just dropping hints. The key bit that was still unobvious to me is the parenthetical statement at the end. What this means is: multiply both sides of $Av = 0$ by $A^{-1}$, giving $A^{-1}Av = A^{-1}0$ (and this actually is valid to do, even though the right-hand side is zero). This means $v = 0$, contradicting the statement above. – Joe Strout Sep 14 '19 at 4:41
• is the opposite direction (of the question) also true ? – Xhero39 May 1 '20 at 18:57

Let your matrix be $A$ and let the columns of your matrix be $c_1,c_2,\cdots,c_n$. Saying there's a subset of linearly dependent columns means that there are columns $c_{i_1},c_{i_2},...,c_{i_k}$ that are linearly dependent, so that there exist nontrivial $a_k$ such that:

$$a_1c_{i_1}+a_2c_{i_2}+\cdots+a_kc_{i_k}=0.$$

Now define the vector $v$ so that $v_{i_k}=a_k$ and $v_i=0$ otherwise. What do you suppose $Av$ equals?

• No need for subindexing. Just $Av=c_1v_1+\ldots+c_nv_n$ is a linear combination. Lin.dependent $\Rightarrow$ $\exists v\ne 0$: $Av=0$ (by definition). – A.Γ. Aug 17 '15 at 22:53
• I think everyone jumped on this one at once. – Christopher Carl Heckman Aug 17 '15 at 22:56
• This is not an answer; it is another question. Nor is it at all clear how this new question relates to the original one. – Joe Strout Sep 14 '19 at 4:30
• @JoeStrout: $Av=0$, so... – Alex R. Sep 14 '19 at 5:41
• @FirasAliAbdelGhani: Of course. If $A$ is not invertible, it has a nontrivial kernel, so that $Ax=0$ for some nonzero $x$, so the columns of $A$ are linearly dependent. – Alex R. May 1 '20 at 19:16

Hint: If $A$ has linearly dependent columns, then $\det(A)=0$.

Another approach without using the determinant: let $A\in \mathbb R^{n\times n}$ (or any other field $\mathbb F$). We write $v_1,\dots v_n$ for the columns of $A$. As the columns are linearly dependent there exists $a_1,\dots,a_n\in \mathbb R$ and $a_i\neq 0$ for at least one $i\in \{1,\dots n\}$ such that $a_1v_1+\dots +a_nv_n=0$. Let $\varphi$ be the linear mapping associated with $A$, then: $$\varphi\left(\begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix}\right)=A\cdot \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} = a_1v_1+\dots +a_nv_n=0.$$ Thus $\varphi$ is not bijective and we conclude that $A$ is not invertible.

• Okay so this is essentially what I don't understand because $A$ is not invertible $\iff$ $\det (A)=0$ so why is your hint true? – James K Aug 17 '15 at 22:44
• Are you having problems with this excact equivalence, with the proof that $\det(A)=0$? – Hirshy Aug 17 '15 at 22:46
• is the opposite direction (of the question) also true ? – Xhero39 May 1 '20 at 18:58