Chapter 1: Matrices & Systems of Equations | MTS203 Linear Algebra
Leon 8th Ed.
Chapter 1: Matrices & Systems of Equations
Linear systems · Row echelon form · Matrix arithmetic · Elementary matrices · Partitioned matrices
Probably the most important problem in all of mathematics is solving a system of linear equations. Over 75% of all problems in scientific or industrial applications involve a linear system at some stage — from economics and genetics to electronics and structural engineering. This chapter builds the complete machinery to solve them.
Section 1.1
Systems of Linear Equations
A linear equation in $n$ unknowns has the form $a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$. A system is a collection of $m$ such equations sharing the same variables $x_1, \ldots, x_n$. We call it an $m \times n$ system.
The Three Possibilities — Fundamental Theorem
Every linear system has exactly one of:
No solution (inconsistent) — the equations contradict each other
Exactly one solution (unique) — the system pinpoints a single point
Infinitely many solutions — parameterized by one or more free variables
Nothing else is possible. This is the bedrock fact of linear algebra.
Two equations in two unknowns. Click to cycle through all three cases. Each case has a distinct geometric picture.
Equivalent Systems & Row Operations
Two systems are equivalent if they have the same solution set. We transform a messy system into a simpler equivalent one using three elementary row operations — none of which change the solution set:
Row Swap: interchange any two equations
Row Scale: multiply any equation by a nonzero constant $\alpha$
Row Replace: add a multiple of one equation to another (the workhorse)
Gaussian Elimination
Use row operations to reduce the system to strict triangular form (each equation has one fewer variable than the one above it), then solve by back substitution — substituting from the bottom equation upward.
📘 Example 1.1 — Back Substitution (4 variables)
Solve the triangular system:
$$2x_1 - x_2 + 3x_3 - 2x_4 = 1,\quad x_2 - 2x_3 + 3x_4 = 2,\quad 4x_3 + 3x_4 = 3,\quad 4x_4 = 4$$
Work from the bottom up
A matrix is in Row Echelon Form (REF) if: (1) all-zero rows are at the bottom, (2) each leading nonzero entry (the pivot) is strictly right of the pivot above — forming a staircase.
It is in Reduced Row Echelon Form (RREF) if additionally: each pivot $= 1$ and is the only nonzero in its column. The process of reaching RREF is Gauss-Jordan reduction.
Staircase structure of REF/RREF. Blue cells = pivots (= 1). Yellow = free columns (no pivot — generate free variables). Grey = forced zeros. Click to toggle between REF and RREF.
Free Variables and the General Solution
Columns with pivots give lead (basic) variables. Columns without pivots give free variables — they can take any value. Each free variable generates a linearly independent direction in the solution set.
Consistency Test — One Line
After row-reducing $[A|\mathbf{b}]$: inconsistent iff a row $[\,0\;\cdots\;0\;|\;c\,]$ with $c \neq 0$ appears. Otherwise: count free variables $k$. If $k=0$ → unique solution; if $k \geq 1$ → infinitely many.
📘 Example 1.3 — RREF with Two Free Variables
$$\begin{pmatrix}-1&1&-1&3\\3&1&-1&-1\\2&-1&-2&-1\end{pmatrix}
\xrightarrow{\text{RREF}}
\begin{pmatrix}1&0&-1&1\\0&1&-2&4\\0&0&0&0\end{pmatrix}$$
Lead variables: $x_1, x_2$. Free variables: $x_3 = s$, $x_4 = t$.
$$x_1 = s - t, \quad x_2 = 2s - 4t$$
$$\mathbf{x} = s\begin{pmatrix}1\\2\\1\\0\end{pmatrix} + t\begin{pmatrix}-1\\-4\\0\\1\end{pmatrix}, \quad s,t \in \mathbb{R}$$
Infinitely many solutions: a 2-dimensional plane through the origin in $\mathbb{R}^4$.
📘 Example 1.4 — Inconsistent System
$$\begin{pmatrix}1&2&1&1\\2&4&2&3\end{pmatrix}
\xrightarrow{R_2 - 2R_1}
\begin{pmatrix}1&2&1&1\\0&0&0&1\end{pmatrix}$$
Row 2 reads $0 = 1$ — a contradiction.
Inconsistent. No solution exists. Geometrically, the two planes are parallel.
Over and Under-determined Systems
Type
Condition
Typical outcome
Overdetermined
More equations than unknowns ($m > n$)
Usually inconsistent (but can have a solution)
Square
$m = n$
Unique solution iff $\det(A) \neq 0$ (see Chapter 2)
Underdetermined
Fewer equations than unknowns ($m < n$)
Either inconsistent or infinitely many
Section 1.3
Matrix Arithmetic
An $m \times n$ matrix $A = (a_{ij})$: $m$ rows, $n$ columns. Entry $a_{ij}$ is in row $i$, column $j$. The $j$-th column vector is $\mathbf{a}_j$.
The Four Operations
Operation
Requires
$(i,j)$ entry of result
$A + B$
Same size $m \times n$
$a_{ij} + b_{ij}$
$\alpha A$
Any scalar $\alpha$
$\alpha\, a_{ij}$
$AB$
$A$ is $m\times n$, $B$ is $n \times r$
$\displaystyle\sum_{k=1}^n a_{ik}\,b_{kj}$
$A^T$
$A$ is $m \times n$
$(A^T)_{ij} = a_{ji}$
Matrix multiplication: entry $(i,j)$ of $AB$ = dot product of row $i$ of $A$ with column $j$ of $B$. Hover over a result cell to highlight the contributing row and column.
⚠ Non-Commutativity
$AB \neq BA$ in general. Always check dimensions before multiplying: "$A$ is $m\times n$, $B$ is $n\times r$" — result is $m\times r$. If sizes don't match, $AB$ is simply undefined.
Key insight — $A\mathbf{x}$ as a linear combination of columns:
This is the most important way to think about matrix-vector multiplication. The system $A\mathbf{x} = \mathbf{b}$ asks: can $\mathbf{b}$ be written as a linear combination of the columns of $A$?
Key Algebraic Rules
Associativity: $(AB)C = A(BC)$ ✓
Distributivity: $A(B+C) = AB + AC$ ✓
$(AB)^T = B^T A^T$ — order reverses for transpose
$AB \neq BA$ in general ✗
$AB = O$ does NOT imply $A = O$ or $B = O$ ✗
Symmetric Matrices
$A$ is symmetric if $A^T = A$ (equivalently, $a_{ij} = a_{ji}$ for all $i,j$). Covariance matrices in statistics, adjacency matrices of undirected graphs, and many physics matrices are symmetric. Key fact: $A^T A$ and $AA^T$ are always symmetric.
📘 Example 1.5 — Matrix Multiplication
$$A = \begin{pmatrix}1&2&0\\3&-1&4\end{pmatrix}_{2\times3},\quad B = \begin{pmatrix}2&1\\0&3\\-1&2\end{pmatrix}_{3\times2}$$
$AB$ is $2\times2$. Entry $(1,1)$: row 1 of $A$ · col 1 of $B = 1(2)+2(0)+0(-1)=2$. Entry $(1,2)$: $1(1)+2(3)+0(2)=7$.
$$AB = \begin{pmatrix}2 & 7 \\ 2 & 8\end{pmatrix}$$
Note: $BA$ is $3\times3$ — completely different object.
$AB = \begin{pmatrix}2&7\\2&8\end{pmatrix}$
Section 1.4
Matrix Algebra & Inverses
Invertible (Nonsingular) Matrix — The Big Equivalence
An $n\times n$ matrix $A$ is invertible if $\exists A^{-1}$ with $AA^{-1} = A^{-1}A = I_n$. All of the following are equivalent:
An elementary matrix $E$ is obtained from $I$ by a single row operation. Left-multiplying $A$ by $E$ performs that row operation on $A$. This gives us a way to express row reduction algebraically.
Three Types and Their Properties
Type
Row operation
$\det(E)$
$E^{-1}$
I
Swap rows $i \leftrightarrow j$
$-1$
$E$ itself (swap back)
II
$R_i \to \alpha R_i\; (\alpha \neq 0)$
$\alpha$
Type II with $1/\alpha$
III
$R_j \to R_j + c\, R_i$
$1$
Type III with $-c$
For any elementary matrix: $\det(EA) = \det(E)\cdot\det(A)$.
LU Factorization (Preview)
Gaussian elimination (Type III operations only, no swaps) factors $A = LU$ where $L$ is lower triangular with 1s on the diagonal and $U$ is upper triangular. Solving $A\mathbf{x} = \mathbf{b}$ splits into two fast triangular solves: $L\mathbf{y} = \mathbf{b}$ then $U\mathbf{x} = \mathbf{y}$. This is how MATLAB and NumPy solve linear systems.
Section 1.6
Partitioned Matrices
We can cut a matrix into blocks (submatrices) and treat them like scalars in multiplication — as long as adjacent block dimensions match. Block multiplication follows the same row-times-column rule.
📘 Example 1.7 — Block Structure Simplifies Inverses
If $A = \begin{pmatrix}I & B \\ O & I\end{pmatrix}$ (block upper triangular), then
$$A^{-1} = \begin{pmatrix}I & -B \\ O & I\end{pmatrix}$$
Verify by block multiplication: $\begin{pmatrix}I&B\\O&I\end{pmatrix}\begin{pmatrix}I&-B\\O&I\end{pmatrix} = \begin{pmatrix}I&O\\O&I\end{pmatrix}$ ✓
Block structure makes the pattern obvious — no computation needed. This idea recurs throughout numerical linear algebra.