Independence, Basis, and Dimension

A key fact to start: more unknowns than equations

Strang calls this “a key lecture” — the day the words independence, span, basis, and dimension “get assigned clear meanings.” And he’s careful about grammar from the first minute: a bunch of vectors is independent, spans a space, is a basis. We wouldn’t talk about a matrix being independent. The dimension is some number.

But first, a highly important fact he hadn’t called direct attention to earlier. Suppose $A$ has more columns than rows — $n$ unknowns, $m$ equations, with $n > m$. Then $A\mathbf{x} = \mathbf{0}$ has nonzero solutions: there is something in the null space of $A$ besides the zero vector.

Why? Not just because “more unknowns than equations seems solvable” — we have a clear algorithm. Elimination reaches echelon form with $n$ variables and at most $m$ pivots, so there will be free variables — at least $n - m$ of them. Assign a free variable a nonzero value (one, “or whatever I like”), solve for the pivot variables, and you have a solution to $A\mathbf{x} = \mathbf{0}$ that isn’t all zeros. Keep this fact in hand; the whole lecture leans on it.

Independence: no combination gives zero

The all-zero combination always gives zero, of course. The question is whether any other combination does. Examples, in the plane:

• A vector and twice that vector. $\mathbf{v}_1$ and $\mathbf{v}_2 = 2\mathbf{v}_1$ are dependent for sure — “if the word dependent means anything, these should be dependent.” Two of the first minus the second is zero: $2\mathbf{v}_1 - \mathbf{v}_2 = \mathbf{0}$.
• A vector and the zero vector. Say $\mathbf{v}_1 = (2, 1)$ and $\mathbf{v}_2 = (0, 0)$. Dependent again: take zero $\mathbf{v}_1$‘s and six $\mathbf{v}_2$‘s — or five — and you get zero. If the zero vector is in the bunch, “independence is dead.”
• Two vectors pointing different directions are independent: no combination gives zero except the zero combination.
• Three vectors in the plane — any three, drawn however carelessly — are dependent. Why must that be?

The answer is the key fact from the start. Put the three vectors into the columns of a matrix $A$ — say $\mathbf{v}_1 = (2, 1)$, $\mathbf{v}_2 = (1, 2)$, $\mathbf{v}_3 = (2.5, -1)$, making $A$ a $2 \times 3$ matrix. More columns than rows, so there are free variables, so there is a nonzero $\mathbf{c} = (c_1, c_2, c_3)$ with $A\mathbf{c} = \mathbf{0}$. That says exactly: go out some $\mathbf{v}_1$, out some more $\mathbf{v}_2$, back on $\mathbf{v}_3$, and end up at zero. Dependent.

This is the move the course has been rehearsing for lectures: a combination of the columns is just $A$ times the vector of $c$‘s, so dependence questions come back to the null space. (The abstract definition never mentioned a matrix — but most of the time our vectors are columns, and then this is the test.)

Spanning a space

We’ve actually seen the next word already. When we took a matrix’s columns and formed all their combinations, we got the column space. Those columns span the column space.

So “span” compresses “take all linear combinations” into one word. The columns of a matrix span the column space — always. Are they independent? Maybe yes, maybe no; it depends on the particular columns. What we’d really like is a set that spans and is independent — the right number of vectors. Fewer, and we wouldn’t have the whole space; more, and they wouldn’t be independent. The word for “just right” is coming.

Basis: enough vectors and not too many

Strang says he’ll always be asking for a basis now, because a basis tells you everything: give me a basis for a subspace and you’ve told me what that subspace is.

Example: bases for $\mathbb{R}^3$. The first basis that comes to mind:

$$\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \quad \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \quad \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}$$

That’s the $x$, $y$, $z$ axes — if those aren’t independent, we’re in trouble. In matrix language, put them in columns: you get the identity matrix, whose null space is only the zero vector. Independent, and they span. A basis. But far from the only one.

