Week 2 — Linear independence, bases, and dimension

Where this week starts

Week 1 handed you objects and no way to compare them: vector spaces over a field \(F\), subspaces, \(\operatorname{span}(S)\), the sum \(U + X\) and the internal direct sum \(U \oplus X\). What you do not have is a number. Nothing in the eight axioms says \(\mathbb{R}^3\) is larger than a plane through the origin inside it. The only comparison so far is containment, a partial order: two subspaces can live in the same space and be incomparable, and a partial order is not a measurement.

That gap surfaced as a loose end. Week 1 proved that \(U + X\) is direct exactly when \(U \cap X = \{0\}\), then warned that this does not on its own force \(U + X = V\). Whether it does is a question about how much room \(U\) and \(X\) occupy inside \(V\), and last week had no vocabulary for room.

The measurement is dimension, and nearly all the work lies in showing it exists. If you and a classmate build bases of the same space by different routes, must the two lists have the same length? The result behind that question is the Steinitz exchange lemma, and everything else this week is a corollary of it: any two bases have the same size, independent lists extend to bases, finite spanning lists contain them, and \(\dim U\), \(\dim X\), \(\dim(U \cap X)\) and \(\dim(U + X)\) satisfy one clean relation.

Two habits should change by the end. Reach for a count before a picture. And distrust the bare word “dimension”: it belongs to a space together with its field of scalars.

Why this matters beyond the definition

A student row reduces a real \(3 \times 5\) matrix, finds two free variables, and reports that the null space has dimension two. A classmate uses different row operations and writes down a visibly different pair of null-space vectors. They argue about whose vectors are right, but the prior question is why both lists must have two members rather than two and three; nothing inside the procedure promises it. If two honest computations could produce bases of different sizes, rank and nullity would be facts about a procedure rather than about the matrix.

The second stake lies past the reach of drawing. Someone claims two three-dimensional subspaces of \(\mathbb{R}^5\) might meet only at the origin; it sounds plausible, because nobody can sketch \(\mathbb{R}^5\) to refute it. The dimension formula settles it in one line: they must share a nonzero vector, however they are positioned.

What you will be able to do

• State linear independence for an arbitrary subset using finite linear combinations, and say why finiteness is in the definition.
• Prove the Steinitz exchange lemma, and deduce that any two bases of a finitely generated space over \(F\) have the same size.
• Decide whether a finite list in \(P_3(F)\), \(M_2(F)\) or \(F^n\) is independent, spanning, both, or neither, exhibiting the dependency when there is one.
• Construct a basis from either side, and say which direction needs Zorn’s lemma once finiteness is dropped.
• Compute \(\dim(U + X)\) from \(\dim U\), \(\dim X\) and \(\dim(U \cap X)\), and decide whether a sum is direct.
• Exhibit a counterexample to the claim that any \(n\) vectors in an \(n\)-dimensional space form a basis, and say why the obvious infinite list in \(F^{\mathbb{N}}\) is not a basis of it.

Terms and notation worth fixing

Symbol or term	What it means in this course
\(F\)	the field of scalars, concretely \(\mathbb{R}\), \(\mathbb{C}\), \(\mathbb{Q}\) or \(\mathbb{F}_2\); division by nonzero scalars is used throughout
\(\operatorname{span}(S)\)	all finite linear combinations of members of \(S\), with \(\operatorname{span}(\emptyset) = \{0\}\)
linearly independent	every finite list of distinct members admits only the trivial vanishing combination
\(\mathcal{B} = (v_1, \dots, v_n)\)	an ordered basis: an independent list that spans, ordered for Week 4’s coordinates
\(\dim_F V\)	the common size of every basis of \(V\) as an \(F\)-vector space, with \(\dim_F \{0\} = 0\)
finite-dimensional	\(V\) has a finite spanning set, equivalently a finite basis; also finitely generated
\(F^{\mathbb{N}}\)	all sequences over \(F\), added and scaled entrywise; the standing infinite-dimensional case
\(U\), \(X\), \(Y\)	subspaces; \(S\) and \(T\) stay reserved for linear maps throughout the block

Independence, spanning, and the exchange lemma

Everything this week turns on one inequality: how long an independent list may be, against how short a spanning list may be. Adding vectors helps you span and hurts independence, and the exchange lemma makes that tension quantitative.

Finite combinations, and why finiteness is in the definition

Definition. Let \(V\) be a vector space over \(F\) and \(S \subseteq V\) any subset, finite or not. Then \(S\) is linearly independent if for every \(k \ge 1\), all distinct \(v_1, \dots, v_k \in S\) and all scalars \(a_1, \dots, a_k \in F\), the equation \(a_1 v_1 + \cdots + a_k v_k = 0\) forces \(a_1 = \cdots = a_k = 0\). Otherwise \(S\) is linearly dependent, and any such equation with the \(a_i\) not all zero is a nontrivial vanishing combination, or a dependency.

