Lesson 14.18 — Systems of Linear Equations

1 Introduction: Solving for Multiple Unknowns

Suppose you visit a stationery shop and purchase 2 pens and 1 notebook for a total of \$70. Shortly after, your friend visits the same shop and buys 1 pen and 1 notebook of the identical brand for \$50.

Now consider the question: What is the individual unit price of a single pen, and what is the unit price of a single notebook?

Formulating the Equations

Let $x$ represent the price of a single pen, and let $y$ represent the price of a single notebook. We can express the receipts as two linear equations:

Equation (1): Your receipt $$2x + y = 70$$

Equation (2): Friend's receipt $$x + y = 50$$

If you analyze equation (1) in isolation, infinitely many pairs of $(x, y)$ satisfy it—for instance, $x = 10, y = 50$, or $x = 25, y = 20$. However, when both constraints must hold simultaneously, a unique solution exists.

Subtracting Equation (2) from Equation (1) eliminates the variable $y$:

$$(2x + y) - (x + y) = 70 - 50 \implies x = 20$$

Substituting $x = 20$ back into Equation (2):

$$20 + y = 50 \implies y = 30$$

Hence, a pen costs \$20, and a notebook costs \$30. This mathematical system is known as a System of Linear Equations. From rendering 3D graphics and balancing electrical networks to training neural networks in machine learning, linear systems form the bedrock of computational problem solving.

2 Linear Equations & Systems of Linear Equations

Definition of a Linear Equation

An algebraic equation is called a Linear Equation if every variable appears to the first power ($1$) only, with no variable cross-products ($xy$), roots ($\sqrt{x}$), or non-linear transcendental functions ($\sin x, e^x$).

• Single Variable: $ax = b$ (e.g., $5x = 20 \implies x = 4$)

• Two Variables: $ax + by = c$ (e.g., $2x + 3y = 12$)

• $n$ Variables: $a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b$

Equation	Linear?	Rationale
$2x + 3y = 12$	✓ Yes (Linear)	Both variables have exponent 1; no cross-products or roots.
$x^2 + y = 10$	✗ No (Non-linear)	Variable $x$ has exponent 2 (quadratic parabolic term).
$xy = 12$	✗ No (Non-linear)	Variables $x$ and $y$ are multiplied together (cross-product).
$\sin(x) + 4y = 8$	✗ No (Non-linear)	Trigonometric sine function violates linearity.

What is a System of Linear Equations?

A collection of two or more linear equations sharing the same set of variables is known as a System of Linear Equations.

In general mathematical notation, a system of $m$ linear equations in $n$ unknown variables is formulated as:

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \ \quad \vdots \ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \end{cases}$$

where $a_{ij}$ denotes coefficients, $x_j$ denotes unknown variables, and $b_i$ denotes constant scalar terms.

3 The Three Possible Solution Regimes

No matter how many variables or equations a linear system contains, its solution space will always fall into exactly one of three mutually exclusive categories:

1 Unique Solution

Single Point of Intersection

Exactly one set of values satisfies all equations in the system simultaneously.

$x + y = 5$
$x - y = 1$
$\implies (x, y) = (3, 2)$

Consistent & Independent

2 Infinitely Many Solutions

Dependent Constraints

The equations represent identical or overlapping constraints with free parameters.

$x + y = 2$
$2x + 2y = 4$
$\implies y = t, x = 2 - t$

Consistent & Dependent

3 No Solution

Contradictory Constraints

Constraints are mutually exclusive. Geometrically, lines or planes are parallel and non-intersecting.

$x + y = 2$
$x + y = 5$
$\implies 0 = 3$ (Contradiction!)

Inconsistent

4 Graphical Method: The Geometry of Linear Systems

In the two-dimensional Cartesian plane ($\mathbb{R}^2$), every linear equation $ax + by = c$ plots as a straight line. Solving a system of two equations is geometrically equivalent to finding the relative spatial relationship between the two lines:

1. Intersecting Lines (Unique)

Slopes are distinct ($m_1 e m_2$). Exactly one intersection point exists.

2. Coincident Lines (Infinite)

Both equations depict the identical geometric line. Every point on the line is a solution.

3. Parallel Lines (None)

Equal slopes ($m_1 = m_2$) with different $y$-intercepts. No common points exist.

