2: Solving Linear Systems

Solving a linear system means finding a recipe that produces a target dish. You have ingredients (matrix columns), you know what you want to cook (the vector $\mathbf{b}$), and you need to figure out the quantities (the solution $\mathbf{x}$). Sometimes there’s exactly one recipe. Sometimes there are infinitely many ways to hit the target. Sometimes it’s impossible,the ingredients you have can’t produce that flavor.

The algorithm for answering “does a solution exist, and if so, what is it?” is row reduction. It’s mechanical, systematic, and reveals everything about the system’s structure. This is the computational heart of linear algebra.

Systems of Linear Equations

(What is a Linear System?)

A system of linear equations looks like:

This is the same as the matrix equation:

where $A$ is the $m \times n$ coefficient matrix, $\mathbf{x}$ is the vector of unknowns, and $\mathbf{b}$ is the target vector.

(Geometric Interpretation)

Each equation represents a hyperplane in $\mathbb{R}^n$. Solving the system means finding where all these hyperplanes intersect.

In $\mathbb{R}^2$: Each equation is a line. The solution is where the lines meet.

• Two lines typically intersect at one point (unique solution)
• Parallel lines never meet (no solution)
• The same line counted twice (infinitely many solutions)

In $\mathbb{R}^3$: Each equation is a plane. The solution is where all planes meet,a point, a line, a plane, or nothing.

In higher dimensions: Same idea, harder to visualize.

(Consistency)

A system is consistent if it has at least one solution. Otherwise it’s inconsistent (no solution exists).

Example of inconsistent system:

These are parallel lines,they never intersect. No $(x, y)$ satisfies both equations.

The Augmented Matrix

To solve $A\mathbf{x} = \mathbf{b}$, we work with the augmented matrix:

This glues the coefficient matrix and the target vector together. Row operations apply to both simultaneously.

Example:

Row Echelon Form

(Pivots)

The pivot of a row is its leftmost nonzero entry.

Example:

The pivots are $2$, $-1$, and $5$.

(Row Echelon Form, REF)

A matrix is in row echelon form if:

1. All zero rows are at the bottom
2. Each pivot is to the right of the pivot in the row above

Examples:

Both are in REF,pivots descend in a “staircase” pattern.

(Reduced Row Echelon Form, RREF)

A matrix is in reduced row echelon form if:

1. It’s in REF
2. Every pivot equals $1$
3. Every pivot is the only nonzero entry in its column

Examples:

RREF is unique,every matrix has exactly one RREF.

Row Operations

Three operations preserve solutions:

1. Row swap: Exchange two rows
2. Row scaling: Multiply a row by a nonzero scalar
3. Row replacement: Add a multiple of one row to another

Key fact: If you row-reduce $[A \mid \mathbf{b}]$ to $[\text{rref}(A) \mid \mathbf{b}']$, the solutions don’t change. The systems $A\mathbf{x} = \mathbf{b}$ and $\text{rref}(A)\mathbf{x} = \mathbf{b}'$ are equivalent.

(Example: Row Reduction)

Solve:

Augmented matrix:

Step 1: $R_2 - 2R_1$, $R_3 - R_1$:

Step 2: $R_3 - R_2$:

Step 3: $R_1 - R_2$:

This is RREF. Now read off the solution.

Variables: Basic and Free

(Basic Variables)

A variable $x_i$ is basic if column $i$ of $\text{rref}(A)$ contains a pivot.

(Free Variables)

A variable $x_i$ is free if column $i$ of $\text{rref}(A)$ has no pivot.

In the example above:

• $x$ and $z$ are basic (columns 1 and 3 have pivots)
• $y$ is free (column 2 has no pivot)

Free variables can take any value,they parameterize the solution set.

(General Solution)

From the RREF:

Solve for basic variables in terms of free variables:

Solution set:

This is a line in $\mathbb{R}^3$,infinitely many solutions parameterized by $t$.

The Rouché–Capelli Theorem

This theorem tells you how many solutions exist by looking at the RREF.

Let:

• $[A \mid \mathbf{b}]$ be the augmented matrix
• $A$ be the coefficient matrix (without $\mathbf{b}$)

(Inconsistent System: No Solutions)

The system is inconsistent if and only if:

The last column of $\text{rref}([A \mid \mathbf{b}])$ has a pivot.

This means you get a row like:

This says $0 = 1$,impossible.

Example:

Last column has a pivot,no solution.

(Unique Solution)

The system has exactly one solution if and only if:

1. Last column of $\text{rref}([A \mid \mathbf{b}])$ has no pivot, AND
2. Every column of $\text{rref}(A)$ has a pivot

Equivalently:

Every variable is basic,no free variables.

Example:

Unique solution: $x = 2$, $y = 3$.

(Infinitely Many Solutions)

The system has infinitely many solutions if and only if:

1. Last column of $\text{rref}([A \mid \mathbf{b}])$ has no pivot, AND
2. $\text{rref}(A)$ has at least one column without a pivot

Equivalently:

There’s at least one free variable.

Dimension of solution set:

This is the number of free variables.

(Summary Table)

Examples

(Example 1: Unique Solution)

Solution: $x = 2$, $y = 1$ (unique).

(Example 2: No Solution)

Inconsistent (pivot in last column).

(Example 3: Infinitely Many Solutions)

General solution: $x = 4 - 2t$, $y = t$ for any $t \in \mathbb{R}$.

This is a line (1-dimensional solution space).

Why This Matters

Row reduction is the universal algorithm for linear systems. It tells you:

• Does a solution exist? (Check for pivot in last column)
• Is it unique? (Count free variables)
• What is the solution? (Solve for basic variables in terms of free ones)

Every computational tool in linear algebra,finding inverses, computing kernels, checking independence,ultimately reduces to row reduction.

The geometry is simple: each equation carves out a hyperplane. The algebra is mechanical: row operations preserve solutions. Together, they give you a complete answer to “does this system have solutions, and if so, what are they?”

Next, we’ll build the geometric language,vectors, spans, linear combinations,that makes sense of what these solutions mean.