The word finite is doing real work. The axioms give a binary addition, and induction extends it to sums of any finite length and no further. An expression \(\sum_{i=1}^{\infty} a_i v_i\) has no meaning in a bare vector space, since it would require convergence, hence a topology that \(F\) and the axioms do not supply. A second dividend is decisive at the end of this page: because independence is tested one finite subfamily at a time, the union of a chain of independent sets is again independent, any dependency in the union already lying in one member of the chain.

Three consequences. A one-element set \(\{v\}\) is independent exactly when \(v \ne 0\), since \(a v = 0\) with \(a \ne 0\) gives \(v = a^{-1}(a v) = 0\). Any set containing \(0\) is dependent, because \(1 \cdot 0 = 0\). The empty set is independent vacuously, which makes \(\dim \{0\} = 0\) come out right.

The field changes what a dependency looks like. In \(\mathbb{F}_2^3\) every nonzero scalar is \(1\), so a dependency is a nonempty subfamily summing to zero: \((1,0,0) + (0,1,0) + (1,1,0) = (0,0,0)\). Those three are dependent over \(\mathbb{R}\) too, by \((1,0,0) + (0,1,0) - (1,1,0) = 0\), but that relation needs \(-1\).

Two descriptions of dependence

Textbooks state dependence two ways, and you should know they are one statement.

Lemma (dependence, two ways). Let \(v_1, \dots, v_k\) be distinct vectors in \(V\), with \(k \ge 1\). The following are equivalent: (1) there are scalars \(a_1, \dots, a_k\), not all zero, with \(a_1 v_1 + \cdots + a_k v_k = 0\); (2) some \(v_j\) lies in \(\operatorname{span}(v_1, \dots, v_{j-1}, v_{j+1}, \dots, v_k)\).

Proof. Assume (1) and choose \(j\) with \(a_j \ne 0\). Because \(F\) is a field, \(a_j^{-1}\) exists, so multiplying by it and rearranging gives \[ v_j = -a_j^{-1} \sum_{i \ne j} a_i v_i , \] which is (2). Conversely, assume (2) and write \(v_j = \sum_{i \ne j} c_i v_i\). Then \[ \sum_{i \ne j} c_i v_i + (-1) v_j = 0 , \] and the coefficient \(-1\) on \(v_j\) is nonzero in any field, since \(1 \ne 0\) there. \(\square\)

Note where the field entered: inverting \(a_j\). Over a commutative ring that step is unavailable. The version used in computation is one-sided.

Discard lemma. If \(v_j \in \operatorname{span}(v_1, \dots, v_{j-1})\), then \(\operatorname{span}(v_1, \dots, v_k) = \operatorname{span}(v_1, \dots, v_{j-1}, v_{j+1}, \dots, v_k)\).

Proof. The right-hand span sits inside the left because it is generated by a subfamily. For the reverse, take \(v = \sum_i b_i v_i\), substitute the expression of \(v_j\) in terms of \(v_1, \dots, v_{j-1}\), and collect: no \(v_j\) survives. \(\square\)

A vector already in the span of the earlier ones is redundant and costs nothing to discard. That is the engine of every reduction below.

The exchange lemma, with proof

Exchange lemma (Steinitz). Let \(V\) be a vector space over \(F\). Suppose \(v_1, \dots, v_m\) is linearly independent and every \(v_i\) lies in \(\operatorname{span}(w_1, \dots, w_n)\) for some finite list \(w_1, \dots, w_n\) in \(V\). Then \(m \le n\).

Read the hypotheses. The \(w_j\) need not be independent, and need not span all of \(V\); their list must be finite; and \(V\) is not assumed finite-dimensional.

Proof. We prove by induction on \(r\) the replacement claim: for each \(r\) with \(0 \le r \le m\), after renumbering the \(w\)’s we have \(r \le n\) and \[ \operatorname{span}(v_1, \dots, v_r, w_{r+1}, \dots, w_n) = \operatorname{span}(w_1, \dots, w_n) . \] For \(r = 0\) this is an identity, and \(0 \le n\).