What happens in Three Dimensions ($\mathbb{R}^3$)?
In $\mathbb{R}^3$, each linear equation $ax + by + cz = d$ represents a flat 2D plane. Solving three equations corresponds to finding the intersection of three planes: they can meet at a single point (unique solution), along a common intersection line (infinitely many solutions), or fail to have any mutual meeting point (no solution). In 4 or higher dimensions, graphical visualization is impossible, making algorithmic matrix methods mandatory.

5 The Substitution Method

The Substitution Method is an algebraic technique where one variable is isolated from one equation and substituted into the remaining equation(s), systematically reducing the number of unknowns.

Step-by-Step Worked Solution:

System:
(1) $x + y = 7$
(2) $2x - y = 5$

Step 1 (Isolate a Variable): From Equation (1), express $y$ in terms of $x$:
$$y = 7 - x$$

Step 2 (Substitute into Equation 2): Replace $y$ with $(7 - x)$ in Equation (2):
$$2x - (7 - x) = 5$$ Caution: Distribute the negative sign to all terms within parentheses:
$$2x - 7 + x = 5 \implies 3x - 7 = 5 \implies 3x = 12 \implies \mathbf{x = 4}$$

Step 3 (Solve for the Remaining Unknown): Plug $x = 4$ back into the isolated expression:
$$y = 7 - 4 \implies \mathbf{y = 3}$$

Step 4 (Verification):
Eq (1): $4 + 3 = 7$ (True)
Eq (2): $2(4) - 3 = 8 - 3 = 5$ (True)
Solution: x = 4, y = 3

6 The Elimination Method (Linear Combinations)

In the Elimination Method, equations are scaled by scalar constants so that coefficients for a chosen unknown match or become opposites, allowing direct addition or subtraction to eliminate that variable.

Worked Example: Elimination via Scaling

(1) $2x + 3y = 13$
(2) $x + y = 5$

Step 1 (Scale to Match Coefficients): Multiply Equation (2) by 2 so that the $x$-coefficient equals that of Equation (1):
$$2 imes (x + y = 5) \implies 2x + 2y = 10 \quad ext{--- (3)}$$

Step 2 (Subtract to Eliminate $x$): Subtract Equation (3) from Equation (1):
$$(2x + 3y) - (2x + 2y) = 13 - 10 \implies y = 3$$

Step 3 (Solve for $x$): Substitute $y = 3$ back into Equation (2):
$$x + 3 = 5 \implies x = 2$$

Solution: $x = 2, y = 3$

7 Gaussian Elimination & Augmented Matrices

Real-world computing problems frequently feature thousands of variables. Manual substitution or elimination is prone to bookkeeping errors. Pioneered by Carl Friedrich Gauss, Gaussian Elimination is a systematic algorithmic pipeline designed for programmable matrix computation.

The Augmented Matrix

We encode a linear system by assembling its coefficients into matrix $A$ and its constants into vector $\mathbf{b}$, forming the combined Augmented Matrix $[A \mid \mathbf{b}]$:

$$\begin{cases} x + y + z = 6 \ 2x - y + z = 3 \ x + 2y - z = 2 \end{cases} \iff \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \ 2 & -1 & 1 & 3 \ 1 & 2 & -1 & 2 \end{array} ight]$$

The vertical line separates the coefficient matrix $A$ from the constant column $\mathbf{b}$.

The 3 Elementary Row Operations (EROs)

1. Row Swapping ($R_i \leftrightarrow R_j$): Interchange the physical position of two rows.

2. Row Scaling ($R_i \leftarrow k R_i, k e 0$): Multiply all elements of a row by a non-zero scalar.

3. Row Replacement ($R_i \leftarrow R_i + k R_j$): Add or subtract a scalar multiple of another row to a row.

Complete 3-Variable Gaussian Elimination Worked Example

Step 1: Eliminate $x$ from Rows 2 and 3 using Pivot in Row 1

The leading pivot entry in Row 1 is 1. We eliminate entries beneath it:

$R_2 \leftarrow R_2 - 2R_1 \implies [2 - 2(1), \; -1 - 2(1), \; 1 - 2(1) \mid 3 - 2(6)] = [0, \; -3, \; -1 \mid -9]$
$R_3 \leftarrow R_3 - R_1 \implies [1 - 1, \; 2 - 1, \; -1 - 1 \mid 2 - 6] = [0, \; 1, \; -2 \mid -4]$

