may-20

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 4 — May 20, 2026

Administrative

• Reflection 1 is live on Quercus. It has 12 questions (multiple choice, select-all, or numeric). There are two attempts — aim to take the first without looking anything up, then review what you got wrong before attempting again. Questions combine two or three steps rather than testing isolated definitions.
• Tutorials: expect problems to become less scaffolded as the semester progresses, converging toward the style of midterm and final questions.
• Today’s alignment: this lecture is more closely aligned with Treil than with Hefferon; Treil’s treatment of Gaussian elimination and row reduction is less algorithmic and shows the underlying structure more clearly.

---

1. A worked example — Gaussian elimination

Consider the system of two equations in three unknowns:

We want to find all triples satisfying both equations. The strategy is to simplify the system step by step — replacing it with an equivalent system (same solution set) that is easier to read off.

Label the equations and . The key move is to eliminate from the second equation:

The second equation becomes , i.e., . We now have:

Scale the second equation by (operation ):

Now use the known value of to eliminate it from the first equation ():

The second equation fixes . The first equation constrains and but cannot fix both — one of them is free. Choosing as the parameter:

Vector form. Grouping terms with and without :

The solution set is a line in , passing through the point with direction vector .

Non-uniqueness of the parametric description

Neither the particular solution nor the direction vector is unique. Any point on the line can serve as the starting point, and any nonzero scalar multiple of the direction vector describes the same direction. The line itself is unique; the way of writing it is not. This is one of the questions in Reflection 1.

The homogeneous counterpart. Setting the right-hand side to zero gives the associated homogeneous system. Its solution set consists of all directions along the original line:

This is the span of the single vector . (The word “span” is defined precisely in §5 below.)

---

2. Elementary row operations

The steps above fall into three types, collectively called elementary row operations:

Operation	Notation	Effect
Add a multiple of one row to another		Eliminates a variable
Swap two rows		Reorders equations
Scale a row by a nonzero scalar		Normalises a coefficient

Each operation is invertible — you can undo it with an operation of the same type — so each transforms the system into one with the same solution set. This is why the arrows in the worked example denote equivalence, not just implication.

Why row operations preserve solution sets

Here is the key idea without a full proof. If satisfies both and , it automatically satisfies (since a linear combination of true equalities is true). Conversely, if it satisfies and , then adding back recovers , so it satisfies . The two systems are equivalent because each is obtainable from the other by operations of the same type.

---

3. Matrix notation

Writing out variables at every step wastes space and obscures the pattern. Once we fix an ordering of variables ( first, second, third), the system carries exactly the same information as two tables of numbers.

Coefficient matrix — the left-hand side coefficients, one row per equation:

Augmented coefficient matrix — the coefficient matrix with the right-hand side appended after a vertical bar:

Row operations on the augmented matrix exactly mirror the operations on equations. The Gaussian elimination of §1 looks like:

Dividing the first row by gives the reduced echelon form:

For a homogeneous system the right-hand side is all zeros and stays all zeros throughout — so for homogeneous systems we can work with just the coefficient matrix, since the right column never changes.

Echelon form vs. reduced echelon form

A matrix is in echelon form (row echelon form) if: (i) all zero rows are at the bottom, and (ii) each leading nonzero entry (called a pivot) is strictly to the right of the pivot in the row above — a staircase pattern. It is in reduced echelon form if additionally: (iii) every pivot equals , and (iv) all entries above each pivot are zero (not just below). Reduced echelon form is the endpoint of the Gauss-Jordan procedure; echelon form is an intermediate target. Both are shown in the matrix sequence above.

---

4. The Gauss-Jordan procedure

The algorithm below transforms any augmented matrix into reduced echelon form, making the solution set immediately readable. It generalises the specific example in §1 to arbitrary systems.

Algorithm (Gauss-Jordan / Gaussian elimination).

