Row reduction is the computational workhorse of the course — it reveals rank, solves systems, and inverts matrices, all with the same three elementary moves. The theory explains why the moves are legal: each one is multiplication by an invertible matrix.
Almost every question so far — independence, span, rank, invertibility — reduces to solving a linear system. Row reduction is the one algorithm that answers them all.
Gaussian elimination is among the most-executed algorithms on Earth — the engine inside solvers for engineering, economics, and scientific computing, and (with pivoting) the core of numerical linear algebra libraries.
Versions of elimination appear in the Chinese Nine Chapters two thousand years ago; Gauss systematized it for astronomy. The exact complexity of matrix computation is still open — the true exponent of matrix multiplication is unknown.
(1) swap two rows; (2) multiply a row by a nonzero scalar; (3) add a multiple of one row to another. An elementary matrix is the result of one such move applied to $I$; performing the move on $A$ is the same as computing $EA$.
Every elementary matrix is invertible, and its inverse is elementary (undo the move). Consequently row operations change neither the solution set of $Ax=0$ nor the rank — they replace $A$ by $EA$ with $E$ invertible.
A matrix is in reduced row echelon form (RREF) when each nonzero row starts with a leading $1$, each leading $1$ sits strictly to the right of the one above, and each leading $1$ is the only nonzero entry in its column. Every matrix has a unique RREF; the number of leading $1$s is its rank.
$Ax=b$ is consistent iff $\operatorname{rank}(A)=\operatorname{rank}(A\,|\,b)$ — a pivot in the augmented column is the contradiction $0=1$. When consistent, the solutions have $n-\operatorname{rank}(A)$ free parameters: one particular solution plus the null space.
$x+2y=5$, $3x+4y=11$.
A homogeneous system with more unknowns than equations has a nontrivial solution: rank $\le$ number of equations $<$ number of unknowns, so a free variable exists. (This is the engine inside the Replacement Theorem of Unit 3.)
$A$ is invertible iff its RREF is $I$. In that case the row operations carrying $A$ to $I$ carry $I$ to $A^{-1}$ — because $E_k\cdots E_1A=I$ means $A^{-1}=E_k\cdots E_1$, which is exactly what lands on the right half of $[A\,|\,I]$.
$A=\left(\begin{smallmatrix}1&2\\3&4\end{smallmatrix}\right)$: reducing $[A\,|\,I]$ gives $A^{-1}=\left(\begin{smallmatrix}-2&1\\3/2&-1/2\end{smallmatrix}\right)$.
• Scaling a row by $0$ is not a row operation — it destroys information and
has no inverse.
• For $Ax=b$, row-reduce the augmented matrix; operating on $A$
alone loses $b$'s bookkeeping.
• "No free variables" needs a pivot in every column of $A$, not
every row.
• Over $\mathbb{Z}_p$ the same algorithm runs verbatim — just divide using
modular inverses.
Original problems written for this guide in the style of Friedberg, Insel & Spence exercises. Write a full solution before opening the answer.
Solve $x+2y=5$, $3x+4y=11$ by row reduction.
Find the rank of $\left(\begin{smallmatrix}1&2&3\\2&4&6\\1&1&1\end{smallmatrix}\right)$.
A homogeneous system has $3$ equations and $5$ unknowns. Must it have a nontrivial solution? How many free variables at least?
Invert $A=\left(\begin{smallmatrix}1&2\\3&4\end{smallmatrix}\right)$.
Show $x+y=1$, $2x+2y=3$ has no solution, using ranks.
Write the elementary matrix that swaps the rows of a $2\times2$ matrix, and find its inverse.
Prove: if $A$ is invertible, then $Ax=b$ has exactly one solution.
How many solutions does $x+y+z=0$ have over $\mathbb{Z}_2$?
Course coverage. This unit is part of the complete MAT240H1 topic map. It should cover the following items before you move on:
Use the current UofT MAT240H1 calendar topics as the coverage spine, and pair lecture notes with a Friedberg-Insel-Spence-style linear algebra text for extra reading. The exact assigned textbook should still be checked against the instructor syllabus.
The systems spine is: row operations preserve solution sets, row echelon form reveals rank and free variables, and elementary matrices encode the operations.
Use these after the main practice set. They are designed to force definition-level reasoning, theorem selection, and mixed application rather than routine calculation only.
What row pattern in an augmented matrix proves inconsistency?
If a system in 5 unknowns has rank 3 and is consistent, how many parameters are in the solution set?
What does left multiplication by an elementary matrix do?
State three equivalent conditions for an $n\times n$ matrix to be invertible.