Suppose the claim holds for some \(r\) with \(r < m\), and write \(U = \operatorname{span}(w_1, \dots, w_n)\). Since \(v_{r+1} \in U\), the inductive hypothesis expands it in the current list: \[ v_{r+1} = a_1 v_1 + \cdots + a_r v_r + b_{r+1} w_{r+1} + \cdots + b_n w_n . \] If every \(b_j\) were zero — which is forced when \(r = n\), as no \(w\) then remains — the equation \(v_{r+1} - a_1 v_1 - \cdots - a_r v_r = 0\) would be a vanishing combination of \(v_1, \dots, v_{r+1}\) with coefficient \(1 \ne 0\) on \(v_{r+1}\), contradicting independence. So some \(b_j\) is nonzero; renumber the remaining \(w\)’s so that \(b_{r+1} \ne 0\). In particular a \(w\) was still available, so \(r + 1 \le n\). Because \(F\) is a field we may divide: \[ w_{r+1} = b_{r+1}^{-1} \Bigl( v_{r+1} - \sum_{i \le r} a_i v_i - \sum_{j \ge r+2} b_j w_j \Bigr) . \] So \(w_{r+1}\) lies in \(\operatorname{span}(v_1, \dots, v_{r+1}, w_{r+2}, \dots, w_n)\), and every other member of the old list visibly lies there too, so the new span contains \(U\). It is also contained in \(U\), since each of its generators is. The two spans agree, and the claim holds for \(r + 1\). Running the induction to \(r = m\) gives \(m \le n\). \(\square\)

Each step of the exchange trades one spanning vector for one independent vector.

The figure is that proof with the algebra removed: each row spans what the original \(w\)’s spanned, each step moves one \(v\) in and one \(w\) out, and the row has only \(n\) slots to run out of.

Corollary. If \(V = \operatorname{span}(w_1, \dots, w_n)\), then every independent subset of \(V\) has at most \(n\) elements, and in particular is finite.

Bases and the theorem that dimension exists

A basis is simultaneously as large as an independent set can be and as small as a spanning set can be. That double description is a theorem with three equivalent clauses.

Three equivalent descriptions of a basis

Definition. A subset \(\mathcal{B} \subseteq V\) is a basis of \(V\) if it is independent and \(\operatorname{span}(\mathcal{B}) = V\). Nothing in that sentence asks \(\mathcal{B}\) to be finite, and the existence theorem later in this section produces infinite ones. When \(\mathcal{B}\) is finite we write it as an ordered list \(\mathcal{B} = (v_1, \dots, v_n)\) of distinct vectors, because Week 4 attaches coordinates and coordinates need an order.

Theorem (three descriptions). Let \(\mathcal{B} = (v_1, \dots, v_n)\) be a finite list of distinct vectors in a vector space \(V\) over \(F\). The following are equivalent. (1) \(\mathcal{B}\) is independent and spans \(V\). (2) \(\mathcal{B}\) is a maximal independent list: independent, and \((v_1, \dots, v_n, v)\) is dependent for every \(v \in V\) outside \(\mathcal{B}\). (3) \(\mathcal{B}\) is a minimal spanning list: it spans \(V\), and deleting any single member leaves a list that does not.

Proof. (1) implies (2): \(\mathcal{B}\) is independent by hypothesis, and for \(v\) outside \(\mathcal{B}\) spanning puts \(v \in \operatorname{span}(\mathcal{B})\), so the dependence lemma makes the enlarged list of distinct vectors dependent.

2. implies (1): only spanning needs work. Fix \(v \in V\) outside \(\mathcal{B}\). By maximality there is a nontrivial relation \(a_1 v_1 + \cdots + a_n v_n + c v = 0\). If \(c = 0\) this is a nontrivial dependency inside \(\mathcal{B}\), contradicting independence; so \(c \ne 0\) and \(v = -c^{-1}(a_1 v_1 + \cdots + a_n v_n) \in \operatorname{span}(\mathcal{B})\).

3. implies (3): if deleting \(v_j\) still spanned \(V\), then \(v_j \in \operatorname{span}(\mathcal{B} \setminus \{v_j\})\) and the dependence lemma would make \(\mathcal{B}\) dependent.

4. implies (1): only independence needs work. If \(a_1 v_1 + \cdots + a_n v_n = 0\) with \(a_j \ne 0\), then \(v_j\) lies in the span of the others, so by the discard lemma the list without \(v_j\) still spans \(V\), contradicting minimality. \(\square\)

The theorem is about a given finite list; it does not claim one exists. Existence is where finite generation, or in general Zorn’s lemma, enters, and nothing above required \(V\) to be finite-dimensional.

Any two bases have the same size

Theorem (dimension is well defined). If \(V\) has a finite basis \(\mathcal{B} = (v_1, \dots, v_n)\), then every basis of \(V\) is finite with exactly \(n\) elements.

Proof. Let \(\mathcal{C}\) be any basis. Each finite subfamily of \(\mathcal{C}\) is independent and lies in \(V = \operatorname{span}(v_1, \dots, v_n)\), so by the exchange lemma has at most \(n\) members; a set all of whose finite subsets have at most \(n\) members has at most \(n\) members, so \(\mathcal{C}\) is finite with \(m \le n\) elements. Reversing the roles, \(\mathcal{B}\) is independent and lies in \(V = \operatorname{span}(\mathcal{C})\), a span of \(m\) vectors, so \(n \le m\). Hence \(m = n\). \(\square\)

