Two pages ago you learned how a set spans a space. Last page you learned how a set can be linearly independent, so that nothing in it is dead weight. Put those together and you get the most useful kind of set in all of linear algebra: big enough to reach every vector, small enough that nothing in it is spare. A set like that is a grid, and a grid gives every point an address.
Give a friend two arrows and a point in the plane, and ask for directions: "so many steps of this arrow, then so many of that one." If the two arrows point different ways, there is exactly one answer, and the friend can find it for any point. That pair of arrows is called a basis, the two numbers are the point's address, and this page is about why the address is always there and always unique. Same thing in space, with three arrows.
Everything on this page comes from the last two: spanning gives every point an address, independence makes it the only one. Counting the arrows it takes is the second half of the page, and that count is the word "dimension" made precise.
The Linear Independence page ended with this: a set is independent exactly when removing any vector shrinks its span. So an independent spanning set is a spanning set with nothing to spare. Here's its name.
The definition is the two ideas from the last two pages, stapled together, plus one small thing: the vectors come in an order.
A basis for a vector space $\V$ is a list of vectors $u_1, u_2, \ldots, u_k$ in $\V$, written $\beta = \{u_1, u_2, \ldots, u_k\}$ and read in that order, that is linearly independent and spans $\V$.
A basis for $\R^2$, $\R^3$, or a line or plane through $0$ is a list of arrows $u_1, u_2, \ldots, u_k$ in it, written $\beta = \{u_1, u_2, \ldots, u_k\}$ and read in that order, that is linearly independent and whose span is the whole thing.
So checking a basis is always two jobs: show the list spans, and show it's independent. The order matters only for the addresses, which come later; the two jobs don't care about it. Here's the first basis everybody meets.
In $\R^n$, let $e_1 = (1, 0, 0, \ldots, 0)$, $e_2 = (0, 1, 0, \ldots, 0)$, $\ldots$, $e_n = (0, 0, \ldots, 0, 1)$. The list $\{e_1, e_2, \ldots, e_n\}$ is the standard basis for $\R^n$.
In $\R^3$, let $e_1 = (1, 0, 0)$, $e_2 = (0, 1, 0)$, and $e_3 = (0, 0, 1)$: one step along each axis. The list $\{e_1, e_2, e_3\}$ is the standard basis for $\R^3$, and $\{e_1, e_2\} = \{(1, 0), (0, 1)\}$ is the standard basis for $\R^2$.
Why is it a basis? Any vector $(a_1, \ldots, a_n)$ is $a_1e_1 + \cdots + a_ne_n$, so the $e_j$'s span $\R^n$. And if $a_1e_1 + \cdots + a_ne_n = 0$, then $(a_1, \ldots, a_n) = (0, \ldots, 0)$, so every coefficient is $0$: independence. One more, just so it's said: $\operatorname{span}(\emptyset) = \{0\}$ and the empty list is independent, so the empty list is a basis for the zero space.
Why is it a basis? Any point $(a, b, c)$ is $a$ steps along $e_1$, then $b$ along $e_2$, then $c$ along $e_3$, so the three arrows reach everything. And the only way $ae_1 + be_2 + ce_3 = (a, b, c)$ comes out as $0$ is $a = b = c = 0$: independent. One more, just so it's said: the zero space $\{0\}$ needs no arrows at all, so its basis is the empty list.
The empty list is a basis. Nothing spans nothing. Somebody put that on a poster.
The standard basis is not the only one, not even close. Here's one that tilts.
Show that $\beta = \{(2, 4), (1, 1)\}$ is a basis for $\R^2$.
It's linearly independent. Suppose $c_1(2, 4) + c_2(1, 1) = (0, 0)$. Matching coordinates, $2c_1 + c_2 = 0$ and $4c_1 + c_2 = 0$. Subtract: $2c_1 = 0$, so $c_1 = 0$, and then $c_2 = 0$. Only the trivial representation.
It spans $\R^2$. Take any $(x, y)$ and look for scalars with $c_1(2, 4) + c_2(1, 1) = (x, y)$:
$$\begin{aligned} 2c_1 + c_2 &= x \\ 4c_1 + c_2 &= y. \end{aligned}$$Subtracting gives $c_1 = \frac{y - x}{2}$, and then $c_2 = x - 2c_1 = 2x - y$. Those work for every $x$ and $y$, so every vector of $\R^2$ is in $\operatorname{span}(\beta)$.
Both jobs done, so $\beta$ is a basis for $\R^2$. (So is $\{(1, 1), (2, 4)\}$, the same arrows in the other order; the two jobs don't care which comes first.)
Here are the two arrows and their grid. Wherever the target goes, the formulas hand over the steps that reach it.
Look at what the spanning half actually found: a formula for the coefficients, and only one formula. For $(3, 5)$ it says $c_1 = 1$ and $c_2 = 1$, and there was no other choice. Same story in space.
Show that $\beta = \{\beta_1, \beta_2, \beta_3\}$ with $\beta_1 = (1, 0, 0)$, $\beta_2 = (1, 1, 0)$, $\beta_3 = (0, 0, 2)$ is a basis for $\R^3$, and write $x = (1, 2, 0)$ as a combination of it.
Set $c_1\beta_1 + c_2\beta_2 + c_3\beta_3 = (x, y, z)$ and match coordinates:
$$\begin{aligned} c_1 + c_2 &= x \\ c_2 &= y \\ 2c_3 &= z. \end{aligned}$$So $c_2 = y$, $c_1 = x - y$, and $c_3 = \tfrac{z}{2}$: a solution for every $(x, y, z)$, so $\beta$ spans $\R^3$. With $(x, y, z) = (0, 0, 0)$ the same formulas force $c_1 = c_2 = c_3 = 0$, so $\beta$ is independent. A basis.
For $x = (1, 2, 0)$ the formulas give $c_1 = 1 - 2 = -1$, $c_2 = 2$, $c_3 = 0$:
$$(1, 2, 0) = -\beta_1 + 2\beta_2 + 0\beta_3.$$In space: three arrows that span a box, and a chain of them that lands on $x$.
Both examples found one recipe per vector, and that's not luck. It's the superpower.
Let $\beta = \{u_1, u_2, \ldots, u_k\}$ be a list of vectors in a vector space $\V$. Then $\beta$ is a basis for $\V$ exactly when every $v$ in $\V$ can be written as
$$v = c_1u_1 + c_2u_2 + \cdots + c_ku_k$$for exactly one list of scalars $c_1, c_2, \ldots, c_k$.
Suppose $\beta$ is a basis. Since $\beta$ spans $\V$, every $v$ is some combination $c_1u_1 + \cdots + c_ku_k$. Suppose $v = d_1u_1 + \cdots + d_ku_k$ as well. Subtracting,
$$0 = (c_1 - d_1)u_1 + (c_2 - d_2)u_2 + \cdots + (c_k - d_k)u_k.$$Since $\beta$ is linearly independent, every coefficient is $0$: $c_i = d_i$ for each $i$. So the representation is unique.
Conversely, suppose every $v$ has exactly one representation. Then every $v$ is in $\operatorname{span}(\beta)$, so $\beta$ spans $\V$. And $0 = 0u_1 + \cdots + 0u_k$ is a representation of $0$; since it's the only one, the trivial representation is the only way to write $0$, which is linear independence. So $\beta$ is a basis. $\blacksquare$
This is a visual argument, not a formal proof. Spanning says every point has at least one route from the origin along the arrows. Suppose some point had two different routes. Walk the first route out and the second route back: you end up home, and you used at least one arrow a different number of times going out than coming back. That's a loop, a nontrivial relation, which an independent set can't have.
It runs backward too: if every point has exactly one route, then $0$ has only the standing-still route, and that is independence. The full proof is in the n version.
Read the two halves side by side. Spanning is what makes a recipe exist. Independence is what makes it unique. Lose either one and the theorem breaks. Try breaking it yourself: drag the tips of $u_1$ and $u_2$ to pick a basis of $\R^2$, then drag $v$ around. The grid is drawn in steps of $u_1$ and $u_2$, so you can read the coefficients straight off it.
When $u_1$ and $u_2$ line up, the grid collapses onto one line. Every $v$ off that line can't be reached at all (not spanning), and every $v$ on it can be reached in infinitely many ways (not independent). A basis is exactly the setup where neither of those happens.
A basis has to do both jobs, and checking only one is the classic slip. $\{(1, 0), (0, 1), (1, 1)\}$ spans $\R^2$, but it's dependent, so it's not a basis. $\{(1, 2)\}$ is independent, but it only spans a line, so it's not a basis for $\R^2$ either (it is a basis for that line). Other books write a basis with angle brackets, ⟨u₁, u₂⟩, or call it an "ordered basis" to stress the order; here every basis is read in order, and the set braces stay.
The unique recipe deserves a name, because it's an address: once you've agreed on a basis, the list of coefficients pins a vector down completely, and different vectors get different lists. The order of the basis is what tells you which number goes first.
Let $\beta = \{u_1, u_2, \ldots, u_k\}$ be a basis, and write $x = c_1u_1 + c_2u_2 + \cdots + c_ku_k$ in the one way it can be written. The coordinate vector of $x$ relative to $\beta$ is $[x]_\beta = (c_1, c_2, \ldots, c_k)$, and the numbers $c_1, \ldots, c_k$ are the coordinates of $x$ relative to $\beta$.
Finding coordinates is solving a system, the same system the spanning check solves, with a specific right side.
Let $\beta = \{(1, 1), (0, 2)\}$, a basis for $\R^2$. Find $[x]_\beta$ for $x = (3, 2)$.
Solve $c_1(1, 1) + c_2(0, 2) = (3, 2)$. The first coordinate says $c_1 = 3$; the second says $3 + 2c_2 = 2$, so $c_2 = -\tfrac{1}{2}$. Check: $3(1, 1) - \tfrac{1}{2}(0, 2) = (3, 3 - 1) = (3, 2)$. So
$$[x]_\beta = \left(3, -\tfrac{1}{2}\right).$$Half a step backward is a perfectly good step. And in the standard basis the coordinates are just the entries: $[x]_{\{e_1, e_2\}} = (3, 2)$, because $(3, 2) = 3e_1 + 2e_2$. That's why you never noticed the standard basis was there.
The walk on the grid, and the same walk written in the other order.
List the same two arrows the other way round, $\gamma = \{(0, 2), (1, 1)\}$, and the same walk reads $[x]_\gamma = \left(-\tfrac{1}{2}, 3\right)$. The point didn't move; the address format did. That's the whole reason a basis is a list and not just a set.
Coordinates turn any vector space with a basis of $k$ vectors into $\R^k$: every $x$ becomes its list $[x]_\beta$. The next theorem says the arithmetic survives the translation, which is what lets the later pages do everything with matrices.
Let $\beta$ be a basis. For any vectors $u, v$ and scalar $c$,
$$[u + v]_\beta = [u]_\beta + [v]_\beta \quad\text{and}\quad [cu]_\beta = c[u]_\beta.$$So a relation $a_1v_1 + \cdots + a_mv_m = 0$ holds among vectors exactly when the same relation holds among their coordinate vectors.
Write $u = a_1u_1 + \cdots + a_ku_k$ and $v = b_1u_1 + \cdots + b_ku_k$, so $[u]_\beta = (a_1, \ldots, a_k)$ and $[v]_\beta = (b_1, \ldots, b_k)$. Adding and regrouping,
$$u + v = (a_1 + b_1)u_1 + \cdots + (a_k + b_k)u_k,$$and by the uniqueness theorem that is the representation of $u + v$, so $[u + v]_\beta = (a_1 + b_1, \ldots, a_k + b_k) = [u]_\beta + [v]_\beta$. Likewise $cu = (ca_1)u_1 + \cdots + (ca_k)u_k$ gives $[cu]_\beta = c[u]_\beta$.
For the last sentence: by the two rules, $[a_1v_1 + \cdots + a_mv_m]_\beta = a_1[v_1]_\beta + \cdots + a_m[v_m]_\beta$. The left side is $[0]_\beta = (0, \ldots, 0)$ exactly when $a_1v_1 + \cdots + a_mv_m = 0$, since $0$ is the only vector whose coordinates are all $0$. $\blacksquare$
This is a visual argument, not a formal proof. On the grid of a basis, $u + v$ is the far corner of the parallelogram with sides $u$ and $v$, and the grid steps to that corner are the steps to $u$ plus the steps to $v$. Doubling an arrow doubles every step along it.
So a chain of arrows that comes home has coordinate vectors that add up to $(0, 0)$, and the other way around. The full proof is in the n version.
Now read a few addresses yourself. Each round shows a basis, its grid, and a point; pick the point's coordinate vector, and the chain shows where your pick really lands. Watch the last round.
Your turn with numbers. In free response, type the coordinates in the basis's order, separated by commas, like 3, -1/2.
Loading practice engine...
Suppose a list $S$ spans $\V$, but it has some dead weight. The Linear Independence page already told you what to do: throw out vectors that are combinations of the others. The next theorem turns that into a process, and promises it always ends with a basis.
If a vector space $\V$ is spanned by a finite list $S$, then some sublist of $S$ is a basis for $\V$. In particular, $\V$ has a finite basis.
If every vector of $S$ is $0$ (or $S$ is empty), then $\V = \{0\}$ and the empty list is a basis inside $S$. Otherwise go through $S$ in order, keeping a vector when it is not in the span of the vectors kept so far and tossing it when it is. Each kept vector is outside the span of the earlier kept ones, so by the Linear Independence page the kept list $\beta$ stays linearly independent at every step.
It remains to show $\beta$ spans $\V$. Every tossed vector was in the span of vectors kept before it, so every vector of $S$ is in $\operatorname{span}(\beta)$. Then $\operatorname{span}(\beta)$ is a subspace containing $S$, so by the smallest-subspace theorem it contains $\operatorname{span}(S) = \V$. So $\beta$ is an independent sublist of $S$ that spans $\V$: a basis. $\blacksquare$
This is a visual argument, not a formal proof. Go through the arrows in order. Keep an arrow when it points somewhere the kept arrows can't already reach; toss it when it lies inside their span. Every kept arrow grows the span by a whole kind: a point becomes a line, a line becomes a plane, a plane becomes all of space. That can happen at most three times, so the process stops, and when it stops every arrow of $S$ sits inside the span of the kept ones.
The kept arrows are independent (each one left the span of the ones before it) and they reach everything $S$ reaches: a basis. The picture leans on the Subspaces page's four kinds. The full proof is in the n version.
The proof is really a recipe: keep what's new, toss what's already in the span. Here it is on real numbers.
The list
$$S = \{(2, -1, 2), (-4, 2, -4), (1, 2, 0), (5, 0, 4), (0, 1, 3)\}$$spans $\R^3$. Find a sublist of $S$ that is a basis for $\R^3$.
Call the vectors $u_1, \ldots, u_5$ and run the process.
The process kept $\beta = \{(2, -1, 2), (1, 2, 0), (0, 1, 3)\}$. It's linearly independent by construction, and by the theorem it's a basis for $\R^3$.
Watch the span grow as the arrows come up: a line, a plane, then everything, with $u_2$ and $u_4$ caught inside.
Now you run it. Each vector comes up in order; keep it or toss it. The purple shows the span of what you've kept so far: a point, then a line, then a plane, and then (if you get there) everything. Drag the background to turn the picture.
Mission 2 is the reminder that "$\V$" doesn't have to be all of $\R^3$. Its list only spans a plane, so the process hands you a basis for that plane, with two vectors. The theorem works for whatever space $S$ spans.
The basis you end up with depends on the order you go through $S$. Start the example above with $u_3$ and you'd keep a different trio. What doesn't change is how many you keep. That's not obvious at all, and it's what the next section proves.
Five little systems is a lot of work. There's a faster way: line the vectors up as the columns of a matrix and eliminate once.
Let $A$ be the matrix whose columns are $u_1, \ldots, u_m$, and row reduce $A$ to a row echelon form. The columns of $A$ in the pivot positions form a basis for $\operatorname{span}\{u_1, \ldots, u_m\}$, and they are exactly the columns the keep-or-toss process keeps. In particular,
$$\dim\operatorname{span}\{u_1, \ldots, u_m\} = \operatorname{rank}(A),$$where $\dim$ is the number of vectors in a basis, defined properly below.
Let $R$ be the reduced row echelon form of $A$. Row operations don't change the solutions of $Ax = 0$ (Systems), and by the column picture a solution $x$ of $Ax = 0$ is a relation $x_1u_1 + \cdots + x_mu_m = 0$ among the columns. So $A$ and $R$ have exactly the same relations among their columns, in the same positions.
In $R$ the relations are easy to read. A pivot column of $R$ is a standard vector $e_i$, so the pivot columns are independent. A non-pivot column of $R$ has nonzero entries only in the pivot rows above it, so it equals the combination of the earlier pivot columns with those entries as coefficients. Carry both facts back to $A$: the pivot columns of $A$ are independent, and every other column of $A$ is a combination of the pivot columns before it. So every column of $A$ is in the span of the pivot columns, and the pivot columns are a basis for the span of all the columns.
Keep-or-toss keeps a column exactly when it is not a combination of the earlier kept columns. By the relations just read off, that happens exactly at the pivot columns. The count of pivot columns is $\operatorname{rank}(A)$ (Rank & Inverses). $\blacksquare$
This is a visual argument, not a formal proof. $Ax$ is a chain of the columns of $A$, so a chain that comes home is a solution of $Ax = 0$. Row operations never change which $x$'s solve $Ax = 0$ (the Systems page: they swing the planes around a line that never moves), so they never change which chains of columns come home. After elimination the loops are visible: a column without a pivot is a chain of the pivot columns before it, and the pivot columns themselves make no loops. Those facts were true of the original columns all along.
The next example runs it on the five vectors you just saw. The full proof is in the n version.
Same five vectors, one elimination.
Find a basis for $\operatorname{span}(S)$, with the same five vectors $S = \{(2, -1, 2), (-4, 2, -4), (1, 2, 0), (5, 0, 4), (0, 1, 3)\}$, by elimination.
Put the vectors in as columns and reduce:
$$A = \begin{pmatrix} 2 & -4 & 1 & 5 & 0 \\ -1 & 2 & 2 & 0 & 1 \\ 2 & -4 & 0 & 4 & 3 \end{pmatrix} \xrightarrow[R_3 \to R_3 - R_1]{R_2 \to 2R_2 + R_1} \begin{pmatrix} 2 & -4 & 1 & 5 & 0 \\ 0 & 0 & 5 & 5 & 2 \\ 0 & 0 & -1 & -1 & 3 \end{pmatrix} \xrightarrow{R_3 \to 5R_3 + R_2} \begin{pmatrix} 2 & -4 & 1 & 5 & 0 \\ 0 & 0 & 5 & 5 & 2 \\ 0 & 0 & 0 & 0 & 17 \end{pmatrix}.$$Pivots in columns $1$, $3$, and $5$. So columns $1$, $3$, $5$ of $A$, which are $(2, -1, 2)$, $(1, 2, 0)$, $(0, 1, 3)$, form a basis for $\operatorname{span}(S)$: the same three the process kept, and $\operatorname{rank}(A) = 3$ says the span is all of $\R^3$. The relations are in there too: column $2$ is $-2$ times column $1$, and column $4$ is $2$ times column $1$ plus column $3$, in $A$ just as in the echelon form.
Your turn at keep-or-toss, either way you like. In free response, type the numbers of the vectors that are kept, like 1, 3, 5.
Loading practice engine...
Here's the big one. Different orders through $S$ gave different bases, but always the same number of vectors. The tool that proves it is a swap: trade one vector of a basis for a new one, and you still have a basis, as long as the new vector actually uses the one it replaces.
The Exchange Lemma. Let $\beta = \{u_1, \ldots, u_k\}$ be a basis for $\V$, and let $v = c_1u_1 + \cdots + c_ku_k$ with $c_i \neq 0$. Then replacing $u_i$ by $v$ gives another basis for $\V$.
Call the new list $\hat\beta = \{u_1, \ldots, u_{i-1}, v, u_{i+1}, \ldots, u_k\}$.
$\hat\beta$ is independent. Suppose $d_1u_1 + \cdots + d_iv + \cdots + d_ku_k = 0$. Substitute $v = c_1u_1 + \cdots + c_ku_k$ and collect: the coefficient of $u_i$ is $d_ic_i$, and the coefficient of each other $u_j$ is $d_j + d_ic_j$. Since $\beta$ is independent, every coefficient is $0$. From $d_ic_i = 0$ and $c_i \neq 0$ we get $d_i = 0$, and then $d_j = 0$ for every $j$. Only the trivial relation.
$\hat\beta$ spans $\V$. Solving $v = c_1u_1 + \cdots + c_ku_k$ for $u_i$ (allowed because $c_i \neq 0$) writes $u_i$ as a combination of the vectors of $\hat\beta$. So every vector of $\beta$ is in $\operatorname{span}(\hat\beta)$, and $\operatorname{span}(\hat\beta)$ is a subspace containing $\beta$, hence containing $\operatorname{span}(\beta) = \V$ (Span). $\blacksquare$
This is a visual argument, not a formal proof. A basis of $\R^3$ is three arrows spanning a box. If $v$ uses $u_1$ (its coefficient on $u_1$ isn't $0$), then $v$ pokes out of the plane of $u_2$ and $u_3$, so swapping it in for $u_1$ leaves a box: still a basis. If $v$ doesn't use $u_3$, it lies in the plane of $u_1$ and $u_2$, and swapping it in for $u_3$ leaves three arrows in one plane, flat: no basis.
So you may trade $v$ for any arrow it actually uses. The full proof is in the n version.
Here's the swap with the numbers from before.
$\beta = \{(1, 0, 0), (1, 1, 0), (0, 0, 2)\}$ is a basis for $\R^3$, and $v = (1, 2, 0) = -\beta_1 + 2\beta_2 + 0\beta_3$. Which basis vectors can $v$ replace?
$v$'s coefficients on $\beta_1$ and $\beta_2$ are $-1$ and $2$, both nonzero, so $v$ can replace either one: $\{(1, 2, 0), (1, 1, 0), (0, 0, 2)\}$ and $\{(1, 0, 0), (1, 2, 0), (0, 0, 2)\}$ are both bases for $\R^3$. (Check the first: $c_1(1, 2, 0) + c_2(1, 1, 0) + c_3(0, 0, 2) = (x, y, z)$ gives $c_3 = \tfrac{z}{2}$, and the first two coordinates, $c_1 + c_2 = x$ and $2c_1 + c_2 = y$, give $c_1 = y - x$, $c_2 = 2x - y$: one solution for every $(x, y, z)$.)
The coefficient on $\beta_3$ is $0$, so the lemma doesn't allow that swap, and indeed $\{(1, 0, 0), (1, 1, 0), (1, 2, 0)\}$ is not a basis: all three vectors have last coordinate $0$, so nothing with $z \neq 0$ is in their span.
Now the payoff. Feed the vectors of one basis into another, one swap at a time, and count.
Let $\V$ be a vector space with a finite basis. Then every basis for $\V$ has the same number of vectors.
Among all bases for $\V$, pick one of smallest size, $\beta = \{u_1, \ldots, u_n\}$, and let $\gamma = \{w_1, w_2, \ldots\}$ be any other basis. By the choice of $\beta$, $\gamma$ has at least $n$ vectors. We show it has at most $n$.
$w_1$ is in $\V = \operatorname{span}(\beta)$, so $w_1 = c_1u_1 + \cdots + c_nu_n$, and some $c_i \neq 0$ because $w_1 \neq 0$. By the Exchange Lemma, swapping $w_1$ in for that $u_i$ gives a basis $\beta_1$ with one $w$ and $n - 1$ $u$'s.
Repeat. Suppose $\beta_k$ is a basis holding $w_1, \ldots, w_k$ and $n - k$ of the $u$'s, with $k < n$. Since $\gamma$ has at least $n$ vectors there is a $w_{k+1}$; write it as a combination of $\beta_k$. Some $u$ in that combination has a nonzero coefficient, for otherwise $w_{k+1}$ would be a combination of $w_1, \ldots, w_k$, a nontrivial relation in the independent list $\gamma$. Swap $w_{k+1}$ in for that $u$: a basis $\beta_{k+1}$ with one more $w$ and one less $u$.
After $n$ swaps, $\beta_n = \{w_1, \ldots, w_n\}$ is a basis for $\V$. If $\gamma$ had another vector $w_{n+1}$, it would be in $\operatorname{span}(\beta_n)$, a combination of $w_1, \ldots, w_n$, again contradicting the independence of $\gamma$. So $\gamma$ has exactly $n$ vectors. $\blacksquare$
This is a visual argument, not a formal proof. In $\R^3$: a basis can't have four arrows, because four arrows in space always close a loop (the too-many theorem), and it can't have two, because two arrows fill at most a plane and space has points off every plane. So every basis of $\R^3$ has exactly three arrows, and the same reasoning gives two for a plane and one for a line.
The full proof swaps one basis into another, one arrow at a time, with the Exchange Lemma, and counts. It is in the n version.
Trade deadline in $\R^3$: we're sending $u_1$ to the other basis for $w_1$, a vector to be named later, and future considerations.
Since every basis has the same size, that size belongs to the space itself, not to whichever basis you happened to pick. So it gets a name.
A vector space is finite-dimensional if it has a basis with finitely many vectors.
$\R^n$ and every subspace of it are finite-dimensional (a subspace's basis is shown below), so on this course the word is a formality. Spaces of functions can need infinitely many basis vectors; they aren't on the syllabus.
The dimension of a vector space $\V$ with a finite basis, written $\dim(\V)$, is the number of vectors in any basis for $\V$.
Infinite-dimensional spaces exist. I'm choosing not to think about them. I can barely hold three in my head.
Count a few bases and the number comes out the way it should.
Find $\dim(\R^n)$,$\dim(\R^3)$, $\dim(\{0\})$, and the dimensions of a line and a plane through the origin in $\R^3$.
The standard basis $\{e_1, \ldots, e_n\}$ has $n$ vectors, so $\dim(\R^n) = n$. (Good news: the word "dimension" means what you always thought it meant.)
The standard basis $\{e_1, e_2, e_3\}$ has three arrows, so $\dim(\R^3) = 3$, and $\dim(\R^2) = 2$. (Good news: the word "dimension" means what you always thought it meant.)
The empty list is a basis for $\{0\}$, so $\dim(\{0\}) = 0$.
A line through the origin is $\operatorname{span}\{u\}$ for some nonzero $u$, and $\{u\}$ is independent. So $\{u\}$ is a basis, and the line has dimension $1$. A plane through the origin is the span of two vectors pointing different ways, and two such vectors are independent, so it has dimension $2$.
The ladder of subspaces, with its dimensions.
Knowing the dimension is a huge shortcut, because it tells you how many vectors a basis has to have before you check anything, and with the right count one of the two jobs comes free.
Let $\V$ be a vector space with $\dim(\V) = n$.
(a) Any linearly independent list in $\V$ has at most $n$ vectors.
(b) Any list that spans $\V$ has at least $n$ vectors.
(c) A list of exactly $n$ vectors in $\V$ is a basis as soon as it is linearly independent, and as soon as it spans $\V$.
(d) Every linearly independent list in $\V$ can be extended to a basis for $\V$ by adding vectors.
(a) Let $\beta$ be a basis with $n$ vectors and $L$ an independent list. The swapping in the proof of the same-size theorem never used that $\gamma$ spans, only that it is independent and that each new vector exists. Run it with $L$ in place of $\gamma$: if $L$ had $n + 1$ vectors, the $(n + 1)$st would be a combination of the first $n$, contradicting independence.
(d) Let $L$ be independent. If $\operatorname{span}(L) \neq \V$, pick a vector of $\V$ outside the span and add it; the longer list is still independent (Linear Independence). By (a) this can happen at most $n - |L|$ times, so eventually the list spans $\V$, and it's a basis.
(b) A spanning list contains a basis (above), and that basis has $n$ vectors, so the list has at least $n$.
(c) If $n$ vectors are independent, extend them to a basis by (d); the basis has $n$ vectors, so nothing was added: the list was already a basis. If $n$ vectors span $\V$, shrink them to a basis; the basis has $n$ vectors, so nothing was removed. $\blacksquare$
This is a visual argument, not a formal proof. Take three arrows in $\R^3$. Either they lie in one plane or they don't. If they do, a chain of them comes home (dependent) and the points above the plane are out of reach (not spanning): they fail both jobs. If they don't, no chain comes home and they span a box that fills space: they pass both jobs. So for three arrows, one test settles the other, which is (c).
(a) and (b) are the same-size picture again: four arrows loop, two arrows miss. For (d), an independent pair spans a plane, and any arrow off that plane completes a basis. The full proof is in the n version.
Part (c) is the one you'll use constantly. If you have the right number of vectors, you only have to do one of the two jobs.
Is $\beta = \{(1, -2, 0), (0, 3, 1), (2, 0, -1)\}$ a basis for $\R^3$?
It has $3$ vectors and $\dim(\R^3) = 3$, so by part (c) it's enough to check independence. Suppose
$$a(1, -2, 0) + b(0, 3, 1) + c(2, 0, -1) = (0, 0, 0).$$Matching coordinates:
$$\begin{aligned} a + 2c &= 0 \\ -2a + 3b &= 0 \\ b - c &= 0. \end{aligned}$$The third equation says $b = c$ and the first says $a = -2c$. Put both into the second: $4c + 3c = 7c = 0$, so $c = 0$, and then $a = b = 0$. Only the trivial representation, so $\beta$ is linearly independent, and therefore a basis for $\R^3$. No need to show it spans: part (c) did that for free. (The triple product is $-7$: a real box, not a flat one.)
The count has to be exactly right, though, or the shortcut is off.
Part (c) only works when the count is exactly right. Two independent vectors in $\R^3$ are not a basis for $\R^3$; they're one short (by (b), anything that spans $\R^3$ needs at least $3$). And four vectors in $\R^3$ can never be a basis, because by (a) an independent list in $\R^3$ has at most $3$. Count first. Sometimes counting is the whole answer.
Pick out the one set that passes both jobs. The answers are sets, so this one stays multiple choice.
Loading practice engine...
Part (d) says an independent list that's too short can always be finished. The recipe is in its proof: add a vector the span doesn't already reach.
$u_1 = (1, 2, 0)$ and $u_2 = (0, 1, 1)$ are linearly independent. Which of $w = (1, 3, 1)$ and $w = (0, 0, 1)$ extends $\{u_1, u_2\}$ to a basis for $\R^3$?
Three independent vectors in $\R^3$ are a basis, and adding $w$ keeps independence exactly when $w \notin \operatorname{span}\{u_1, u_2\}$. So test each $w$ for the span: $au_1 + bu_2 = (a, 2a + b, b)$.
$w = (1, 3, 1)$: $a = 1$, $b = 1$, and the middle is $2 + 1 = 3$. It matches, so $w = u_1 + u_2$ is in the span. No good.
$w = (0, 0, 1)$: $a = 0$, $b = 1$, and the middle should be $0$ but $2a + b = 1$. Not in the span, so $\{(1, 2, 0), (0, 1, 1), (0, 0, 1)\}$ is independent, and by part (c) a basis for $\R^3$.
One candidate lands in the plane of $u_1$ and $u_2$; the other sticks out of it.
Your turn to finish a basis. In free response, type any vector that works, like 1, 0, 2; there are many right answers, and the checker tests yours.
Loading practice engine...
A subspace sits inside $\V$, so it seems like it should be "smaller." Dimension makes that precise, and it finally settles a claim from the Subspaces page.
Let $\W$ be a subspace of a vector space $\V$ with $\dim(\V) = n$. Then $\W$ has a finite basis and $\dim(\W) \leq \dim(\V)$. Moreover, if $\dim(\W) = \dim(\V)$, then $\W = \V$.
If $\W = \{0\}$, the empty list is a basis and $\dim(\W) = 0 \leq n$. Otherwise pick a nonzero $x_1$ in $\W$; $\{x_1\}$ is independent. Keep going: while the independent list $\{x_1, \ldots, x_k\}$ doesn't span $\W$, pick a vector of $\W$ outside its span and add it; the list stays independent (Linear Independence). Every list built this way is an independent list in $\V$, so by part (a) it has at most $n$ vectors, and the process must stop. When it stops, the list spans $\W$: a basis for $\W$ with $k \leq n$ vectors, so $\dim(\W) = k \leq n$.
If $\dim(\W) = n$, a basis for $\W$ is a list of $n$ independent vectors in $\V$, hence a basis for $\V$ by part (c). Then $\W = \operatorname{span}(\text{that basis}) = \V$. $\blacksquare$
This is a visual argument, not a formal proof. Let $\W$ be a plane through $0$ in $\R^3$, with its basis of two arrows. Any arrow of $\R^3$ off the plane extends those two to a basis of all of space, so $\W$'s basis is part of a basis of $\R^3$: it can't be longer. And $\W$ can't have three independent arrows, because a third arrow inside the plane always loops with the first two; three independent arrows would span a box, all of space, so a subspace of dimension $3$ is $\R^3$ itself.
The full proof is in the n version.
Here's the claim it settles: the list of subspaces of $\R^3$ on the Subspaces page really is complete.
Every subspace of $\R^3$ is one of these: the zero subspace $\{0\}$ (dimension $0$), a line through $0$ (dimension $1$), a plane through $0$ (dimension $2$), or all of $\R^3$ (dimension $3$). Every subspace of $\R^2$ is $\{0\}$, a line through $0$, or $\R^2$.
Let $\W$ be a subspace of $\R^3$. By the theorem, $\dim(\W)$ is $0$, $1$, $2$, or $3$. If it's $0$, the basis is empty and $\W = \{0\}$. If it's $1$, $\W = \operatorname{span}\{u\}$ for a nonzero $u$: a line through $0$. If it's $2$, $\W = \operatorname{span}\{u, v\}$ with $u, v$ independent, so neither is a multiple of the other: a plane through $0$ (Lines & Planes). If it's $3$, $\W = \R^3$ by the theorem's last sentence. The same argument in $\R^2$ stops at dimension $2$. $\blacksquare$
On the Subspaces page this was the four kinds picture, with a promise that the counting would be checked properly. Here's the check: a subspace's dimension is a whole number from $0$ to $3$, a basis of one arrow spans a line, a basis of two arrows spans a plane, and dimension $3$ means all of space. There's no room for a fifth kind, or for anything "one and a half dimensional" between a line and a plane.
Most subspaces you'll meet are cut out by equations, and the way to get the dimension is to solve the equations and count the free unknowns. Each free unknown hands you one basis vector.
Find a basis for, and the dimension of, the plane $\W = \{(x, y, z) \in \R^3 : x - 2y + 3z = 0\}$.
Solve for $x$: $x = 2y - 3z$, with $y$ and $z$ free. Every vector of $\W$ looks like
$$(2y - 3z, \ y, \ z) = y(2, 1, 0) + z(-3, 0, 1).$$So $\{(2, 1, 0), (-3, 0, 1)\}$ spans $\W$. It's independent too: look at the last two coordinates, which are $y$ and $z$ themselves, so $y(2, 1, 0) + z(-3, 0, 1) = 0$ forces $y = z = 0$. That's a basis with $2$ vectors, so $\dim(\W) = 2$: a plane, as promised. And the coordinates of a vector of $\W$ in this basis are just its free unknowns, $(y, z)$.
The two basis arrows lie in the plane, square to its normal vector, and their grid covers it.
Nothing changes with more unknowns and more equations.
Find a basis for, and the dimension of,
$$\W = \{(x_1, x_2, x_3, x_4) \in \R^4 : x_1 + x_2 - x_3 = 0, \ x_2 = 2x_4\}.$$The second equation gives $x_2 = 2x_4$, and then the first gives $x_1 = x_3 - x_2 = x_3 - 2x_4$. Nothing restricts $x_3$ or $x_4$, so they're free. Every vector of $\W$ looks like
$$(x_3 - 2x_4, \ 2x_4, \ x_3, \ x_4) = x_3(1, 0, 1, 0) + x_4(-2, 2, 0, 1).$$So $\{(1, 0, 1, 0), (-2, 2, 0, 1)\}$ spans $\W$, and it's independent by the same trick (the third and fourth coordinates are $x_3$ and $x_4$). A basis with $2$ vectors, so $\dim(\W) = 2$. Two equations in four unknowns, two free unknowns, dimension $2 \leq 4$.
In both examples the dimension came out as unknowns minus equations. Be careful with that.
"Unknowns minus equations" is a shortcut, not a rule, and it fails when one equation is secretly a combination of the others. If $\W$ in $\R^3$ is cut out by $x - y + z = 0$ and $2x - 2y + 2z = 0$, the second equation is just the first doubled, so it cuts nothing new: $\dim(\W) = 2$, not $1$. Count the free unknowns after you solve. (In matrix language: the dimension is the number of unknowns minus the rank, never minus the number of rows.)
Your turn. In free response, type the dimension as a number.
Loading practice engine...
"Count the free unknowns" is about to become a theorem. The solutions of $Ax = 0$ form a subspace whose dimension is the number of unknowns minus $\operatorname{rank}(A)$, and the span of $A$'s columns has dimension $\operatorname{rank}(A)$; add them and you get the number of columns. The next page draws all four of a matrix's subspaces and shows how they fit together.
A screen makes a color from three numbers: how much red, green, and blue light to emit. In a simple linear model, a color is a vector $(r, g, b)$, mixing two lights adds their vectors, and turning a light up scales it, so colors live in $\R^3$ and the three primaries are the standard basis. A projector doesn't have to use those three lamps.
A projector's three lamps emit the colors $L_1 = (1, 1, 0)$, $L_2 = (0, 1, 1)$, and $L_3 = (1, 0, 1)$ at full power, and a lamp at power $c$ emits $c$ times its color. An artist asks for the color $t = (0.7, 0.5, 0.4)$. Can the projector make it, and at what powers? What if only the first two lamps worked?
The question is whether $t$ is in $\operatorname{span}\{L_1, L_2, L_3\}$, and with what coefficients. First the count: three vectors in $\R^3$, so they're a basis as soon as they're independent. Suppose $aL_1 + bL_2 + cL_3 = 0$: coordinate by coordinate, $a + c = 0$, $a + b = 0$, $b + c = 0$. Adding all three, $2(a + b + c) = 0$, so $a + b + c = 0$, and subtracting each equation from that gives $b = a = c = 0$. Independent, so a basis: every color is a combination of the lamps, in exactly one way.
For $t$: $a + c = 0.7$, $a + b = 0.5$, $b + c = 0.4$. Adding, $a + b + c = 0.8$, so $b = 0.1$, $c = 0.3$, $a = 0.4$. Check: $0.4(1, 1, 0) + 0.1(0, 1, 1) + 0.3(1, 0, 1) = (0.7, 0.5, 0.4)$. The powers are the coordinates of $t$ in the lamp basis: $[t]_{\{L_1, L_2, L_3\}} = (0.4, 0.1, 0.3)$.
With only $L_1$ and $L_2$, the reachable colors are $aL_1 + bL_2 = (a, a + b, b)$, a plane: the green entry is always the red plus the blue. For $t$ that would need $0.5 = 0.7 + 0.4$. Two lamps span a two-dimensional slice of color space, and $t$ is off it.
Real displays work this way with real measurements: a color's coordinates in one device's basis are converted to another's by solving exactly this kind of system, and a color whose coordinates come out negative is one that device can't show. The conversion itself is a matrix, which is where the Linear Maps pages are headed.
The toolkit for this page: a basis spans and is independent, so every vector has exactly one set of coordinates, listed in the basis's order. To find a basis inside a spanning set, keep what's new and toss what's already in the span, or eliminate and read off the pivot columns. Every basis of a space has $\dim(\V)$ vectors, with exactly that many checking one of the two jobs is enough, and a subspace's dimension never exceeds the space's.
Every question so far came right after its idea, which is a hint a quiz never gives you. Down here the hint is gone. First, true or false: a claim from anywhere on this page, and you decide whether it holds.
Loading practice engine...
Next, a mixed set: every question type on this page, shuffled. Type coordinates and vectors on one line with commas, like 3, -1/2, and a dimension as a number. The which-set questions stay multiple choice.
Loading practice engine...
Made it this far? Time for something with a little heat. Two vectors are fixed and a third has one unknown entry $k$. For exactly one $k$ the three stop being a basis. Count first (three vectors in $\R^3$, so it's all about independence), then find the $k$ that flattens the box. In free response, type the number.
Loading practice engine...