We've been focused on solving these linear systems but if we step back a bit, we notice that there are some coincidences that keep popping up. For instance, we can see the rank of a matrix has a deep connection with the number of vectors we care about. But what exactly is that connection?
Here's one question to start with that we keep coming back to. Recall the column space of a matrix is spanned by its columns. The question we had was whether we needed all of those columns. Our factorization of $A$ into $CR$ suggests that the answer is sometimes no. We've also asked the same question of the null space: how do we know that the special solutions are really the vectors we need and want to describe the null space?
In both cases, we have sets of vectors that span our respective spaces, but we desire something stronger to say about these kinds of sets. We also want to know that our spanning sets are linearly independent. This is an important concept, so we give it a name.
A basis for a vector space $V$ is a linearly independent set that spans $V$.
The standard basis for $\mathbb R^3$ is the unit vectors $\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}$. It's clear this set is linearly independent. Do they span $\mathbb R^3$? Well, take a vector of your choice $\begin{bmatrix} x \\ y \\ z \end{bmatrix}$. Then you can write it as \[\begin{bmatrix} x \\ y \\ z \end{bmatrix} = x \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + y \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} + z \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}.\]
It's important to remember that a basis is both a linearly independent set and a spanning set. It's possible to have a linearly independent set that doesn't span a space—this says that we have too few vectors. It's also possible to have a spanning set that isn't linearly independent—this says we have too many vectors.
Consider the column space of a matrix $\begin{bmatrix} 3 & 1 \\ 9 & 3 \end{bmatrix}$. We've defined its column space to be the vectors that are the linear combinations of its columns. However, its columns aren't a basis for the column space. Why? The columns aren't linearly independent. So a basis for the column space would be any one of the columns, but not both.
Now is a good time to remember the other definition for linear independence. Recall that a set of vectors is linearly independent if no vector in the set can be written as a linear combination of any of the others. But we recall the following.
We say that the set of vectors $\mathbf v_1, \dots, \mathbf v_n$ is linearly independent if and only if the only solution to \[x_1 \mathbf v_1 + \cdots + x_n \mathbf v_n = \mathbf 0\] is $x_1 = \cdots = x_n = 0$.
We have been making plenty of use of this definition already. For instance, this is the crux of our arguments about the number of solutions for the linear equation $A \mathbf x = \mathbf 0$.
One reason why this definiton is preferred is that it makes it clear that linear independence is a property of the set of vectors collectively. When we talk about linear dependence, we often try to find a specific vector that is "dependent" on the others. But that's not how it works, because we can always rewrite the "dependence" another vector is the "dependent" one.
Here is another interesting consequence of this definition.
Let $\mathbf v_1, \dots, \mathbf v_n$ be a basis. There is exactly one way to write a vector $\mathbf u$ as a linear combination of the basis vectors.
Suppose that there are two ways to write $\mathbf u$ as a linear combination of the basis vectors. This means we have \begin{align*} \mathbf u &= a_1 \mathbf v_1 + \cdots + a_n \mathbf v_n \\ \mathbf u &= b_1 \mathbf v_1 + \cdots + b_n \mathbf v_n \end{align*} Then since $\mathbf u - \mathbf u = \mathbf 0$, we have \begin{align*} \mathbf 0 &= (a_1 \mathbf v_1 + \cdots + a_n \mathbf v_n) - (b_1 \mathbf v_1 + \cdots + b_n \mathbf v_n) \\ &= (a_1 - b_1) \mathbf v_1 + \cdots + (a_n - b_n) \mathbf v_n \end{align*} However, our basis is linearly independent, which means that the only linear combination of $\mathbf v_i$'s that results in $\mathbf 0$ is when all the scalars are $0$. This means that we must have $a_i - b_i = 0$ for every $i$ and therefore, $a_i = b_i$. In other words, the two linear combinations we thought we had are actually the same.
Intuitively, this makes sense—if each vector in the basis is independent of the others, then there should be no way of "scaling" it and adjusting the other vectors to compensate.
But it's important not to confuse this with the idea of a "unique" basis—there is actually no such thing. In fact, a vector space may have infinitely many bases.
Here's another example of a basis for $\mathbb R^3$: $\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$. To see this, observe that we have for any $x,y,z$, \[z \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + (y - z) \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} + (x - y) \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} z + (y-z) + (x-y) \\ z + (y - z) \\ z \end{bmatrix} = \begin{bmatrix} x \\ y \\ z \end{bmatrix}. \]
So if there are so many bases out there for vector spaces, how do we find one? One way is to take advantage of tools we've already been working with.
Let $A$ be an invertible $n \times n$ matrix. Then the columns of $A$ are a basis for $\mathbb R^n$.
Since $A$ is invertible, the only solution to $A \mathbf x = \mathbf 0$ is $\mathbf 0$. Therefore, its columns are linearly independent. And because $A$ is invertible, we know that the linear equation $A \mathbf x = \mathbf b$ always has a solution. In other words, the columns of $A$ span $\mathbb R^n$. Since the columns of $A$ are both linearly independent and span $\mathbb R^n$, they form a basis for $\mathbb R^n$.
Consider again our friend the matrix $R = \begin{bmatrix} 1 & 3 & 0 & 1 \\ 0 & 0 & 1 & 5 \\ 0 & 0 & 0 & 0 \end{bmatrix}$. We want to find bases for its column and row spaces. Here, the choice of the pivot columns is obvious for a basis for the column space—they're the standard basis. This tells us that the column space of $R$ is a two-dimensional subspace inside of $\mathbb R^3$. But considering what we said about bases not being unique, this is not our only choice.
Now consider the row space of $R$. The two non-zero rows are the obvious choice. This tells us that the row space of $R$ is also a two-dimensional space, but this one is a subspace of $\mathbb R^4$.
Here, we've used the word dimension, but what does "dimension" really mean? There's an intuitive geometric definition—the number of "directions" that we have. But this breaks down very quickly after we leave $\mathbb R^3$ and go to higher-dimensional space.
Instead, we will think of the dimension of a space in terms of its basis. We think of the basis as having the "right" size—we have exactly as many vectors as we need and no more. So our notion of dimension will be based on this.
The dimension of a vector space $V$ is the number of vectors in a basis for $V$.
It may seem a bit strange for this number to be based on just the number of vectors, since we can have any number of bases. But the special property here really is the number. This definition comes from the following result.