Definition. For such a \(V\) we write \(\dim_F V = n\) and call \(V\) finite-dimensional, with \(\dim_F \{0\} = 0\) from the empty basis. A space with no finite basis is infinite-dimensional.

Say it once out loud: dimension is a theorem, not a definition. The familiar counts follow. \(\dim_F F^n = n\) from the standard basis. \(\dim_F P_3(F) = 4\) from \((1, x, x^2, x^3)\) — the subscript bounds the degree, so the count is four, not three. \(\dim_F M_2(F) = 4\) from the matrix units \(E_{11}, E_{12}, E_{21}, E_{22}\). And \(\dim_{\mathbb{F}_2} \mathbb{F}_2^3 = 3\), though that space has eight elements.

Corollary A. In a space \(V\) of dimension \(n\), every independent list has at most \(n\) members and every spanning list has at least \(n\). Consequently every subspace \(U\) of \(V\) is finite-dimensional with \(\dim_F U \le n\): build an independent list inside \(U\) by adjoining at each stage some vector of \(U\) outside the span of what you have; that must stop by the first sentence, and a list it stops at is a maximal independent list in \(U\), hence a basis of \(U\).

Corollary B (either hypothesis suffices). Let \(\dim_F V = n\) and let \(L\) be a list of exactly \(n\) distinct vectors of \(V\). Then \(L\) is independent if and only if it spans \(V\), and in either case it is a basis.

Proof. If \(L\) is independent but does not span, pick \(v\) outside \(\operatorname{span}(L)\) and adjoin it. The result is still independent: in a relation \(\sum a_i u_i + c v = 0\), a nonzero \(c\) would put \(v = -c^{-1}\sum a_i u_i\) inside \(\operatorname{span}(L)\), so \(c = 0\) and then every \(a_i = 0\). That is an independent list of \(n + 1\) vectors, contradicting Corollary A. If instead \(L\) spans but is dependent, some member lies in the span of the others, so the discard lemma yields a spanning list of \(n - 1\) vectors, again contradicting Corollary A. \(\square\)

Corollary C. If \(U\) is a subspace of a finite-dimensional \(V\) with \(\dim_F U = \dim_F V\), then \(U = V\): a basis of \(U\) is an independent list of \(\dim V\) vectors in \(V\), hence a basis of \(V\) by Corollary B, so every vector of \(V\) is a combination of vectors of \(U\) and therefore lies in \(U\).

Building a basis from either side

Reduction. Every finite spanning list of \(V\) contains a basis. Scan left to right: keep \(u_1\) if it is nonzero, and keep each later \(u_j\) exactly when \(u_j\) is not in the span of those kept so far. The discard lemma says the span never changes, so the survivors still span \(V\). They are independent too: given a nontrivial relation among them, take the largest index whose coefficient is nonzero and solve for that vector, placing it in the span of the earlier survivors — but it was kept precisely because it was not there.

Extension. If \(V\) is finite-dimensional and \(L\) is independent, then \(L\) extends to a basis. If \(L\) spans, it already is one. Otherwise pick \(v \notin \operatorname{span}(L)\) and adjoin it; the computation inside Corollary B keeps the list independent. Each step lengthens the list by one, and by Corollary A no independent list exceeds \(\dim_F V\), so the process halts at a basis after at most \(\dim_F V - |L|\) steps.

Shrinking a spanning list and growing an independent list both stop at a basis.

The figure shows the two procedures converging. From the left, a spanning list of six vectors in a four-dimensional space sheds one redundant vector at a time and cannot fall below four; from the right, an independent list of two gains one at a time and cannot climb above four. They meet only at length \(\dim_F V\).

Finiteness matters for the extension direction: drop it and the halting argument disappears. In full generality, “every independent set extends to a basis” is proved with Zorn’s lemma, not by an algorithm.

Bases nobody can write down

Theorem (existence). Every vector space over a field has a basis.

The proof orders the independent subsets of \(V\) by inclusion and applies Zorn’s lemma; its hypothesis checks out because of the finiteness clause insisted on above, the union of a chain of independent sets being independent. A maximal independent set \(\mathcal{B}\) therefore exists, and it spans. Take \(v \in V\) outside \(\mathcal{B}\). Maximality supplies a nontrivial relation \(a_1 v_1 + \cdots + a_k v_k + c v = 0\) with \(v_1, \dots, v_k\) distinct members of \(\mathcal{B}\); were \(c = 0\), that relation would be a dependency inside \(\mathcal{B}\), so \(c \ne 0\) and \(v = -c^{-1}(a_1 v_1 + \cdots + a_k v_k) \in \operatorname{span}(\mathcal{B})\). Hence \(\mathcal{B}\) is a basis. That is the computation proving (2) implies (1) above, run without assuming the set is finite — which matters, because the set Zorn’s lemma hands back is in general infinite and the three-descriptions theorem was stated only for finite lists. The argument is non-constructive.

