june-10

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 10 — June 10, 2026

Administrative

• Midterm (Saturday, June 13, 9–11 AM): closed book; no calculators or electronic devices. Bring your UToronto ID card — booklets are matched to students via QR codes. Arrive a few minutes early.
• Pre-midterm office hours: Thursday (afternoon in-person; morning and evening online) and Friday (afternoon in-person; evening online). Approximately 4 TA hours across both days. Check Quercus/Piazza for exact times and links.
• Next Tuesday (June 16) follows the Friday schedule for all courses (U of T makeup for Good Friday). Tutorial section 0004 runs; one hour of lectures.
• Additional course materials: three new pages are posted — Theorems and Definitions, Row Reduction and RREF, and The Coordinate Map. All have been reviewed and proofread by the instructor. Theorems and Definitions is particularly recommended before the midterm.
• Rank-nullity and the midterm: the statement and the examples from Lecture 9 §4 are on the midterm. The proof is not required. What is expected: knowing the statement, being comfortable with the examples (dimensions add up), and having the “degrees of freedom” intuition.
• Reflection question clarification: students who interpreted “write ” as writing the literal expression rather than computing the value will receive full credit.
• Reading week: begins the week of June 16–20 (extended due to the half-course exam session that week).

---

1. The road ahead

We now have the central language of linear algebra — vector spaces and linear transformations. Before proceeding to today’s proofs, a brief map of where the course goes next. None of this is midterm material.

The first questions we will ask about a linear transformation are function-theoretic: can be inverted? A linear map that is both injective (different inputs give different outputs) and surjective (every vector in is an output) is called an isomorphism. The conclusion turns out to be clean: every finite-dimensional vector space of dimension is isomorphic to . The space of polynomials of degree at most 2 and the space are “the same object” from a linear-algebraic perspective — two descriptions of one structure, related by an isomorphism that sends each polynomial to its coordinate vector.

The deeper question is what a transformation does geometrically. The main tools are eigenvalues and eigenvectors — directions that merely stretches without rotating. The search for eigenvalues will force the introduction of complex numbers, naturally and unavoidably. After eigenvalues come determinants — a single scalar attached to a matrix that encodes its volume-scaling factor and controls invertibility. The course closes with applications: the most concrete is PageRank, the algorithm that made Google a search engine, which is built from scratch using the tools we are assembling now.

---

2. Steinitz Exchange Lemma — proof

The lemma was stated in Lecture 5 (May 27). Today’s lecture gives the full proof.

Theorem (Steinitz Exchange Lemma)

Let be a vector space with a finite spanning set . Let be any linearly independent set of vectors in . Then

Any linearly independent set is at most as large as any spanning set.

Proof

Write and .

Step 1: insert . Since spans :

Since (a linearly independent set contains no zero vector), at least one . Solve for :

So . Any vector that was expressible using can now be expressed without it (substitute the formula above). Therefore replacing by still gives a spanning set:

Step 2: insert . We want to replace one of the remaining (not the position already occupied by ) with . Write in terms of the current spanning set :

Why some -coefficient must be nonzero. Suppose all for — that is, all the coefficients attached to the remaining ‘s are zero. Then . But and are both in , which is linearly independent, so is impossible. Therefore some with . Solve for :

Replacing by yields a spanning set .

Repeating the argument. At each subsequent step, we have a spanning set containing and some remaining ‘s. Write in terms of this set. If all coefficients on the remaining ‘s were zero, then would be a linear combination of — a non-trivial dependence inside , impossible. So some -coefficient is nonzero, and we can make the exchange.

Conclusion. The exchange succeeds as long as there are remaining ‘s to replace. If , after steps the spanning set consists entirely of vectors from . Any remaining lies in , so

for some scalars — a non-trivial linear combination of summing to (the coefficient of is ). This contradicts the independence of . So is impossible, and .

Why dimension is well-defined

The theorem that all bases of have the same size follows in two lines. Let and be two bases. Then is linearly independent and spans , giving . Symmetrically , so . The proof uses no coordinates, no row operations, no real numbers — only vectors.

---

3. Basis extension

Theorem (Basis Extension)

Let be a subspace of a finite-dimensional vector space . Every basis of can be extended to a basis of .

Proof

Let be a basis of , with . If then and there is nothing to prove. Otherwise , so there exists with . Since lies outside the current span, is linearly independent. Repeat: at each stage, if the current list does not yet span , pick a vector outside its span and append it — this preserves linear independence. After at most steps the list has linearly independent vectors; by the dimension shortcut (Lecture 7, §3), this is already a basis of .

Why the process terminates

Each step strictly increases the size of the linearly independent list. The Steinitz lemma guarantees that any linearly independent set in has size at most . So the process cannot run indefinitely — it must terminate at a basis.

This theorem is the key tool for the rank-nullity proof below, and is the standard technique for any dimension argument involving subspaces.

---

4. Rank-nullity theorem — full proof

The statement, intuition, and proof strategy were given in Lecture 9 §5. The missing ingredient was Basis Extension (§3 above), which allows us to extend a basis of to a basis of . We now complete the proof.

Theorem (Rank-Nullity)

Let be a linear transformation with finite-dimensional. Then

Proof

Step 1: set up the right basis of . Let be a basis of , where . By Basis Extension (§3), complete this to a basis of :

Step 2: the set is a basis of .

Spanning. Any image vector has the form . Expand in and apply linearity:

Every image vector is a linear combination of .

Linear independence. Suppose . By linearity:

Since spans , write . Then:

Since is linearly independent, all coefficients are zero: in particular .

Step 3: count.

The picture

The basis spans the “flat” directions — those that collapses to . The extension spans the “surviving” directions. Their images land as linearly independent vectors in , exactly filling . Directions that vanish + directions that survive = total directions in .

---

5. Dimension of a sum of subspaces

As an application of the Basis Extension technique, we state (without full proof) the following formula, which appeared in tutorial problems.

Proposition

Let and be finite-dimensional subspaces of a vector space . Then

where the sum .

Proof strategy. Take a basis of ; extend it to a basis of ; extend it separately to a basis of . The union of these two extended bases is a basis of . Counting the vectors gives the formula. Verifying that is itself a subspace of is a recommended exercise.

---

Textbook references

Topic	Axler	Hefferon	Treil
Steinitz Exchange Lemma	Ch. 2, 2.22–2.23	Ch. 2, §II.1	Ch. 2, §2
Basis extension	Ch. 2, 2.32–2.33	Ch. 2, §II.2	Ch. 2, §2
Rank-nullity (full proof)	Ch. 3, 3.22	Ch. 3, §IV.2	Ch. 3, §3
Dimension of a sum	Ch. 2, 2.43	Ch. 2, §III	Ch. 2, §3