$$\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \ 0 & -3 & -1 & -9 \ 0 & 1 & -2 & -4 \end{array} ight]$$

Step 2: Pivot Swapping and Eliminating $y$ from Row 3

Swap $R_2$ and $R_3$ to acquire a convenient pivot of 1 ($R_2 \leftrightarrow R_3$):

$$\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \ 0 & 1 & -2 & -4 \ 0 & -3 & -1 & -9 \end{array} ight]$$

Eliminate $-3$ from Row 3 using $R_2$ ($R_3 \leftarrow R_3 + 3R_2$):

$R_3 \leftarrow R_3 + 3R_2 \implies [0 + 3(0), \; -3 + 3(1), \; -1 + 3(-2) \mid -9 + 3(-4)] = [0, \; 0, \; -7 \mid -21]$

$$\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \ 0 & 1 & -2 & -4 \ 0 & 0 & -7 & -21 \end{array} ight] \quad ext{(Row Echelon Form)}$$

Step 3: Systematic Back-Substitution

With the matrix in upper-triangular Row Echelon Form, solve from bottom to top:

• From Row 3: $-7z = -21 \implies \mathbf{z = 3}$

• From Row 2: $y - 2z = -4 \implies y - 2(3) = -4 \implies y - 6 = -4 \implies \mathbf{y = 2}$

• From Row 1: $x + y + z = 6 \implies x + 2 + 3 = 6 \implies x + 5 = 6 \implies \mathbf{x = 1}$

Final Solution: $\mathbf{(x, y, z) = (1, 2, 3)}$

8 The Matrix Equation Form: $A\mathbf{x} = \mathbf{b}$

Using the matrix-vector multiplication rules mastered in the previous lesson, every linear system collapses into a compact, unified equation:

$$A\mathbf{x} = \mathbf{b}$$

Coefficient Matrix $A \in \mathbb{R}^{m imes n}$

Unknown Variable Vector $\mathbf{x} \in \mathbb{R}^{n imes 1}$

Target / Constant Vector $\mathbf{b} \in \mathbb{R}^{m imes 1}$

Gilbert Strang's Dual Perspective: Row Picture vs. Column Picture

Row Picture (Hyperplane Intersections): Each row defines a geometric plane in multidimensional space. Solving the system finds the mutual intersection point of all planes.

Column Picture (Vector Linear Combinations): We seek scalar coefficients $x_1, \dots, x_n$ such that the linear combination of matrix columns equals vector $\mathbf{b}$: $$x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + \dots + x_n \mathbf{a}_n = \mathbf{b}$$

9 Detecting Consistent vs. Inconsistent Systems

During Gaussian elimination, the terminal rows of the augmented matrix immediately signal the existence and nature of solutions:

Inconsistent System (No Solution)

If a row exhibits zeros across all coefficients but ends with a non-zero constant:

$[0 \quad 0 \quad 0 \mid 5] \implies 0x + 0y + 0z = 5 \implies \mathbf{0 = 5}$ (Mathematical Impossibility / Contradiction!)

Consistent System with Free Variables (Infinitely Many Solutions)

If an entire row consists exclusively of zeros:

$[0 \quad 0 \quad 0 \mid 0] \implies 0x + 0y + 0z = 0 \implies \mathbf{0 = 0}$ (Always True / Redundant Equation)

Fewer independent pivots exist than variables. Non-pivot columns represent free parameters ($t, s \in \mathbb{R}$) yielding an infinite solution continuum.

10 Solving Linear Systems in Python (NumPy)

In computational workflows, NumPy offers high-performance LAPACK routines via `linalg.solve` to compute solutions with optimal cache and vectorization:

import numpy as np

# Linear System:
# x + y + z = 6
# 2x - y + z = 3
# x + 2y - z = 2

A = np.array([
    [1,  1,  1],
    [2, -1,  1],
    [1,  2, -1]
], dtype=float)

b = np.array([6, 3, 2], dtype=float)

# Solve Ax = b directly via LU factorization
x = np.linalg.solve(A, b)

print("Solution vector x:", x)
# Output: [1. 2. 3.] -> x=1, y=2, z=3

# Verify: A @ x must equal b within numerical tolerances
is_correct = np.allclose(A @ x, b)
print("Verification:", is_correct)  # True