Such a basis is called a Hamel basis, and nobody has written one down for \(F^{\mathbb{N}}\), nor for \(\mathbb{R}\) over \(\mathbb{Q}\). Here is the trap. Let \(e_i \in F^{\mathbb{N}}\) be the sequence with \(1\) in position \(i\) and \(0\) elsewhere. The set \(\{e_1, e_2, \dots\}\) is independent and looks like a basis, but a member of its span is by definition a finite combination, hence a sequence with finitely many nonzero entries, and \((1, 1, 1, \dots)\) is not among them. Those vectors form a basis of the proper subspace of finitely supported sequences.

Counting inside a sum of subspaces

With dimension in hand we can measure the Week 1 constructions: one formula relates four numbers and closes the question Week 1 left open.

The dimension formula and its proof

Theorem (dimension formula). Let \(U\) and \(X\) be finite-dimensional subspaces of a vector space \(V\) over \(F\). Then \(U + X\) is finite-dimensional and \[ \dim_F (U + X) = \dim_F U + \dim_F X - \dim_F (U \cap X) . \]

Proof. Since \(U \cap X\) is a subspace of the finite-dimensional \(U\), it is finite-dimensional by Corollary A; let \((z_1, \dots, z_k)\) be a basis of it. Extend that basis to a basis \((z_1, \dots, z_k, u_1, \dots, u_p)\) of \(U\), so \(\dim U = k + p\), and separately to a basis \((z_1, \dots, z_k, x_1, \dots, x_q)\) of \(X\), so \(\dim X = k + q\); both extensions exist by the extension theorem. We claim \[ \mathcal{B} = (z_1, \dots, z_k,\; u_1, \dots, u_p,\; x_1, \dots, x_q) \] is a basis of \(U + X\). It spans: any element of \(U + X\) is \(u + x\), and expanding \(u\) in the basis of \(U\) and \(x\) in the basis of \(X\) writes it over \(\mathcal{B}\). For independence, suppose \[ \sum_{i=1}^{k} a_i z_i + \sum_{j=1}^{p} b_j u_j + \sum_{l=1}^{q} c_l x_l = 0 , \] and set \(y = \sum_l c_l x_l\). Then \(y \in X\), while the relation also gives \(y = -\sum_i a_i z_i - \sum_j b_j u_j \in U\), so \(y \in U \cap X\) and \(y = \sum_i d_i z_i\) for some \(d_i\). Subtracting, \(\sum_l c_l x_l - \sum_i d_i z_i = 0\) is a vanishing combination of the basis \((z_1, \dots, z_k, x_1, \dots, x_q)\) of \(X\), so every \(c_l = 0\). The original relation then reads \(\sum_i a_i z_i + \sum_j b_j u_j = 0\), a vanishing combination of a basis of \(U\), so every \(a_i\) and \(b_j\) is zero as well. Counting \(\mathcal{B}\), \[ \dim(U + X) = k + p + q = (k + p) + (k + q) - k . \qquad \square \]

Two overlapping dimension bars, with the shared block subtracted once.

The figure is the proof’s bookkeeping: the \(z\)’s are the shared block where the two upper bars overlap, the \(u\)’s stick out on the left, the \(x\)’s on the right, and the lower bar is their concatenation. Adding \(\dim U\) and \(\dim X\) counts the shared block twice, so it comes off once.

When the sum is direct, and what Week 1 left open

Corollary. For finite-dimensional subspaces \(U\) and \(X\), the sum \(U + X\) is direct if and only if \(\dim(U + X) = \dim U + \dim X\). Week 1 showed directness is equivalent to \(U \cap X = \{0\}\), which for a finite-dimensional subspace is equivalent to \(\dim(U \cap X) = 0\); substitute into the formula.

In \(\mathbb{R}^3\) let \(U\) be the \(xy\)-plane and \(X\) the \(yz\)-plane. Then \(U + X = \mathbb{R}^3\), so the formula reads \(3 = 2 + 2 - \dim(U \cap X)\) and forces \(\dim(U \cap X) = 1\): the intersection is the \(y\)-axis, as the picture showed last week, but now derived rather than observed.

Corollary. If \(V\) is finite-dimensional, \(U \cap X = \{0\}\), and \(\dim U + \dim X = \dim_F V\), then \(V = U \oplus X\). The formula gives \(\dim(U + X) = \dim U + \dim X = \dim V\), and Corollary C upgrades that to \(U + X = V\). So “\(U \cap X = \{0\}\)” and “\(U + X = V\)” are genuinely independent conditions, and dimension is exactly the arithmetic saying when one implies the other.