1. Find the leftmost non-zero column. If the current leading entry is zero, swap with a lower row that has a non-zero entry in that column.
2. Scale the current row so the leading entry becomes .
3. Eliminate: subtract multiples of the current row from all other rows (not just rows below) to make every other entry in that column zero.
4. Move down to the next row and repeat from step 1, ignoring all rows and columns already processed.

The result is the reduced echelon form (also called reduced row echelon form, or RREF).

Pivot and free variables. Each column containing a pivot (a leading ) corresponds to a pivot variable — it is determined by the remaining variables. Each column without a pivot corresponds to a free variable — it can be assigned any real value, becoming the parameter(s) in the solution.

In the example of §1: columns 1 and 3 contain pivots ( and ), while column 2 does not ( is free).

Uniqueness of reduced echelon form

A remarkable fact — which Hefferon proves carefully in Ch. 1 — is that the reduced echelon form of a matrix is unique, regardless of which sequence of valid row operations you use to reach it. In particular, the set of pivot columns is uniquely determined by the original matrix. This means the distinction between pivot and free variables does not depend on how you row-reduce, only on the matrix itself (and the chosen ordering of variables).

Number of parameters and geometry

The number of free variables equals the number of parameters in the general solution, which in turn determines the dimension of the solution set:

• 0 free variables → unique solution (a single point)
• 1 free variable → solution is a line
• 2 free variables → solution is a plane
• free variables → solution is a “-dimensional flat” inside

This will be made precise when we study dimension later in the course.

---

5. Particular solution plus homogeneous solution

The structure of the solution set seen in §1 — a specific point plus all possible homogeneous solutions — is not a coincidence. It holds for any linear system.

Lemma. If is any particular solution of the (non-homogeneous) system , then the complete solution set is

Proof sketch. If and both solve , then solves (the ‘s cancel). Conversely, if solves the homogeneous system, then solves the original: .

This is why understanding the homogeneous system is essentially the same as understanding the original: once you have one particular solution, the rest of the solution set is determined by the homogeneous part. Geometrically, the homogeneous solutions are the directions along the solution set; the particular solution is the offset from the origin.

---

6. Subspaces

The solution set of a homogeneous system is not just a subset of — it inherits the vector space structure. This motivates the following definition.

Definition

A subspace of a vector space is a subset that is:

1. Contains the zero vector:
2. Closed under addition:
3. Closed under scalar multiplication:

Equivalently (and, arguably, better): is a subspace of if and only if is itself a vector space with respect to the same operations as . Conditions (2) and (3) — the closure conditions — are what need to be verified; all other vector space axioms (commutativity, associativity, distributivity, …) are automatically inherited from .

The zero vector condition

Conditions (2) and (3) alone do not guarantee : condition (3) implies if is nonempty. The usual convention is to list explicitly, or equivalently require . Note: is not one of the eight listed axioms — it is a consequence of them (a good exercise for Tutorial 2).

Lemma

The solution set of any homogeneous system of linear equations in variables is a subspace of .

Proof

Let be the solution set. Check the three conditions:

1. Plugging into a homogeneous equation gives , so .
2. If then — this is exactly the Lemma proved in Lecture 3 (§4), applied equation by equation.
3. If and , then plugging into any equation gives .

Geometric picture. In , the subspaces are exactly: , all lines through the origin, and itself. In : , lines through the origin, planes through the origin, and .

Why "through the origin"?

A line or plane in or that does not pass through the origin cannot be a subspace: it violates condition (1), since the zero vector is not on it. This is also why the solution set of a non-homogeneous equation is never a subspace — it is a coset of a subspace, shifted away from the origin by the particular solution.

---

7. Span

We have already encountered linear combinations without naming them. Looking back at §1, the parametric solution

writes every solution as for . The homogeneous part — the set — is precisely the set of all scalar multiples of the direction vector, which is the same as all linear combinations of that single vector. More generally, when there are free variables, the parametric form writes every solution as a linear combination of direction vectors (plus a fixed particular solution). We now name this operation precisely.

Definition

Let be a vector space and let . A linear combination of is any expression of the form

where are called the coefficients of the linear combination.