Production Engineering Rule: Never compute `np.linalg.inv(A) @ b` to solve $A\mathbf{x} = \mathbf{b}$! Matrix inversion requires double the operations ($O(n^3)$), scales poorly, and magnifies floating-point roundoff errors. `np.linalg.solve()` applies stable LU factorization ($O(n^3/3)$) with partial pivoting.

11 Real-World Applications in Computer Science & AI

Virtually every physical, statistical, or geometric simulation reduces to solving systems of linear equations:

1. Circuit Simulation (SPICE)

Applying Kirchhoff's Current and Voltage Laws at every node and loop in modern microchips generates sparse linear systems with millions of unknowns solved every millisecond.

2. Machine Learning: Normal Equations

Fitting an optimal linear model via Ordinary Least Squares analytically solves the Normal Equations $(X^T X)\mathbf{w} = X^T \mathbf{y}$ for model weights $\mathbf{w}$.

3. Computer Graphics & Ray Tracing

Detecting whether a camera light ray intersects a triangular polygon in 3D game engines uses the Möller–Trumbore algorithm, which solves a $3 imes 3$ linear system for ray distance and barycentric coordinates.

4. Google's Original PageRank

Modeling web user navigation as a Markov chain leads to a massive linear system $(I - \alpha P^T)\mathbf{r} = \frac{1 - \alpha}{N}\mathbf{1}$, determining global webpage ranking.

12 8 Common Pitfalls & Traps

Pitfall 1: Distributing Negative Signs Incorrectly

Failing to change signs across all terms when subtracting parentheses: $-(ax + b) = -ax - b$, not $-ax + b$.

Pitfall 2: Forgetting the Constant Column in Augmented Matrices

Scaling row coefficients by a scalar while neglecting to scale the constant vector entry $b_i$.

Pitfall 3: Dividing by a Zero Pivot

Attempting elimination when the pivot entry is zero. Always perform partial pivoting (row swapping) first.

Pitfall 4: Misinterpreting $0 = 0$ as "No Solution"

$0 = 0$ is an identity signifying a redundant constraint. The system has infinitely many solutions, not zero solutions.

Pitfall 5: Conflating $0 = c$ with Infinite Solutions

A row $[0 \dots 0 \mid c]$ with $c e 0$ is a flat contradiction ($0 = c$). It strictly denotes No Solution (Inconsistent).

Pitfall 6: Verifying on Only One Equation

Candidate solutions that satisfy Equation 1 might violate Equation 2. Always substitute into all system equations.

Pitfall 7: Overlooking Ill-Conditioned Systems

When lines are nearly parallel, tiny rounding noise produces wildly erratic solutions. Check condition numbers `np.linalg.cond(A)`.

Pitfall 8: Relying on `inv(A) @ b` in Software

Computing explicit matrix inverses is numerically unstable and computationally wasteful compared to direct Gaussian/LU solvers.

Interactive Hands-on Lab

Systems of Linear Equations Workbench

Explore geometric intersections, step through 3x3 Gaussian elimination, and simulate real electrical circuits in real time.

Line 1 (Indigo): $a_1 x + b_1 y = c_1$

Line 2 (Emerald): $a_2 x + b_2 y = c_2$

Determinant $\det(A)$: -3.0

System Status: Unique Solution

Intersection Coords: (x = 3.00, y = 1.00)

Line 1 Line 2 Intersection

Key Takeaways

1. Simultaneous Constraints

A system of linear equations seeks variable assignments that satisfy every constraint at the same time.

2. Three Outcomes

Every linear system has either a Unique Solution, Infinitely Many Solutions, or No Solution.

3. Geometric Interpretation

Intersection points of lines in 2D or planes in 3D; higher dimensions generalize to hyperplanes.

4. Substitution Method

Isolate one unknown and substitute into other equations—fast for manual small problems.

5. Elimination Method

Scale and add/subtract equations to cancel variables—the foundational concept behind row operations.

6. Gaussian Elimination

Transform augmented matrices to upper-triangular Row Echelon Form and solve via back-substitution.

7. Matrix Formulation

$A\mathbf{x} = \mathbf{b}$ expresses systems as a linear combination of matrix columns or intersection of row planes.

8. Consistency Diagnosis

A row $[0 \dots 0 \mid c]$ with $c e 0$ proves Inconsistency (No Solution); $[0 \dots 0 \mid 0]$ reveals free variables.

9. Production Coding Rule

Never use `inv(A) @ b` in software; always use `np.linalg.solve(A, b)` or LU factorization for stability.