Dimension depends on the field

Dimension attaches to a set of vectors together with the field acting on it. Over \(\mathbb{C}\) the space \(\mathbb{C}\) has basis \((1)\), so \(\dim_{\mathbb{C}} \mathbb{C} = 1\). Over \(\mathbb{R}\) the same set has basis \((1, i)\), since \(a + bi\) is the general element and \(a \cdot 1 + b \cdot i = 0\) with \(a, b \in \mathbb{R}\) forces \(a = b = 0\); so \(\dim_{\mathbb{R}} \mathbb{C} = 2\). The vectors did not change; the scalars did.

The same vectors carry different dimensions over different fields.

The figure runs the same comparison for \(\mathbb{C}^2\), of dimension two over \(\mathbb{C}\) and four over \(\mathbb{R}\) with \(\mathbb{R}\)-basis \(\bigl((1,0), (i,0), (0,1), (0,i)\bigr)\), and records \(\mathbb{R}\) over \(\mathbb{Q}\) as infinite-dimensional. Its last row is arithmetic worth remembering: \(\mathbb{F}_2^3\) has dimension three and exactly \(2^3 = 8\) elements, since coordinates against a basis of size \(d\) over a field with \(|F|\) elements give \(|F|^d\) vectors. Hence \(\dim_F V\) whenever two fields are in view.

Worked example — trimming a spanning list of polynomials to a basis

Work in \(V = P_3(F)\), polynomials over \(F\) of degree at most three, with \(\dim_F V = 4\) and standard basis \((1, x, x^2, x^3)\). Take \[ \begin{aligned} p_1 &= 1 + x, & p_2 &= x + x^2, & p_3 &= 1 + 2x + x^2, \\ p_4 &= x^2 + x^3, & p_5 &= 1 + x + x^2 + x^3, & p_6 &= x^3 . \end{aligned} \] Six vectors in a four-dimensional space are dependent by Corollary A, so at least two will be discarded. Write each as its coefficient quadruple against \((1, x, x^2, x^3)\): \[ p_1 = (1,1,0,0), \; p_2 = (0,1,1,0), \; p_3 = (1,2,1,0), \; p_4 = (0,0,1,1), \; p_5 = (1,1,1,1), \; p_6 = (0,0,0,1). \]

Step 1. \(p_1 \ne 0\), so keep it; the kept span is \(\{(a,a,0,0)\}\).

Step 2. \(p_2\) has third coordinate \(1\), every \((a,a,0,0)\) has third coordinate \(0\): keep \(p_2\), and the kept span becomes \(\{(a, a+b, b, 0)\}\).

Step 3. Matching \(p_3 = (1,2,1,0)\) needs \(a = 1\) and \(b = 1\), and then \(a + b = 2\) checks. So \(p_3 = p_1 + p_2\), and directly \((1 + x) + (x + x^2) = 1 + 2x + x^2\). Discard \(p_3\) — the dependency exhibited, not asserted.

Step 4. Every \((a, a+b, b, 0)\) has fourth coordinate \(0\) and \(p_4\) has fourth coordinate \(1\): keep \(p_4\), and the kept span becomes \(\{(a, a+b, b+c, c)\}\).

Step 5. Matching \(p_5 = (1,1,1,1)\): the first coordinate gives \(a = 1\), the fourth gives \(c = 1\), then \(a + b = 1\) gives \(b = 0\), and the third coordinate check is \(b + c = 0 + 1 = 1\), which matches. So \(p_5 = p_1 + p_4\), and directly \((1 + x) + (x^2 + x^3) = 1 + x + x^2 + x^3\). Discard \(p_5\).

Step 6. Matching \(p_6 = (0,0,0,1)\) forces \(a = 0\), then \(b = 0\), then \(c = 1\), and the third coordinate would be \(b + c = 1\) rather than \(0\). Keep \(p_6\).

Four survive: \(p_1, p_2, p_4, p_6\). Stacking their coordinate rows in order gives \[ \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix}, \] upper triangular with every diagonal entry \(1\), so back substitution recovers the standard basis: \[ x^3 = p_6, \quad x^2 = p_4 - p_6, \quad x = p_2 - p_4 + p_6, \quad 1 = p_1 - p_2 + p_4 - p_6 . \] Expand the last to check it: \((1 + x) - (x + x^2) + (x^2 + x^3) - x^3 = 1\), the \(x\), \(x^2\) and \(x^3\) terms cancelling in pairs. So \((p_1, p_2, p_4, p_6)\) spans \(P_3(F)\), and four spanning vectors in a four-dimensional space form a basis by Corollary B. The count is \(4 = \dim_F P_3(F)\), with \(6 - 2 = 4\) accounting for the discards.