Another basis. Start with $(1, 1, 2)$ and $(2, 2, 5)$. Independent? Yes. Do they span $\mathbb{R}^3$? No — some vectors in $\mathbb{R}^3$ are not combinations of those two. We need a third vector, and it would be a goof to pick $(3, 3, 7)$: that’s the sum of the first two, it lies in their plane, and the attempt at a basis would be dead. Any vector not in that plane works — Strang tries $(3, 3, 8)$: “at least it’s not the sum of those two vectors,” and it does give a basis.

One more question, to be sure the idea has landed. Take just the two vectors $(1, 1, 2)$ and $(2, 2, 5)$ again. Are they a basis for anything? Sure — they’re independent, so they’re a basis for the space they span: a plane inside $\mathbb{R}^3$. Stick in $(3, 3, 7)$, which lies in that plane, and the three vectors still span the plane but are no longer a basis — independence is gone.

Every basis has the same size: dimension

The basis is not unique — “there’s zillions of bases.” Any invertible $3 \times 3$ matrix has columns that form a basis for $\mathbb{R}^3$. But all those bases share something, and you saw it coming: when Strang stopped at two vectors, you said “not a basis” because there weren’t enough vectors.

So the four words, in order: independence looks at combinations not being zero; spanning looks at all the combinations; basis combines the two; dimension counts the vectors in any basis.

A worked example: both dimensions of a matrix

Other bases for that column space work too: columns 1 and 3, or 2 and 3, or 2 and 4 — or vectors not among the columns at all, like $(2, 2, 2)$ and $(7, 5, 7)$ (that’s the sum of all four columns). Independent, and the count is right: two.

The lecture ends with the language merging into two formulas. The rank of $A$ — the number of pivot columns — is the dimension of the column space. (“Of course, you say. It had to be.”) But mind the grammar: a matrix has a rank; a subspace has a dimension. You don’t take the dimension of $A$ — you take the dimension of the column space of $A$. And for the null space: $n$ columns, $r$ of them pivots, leaves $n - r$ free variables.

$$\dim C(A) = r, \qquad \dim N(A) = n - r$$

That’s the key spaces, their bases, and their dimensions.

Problems

Work these before revealing the solutions — they’re exactly the questions “the homework asks, the quizzes ask, the final exam will ask.”

Problem 9.1 Testing independence

Are the vectors

$$\mathbf{v}_1 = \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix}, \quad \mathbf{v}_2 = \begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix}, \quad \mathbf{v}_3 = \begin{bmatrix} 4 \\ 5 \\ 2 \end{bmatrix}$$

independent or dependent? If dependent, give a nonzero combination that equals the zero vector.

Show solution

Put them in the columns of $A$ and look for a nonzero vector in the null space. Try to write $\mathbf{v}_3$ as $c_1\mathbf{v}_1 + c_2\mathbf{v}_2$: the third components force $c_1 = 2$, then the first components give $2 + 2c_2 = 4$, so $c_2 = 1$. Check the middle: $2(2) + 1(1) = 5$. ✓ So $\mathbf{v}_3 = 2\mathbf{v}_1 + \mathbf{v}_2$, and

$$2\mathbf{v}_1 + \mathbf{v}_2 - \mathbf{v}_3 = \mathbf{0}.$$

The vectors are dependent: $(2, 1, -1)$ is in the null space of the matrix with these columns, so the rank is $2$, less than $n = 3$.

Problem 9.2 Forced dependence

Explain, using pivots and free variables, why any four vectors in $\mathbb{R}^3$ must be dependent. Then state the general fact for $n$ vectors in $\mathbb{R}^m$.

Show solution

Put the four vectors in the columns of a matrix $A$, which is $3 \times 4$. Elimination produces at most $3$ pivots (one per row), so at most $3$ of the $4$ columns are pivot columns — at least one free variable is left over. Assign that free variable a nonzero value and solve for the pivot variables: this gives a nonzero $\mathbf{c}$ with $A\mathbf{c} = \mathbf{0}$, i.e. a nonzero combination of the four vectors equal to zero. Dependent.

