june-17

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

Administrative

• Tutorial format going forward: tutorial and final long-answer questions will follow an A/B/C structure — part A (computation/manipulation), part B (explanation), part C (proof). The difficulty increase from Week 5 to Week 6 tutorials is deliberate and permanent.
• Reading week: begins tomorrow (June 17). This lecture is the only course activity this week. A tutorial problem sheet from today is also available as optional extra practice.
• Midterm results and curve: the midterm will be posted today for review. After looking at submissions, the volume of problems was likely greater than optimal for the time given. A possible curve is under consideration — not a flat percentage bonus, but raising the total-point denominator (e.g., if one full question was unfairly inaccessible, its points would be removed from the maximum). No final decision has been made yet; an announcement will follow during reading week.
• Midterm grades and regrade requests: grades will be posted to Piazza today or tomorrow (double-reviewed). A regrade request window of approximately 10 days will follow. Requests are to be submitted as private Piazza questions; details will be announced. Reviewing your own midterm is strongly encouraged — identifying gaps under exam conditions is one of the most valuable learning activities.
• Presentation alternative: a poll for students who have not yet presented and wish to substitute a one-on-one meeting will go out during reading week.

---

1. Injectivity and surjectivity for linear maps

Last time we developed the language of injectivity and surjectivity for maps of sets. Now we apply it to linear transformations, where the extra structure — kernel and image — gives us clean algebraic characterisations.

Proposition

A linear transformation is injective if and only if .

Proof

() Suppose is injective. Let , so . Since also , we have . Injectivity gives . So the kernel contains only .

() Suppose . Assume . Then by linearity:

so . Therefore , so is injective.

Proof strategy note

The first direction tempts a proof by contradiction (“suppose something non-zero is in the kernel…”), but contradiction is not needed: simply take any and show it must be . Removing the unnecessary negation gives a cleaner, direct proof.

The picture to hold in mind: the kernel is the set of vectors that get “killed” to . An injective map kills nothing (except itself, which is unavoidable). Any non-trivial kernel means two distinct vectors — and — map to the same output , violating injectivity.

Proposition

A linear transformation is surjective if and only if .

This is not so much a theorem as a translation. Surjectivity means every has some with ; that is exactly the statement that every element of belongs to the image of , i.e., . No additional argument is needed — the two phrases are the same claim in two notations.

---

2. Dimension constraints on injectivity and surjectivity

The rank-nullity theorem () is the key tool for deciding whether a linear map between specific spaces can be injective, surjective, or bijective. Two illustrative cases:

Case: .

• Can be surjective? No. The rank-nullity theorem gives . So is at most a 2-dimensional subspace of , which cannot equal all of (a 3-dimensional space).
• Can be injective? Yes. Send the standard basis of to any two linearly independent vectors in . The image is a plane in , and the kernel is .
• Can be bijective? No, since it cannot be surjective.

Case: .

• Can be surjective? Yes. Projection onto any two-dimensional subspace works: every output vector is achieved.
• Can be injective? No. If had trivial kernel, rank-nullity gives , but has dimension at most 2 — a contradiction.
• Can be bijective? No, since it cannot be injective.

Example. Let have matrix , where the columns are . The three columns live in , so they must be linearly dependent. Inspection shows , i.e.,

So , and is not injective — as expected.

The general principle

Any bijective linear map between finite-dimensional spaces forces . Proof: bijectivity implies (nullity 0) and , so rank-nullity gives . Conversely, any two vector spaces of equal (finite) dimension are isomorphic: send a basis of to a basis of ; the resulting linear map is bijective. So a bijective linear map exists between and if and only if .

---

3. A digression on cardinality

The dimension argument above relied completely on linearity. Remove linearity and the story becomes radically different.

Question: is there a bijection (as sets, not necessarily linear) between and ? Your intuition says no — the plane “has more points.” But intuition is wrong: there exists a bijection. Here is one construction.

Restrict attention to to avoid carrying-digit complications. Every has a decimal expansion Send to the pair:

interleaving the even-indexed and odd-indexed digits into two separate decimal expansions. To recover from the pair, re-interleave — so is invertible, hence bijective.

What makes this possible

The map is a bijection, but it is violently discontinuous — it tears apart at every point and reassembles the pieces. This is only possible because bijectivity for sets is purely a counting statement: “same number of elements.” The rational numbers and the integers are also bijective as sets (list the rationals in a diagonal grid and enumerate them), yet and are not bijective — Cantor’s diagonal argument shows that is strictly larger. This study of the “sizes” of infinite sets is called cardinality. The moral for us: the restriction to linear maps is what makes linear algebra tractable. Without it, we enter a world where a line has as many points as a plane, and a clean theory becomes impossible.

---

4. Composition of linear maps

We have multiple vector spaces connected by linear transformations. The natural next operation is to chain them.

Definition (Composition)

Let and be linear transformations. Their composition is the map

Note the ordering: means “first apply , then apply .” The right-to-left convention matches the bracket convention but conflicts with the left-to-right reading of "" — this mismatch is simply a convention one learns to live with.

Linearity of compositions. If and are linear, then so is :

---

5. Matrix multiplication

Suppose has matrix (an matrix) and has matrix (an matrix). We want to find the matrix of the composition .

The matrix of a linear map is determined by where the basis goes. So we need to compute for each standard basis vector of . This gives us the -th column of the matrix of .

Compute, using linearity:

where denotes the -th column of and is the entry of .

This says: the -th column of the product matrix is the linear combination of the columns of with coefficients taken from the -th column of .

Definition (Matrix product)

Let be an matrix and an matrix. Their product is the matrix whose -th column is

Equivalently, the entry of is

This is why the product represents the composition : the formula is not an arbitrary definition but the unique answer to “what matrix makes work in coordinates.”

Why and not ?

The ordering is forced by the composition convention. is applied first (matrix ) and second (matrix ), so the product is on the left, on the right. Reversing the order gives a completely different matrix (when both products are defined). In general, — matrix multiplication is not commutative.

Numerical example. Let (matrix of , so ) and (matrix of ).

Column 1 of : .

Column 2 of : .

So .

The element formula

To compute a single entry : take row of and column of , and multiply entry-by-entry, summing the results. This is the dot product of a row and a column — the same operation as multiplying a matrix by a column vector (which is a special case with ).

---

Textbook references

Topic	Axler	Hefferon	Treil
Injective ker T = {0}	Ch. 3, 3.16	Ch. 3, §IV.2	Ch. 3, §3
Surjective Im T = W	Ch. 3, 3.19	Ch. 3, §IV.2	Ch. 3, §3
Composition of linear maps	Ch. 3, 3.7–3.9	Ch. 3, §III.1	Ch. 2, §2
Matrix multiplication	Ch. 3, 3.43–3.45	Ch. 3, §III.4	Ch. 2, §2
Cardinality	—	—	—