may-27

These lecture notes were generated by Claude inside a Cowork environment with knowledge of the syllabus and course materials, and generated from the audio transcript of the lecture. The lecture notes are not a transcript, and skip some parts while adding small details with sources/clarifications. These notes have been checked by me to be correct. I have added and edited the file for correctness and alignment with necessary material. All right-margin aside notes are additional to the course, and are not part of the learning objectives.

Lecture 6 — May 27, 2026

Administrative

• Tutorials: the difficulty will increase gradually — not the conceptual difficulty, but the scaffolding. Problem sets will grow more self-contained and rely on more accumulated material. If you open a tutorial sheet and feel completely lost, that is a signal to revisit the weekly material.
• Office hours: an online poll for convenient hours will be posted shortly. TAs will also hold in-person office hours near tutorial times, especially as the midterm approaches.
• Midterm: Saturday, June 13, 9–11 am. Details to follow at least 10 days in advance.
• Reflection 2: assigned this Friday, due the following Wednesday. The score-visibility bug will be fixed.

---

1. The arc so far

Before proving anything new, it is worth stepping back and seeing the logical arc of the past three weeks, because today’s material is its culmination.

We began with systems of linear equations. Using the augmented coefficient matrix and elementary row operations we can always simplify a system to reduced echelon form (RREF), which reads off the general solution directly. Two facts about RREF are worth noting: existence — the procedure always terminates — and uniqueness — the RREF of a given matrix is the same regardless of the sequence of row operations used. Uniqueness is proved carefully in Hefferon; it is not obvious.

From RREF we learned two structural facts about solution sets. First, solutions are subspaces of (where is the number of variables): the zero vector is always a solution, and the solution set is closed under addition and scalar multiplication. Second, the parametric form produced by RREF writes every solution as a span of finitely many direction vectors.

At this point the arithmetic recedes. The interesting object is the subspace — not the specific system that produced it. This shift is characteristic of a recurrent move in mathematics: once a geometric structure has been extracted from a computation, you drop the computation and work directly with the structure. Systems of linear equations motivated subspaces; subspaces will now be studied on their own terms, and systems will appear less and less.

We now ask: given a subspace expressed as a span, how do we describe it efficiently, without redundant vectors? That question leads to bases, and today to their most important property: dimension.

This is also the point where the course makes a methodological choice that most introductory linear algebra courses never name explicitly. Linear algebra can be done in two registers. A coordinate approach always fixes a basis first and then works with the resulting number arrays: vectors become columns, linear maps become matrices, and geometric statements become calculations about pivots. A coordinate-free approach argues directly about spans, independence, and exchange, without anchoring to any specific basis. The theorems are the same; the proofs look different; the intuition they convey is different too.

Today’s lecture makes this contrast explicit. The theorem that all bases have the same number of vectors — the theorem that makes dimension well-defined — will be proved in both registers, and comparing the two proofs is itself part of the lesson. The coordinate proof (RREF, pivot-counting) is short and mechanical; it is the approach taken by Hefferon and Treil. The coordinate-free proof (Steinitz exchange) is structural; it is Axler’s approach. Neither is “more rigorous” than the other, but they differ enormously in what they reveal.

---

2. Linear dependence and non-unique representations

The following lemma makes the connection between linear dependence and the redundancy we saw in Lecture 5 fully precise.

Lemma

Let be a vector space and . The vectors are linearly dependent if and only if there exists a vector that can be expressed as two different linear combinations of .

Proof

We prove both directions.

() Suppose are linearly dependent. Then there exist , not all zero, such that . Consider the vector . It has two representations as a linear combination of the :

Since not all are zero, these are two genuinely different linear combinations producing the same vector.

() Suppose some has two different representations:

where . Subtracting the second from the first:

Since the two tuples of coefficients differ, at least one . This is therefore a non-trivial linear combination equal to , so are linearly dependent.

Why the zero vector? In the forward direction we could have chosen any vector — once you have a non-trivial relation summing to , you can add it to any existing representation to produce a second, different one. The zero vector is simply the most convenient choice because it always has at least one representation (the trivial one).

Uniqueness of representation

The contrapositive of this lemma is the statement we actually want in practice: are linearly independent if and only if every vector that can be written as a linear combination of them can be written in exactly one way. This is why independence is the right condition for a basis: it makes the representation of every vector in the span unique, which is what gives us well-defined coordinates.

---

3. Dependence and redundant vectors

The next lemma characterises dependence in terms of whether any single vector in the list can be “absorbed” by the others.

Lemma

Let . The following are equivalent:

1. are linearly dependent.
2. There exists an index such that — i.e., is a linear combination of the remaining vectors.

Here denotes that is omitted from the list.

Proof

() Suppose for some scalars . Rearranging:

The coefficient of is , so this is a non-trivial linear combination equal to . Hence are linearly dependent.