This establishes that the six polynomials span \(P_3(F)\) and that a basis can be extracted, not that \((p_1, p_2, p_4, p_6)\) is preferred; scanning right to left keeps a different four. A basis is a choice, never a canonical object.

One field remark. Both dependencies, \(p_3 = p_1 + p_2\) and \(p_5 = p_1 + p_4\), are identities with integer coefficients, so they hold over every field and the same four survive over \(\mathbb{Q}\) or \(\mathbb{F}_2\). Over \(\mathbb{F}_2\) the polynomial \(p_3\) is displayed differently, since \(2x = 0\) makes it read as \(1 + x^2\), but its quadruple \((1,2,1,0)\) still equals \((1,0,1,0) = p_1 + p_2\) there.

The same reasoning, transferred

Run the identical procedure in \(V = M_2(F)\), with \(\dim_F M_2(F) = 4\) and standard basis \((E_{11}, E_{12}, E_{21}, E_{22})\). Take \[ A_1 = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}, \quad A_2 = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \quad A_3 = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}, \quad A_4 = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} , \] whose coordinates in the order \(E_{11}, E_{12}, E_{21}, E_{22}\) are \((1,1,1,1)\), \((0,1,1,1)\), \((0,0,1,1)\) and \((0,0,0,1)\). Scanning left to right: \(A_1 \ne 0\), keep. Multiples of \(A_1\) are \((a,a,a,a)\), so matching \(A_2\) would need \(a = 0\) from the first coordinate and \(a = 1\) from the second; keep \(A_2\), and the kept span is \(\{(a, a+b, a+b, a+b)\}\). For \(A_3 = (0,0,1,1)\) we would need \(a = 0\) and \(a + b = 0\), hence \(b = 0\) and third coordinate \(0\), not \(1\); keep \(A_3\), and the kept span becomes \(\{(a, a+b, a+b+c, a+b+c)\}\). For \(A_4 = (0,0,0,1)\) the first three coordinates force \(a = 0\), then \(b = 0\), then \(c = 0\), leaving fourth coordinate \(0\); keep \(A_4\).

Nothing was discarded, and differences recover the standard basis: \(E_{11} = A_1 - A_2\), \(E_{12} = A_2 - A_3\), \(E_{21} = A_3 - A_4\), \(E_{22} = A_4\); check the second entry by entry, \(A_2 - A_3\) having entries \(0 - 0\), \(1 - 0\), \(1 - 1\), \(1 - 1\).

What stayed the same is the procedure. What changed is the reason the count is four: in \(P_3(F)\) we started above the dimension and were pushed down by two discards, while here we started at four independent vectors and discarded nothing, so Corollary B certifies a basis from independence alone. Only entries \(0\) and \(1\) and their differences appeared, so over \(\mathbb{F}_2\) the space \(M_2(\mathbb{F}_2)\) has \(2^4 = 16\) elements and still dimension four.

Second worked example — two three-dimensional subspaces of a five-dimensional space

Let \(U\) and \(X\) be subspaces of \(\mathbb{R}^5\) with \(\dim U = \dim X = 3\). Nothing else is assumed. Claim: \(\dim(U \cap X) \ge 1\), so they share a nonzero vector.

Working. \(U + X\) is a subspace of \(\mathbb{R}^5\), so \(\dim(U + X) \le 5\) by Corollary A. Rearranging the dimension formula, \[ \dim(U \cap X) = \dim U + \dim X - \dim(U + X) \ge 3 + 3 - 5 = 1 . \] That is the entire argument, and no picture was consulted.

Intersection exactly one-dimensional. Take \(U = \operatorname{span}(e_1, e_2, e_3)\) and \(X = \operatorname{span}\bigl((1,1,0,0,0), e_4, e_5\bigr)\). A general element of \(X\) is \((a, a, 0, b, c)\), and lying in \(U\) forces \(b = c = 0\), leaving \((a,a,0,0,0)\). So \(U \cap X = \operatorname{span}\bigl((1,1,0,0,0)\bigr)\), of dimension one, and the shared vector is not a standard basis vector. Meanwhile \(U + X\) contains \(e_1, \dots, e_5\), hence equals \(\mathbb{R}^5\), and \(3 + 3 - 1 = 5\) checks.

Intersection larger. Take \(U = \operatorname{span}(e_1, e_2, e_3)\) and \(X = \operatorname{span}(e_2, e_3, e_4)\). An element of \(U\) is \((a,b,c,0,0)\) and one of \(X\) is \((0,d,e,f,0)\); equating forces \(a = 0\) and \(f = 0\), so \(U \cap X = \operatorname{span}(e_2, e_3)\) has dimension two. Here \(U + X = \operatorname{span}(e_1, e_2, e_3, e_4)\) has dimension four, and \(3 + 3 - 2 = 4\) checks.