In general: any $n$ vectors in $\mathbb{R}^m$ with $n > m$ are dependent, because the $m \times n$ matrix has at most $m$ pivots and therefore at least $n - m$ free variables.

Problem 9.3 Completing a basis

The vectors $\mathbf{v}_1 = (1, 0, 1)$ and $\mathbf{v}_2 = (1, 1, 0)$ are independent. (a) What space are they a basis for? (b) Give a third vector $\mathbf{v}_3$ so that $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3$ is a basis for $\mathbb{R}^3$, and a third vector that fails.

Show solution

(a) They are a basis for the space they span: the plane inside $\mathbb{R}^3$ consisting of all combinations $c_1\mathbf{v}_1 + c_2\mathbf{v}_2$. They span it by construction and they’re independent, so both basis requirements hold.

(b) Any vector not in that plane works. Take $\mathbf{v}_3 = (0, 0, 1)$: the matrix

$$\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}$$

row reduces with three pivots (subtract row 1 from row 3 to get $(0, -1, 1)$, then add row 2), so it is invertible and the columns are a basis for $\mathbb{R}^3$.

A choice that fails: $\mathbf{v}_3 = \mathbf{v}_1 + \mathbf{v}_2 = (2, 1, 1)$. It lies in the plane, the three vectors are dependent ($\mathbf{v}_1 + \mathbf{v}_2 - \mathbf{v}_3 = \mathbf{0}$), and the attempt at a basis is dead.

Problem 9.4 Both dimensions at once

For

$$A = \begin{bmatrix} 1 & 3 & 4 \\ 2 & 6 & 8 \\ 1 & 3 & 4 \end{bmatrix}$$

find a basis for the column space, a basis for the null space, and the dimensions of both. Check that the dimensions add to $n$.

Show solution

Every column is a multiple of the first: column 2 is $3 \times$ column 1, column 3 is $4 \times$ column 1. Elimination leaves one pivot, so the rank is $r = 1$.

Column space: the pivot column, $(1, 2, 1)$, is a basis by itself. $\dim C(A) = 1$ — the column space is a line in $\mathbb{R}^3$.

Null space: free variables $x_2, x_3$. Special solutions: set $(x_2, x_3) = (1, 0)$, then $x_1 + 3 = 0$ gives $(-3, 1, 0)$; set $(x_2, x_3) = (0, 1)$, then $x_1 + 4 = 0$ gives $(-4, 0, 1)$. These two are independent and span the null space, so they’re a basis and $\dim N(A) = n - r = 3 - 1 = 2$.

Check: $\dim C(A) + \dim N(A) = 1 + 2 = 3 = n$. ✓

Problem 9.5 Dimension does half the work

A subspace $S$ of $\mathbb{R}^4$ is known to have dimension $2$, and the vectors $\mathbf{w}_1 = (1, 1, 0, 0)$ and $\mathbf{w}_2 = (0, 1, 1, 0)$ both lie in $S$. Without any further information about $S$, show that $\mathbf{w}_1, \mathbf{w}_2$ is a basis for $S$.

Show solution

First, independence: $c_1\mathbf{w}_1 + c_2\mathbf{w}_2 = (c_1, c_1 + c_2, c_2, 0)$ equals zero only when $c_1 = 0$ (first component) and $c_2 = 0$ (third component). So they are independent.

Now use the lecture’s key point: if the dimension is known to be $2$ and we have $2$ independent vectors in the space, they are automatically a basis. Suppose they did not span $S$. Then some vector of $S$ is outside their span, and adjoining it gives $3$ independent vectors in $S$ — which could be extended to a basis of $S$ with at least $3$ vectors, contradicting the fact that every basis of $S$ has exactly $2$ vectors. So $\mathbf{w}_1, \mathbf{w}_2$ span $S$, and being independent as well, they are a basis.