We now give a name to the set of all linear combinations one can form from a given collection of vectors.

Definition

Let be a set of vectors in a vector space . The span of is

By convention, (the empty sum is defined to be zero).

Examples in .

— the line through the origin in the direction .

— every point in the plane is reachable.

.

The solution set from §1 revisited. The homogeneous solution set is — all scalar multiples of the direction vector.

An infinite-dimensional example. Let denote the vector space of all real sequences , with termwise operations. Define the elementary sequences

and let . What is ?

A linear combination produces the sequence — a sequence that is eventually zero. So:

In particular, the constant sequence is not in , even though it looks like "" — this infinite sum has no meaning in our setting, because the definition of span only allows finite linear combinations.

Infinite sums and functional analysis

In finite-dimensional spaces, the restriction to finite linear combinations is invisible — every subspace is a span of finitely many vectors. In infinite-dimensional spaces, it is crucial. The study of infinite linear combinations — series of vectors, convergence, completeness — is the domain of functional analysis, where the vector spaces are Banach spaces or Hilbert spaces and the theory requires significant analytic machinery. This example previews why infinite-dimensional linear algebra is genuinely harder: even something as simple as the span of all elementary sequences does not fill the whole space.

---

8. Lemma: Span(S) is a subspace

Lemma

For any set of vectors in a vector space , the span is a subspace of .

Proof

We verify the three subspace conditions.

Zero vector. If , then by convention, which contains . Otherwise, for any , we have .

Closed under addition. Take two elements of :

where (we can use the same list by setting missing coefficients to zero). Then, using distributivity of scalars over vectors (but also commutativity and associativity to move the summands around),

Closed under scalar multiplication. For , using associativity of scalar multiplication :

Which axioms were used? The proof implicitly uses: distributivity ; distributivity ; and associativity of scalar multiplication . This is a good exercise for seeing what the axioms of a vector space are actually for — they are not arbitrary; they are precisely what is needed to make statements like this lemma work in any vector space, not just .

---

Looking ahead

The next step is to ask: when does a set of vectors efficiently span a space? That is, when can we remove some vectors from without shrinking ? This leads to the concept of linear independence (and its opposite, linear dependence), and ultimately to the notion of a basis — a minimal spanning set. These are the central topics of Chapter 2 in Axler and Chapter 2 in Hefferon.

---

Textbook references

Treil as a reference for this lecture

As noted at the start of lecture, Treil’s Linear Algebra Done Wrong is more closely aligned with today’s material than Hefferon. Treil introduces systems of linear equations through the language of linear combinations and matrix multiplication from the outset, making the connection between row reduction and the underlying geometry more transparent. See Treil, Ch. 1, §§1–2.

Topic	Axler (2nd ed.)	Hefferon (4th ed.)	Treil
Elementary row operations	—	Ch. 1, §I.1–I.2	Ch. 1, §1
Gaussian elimination (worked examples)	—	Ch. 1, §I.1–I.2	Ch. 1, §1
Echelon form and reduced echelon form	—	Ch. 1, §I.2	Ch. 1, §1
Uniqueness of reduced echelon form	—	Ch. 1, §II.3 (Thm. 2.6)	—
Pivot and free variables	—	Ch. 1, §I.2	Ch. 1, §1
Particular + homogeneous decomposition	—	Ch. 1, §I.3, Lemma 3.7	Ch. 1, §2
Subspace — definition	Ch. 1, “Subspaces”	Ch. 2, §I.2, Def. 2.1	Ch. 1, §3
Solution set of homogeneous system = subspace	Ch. 1, “Subspaces” (Example)	Ch. 2, §III.1	Ch. 1, §3
Span — definition	Ch. 2, “Span and Linear Independence”	Ch. 2, §I.2, Def. 2.13	Ch. 2, §1
Span is a subspace	Ch. 2, “Span and Linear Independence”	Ch. 2, §I.2	Ch. 2, §1
Infinite-dimensional example ()	Ch. 1,	—	—