The forcing is about five, not about three. In \(\mathbb{R}^6\) the subspaces \(\operatorname{span}(e_1, e_2, e_3)\) and \(\operatorname{span}(e_4, e_5, e_6)\) are three-dimensional and meet only at the origin, with \(3 + 3 - 0 = 6\). The overlap in \(\mathbb{R}^5\) was forced by the ambient dimension being smaller than \(3 + 3\), and nothing else. Worth memorising: for subspaces of a finite-dimensional \(V\), \(\dim(U \cap X) \ge \dim U + \dim X - \dim V\).

The misreading to avoid

The sentence to disarm is “any \(n\) vectors in an \(n\)-dimensional space form a basis.” Students say it because the two true statements nearby sound like it.

It is false. In \(P_3(\mathbb{R})\), of dimension four, take \(1\), \(x\), \(2x\) and \(x^2\): four vectors in a four-dimensional space, dependent because \(2 \cdot x - 1 \cdot (2x) = 0\). Their span is \(\operatorname{span}(1, x, x^2)\), a proper subspace of dimension three that misses \(x^3\). The same failure in \(\mathbb{R}^3\): the vectors \((1,0,0)\), \((2,0,0)\) and \((0,1,0)\) span only the \(xy\)-plane, since \(2v_1 - v_2 = 0\).

What is true is Corollary B: in an \(n\)-dimensional space, \(n\) independent vectors form a basis and \(n\) spanning vectors form a basis. Either hypothesis suffices alone, but one of them is needed: the count is a consequence of being a basis, not a test for it.

A second misreading is just as common: “infinite-dimensional means the space has no basis.” Every vector space has a basis, by the Zorn’s lemma argument above; what infinite-dimensionality costs is not existence but exhibition, and the tempting candidate \(\{e_1, e_2, \dots\}\) in \(F^{\mathbb{N}}\) spans only the finitely supported sequences. A third, smaller one: “\(\dim V\) is a number attached to \(V\).” It is attached to \(V\) and to \(F\).

Practice on your own

These are for your own checking as you read; nothing here is collected.

1. Prove that a list \((v_1, \dots, v_k)\) with \(v_1 \ne 0\) is dependent if and only if some \(v_j\) with \(j \ge 2\) lies in \(\operatorname{span}(v_1, \dots, v_{j-1})\), and say why the reduction uses this sharper form.
2. In \(\mathbb{F}_2^4\), decide whether \((1,1,0,0)\), \((0,1,1,0)\), \((0,0,1,1)\) and \((1,0,0,1)\) are independent. Add all four together first, then identify the span and its dimension.
3. Let \(U\) and \(X\) be subspaces of a finite-dimensional \(V\) with \(\dim U = 7\), \(\dim X = 5\) and \(\dim V = 10\). Which values can \(\dim(U \cap X)\) take? Justify both bounds and exhibit subspaces of \(\mathbb{R}^{10}\) realising each.
4. Exhibit an infinite independent set and an infinite spanning set in \(F^{\mathbb{N}}\), say what the exchange lemma does and does not tell you about them, and name the sentence of its proof that needs the spanning list to be finite.
5. Prove, without invoking the dimension formula, that if \(V\) is finite-dimensional and \(\dim U + \dim X > \dim V\) then \(U \cap X \ne \{0\}\).

Where to read more

• The optional Roman alignment for this week is Chapter 1, in the sections on spanning sets and linear independence and on the dimension of a vector space. It is optional: a borrowed or library copy is sufficient, and nothing here requires you to purchase it.
• MIT OpenCourseWare 18.700 Linear Algebra treats independence, bases and dimension at this level of abstraction.
• MIT OpenCourseWare 18.06 Linear Algebra is the computational counterpart, for practice reading independence off a row reduction.
• Linear Algebra Done Wrong (Treil) develops bases and dimension over a general field and states the exchange argument close to the form above.
• Course pages: the notes overview, the syllabus, the schedule, and the resources page. Availability and licence terms for the sources above are still being confirmed, so treat each as optional reading.

Where this goes next

Week 3 studies maps between spaces. A linear transformation \(T \colon V \to W\) turns out to be determined by almost nothing — its values on a single basis, chosen arbitrarily — which only this week’s material makes sayable. Its kernel and image are subspaces, and the rank-nullity theorem says their dimensions add to \(\dim V\) whenever \(V\) is finite-dimensional. That proof extends a basis of a subspace to a basis of the whole space, and the counterexample showing it fails without finite-dimensionality lives in \(F^{\mathbb{N}}\).

Keep three things within reach: the exchange lemma, the two construction directions, and the habit of writing \(\dim_F V\). The course home page lists the block in order.