() Suppose are linearly dependent: there exist , not all zero, with . Since not all are zero, there exists an index with . Isolating :

Since , we may divide by :

So is a linear combination of the remaining vectors.

Note on the index

The lemma does not say that every vector in the list is redundant — only that at least one is. For example, in the dependent set , removing either of the first two works, but not not the third.

---

4. Removing a redundant vector preserves the span

Lemma

Let be a set of vectors in a vector space . If is linearly dependent, then there exists such that

Proof

Since is linearly dependent, by the previous lemma there exists such that .

The inclusion holds because every linear combination of vectors in is also a linear combination of all vectors in (just set the coefficient of to zero).

For the reverse inclusion, take any :

Since , we can substitute its expression in terms of the remaining vectors, eliminating from the combination entirely. The result is a linear combination of vectors in , so .

---

5. Building a basis from a finite spanning set

The three lemmas above give a concrete procedure for constructing a basis.

Procedure. Let be a subspace and suppose for some finite set .

1. If is linearly independent, stop — is already a basis for .
2. If is linearly dependent, the previous lemma guarantees an element whose removal preserves . Remove it.
3. Repeat with .

Since is finite and shrinks by at least one element at each step, the procedure terminates. The result is a linearly independent spanning set for , i.e., a basis.

The empty set is linearly independent (vacuously — there is no linear combination to form, let alone a non-trivial one), so if the procedure reaches the subspace is , which is the zero subspace, and is its basis.

Why finiteness is essential

If is infinite, the procedure never terminates. Moreover, starting from a dependent infinite set, even after removing countably many elements, you may not arrive at a linearly independent set in finite steps. Handling infinite-dimensional spaces requires more sophisticated arguments (Zorn’s lemma). For this course we work exclusively in finitely-spanned spaces.

---

6. Dimension — definition and the well-definedness problem

Definition

The dimension of a finitely-spanned vector space , written , is the number of vectors in a basis of .

The problem. This definition is potentially ambiguous. Different choices of spanning set in the procedure above — or different orders of removing vectors — might, a priori, yield bases of different sizes. If so, “dimension” would not be well-defined: could have two bases of sizes and simultaneously, and would be meaningless.

Geometric intuition strongly suggests this cannot happen: a plane in always needs exactly direction vectors, no matter how you choose them. But we need a proof that works in abstract vector spaces — including polynomials, sequences, and other examples where the geometry is less visible.

---

7. Theorem: all bases have the same number of vectors

Two genuinely different proofs of this theorem exist, and they are worth examining side by side.

The coordinate proof expresses one basis in terms of the other, collects the coefficients into a matrix, and uses the fact that a homogeneous system with more variables than equations always has a non-trivial solution. The contradiction with linear independence then forces the two bases to have the same size. This is what Hefferon and Treil do. The argument is clean and short, but it drains the geometry out of a geometric statement: independence of a set of directions becomes a rank condition, and the conclusion falls out of a pivot count with no explanatory content.

The coordinate-free proof (Steinitz, §8) never sets up a matrix. Instead, it iteratively swaps vectors between the two sets, maintaining the spanning property at every step. The bound emerges from the fact that swapping can only continue as long as there are vectors left to swap — finiteness of the set, not arithmetic of pivots, is what does the work. The geometry remains visible throughout.

We present the coordinate proof first, because it is technically simpler and illustrates the double role of RREF beyond systems of equations. The Steinitz proof follows in §8.

Theorem

Let be a finitely-spanned vector space. All bases of contain the same number of vectors.

Proof

(Proof by contradiction, coordinate/RREF approach.)

Setup. Assume has two bases of different sizes. Call them and with . Without loss of generality, assume (otherwise swap the names of the two bases).

(We also assume, without proof here, that both bases are finite — a fact that requires a separate argument from the assumption that is finitely spanned.)

Expressing in terms of . Since spans and each , we can write

for some scalars . Following the Einstein convention, the upper index is the output/row index (which -component) and the lower index is the input/column index (which -vector).

Using independence of . Suppose . Substituting the expressions above:

Since are linearly independent, every coefficient of must be zero:

The contradiction. This is a homogeneous system of equations in unknowns . Since , the coefficient matrix has more columns than rows. In the RREF, there are at most pivot columns (one per row), so at least one of the variables must be free. A homogeneous system with a free variable always has non-trivial solutions. Hence there exist , not all zero, such that .

This contradicts the linear independence of .

Added. Denis

The clean RREF argument

The proof above required both and to be bases — in particular, had to be linearly independent. A sharper version of the same column-counting idea removes that requirement entirely. The spanning set need not be independent.

Key Lemma. If , then no vectors in can be linearly independent.

Proof. Let and write . Let be the matrix of coefficients. Consider the homogeneous system . Since has more columns than rows, its RREF has at most pivots among columns, leaving at least one free variable. So there exists with . Now observe:

So are linearly dependent.

The crucial point: the need not be independent. The implication runs only one way — — and that is all that is needed.

Corollary: has no infinite basis. Any infinite linearly independent set would contain elements that are linearly independent (any subset of a linearly independent set is independent, directly from the definition), contradicting the lemma.

The theorem now follows cleanly: if is a basis with vectors and with , then by the lemma. By symmetry (swapping the roles of and ) we also get , so .

Why this is not secretly Steinitz. The Steinitz exchange lemma constructs an explicit swap, proving not just the size bound but also that any linearly independent set can be extended to a basis. The RREF argument here is purely a rank bound: the map must have a non-trivial kernel, full stop — no induction on swaps, no spanning-set maintenance, just column-counting.

Why the RREF proof is unsatisfying

Many students come to this proof feeling that the result is obvious — of course a plane needs exactly 2 independent directions, not 5 and not 1. The RREF proof then lands with a thud: what does pivot-counting have to do with that geometric intuition? Nothing, really. The proof works by translating a statement about directions in space into a statement about ranks of matrices, deriving a contradiction, and translating back — without ever engaging with the geometric content. It is a perfectly valid proof, but it explains nothing. The Steinitz proof in §8 stays in geometric language throughout, and when it concludes the reason is visible: you simply ran out of vectors to exchange. That is the argument the intuition was pointing at all along.

---

8. The Steinitz exchange lemma (Axler 2.22)

The RREF proof treats the two bases asymmetrically (we expressed in terms of but not vice versa) and the key step is purely computational. The following lemma is the structural heart of the matter.

Lemma (Steinitz's Exchange Lemma — Axler 2.22)

Let be a vector space and suppose for some finite set . If is any linearly independent set, then .

The proof was not covered during the lecture. Denis

Proof

Setup. Write and . We construct a sequence of sets , each spanning and having exactly elements, where contains as its first elements.

Base case (). Set . It spans by assumption and has elements.

Inductive step. Suppose spans , where are the remaining elements (vectors from , possibly relabelled in earlier steps). We construct .

Since spans and :

Key observation. At least one must be nonzero. If all , then , contradicting the linear independence of .

(Note what happens if , i.e., : there are no at all, the -sum is empty, and would have to be a linear combination of alone. That directly contradicts independence of . So the inductive step cannot be executed once , which forces .)

When : relabel so that . Solving the expansion for :

So lies in the span of the remaining vectors. By the span-preservation lemma (§4), removing it does not shrink the span. Set

Then spans , has elements, and contains .

Conclusion. The inductive step succeeds for every with , and fails — producing a contradiction with the independence of — the moment . Therefore .

How the theorem follows. If and are both bases:

• spans , and is linearly independent, so .
• spans , and is linearly independent, so .
• Therefore .

This argument is symmetric — it treats both bases on equal footing — and the geometry is transparent: you cannot fit more independent directions into a space than it takes to span it.

Finitely-spanned vs. finite-dimensional

The Steinitz lemma assumes is spanned by a finite set . This is actually equivalent to saying is finite-dimensional (it has a finite basis), once the theorem is in hand. Before the theorem, “finitely spanned” is the weaker assumption we can work with. Many important spaces — , , polynomials of all degrees — are infinite-dimensional: no finite spanning set exists. The Steinitz lemma and the dimension theorem simply do not apply to them.

---

Looking ahead

With dimension defined and well-founded, the next lecture will complete the proof of the Steinitz exchange lemma, then use dimension to:

• Classify all subspaces of by their dimension (-dimensional = , -dimensional = line through origin, …, -dimensional = ).
• Relate the dimension of a solution space to the number of free variables in the corresponding system (dimension = number of free variables).
• Introduce the rank of a matrix as the dimension of the column space, and state the rank–nullity theorem.

---

Textbook references

Topic	Axler (2nd ed.)	Hefferon (4th ed.)	Treil
Linear dependence ↔ non-unique representations	Ch. 2, “Linear Independence”	Ch. 2, §II.1	Ch. 2, §2
Dependence ↔ one vector in span of others	Ch. 2, 2.21	Ch. 2, §II.1, Lem. 1.7	Ch. 2, §2
Removing a dependent vector preserves span	Ch. 2, 2.21	Ch. 2, §II.1	Ch. 2, §2
Building a basis from a finite spanning set	Ch. 2, 2.31	Ch. 2, §I.1, Thm. 1.12	Ch. 2, §3
Dimension — definition	Ch. 2, 2.36	Ch. 2, §I.1, Def. 1.9	Ch. 2, §3
All bases have the same size	Ch. 2, 2.35	Ch. 2, §I.1, Thm. 1.12	Ch. 2, §3
Steinitz exchange lemma	Ch. 2, 2.22	Ch. 2, §I.2	Ch. 2, §3