5.2: Linear independence and invertibility

Counting inputs¶

Let’s return to the matrices we used as a running example in Chapter 5.1, $A$, $B$, and $C$:

All three can produce the output $\vec b=\begin{bmatrix}4\\9\\5\end{bmatrix}$; in other words, $\vec b\in\operatorname{colsp}(A)$, $\vec b\in\operatorname{colsp}(B)$, and $\vec b\in\operatorname{colsp}(C)$. But knowing the output doesn’t always tell us what the input was.

• For $A$, the input has to be $\begin{bmatrix}4\\5\end{bmatrix}$: its two entries become the first and third entries of the output. So

  $$A\begin{bmatrix}4\\5\end{bmatrix}=\begin{bmatrix}4\\9\\5\end{bmatrix}$$

  is the only way to produce $\vec b$.

• For $B$, there is more than one way:

  $$B\begin{bmatrix}4\\5\\0\end{bmatrix} =B\begin{bmatrix}2\\6\\1\end{bmatrix} =\begin{bmatrix}4\\9\\5\end{bmatrix}.$$

  In fact, there are infinitely many inputs of the form $\begin{bmatrix}4-2t\\5+t\\t\end{bmatrix}$. Knowing the output doesn’t let us recover the input.

• For $C$, the only input is $\begin{bmatrix}4\\5\\0\end{bmatrix}$. To see why, write $C\vec x=\vec b$ in matrix form:

  $$\begin{bmatrix}1&0&2\\1&1&4\\0&1&3\end{bmatrix} \underbrace{\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}}_{\vec x} =\underbrace{\begin{bmatrix}b_1\\b_2\\b_3\end{bmatrix}}_{\vec b} =\begin{bmatrix}4\\9\\5\end{bmatrix}.$$

  The equations are

  $$x_1+2x_3=4,\qquad x_1+x_2+4x_3=9,\qquad x_2+3x_3=5.$$

  The first and third equations give $x_1=4-2x_3$ and $x_2=5-3x_3$. Substituting into the second gives $9-x_3=9$, so $x_3=0$. Then $x_1=4$ and $x_2=5$.

What is different about the columns of these matrices?

Linear independence¶

Think of a collection of vectors as building blocks. If one of them can already be made using the others, it is redundant: removing it doesn’t change the span.

Sometimes we just say independent instead of linearly independent; they mean the same thing.

Dependent columns¶

For the matrix

call the columns $\vec a_1,\vec a_2,\vec a_3$. They satisfy

So the three columns are linearly dependent. The third column doesn’t add anything to the span of the first two.

This relationship is also why different inputs can produce the same output. Adding one copy of $\vec a_3$ is the same as adding two copies of $\vec a_1$ and subtracting one copy of $\vec a_2$. We can compensate by changing the other coefficients:

This works for any starting input and any real number $t$. Every output in $\operatorname{colsp}(B)$ has infinitely many inputs.

We could remove the third column, but we could also remove the second, since $\vec a_2=2\vec a_1-\vec a_3$. There may be several choices of which vector to remove from a dependent collection.

Independent columns¶

The columns of

are independent: neither is a scalar multiple of the other. Each vector on their plane has just one representation using these two columns.

Now consider

The first two columns are the same as $A$’s. The third column is outside their plane,

since $2-4+3\ne0$. It cannot be made using the first two. These three columns are independent, and every vector in their span has just one representation using them.

Invertibility¶

Recall that an inverse undoes multiplication by a matrix. For an $n\times n$ matrix $A$, its inverse $A^{-1}$ satisfies

If we know the output $\vec b$, we can recover the input by computing $\vec x=A^{-1}\vec b$. So an invertible matrix must produce every vector in $\mathbb R^n$, and each output must come from exactly one input.

This leads to a series of equivalent statements, which connect invertibility to the column space and linear independence.

We don’t need a new inverse formula for each matrix size. We can often decide whether a matrix is invertible by looking at its columns!

For our three matrices:

Both $A$ and $C$ have independent columns, but $A$ only produces vectors on a plane, while $C$ produces every vector in $\mathbb R^3$. The equivalences in the “Invertibility and columns” box above apply to square matrices.

Example: $4\times4$ matrices¶

Consider the two matrices

• $H$ is invertible. Its columns point along four different coordinate directions, so none can be made using the others. More explicitly,

  $$H\begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix} =\begin{bmatrix}2x_2\\-3x_1\\4x_4\\5x_3\end{bmatrix}.$$

  Every output $\begin{bmatrix}b_1\\b_2\\b_3\\b_4\end{bmatrix}$ has exactly one input: $\begin{bmatrix}-b_2/3\\b_1/2\\b_4/5\\b_3/4\end{bmatrix}$.

• $J$ is not invertible. Every output has third entry zero, so it cannot produce every vector in $\mathbb R^4$. Its third column is also $\frac12$ times its first minus $\frac43$ times its second, so the columns are dependent.

More examples¶

Consider these three matrices. What can their columns tell us about invertibility?

• $D$ is not invertible. Its second column is a combination of its first and third columns: $\vec a_2=3\vec a_1-2\vec a_3$. For example,

  $$D\begin{bmatrix}3\\0\\-2\end{bmatrix} =D\begin{bmatrix}0\\1\\0\end{bmatrix} =\begin{bmatrix}4\\7\\-6\end{bmatrix}.$$

• $E$ is invertible. For any output $\begin{bmatrix}b_1\\b_2\\b_3\end{bmatrix}$, the equations are

  $$3x_1-2x_2+x_3=b_1,\qquad -x_2+4x_3=b_2,\qquad 2x_3=b_3.$$

  Starting with the last equation, we can determine $x_3$, then $x_2$, then $x_1$. Each is uniquely determined, whatever $b_1,b_2,b_3$ are.

• $F$ is not invertible. Its second column is zero. For example,

  $$F\begin{bmatrix}1\\0\\0\end{bmatrix} =F\begin{bmatrix}1\\5\\0\end{bmatrix} =\begin{bmatrix}1\\0\\2\end{bmatrix}.$$

A column relationship can save us a lot of work. For instance, a zero column is always redundant: adding any multiple of $\vec0$ doesn’t change a linear combination. Changing the corresponding input entry therefore has no effect on the output.

Independence describes the vectors we’re using to build outputs. In Chapter 5.3, we’ll look more closely at the set of outputs itself: what do these lines, planes, and higher-dimensional collections have in common, and how many independent vectors do we need to describe them?