Mathematical Foundations for Machine Learning

Solving Systems of Linear Equations

📅 Published: 2026-07-07

🎓 Level: postgraduate

👥 Audience: Postgraduate students in Mathematical Foundations for Machine Learning

Hook. What do GPT-4, a GPS navigation system, and a factory deciding how many phones to manufacture all have in common? They all run on the same mathematical engine: solving linear equations. This lecture builds that engine from scratch. We start with two simple equations and scale up to the trillion-parameter systems that power large language models.

Every neural network, every linear regression, every constrained optimization problem rests on one core skill. That skill is finding values that satisfy multiple linear equations at once. You will learn to write these systems compactly using matrices. You will transform them step by step into a form where the solution stares you in the face. You will also learn to recognize when a system has exactly one answer, no answer, or infinitely many.

By the end of this lecture, the augmented matrix and row operations will be second nature. More importantly, you will see why the linear equation $w^{T} x + b = 0$ is the DNA of modern machine learning.

2.1 What Is a Linear Equation

Hook. You have used linear equations since middle school without realizing their full power.

2 X + Y = 5

looks simple. But the same structure — variables multiplied by constants and added up — runs every neural network on the planet. Before we build trillion-parameter systems, we need to know what "linear" actually means.

2.1.1 Definition and Core Idea

Intuition. Think of a balance scale — the old-fashioned kind with two pans. You put some weights on the left pan and some on the right. The scale stays level when the total weight on both sides is equal. A linear equation is exactly that rule: the left side (a sum of scaled variables) must equal the right side (a constant). Double every weight on the left, and you must double the right side to keep balance. That flat, proportional relationship — never curving, never bending — is what "linear" means.

The analogy breaks in one way: a real balance scale can tip when overloaded. A linear equation never tips — it is an exact mathematical statement. Either the numbers satisfy it or they do not. No wiggle room.

A linear equation is an equation where every variable has degree one. No variable is raised to a power higher than 1. For example, $2 X + Y = 5$ is linear because $X$ appears as $X^{1}$ and $Y$ appears as $Y^{1}$ . There are no squared terms, no products of variables, no trigonometric functions, no logarithms. Just variables multiplied by constants and added together.

The name comes from the graph. Rewrite $2 X + Y = 5$ as $Y = 5 - 2 X$ . Plot it — in a tool like Desmos, or by hand — and you get a straight line. The equation depicts a line.

But "linear" does not mean "a line in all dimensions." In three variables, a linear equation like $X + 2 Y - Z = 4$ represents a plane — a flat sheet cutting through space. In $n$ variables, it represents a hyperplane — still a flat surface, never curved. The defining property never changes. Variables never multiply each other. They never appear with exponents other than 1.

Boundary. Linear only means degree-1 in the variables. If you see

sin (X)

X^{2}

e^{Y}

, or

X \cdot Y

, the equation is nonlinear. Do not confuse "the graph is a line" with "the equation is linear". A circle

(X^{2} + Y^{2} = 1)

is not linear even though it is a smooth curve. The test is always: are the variables only added, never multiplied together, never inside any function?

2.1.2 Formal Form

A general linear equation in $n$ variables is written as:

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b

Symbol	Type	Meaning
$x_{i}$	scalar	Variable (unknown), degree 1
$a_{i}$	scalar	Coefficient (constant multiplier attached to $x_{i}$ )
$b$	scalar	Constant term (right-hand side)
$n$	integer	Number of variables in the equation

Every coefficient $a_{i}$ tells you how much weight variable $x_{i}$ carries. If $a_{3} = 0$ , then $x_{3}$ effectively does not appear in this equation — it carries zero weight. The right-hand side $b$ is the target value the weighted sum must hit.

Worked Example: Is it linear?

Classify each equation as linear or nonlinear:

Equation	Verdict	Reason
$3 X_{1} - 2 X_{2} + X_{3} = 7$	Linear	Variables only multiplied by constants, added.
$X^{2} + Y = 5$	Nonlinear	$X$ appears with exponent 2.
$X_{1} X_{2} + X_{3} = 10$	Nonlinear	$X_{1}$ and $X_{2}$ are multiplied together.
$sin (X) + Y = 0$	Nonlinear	$sin (X)$ is a nonlinear function of $X$ .
$0.5 X_{1} + 0 X_{2} = 3$	Linear	$0 X_{2}$ is fine — coefficient zero means the variable is absent.
$2 \cdot X - π Y = e$	Linear	Constants can be irrational; only the variables must be degree-1.

Sense-check: The last equation looks exotic with $2$ , $π$ , and $e$ , but it is just a flat proportional relationship between $X$ and $Y$ . The coefficients being irrational does not break linearity.

Scope: Assumptions of linearity. For an equation to be linear, three conditions must hold:

Degree-1 variables: Every variable appears only as $x_{i}^{1}$ . No $x_{i}^{2}$ , $x_{i}$ , or $1/ x_{i}$ .
No products of variables: Terms like $x_{1} x_{2}$ or $x_{i} x_{j}$ are forbidden.
Coefficients are constants: Each $a_{i}$ is a fixed number, not a function of any variable.

If any condition fails, the equation is nonlinear. Nonlinear equations are harder to solve, often have multiple isolated solutions, and require entirely different methods (Newton's method, not Gaussian elimination).

Visual Intuition. Open Desmos and type 2x + y = 5. You will see a straight line crossing the y-axis at $(0, 5)$ and the x-axis at $(2.5, 0)$ . The line slopes downward. The coefficient of $X$ is positive and the coefficient of $Y$ is positive, so rearranging to $Y = 5 - 2 X$ gives a negative slope of $- 2$ . Every point on that line is a solution to the equation. Points above the line give $2 X + Y > 5$ ; points below give $2 X + Y < 5$ . The line is the boundary where equality holds.

In 3D, the equation $2 X + Y + Z = 5$ becomes a plane. If you slice it with the XY-plane (setting $Z = 0$ ), you get back the 2D line $2 X + Y = 5$ . The plane tilts in 3D space, but it never bends.

Common Pitfalls.

"Linear" means more than "a line." A sine wave is a curved line, but $sin (X)$ is nonlinear. The shape of the graph is not the test — the algebraic form is.
Zero coefficients are OK. $0 X_{1} + 3 X_{2} = 7$ is still linear. The term $0 X_{1}$ is just absent — it does not make the equation quadratic or degenerate.
Constants can be anything. $5 X + ln (2) Y = π$ is linear. The coefficients are constants — their specific numeric form does not matter. Only the variables must be degree-1.
Rearranging does not break linearity. $Y = 5 - 2 X$ and $2 X + Y = 5$ are the same linear equation. Moving terms across the equals sign preserves linearity.

Recap. A linear equation is a weighted sum of degree-1 variables set equal to a constant. It graphs as a line (2D), plane (3D), or hyperplane (nD) — always flat, never curved. This flatness is what makes linear systems systematically solvable.

Bridge. One linear equation gives you a line. But one line has infinitely many points. To pin down a single point, you need a second equation that crosses the first — a system of linear equations. That is where we go next.

Real-World & Domain Connection. Linear equations are the workhorse of linear programming, the field that optimizes everything from airline crew schedules to portfolio allocations. When FedEx routes 50,000 packages through Memphis overnight, the constraint "total package weight ≤ plane capacity" is a linear inequality. It is built from linear equations. When an engineer checks whether a bridge can hold a given load, the force-balance equations are linear. The simplicity of linear equations — add, multiply by constants, never bend — is exactly what makes them computable at enormous scale. Every optimization solver (Gurobi, CPLEX, open-source alternatives) is, at its core, a machine for solving millions of linear equations.

2.2 Systems of Linear Equations and the Common Solution

Hook. One equation gives you a line. But a line has infinitely many points — which one is the answer? You need a second line that crosses the first. The intersection is the single point that satisfies both. This is the central idea behind every system of linear equations. Bring in enough constraints to narrow down the possibilities until only one answer remains.

2.2.1 Definition

Intuition. Imagine you and a friend are trying to meet at a café. You each know your own path — two straight-line routes through the city. If your paths cross exactly once, that intersection is your meeting point. A system of linear equations works the same way. Each equation is a path (a line, plane, or hyperplane), and the solution is where all paths intersect.

The analogy breaks when paths are parallel (no meeting point) or coincident (infinite meeting points). Those are real outcomes — we will handle them in Section 2.9.

A system of linear equations is a collection of two or more linear equations that share the same variables. The goal is to find values for those variables that satisfy every equation simultaneously — a common solution.

A system of $m$ linear equations in $n$ unknowns:

a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{mn} x_{n} = b_{1} = b_{2} ⋮ = b_{m}

$a_{ij}$ is the coefficient of variable $x_{j}$ in equation $i$ (row $i$ , column $j$ ).
$b_{i}$ is the constant on the right-hand side of equation $i$ .
A solution is an $n$ -tuple $(x_{1}, x_{2}, \dots, x_{n})$ that makes every equation true.

2.2.2 The General Problem

Whether you have two equations or millions, the core question is the same. Does a common point exist that satisfies all of them? If it does, that point is the solution. The methods for finding it — elimination, substitution, matrix row operations — all work toward the same goal.

The only thing we are looking for is a common point — a common solution for all equations. This holds for two equations or a trillion.

Worked Example: Graphical intersection (2D).

Consider:

2 X + Y X + Y = 5 = 10 (Line 1) (Line 2)

Rewrite both in slope-intercept form:

Y = 5 - 2 X (Line 1: slope - 2, intercept 5)

Y = 10 - X (Line 2: slope - 1, intercept 10)

To find the intersection, set them equal:

5 - 2 X = 10 - X \Rightarrow - 2 X + X = 10 - 5 \Rightarrow - X = 5 \Rightarrow X = - 5

Plug $X = - 5$ into Line 1:

Y = 5 - 2 (- 5) = 5 + 10 = 15

Solution: $(X, Y) = (- 5, 15)$ .

Sense-check: Plug into Line 2: $- 5 + 15 = 10$ ✓. Both equations are satisfied. The two lines cross at exactly one point — a unique solution.

Visual Intuition. Plot both lines in Desmos. Line 1 ( $Y = 5 - 2 X$ ) slopes downward steeply, crossing the y-axis at $(0, 5)$ . Line 2 ( $Y = 10 - X$ ) slopes downward gently, crossing at $(0, 10)$ . They intersect in the second quadrant at $(- 5, 15)$ — left of the origin, high up. That point is the only one that belongs to both lines.

Scope. A system of linear equations can have:

Exactly one solution (lines intersect at a single point)
No solution (lines are parallel, never meet)
Infinitely many solutions (lines are coincident — the same line)

We explore all three outcomes in detail in Section 2.9. For now, the focus is on the unique-solution case: $m$ equations, $n$ unknowns, $m = n$ , one answer.

Common Pitfalls.

Thinking fewer equations means an easier problem. Fewer equations than unknowns usually means you cannot pin down a unique answer. You need at least as many independent equations as variables.
Assuming every system has a solution. Not all systems do. The equations might contradict each other. We will see how to detect this in Section 2.9.
Forgetting to check the answer. Always plug your solution back into every original equation. A single equation satisfied is not enough — all must hold.

Q: If there are N variables, do we need exactly N equations to solve the system?

A: Yes — if you have fewer equations than unknowns, you generally cannot find a unique solution. The number of equations must match the number of variables for the system to be solvable uniquely. If you have more unknowns than equations, the system becomes underdetermined. You may have infinitely many solutions or none at all, depending on consistency.

Several students asked this — it is a foundational point. The intuition: each equation is one constraint. With $N$ variables, you need $N$ independent constraints to fix all $N$ values.

Recap. A system of linear equations is a set of equations sharing the same variables. The common solution is the point — in 2D, the intersection — that satisfies every equation at once.

Bridge. We now know what systems look like and what we are solving for. So why does any of this matter for machine learning? The answer is the single equation $w^{T} x + b = 0$ . It is repeated trillions of times inside every neural network.

Real-World & Domain Connection. Systems of linear equations appear wherever multiple constraints must be satisfied simultaneously. In circuit analysis (Kirchhoff's laws), the currents through each branch of a circuit form a linear system. In chemical stoichiometry, balancing a reaction like $a CH_{4} + b O_{2} \to c CO_{2} + d H_{2} O$ means solving for the integer coefficients $a, b, c, d$ — a system of linear equations in disguise. In GPS navigation, your receiver solves a system of four equations (one per satellite). It pins down your 3D position plus clock bias. Every one of these applications asks the same question: what values satisfy all these linear relationships at once?

2.3 Linear Equations as the Foundation of Machine Learning

Hook. Every time ChatGPT generates a word, it evaluates trillions of linear equations — each one no more complex than

2 X + 5 = 8

. The "intelligence" of a large language model is built from billions of these tiny linear operations stacked together. If you understand the linear equation

w^{T} x + b = 0

, you understand the atomic unit of modern AI.

2.3.1 The Governing Equation of Neural Networks

Intuition. Imagine a massive soundboard in a recording studio, but with 1.7 trillion slider knobs. Each slider controls one number — a weight. When audio (input data) flows through the board, every slider adjusts how much of each input signal passes through. The output is a mix of all inputs, each scaled by its slider position. Training the model means sliding all 1.7 trillion knobs until the output sounds right. Each slider position is one parameter. Each slider participates in one linear equation: input × weight + bias = output.

The analogy breaks because real soundboards mix signals in parallel; neural networks stack many mixing boards in sequence. But the core idea holds: each layer is a linear transformation — a weighted sum — followed by a simple nonlinearity.

Neural networks, including LLMs, are built on one governing equation:

w^{T} x + b = 0

Symbol	Type	Shape	Meaning
$w$	vector	$n \times 1$	Weight parameters — what the model learns
$x$	vector	$n \times 1$	Input features — the data fed to this layer
$b$	scalar/vector	$1 \times 1$ or $m \times 1$	Bias term — the intercept, shifts the output
$w^{T} x$	scalar	$1 \times 1$	Dot product: $w_{1} x_{1} + w_{2} x_{2} + \dots + w_{n} x_{n}$

Expanded, the dot product is exactly the form of a linear equation from Section 2.1:

w^{T} x = w_{1} x_{1} + w_{2} x_{2} + \dots + w_{n} x_{n}

Add the bias and set to zero. You now have the decision boundary. It is the hyperplane that separates one class from another in a classifier. It is also the activation threshold that decides whether a neuron fires.

Structurally, this is identical to $2 X + 5 = 8$ — just with vectors instead of scalars. The math scales, but the form does not change.

2.3.2 The Scale: GPT-4 and 1.7 Trillion Parameters

To make this concrete: GPT-4 has approximately 1.7 trillion parameters. Each parameter is a single weight — a single entry in some weight vector $w$ inside the model. Each weight participates in exactly one linear equation of the form $w^{T} x + b = 0$ (per input).

When you train the model, you are solving — iteratively, not directly — for the values of all 1.7 trillion weights. The training data provides millions of $(x, y)$ pairs (input, desired output). The optimization algorithm nudges each weight to reduce the mismatch between predicted and desired output. After billions of such nudges, the weights converge to values that make the model work.

2.3.3 Why Solving Matters

A tiny neural network layer, by hand.

Consider a single neuron with two inputs:

z = w_{1} x_{1} + w_{2} x_{2} + b

Suppose we have one training example. Let $x_{1} = 2$ , $x_{2} = 3$ , and we want the output $z$ to be 10. The unknowns are $w_{1}, w_{2},$ and $b$ .

We have one equation: $2 w_{1} + 3 w_{2} + b = 10$ . Three unknowns, one equation — infinitely many solutions. This is why neural networks need many training examples: each example adds one equation. With enough examples (and some regularization), the system becomes determined and the weights are pinned down.

Now scale this up: GPT-4 has 1.7 trillion unknowns and is trained on trillions of tokens. It is the same idea — just at enormous scale.

Scope: What this equation is and is not.

It IS a linear equation. $w^{T} x + b = 0$ has no variable raised above degree 1, no products of variables, no nonlinear functions applied to the variables themselves.
It is NOT the whole neural network. A neural network stacks many such linear transformations, each followed by a nonlinear activation function like ReLU ( $max (0, z)$ ) or sigmoid. Without the nonlinearities, stacking linear layers would collapse into a single linear layer — nothing would be gained. The nonlinearities are what give neural networks their expressive power. But the atomic operation inside every layer is still linear.
Training is NOT Gaussian elimination. You cannot solve 1.7 trillion equations with row operations — the computational cost would be astronomical ( $O (n^{3})$ ). Instead, neural networks use gradient descent: an iterative algorithm that takes small steps downhill on an error surface. The matrix intuition from REF/RREF still transfers — you are manipulating matrices to understand data transformations.

Visual Intuition. Picture a single neuron as a dividing line in 2D. The equation $w_{1} x_{1} + w_{2} x_{2} + b = 0$ is a line. Points on one side of the line give $w^{T} x + b > 0$ (neuron fires); points on the other side give $w^{T} x + b < 0$ (neuron stays silent). Training adjusts the slope ( $w_{1}, w_{2}$ ) and position ( $b$ ) of this line until it best separates the data. In 3D, the neuron becomes a dividing plane. In higher dimensions, a dividing hyperplane. Same equation, same geometry — just more dimensions.

Common Pitfalls.

"1.7 trillion parameters" sounds like 1.7 trillion separate equations to solve simultaneously. It is not — each weight participates in one linear combination per input. The weights themselves are the unknowns, not the equations. The equations come from the training data.
Thinking neural networks solve linear systems with Gaussian elimination. They do not. They use iterative optimization (gradient descent). The REF/RREF material in this lecture builds matrix intuition; it is not the algorithm used to train models.
Confusing a single linear layer with the whole network. One layer is linear. A deep network is a composition of linear and nonlinear functions. The linear part is what we study here; the nonlinear part comes later in the course.

Q: Are the 1.7 trillion parameters in GPT-4 the same thing as the linear equations?

A: Yes, exactly. Each parameter is a weight in a linear equation. The weight vector is enormous — on the order of "trillion × 1" — but conceptually it is still a vector. Each entry is one weight in one linear equation of the form $w^{T} x + b = 0$ .

Q: What is the actual size of these weight matrices?

A: They are very large — on the order of trillion-by-one for individual weight vectors. In practice, weights are organized into matrices (e.g., $W \in R^{d_{out} \times d_{in}}$ ), not a single flat vector. But each row of that matrix is a weight vector participating in its own linear equation. The total parameter count — 1.7 trillion — is the sum of all entries. It spans all weight matrices and bias vectors in the model.

Several students asked variations of these questions — the scale is hard to internalize. The key insight: no matter how big the vector gets, the math is the same. It matches the 2-variable equations you solved in high school.

Recap. The equation

w^{T} x + b = 0

is the atomic unit of every neural network. It is a linear equation — identical in form to the ones you solve with Gaussian elimination. GPT-4 has 1.7 trillion such parameters, each one a weight in this equation.

Bridge. Understanding how linear systems are systematically solved is the gateway to machine learning. First we solve by hand with elimination. Then we solve with matrices. Let us start with the simplest method: elimination.

Real-World & Domain Connection. Every large language model — GPT-4 (OpenAI), Claude (Anthropic), Llama (Meta), Gemini (Google) — uses this same governing equation at its core. The "intelligence" emerges from stacking many such linear transformations with nonlinear activation functions between them. Strip away the activations, and what remains is a cascade of linear equations.

The same structure powers three other fields. Convolutional neural networks use it for image recognition: each filter is a linear combination of pixel values. Recommendation systems use it as user embeddings × item embeddings + bias = predicted rating. Time-series forecasting uses it as linear regression on lagged values. Linear algebra is the common language they all speak.

2.4 Elimination and Substitution Methods

Hook. Before matrices, before row operations, before Gaussian elimination — there was the method you learned in school. Multiply one equation, subtract from another, solve for one variable, plug it back in. It works perfectly for two equations. But try it on a thousand equations and you will drown in algebra. Understanding why it fails at scale is the motivation for everything that follows.

2.4.1 The High-School Methods

Intuition. You are balancing two seesaws at once. One seesaw says

X + Y = 3

; the other says

2 X + 3 Y = 7

. You want the pair of weights

(X, Y)

that keeps both seesaws level. The elimination trick: make the

X

-terms on both seesaws match, then subtract one entire seesaw from the other. The

X

cancels out, leaving only

Y

. Solve that, then plug

Y

back into either seesaw to get

X

The analogy breaks because real seesaws pivot around a center point; linear equations do not pivot — they are rigid constraints. But the idea of "canceling out" one variable by matching coefficients is the core insight.

Given two equations:

X + Y 2 X + 3 Y = 3 = 7

The goal is to find $X$ and $Y$ . The standard method is elimination: eliminate one variable, solve for the other, then substitute back.

2.4.2 Worked Example: Elimination

Step 1 — Eliminate $X$ : Multiply the first equation by 2 so the $X$ -coefficient matches the second equation's $X$ -coefficient.

2 \times (X + Y = 3) \Rightarrow 2 X + 2 Y = 6

Subtract the second equation from this new equation:

(2 X + 2 Y) - (2 X + 3 Y) = 6 - 7

2 X + 2 Y - 2 X - 3 Y = - 1 \Rightarrow - Y = - 1 \Rightarrow Y = 1

Step 2 — Back-substitute: Plug $Y = 1$ into the simpler equation ( $X + Y = 3$ ):

X + 1 = 3 \Rightarrow X = 2

Solution: $(X, Y) = (2, 1)$ .

Sense-check: Plug into the second equation: $2 (2) + 3 (1) = 4 + 3 = 7$ ✓. Both equations are satisfied. Graphically, the lines $X + Y = 3$ and $2 X + 3 Y = 7$ intersect exactly at $(2, 1)$ .

Someone said multiply the first equation by two and subtract the second from it to eliminate X. That is why it is called elimination — we eliminate one variable.

2.4.3 Why These Methods Do Not Scale

Elimination and substitution work beautifully for two equations with two variables. But what if you have 1000 equations in 1000 unknowns? Writing out "multiply equation 47 by 3.2, subtract from equation 89" becomes unmanageable. You need a more compact notation — and that is where matrices come in.

The importance of matrices here is you have to realize these are only two equations. What would happen when you have more equations and hundreds of variables? It becomes a lot difficult to actually do the back substitution or elimination method. So what we do is we use a slightly easier notation, which is called the matrix notation.

Scope: When elimination works and when it fails.

Elimination works when:

The system is consistent (a solution exists).
Coefficients are not all zero in the column you are eliminating.
You are working over a field (real numbers, complex numbers — division always works for nonzero scalars).

Elimination breaks when:

A pivot (the coefficient you are using to eliminate) is zero. You then need to swap rows, which is fine if a nonzero pivot exists in a lower row.
The system is singular — no row swap can produce a nonzero pivot. This means the equations are either redundant or contradictory. We will diagnose these cases in Section 2.9.

Visual Intuition. Picture the two lines from the example. Line 1: $Y = 3 - X$ (slope $- 1$ , crosses axes at $(3, 0)$ and $(0, 3)$ ). Line 2: $Y = \frac{7 - 2 X}{3}$ (slope $- \frac{2}{3}$ , crosses at $(3.5, 0)$ and $(0, 2.33)$ ). They intersect at $(2, 1)$ . The elimination step — multiplying and subtracting — is the algebraic equivalent of finding where the lines cross. You do not need to draw them; the algebra finds the intersection for you.

Common Pitfalls.

Forgetting to apply the multiplier to the right-hand side. When you multiply an equation by 2, you must multiply the constant on the right as well. $X + Y = 3$ becomes $2 X + 2 Y = 6$ , not $2 X + 2 Y = 3$ .
Subtracting in the wrong order. $(2 X + 2 Y) - (2 X + 3 Y)$ gives $- Y$ . Reversing the subtraction gives $+ Y$ . Pick one order and stay consistent.
Stopping after finding one variable. Elimination gives you one variable. You must back-substitute to get the rest.

Q: What if one equation in the system is nonlinear (e.g., contains

X^{2}

A: If the nonlinear term (e.g., $K^{2}$ ) appears in multiple equations, you can substitute $M = K^{2}$ to linearize the system temporarily. Solve for $M$ using linear methods. Then back-substitute $K = \pm M$ . But this only works if the same nonlinear term replicates across equations. An isolated $X^{2}$ in one equation cannot be handled by linear elimination. You would need nonlinear solution methods (Newton's method, etc.).

Recap. Elimination is the simplest method for solving small linear systems: match coefficients, subtract to cancel one variable, solve, and back-substitute. It works perfectly for 2–3 equations but becomes unmanageable at scale.

Bridge. The bottleneck is notation — writing variable names over and over. The fix is to strip the variables away entirely and keep only the coefficients and constants. That is the augmented matrix.

Real-World & Domain Connection. Elimination is the algorithm behind every row-reduction operation in linear algebra software. When you call np.linalg.solve(A, b) in NumPy, the library is doing elimination under the hood. It uses many optimizations (partial pivoting, LU decomposition) for numerical stability. The same principle powers circuit simulators (SPICE) and structural analysis software (finite element method solvers). It also powers any system that needs to solve $A x = b$ for moderate-sized $A$ . The 1000-equation case that breaks hand calculation is routine for a computer. But the algorithm is the same one you just did by hand.

2.5 The Augmented Matrix Representation

Hook. The elimination method works — but rewriting

X_{1}, X_{2}, X_{3}

in every equation is tedious. What if you could throw away the variable names entirely and work only with the numbers? That is exactly what the augmented matrix does. It is the spreadsheet of linear algebra: rows are equations, columns are variables, and the column after the bar is the answer.

2.5.1 Definition and Construction

Intuition. Imagine a spreadsheet. Row 1 is equation 1, row 2 is equation 2, and so on. Columns A, B, C hold the coefficients of

X_{1}, X_{2}, X_{3}

. Column D holds the right-hand-side constants. The variable names become column headers — you write them once at the top and never again. Now every row operation (multiply, add, subtract) is just a spreadsheet formula applied to an entire row. No

X

's to carry around, no equals signs to align — just clean numbers in a grid.

The analogy is more than an analogy: MATLAB and NumPy literally store matrices as arrays in memory. When you call a solver, it reads rows and columns from a 2D array — exactly like a spreadsheet.

An augmented matrix is a compact way to write a system of linear equations. You strip away the variable names and the equality signs. You keep only the coefficients and the right-hand-side constants, separated by a vertical bar.

Given a system of 3 equations in 3 unknowns:

2 X_{1} + X_{2} + X_{3} X_{1} - X_{2} + X_{3} X_{1} + X_{2} - 2 X_{3} = 5 = 10 = 6

The augmented matrix is:

211 1 - 1 1 11 - 2 5106

Construction rule: Row $i$ gets the coefficients from equation $i$ . Column $j$ (before the bar) gets the coefficients of $X_{j}$ . The last column gets the right-hand-side constants. The vertical bar is a visual reminder of where the equals sign was.

At the top we write the variables which are $X_{1}, X_{2}, X_{3}$ . The first equation: the coefficient of $X_{1}$ is 2, $X_{2}$ is 1, $X_{3}$ is 1. On the right-hand side you have 5.

2.5.2 Why This Representation Helps

The key benefit: you are freed from rewriting the variable names. Each row is one equation. Each column (before the bar) corresponds to one variable. The rightmost column holds the constants. All the work of solving now happens by manipulating rows. You never touch the variable names again until you read off the final answer.

Worked Example: Building an augmented matrix.

System:

3 X_{1} + 0 X_{2} - X_{3} - X_{1} + 2 X_{2} + X_{3} 0 X_{1} + X_{2} + 5 X_{3} = 4 = 0 = - 2

Augmented matrix:

3 - 1 0 021 - 1 15 40 - 2

Notice: a zero coefficient ( $0 X_{2}$ in equation 1, $0 X_{1}$ in equation 3) becomes a 0 in the matrix. These zeros are important — they show that the variable is absent from that equation. The matrix must have an entry in every position; missing variables are zeros, not blanks.

2.5.3 The General Form

For $m$ equations in $n$ unknowns:

[A ∣ b] = a_{11} a_{21} ⋮ a_{m 1} a_{12} a_{22} ⋮ a_{m 2} \dots \dots ⋱ \dots a_{1 n} a_{2 n} ⋮ a_{mn} ∣ ∣ ∣ ∣ b_{1} b_{2} ⋮ b_{m}

$A$ is the $m \times n$ coefficient matrix (left of the bar).
$b$ is the $m \times 1$ constant vector (right of the bar).
Together, $[A ∣ b]$ is the augmented matrix.

Common Pitfalls.

Forgetting to align columns by variable. If equation 2 is written as $X_{3} - X_{2} + X_{1} = 10$ , you must reorder it to $X_{1} - X_{2} + X_{3} = 10$ before extracting coefficients. The columns must be consistent across all rows.
Leaving blanks instead of zeros. A missing variable is a zero coefficient, not an empty cell. Write 0 in the matrix — it matters for row operations.
Omitting the vertical bar. The bar is not mathematically necessary, but it is a crucial visual cue: left side = coefficients, right side = constants. Many students accidentally apply row operations to the constants column incorrectly because they lose track of the boundary.

Recap. The augmented matrix

[A ∣ b]

is a compact, variable-free representation of a linear system. Rows = equations, columns before bar = variables, column after bar = constants.

Bridge. We now have the system in a clean matrix form. The question is: what operations can we perform on these rows to solve it? The answer: exactly three — row swap, row scaling, and row replacement.

Real-World & Domain Connection. Every numerical linear algebra library — MATLAB, NumPy, LAPACK, Eigen — stores linear systems as matrices internally. When you call np.linalg.solve(A, b), NumPy builds the augmented matrix $[A ∣ b]$ . It then applies row operations, with optimizations like partial pivoting and LU decomposition. The augmented matrix is not just a pedagogical tool — it is the actual data structure used in production solvers. High-performance computing (HPC) codes for weather simulation, computational fluid dynamics, and structural analysis all pass around augmented matrices. They use augmented matrices as their fundamental unit of work.

2.6 Elementary Row Operations

Hook. You have a matrix full of numbers. How do you reshape it into a form where the solution jumps out? You need a set of legal moves — operations that change how the equations look but never change the answer. There are exactly three. Every method in this course, from Gaussian elimination to computing matrix inverses, is just a sequence of these three moves.

2.6.1 The Three Allowed Operations

Think of the augmented matrix as a deck of cards, with each card being one row (one equation). You have three legal moves.

Swap any two cards. Reordering equations does not change the solution.
Scale all numbers on one card by a nonzero constant. Scaling an equation does not change what values satisfy it.
Replace one card with itself minus a multiple of another. This is the elimination move. It combines equations to cancel terms.

Any sequence of these three moves preserves the solution set. Any other move (squaring a row, deleting a row, adding a constant) breaks it.

The analogy breaks because real cards have a fixed order. Here the "deck" is a mathematical object and row swaps are fully reversible. But the constraint is the same: only these three operations are fair game.

Once the system is in augmented matrix form, you can manipulate the rows using exactly three elementary row operations.

Operation	Notation	What It Does	Why It Preserves Solutions
Row swap	$R_{i} \leftrightarrow R_{j}$	Exchange two rows	Reordering equations does not change their meaning
Row scaling	$R_{i} \leftarrow c R_{i} (c \neq = 0)$	Multiply every entry in a row by $c$	Multiplying both sides of an equation by the same nonzero number preserves equality
Row replacement	$R_{i} \leftarrow R_{i} - c R_{j}$	Subtract $c$ times row $j$ from row $i$	This is the elimination move — subtracting equal quantities from both sides

Row 2 equals 2 times row 1 minus row 2. That is row replacement — the workhorse operation that zeros out entries to create the staircase pattern.

2.6.2 What These Operations Achieve

The goal is to transform the augmented matrix into a form where the solution becomes obvious. You systematically create zeros below (and eventually above) the pivot entries — the first nonzero entry in each row.

These are the basic operations. Every step of Gaussian elimination and Gauss-Jordan elimination is just a sequence of these three moves.

Trace: Applying row operations to a simple system.

Start with:

[1324511]

Operation 1 (Row replacement): $R_{2} \leftarrow R_{2} - 3 R_{1}$

New row 2: $[3, 4, 11] - 3 [1, 2, 5] = [3 - 3, 4 - 6, 11 - 15] = [0, - 2, - 4]$

[10 2 - 2 5 - 4]

Operation 2 (Row scaling): $R_{2} \leftarrow - \frac{1}{2} R_{2}$

[102152]

Operation 3 (Row replacement): $R_{1} \leftarrow R_{1} - 2 R_{2}$

New row 1: $[1, 2, 5] - 2 [0, 1, 2] = [1, 0, 1]$

[100112]

Solution: $X_{1} = 1$ , $X_{2} = 2$ . Sense-check: $1 + 2 (2) = 5$ ✓; $3 (1) + 4 (2) = 11$ ✓.

Scope: What these operations preserve and what they do not.

Preserved: The solution set. If $(x_{1}, \dots, x_{n})$ satisfied the original system, it satisfies the transformed system, and vice versa.
NOT preserved: The individual equations. After $R_{2} \leftarrow R_{2} - 3 R_{1}$ , row 2 is a new equation — a linear combination of the original equations. It is not the original equation 2. But it carries equivalent information.
NOT preserved: The determinant (if the matrix is square). Row swaps flip the sign; row scaling multiplies the determinant. These properties matter later but do not affect the solution.

Common Pitfalls.

Scaling by zero. $R_{i} \leftarrow 0 \cdot R_{i}$ replaces an entire equation with $0 = 0$ , destroying the information it carried. Scaling by zero is forbidden — $c$ must be nonzero.
Mixing up row replacement direction. $R_{i} \leftarrow R_{i} - c R_{j}$ means: modify row $i$ . Do NOT modify row $j$ . Only row $i$ changes. Row $j$ stays as it was.
Applying an operation to only part of a row. Every entry in the row — including the constant on the right of the bar — must be updated. Forgetting the constant column is the single most common error in Gaussian elimination.
Thinking "legal" means "the same equation." Row replacement produces a new equation that is a linear combination of old ones. It looks different but is equivalent in terms of what solutions it allows.

Recap. There are exactly three elementary row operations: swap, scale (by nonzero constant), and replace (subtract a multiple of one row from another). Every solution-preserving transformation of a linear system is a sequence of these three moves.

Bridge. Armed with these three operations, we can now systematically transform any augmented matrix into Row Echelon Form. That is the triangular shape where back-substitution solves the system. That algorithm is Gaussian elimination.

Real-World & Domain Connection. Row operations are the primitive instructions executed by every linear algebra processor. GPU-accelerated libraries like cuBLAS (NVIDIA) perform row operations on thousands of rows in parallel. The same three operations, just vectorized across hardware threads. When a self-driving car updates its Kalman filter, it runs row operations on a small matrix dozens of times per second. A Kalman filter is a linear system for sensor fusion. The algorithm is identical to what you do by hand. Only the scale and speed differ.

2.7 Row Echelon Form and Gaussian Elimination

Hook. You have an augmented matrix. You have three row operations. The question now is: can you apply them in a systematic sequence? One that always produces a triangular form where the solution is obvious? Yes. That sequence is Gaussian elimination, and the target shape is called Row Echelon Form.

2.7.1 Definition of Row Echelon Form (REF)

Intuition. Think of REF as cleaning a messy room into organized piles. Before cleaning, items (numbers) are scattered everywhere. After cleaning, you have one pile per category, and each pile sits neatly to the right of the previous one. The first pile (pivot 1) occupies the leftmost space. The next pile (pivot 2) starts farther right. Zeros fill the space below each pile — nothing spills downward. Any completely empty rows go to the bottom. This staircase of "piles" is what makes back-substitution possible: you untie the knot starting from the last row.

The analogy breaks because real cleaning does not guarantee the piles form a perfect staircase. But in REF, the staircase is rigid and defined by the pivot positions.

A matrix is in Row Echelon Form when it satisfies two conditions:

All zero rows are at the bottom. A row of only zeros must sit below any row that has a nonzero entry.
Each pivot is strictly to the right of the pivot above it, and all entries below every pivot are zero. The first nonzero entry in any row — the pivot — sits farther right than the pivot in the row above. Below each pivot, the column contains only zeros.

Visually, the pivots form a staircase stepping down and to the right:

* 000 * * 00 * * * 0 * * * 0 ∣ ∣ ∣ ∣ * * * *

$*$ = pivot (nonzero)
$*$ = any number (can be zero or nonzero)
Everything below each pivot = 0
Zero rows (if any) at the very bottom

This is a nice-looking staircase pattern. The first element in the column is called a pivot element. We want these bold boxes as nonzero, and everything below them as zero.

2.7.2 Gaussian Elimination — The Process

Purpose: Transform any augmented matrix $[A ∣ b]$ into Row Echelon Form, from which the solution can be found by back-substitution.

Inputs: An $m \times (n + 1)$ augmented matrix $[A ∣ b]$ .

Outputs: The same matrix transformed to REF, with the same solution set.

Steps:

Start at column 1, row 1. Set current row $r = 1$ , current column $c = 1$ .
Find a pivot. Look down column $c$ from row $r$ to row $m$ . The first nonzero entry is your pivot. If the pivot is not in row $r$ , swap it up to row $r$ ( $R_{r} \leftrightarrow R_{pivot row}$ ).
Eliminate below. For every row $i > r$ , perform $R_{i} \leftarrow R_{i} - \frac{a _{i c}}{a _{r c}} R_{r}$ . This zeros out the entry at position $(i, c)$ .
Advance. Move to the next row ( $r \leftarrow r + 1$ ) and next column ( $c \leftarrow c + 1$ ).
Repeat from step 2 until $r > m$ or $c > n$ .

After reaching REF, solve by back-substitution: the last equation has only one variable (or reveals inconsistency), so you solve it directly. Substitute that value into the second-to-last equation, which now has only one unknown, and work upward.

2.7.3 Worked Example: Gaussian Elimination

Given the system:

X_{1} + X_{2} + X_{3} 2 X_{1} + X_{2} + 2 X_{3} 4 X_{1} + X_{2} + X_{3} = 15 = 25 = 21

Step 1 — Write the augmented matrix:

124111121152521

Step 2 — Eliminate below the first pivot (column 1, row 1):

Pivot = $a_{11} = 1$ . Zero out rows 2 and 3.

R_{2} R_{3} \leftarrow R_{2} - 2 R_{1} : \leftarrow R_{3} - 4 R_{1} : [2, 1, 2, 25] - 2 [1, 1, 1, 15] [4, 1, 1, 21] - 4 [1, 1, 1, 15] = [0, - 1, 0, - 5] = [0, - 3, - 3, - 39]

100 1 - 1 - 3 10 - 3 15 - 5 - 39

Step 3 — Eliminate below the second pivot (column 2, row 2):

Pivot = $a_{22} = - 1$ . Zero out row 3.

R_{3} \leftarrow R_{3} - 3 R_{2} : [0, - 3, - 3, - 39] - 3 [0, - 1, 0, - 5] = [0, 0, - 3, - 24]

REF achieved:

100 1 - 1 0 10 - 3 15 - 5 - 24

Step 4 — Back-substitution:

Row 3: - 3 X_{3} = - 24 Row 2: - X_{2} + 0 \cdot X_{3} = - 5 Row 1: X_{1} + X_{2} + X_{3} = 15 \Rightarrow X_{3} = 8 \Rightarrow - X_{2} = - 5 \Rightarrow X_{2} = 5 \Rightarrow X_{1} + 5 + 8 = 15 \Rightarrow X_{1} = 2

Solution: $(X_{1}, X_{2}, X_{3}) = (2, 5, 8)$ .

Sense-check:

Eq 1: $2 + 5 + 8 = 15$ ✓
Eq 2: $2 (2) + 5 + 2 (8) = 4 + 5 + 16 = 25$ ✓
Eq 3: $4 (2) + 5 + 8 = 8 + 5 + 8 = 21$ ✓

Complexity & Cost. Gaussian elimination on an

n \times n

matrix takes

O (n^{3})

operations — roughly

\frac{2}{3} n^{3}

multiplications. For

n = 1000

, that is about 670 million operations — fine for a computer. For

n = 1 0^{6}

, it is

\sim 6.7 \times 1 0^{17}

operations — completely infeasible. This cubic cost is why neural networks cannot use Gaussian elimination for training. The matrix would be too large.

When to Use / Alternatives.

Use Gaussian elimination for solving $A x = b$ directly when $n \leq 1 0^{4}$ and $A$ is dense.
Use iterative methods (Jacobi, Gauss-Seidel, conjugate gradient) when $n$ is very large and $A$ is sparse.
Use LU decomposition when you need to solve $A x = b$ for multiple different $b$ with the same $A$ .
Never use Gaussian elimination to train neural networks — gradient descent is the right tool for that scale.

Why the upper-triangular shape matters: When everything below the diagonal is zero, the last row contains only one variable. You solve it instantly. Then each row above adds exactly one new variable, which you solve by plugging in values you already know. It is like untying a knot — you loosen the last strand first, then work backward.

Visual Intuition. Picture the matrix as a set of steps. Row 1 has information about all three variables. Row 2 has information about $X_{2}$ and $X_{3}$ only (the $X_{1}$ entry is zero). Row 3 has information about $X_{3}$ only. This is the staircase. You step onto row 3 first (solving $X_{3}$ ). Then use that to step up to row 2 (solving $X_{2}$ ). Then step up to row 1 (solving $X_{1}$ ). Each step upward uses exactly one new piece of information.

Common Pitfalls.

Stopping before the staircase is complete. You must zero out ALL entries below each pivot. A single nonzero below a pivot means the matrix is not in REF and back-substitution will give wrong answers.
Misidentifying the pivot. The pivot is the first nonzero entry in the current row from the left. If the entry at $(r, c)$ is zero, you must either swap rows or move to the next column.
The pivot must stay in its assigned row. The pivot for column 2 cannot be in row 1 — that column's pivot position is already taken by row 1. The staircase forces each pivot to shift rightward.
Dividing by zero in the multiplier. The multiplier for elimination is $\frac{a _{i c}}{a _{r c}}$ . If $a_{r c} = 0$ , you cannot divide — swap rows first to bring a nonzero pivot into position.

Recap. Gaussian elimination is the systematic algorithm that applies row operations. It transforms any augmented matrix into Row Echelon Form. That is an upper-triangular staircase where back-substitution solves the system.

Bridge. REF requires back-substitution. But what if we go further — clean ABOVE each pivot too, and scale every pivot to 1? Then the solution is readable directly, no substitution needed. That is Gauss-Jordan elimination, producing Reduced Row Echelon Form.

Real-World & Domain Connection. Gaussian elimination is the foundation of every direct linear solver. LAPACK's dgesv routine performs it with partial pivoting. It swaps rows to use the largest available pivot for numerical stability. The same routine powers MATLAB's backslash operator A\b and NumPy's np.linalg.solve.

The same algorithm computes matrix inverses, determinants, and ranks. In PageRank (Google's original search algorithm), the core step is solving a linear system. Its size equals the number of web pages — millions of equations. Specialized Gaussian elimination variants exploit sparsity to make this feasible.

2.8 Reduced Row Echelon Form and Gauss-Jordan Elimination

Hook. REF gives you a staircase — but you still have to climb it with back-substitution. What if you could clean the matrix so thoroughly that the answer stares you in the face, no substitution needed? That is Reduced Row Echelon Form: every pivot is 1, and every pivot column is zero everywhere except at the pivot itself. The solution becomes the rightmost column.

2.8.1 Definition of Reduced Row Echelon Form (RREF)

Intuition. REF is like cleaning a messy room into piles — one pile per variable. You know which items belong to which pile, but you still need to dig through them. RREF is like labeling every single item in every pile. Now you can instantly read off exactly what you have. Pile 1 contains only

X_{1} = 2

. Pile 2 contains only

X_{2} = 5

. Pile 3 contains only

X_{3} = 8

. No digging, no back-substitution — the answer is directly visible.

The analogy breaks because real labeling is tedious; RREF is more work than REF. But the clarity at the end is absolute — the rightmost column IS the answer vector.

RREF is REF with two additional requirements:

Every pivot equals 1. Scale each pivot row so the leading entry becomes 1.
All entries above every pivot are zero (not just below). The pivot is the only nonzero entry in its entire column.

In RREF, the solution is directly readable — no back-substitution needed:

100010001 ∣ ∣ ∣ a b c \Rightarrow X_{1} = a, X_{2} = b, X_{3} = c

An equation like $X_{3} = 10$ , $X_{2} = 0$ , $X_{1} = 5$ — it is immediately readable. That is the target of RREF.

2.8.2 Gauss-Jordan Elimination — The Process

Purpose: Extend Gaussian elimination to produce Reduced Row Echelon Form, where the solution is directly readable without back-substitution.

Inputs: An augmented matrix already in REF. Or the original matrix — Gauss-Jordan can be applied from scratch. It zeros both below and above each pivot in one pass.

Outputs: The same matrix in RREF. Every pivot = 1. Every pivot column is a unit vector — all zeros except the 1 at the pivot.

Steps (starting from REF):

Normalize pivots to 1. For each pivot row $r$ , scale: $R_{r} \leftarrow \frac{1}{a _{r, pivot}} R_{r}$ .
Zero out above pivots, right to left. Start from the rightmost pivot. For each row $i$ above the pivot row $r$ : $R_{i} \leftarrow R_{i} - a_{i, pivot} \cdot R_{r}$ . This zeros out the entry above the pivot.
Move left to the next pivot and repeat step 2.

2.8.3 Continuing the Worked Example to RREF

Starting from the REF matrix from Section 2.7:

100 1 - 1 0 10 - 3 15 - 5 - 24

Normalize pivots to 1:

R_{2} R_{3} \leftarrow - 1 \cdot R_{2} : \leftarrow - \frac{1}{3} \cdot R_{3} : [0, - 1, 0, - 5] [0, 0, - 3, - 24] \to [0, 1, 0, 5] \to [0, 0, 1, 8]

1001101011558

Zero out above the third pivot (column 3):

$R_{1} \leftarrow R_{1} - R_{3}$ : $[1, 1, 1, 15] - [0, 0, 1, 8] = [1, 1, 0, 7]$

100110001758

Zero out above the second pivot (column 2):

$R_{1} \leftarrow R_{1} - R_{2}$ : $[1, 1, 0, 7] - [0, 1, 0, 5] = [1, 0, 0, 2]$

100010001258

Solution read directly: $X_{1} = 2$ , $X_{2} = 5$ , $X_{3} = 8$ .

Sense-check: Same solution as the REF back-substitution — both methods give the same answer. RREF just made it instant.

You will have to think through what we can do. Then apply the operations that make everything above the pivot element zero. Also make everything below the pivot element zero.

Complexity & Cost. Gauss-Jordan requires about 50% more operations than Gaussian elimination — roughly

n^{3}

vs.

\frac{2}{3} n^{3}

multiplications. For hand calculation on small matrices, the extra work is worth the clarity. For large-scale computation, Gaussian elimination with back-substitution is preferred.

When to Use / Alternatives.

Use Gauss-Jordan (RREF) for: computing matrix inverses ( $[A ∣ I] \to [I ∣ A^{- 1}]$ ), finding the rank, and solving small systems by hand. Also for theoretical work where you need the cleanest form.
Use Gaussian elimination (REF) for: large systems where back-substitution is cheaper than zeroing above pivots. And when you only need the solution, not the fully reduced form.
Naming: Gaussian elimination → REF is sometimes called the Gauss method. Gauss-Jordan elimination → RREF is the Gauss-Jordan method.

Visual Intuition. Picture the matrix transforming through three stages. Stage 1 (REF): a staircase of pivots with numbers above them — useful but not final. Stage 2 (normalized pivots): the staircase steps are all exactly 1. Stage 3 (RREF): the staircase collapses into a perfect diagonal of 1s, with zeros everywhere else in those columns. The rightmost column has become the answer — $X_{1}$ in row 1, $X_{2}$ in row 2, $X_{3}$ in row 3. The matrix has become an identity matrix with the solution appended.

Common Pitfalls.

Zeroing above pivots in the wrong order. Always go right-to-left. If you zero above the leftmost pivot first, later operations on right columns may reintroduce nonzero entries above left pivots. Right-to-left guarantees that each cleanup is permanent.
Forgetting to normalize pivots to 1. A pivot of $- 3$ with zeros above and below is not RREF — the pivot must be exactly 1.
Thinking RREF is always worth the extra work. For a $1000 \times 1000$ system, Gauss-Jordan costs ~50% more than Gaussian elimination. Use REF + back-substitution for large systems; use RREF for small systems and theoretical work.

Recap. Gauss-Jordan elimination extends Gaussian elimination: normalize every pivot to 1, then zero out above every pivot (right-to-left). The result is RREF — a matrix where the solution is the rightmost column, directly readable.

Bridge. Now that we can solve systems fully, the natural question is: does every system have a solution? And if it does, is it unique? The answer depends on what shape the REF/RREF matrix takes. That is the topic of the next section — the three possible outcomes.

Real-World & Domain Connection. RREF is the algorithm behind matrix inversion. To find $A^{- 1}$ , you augment $A$ with the identity matrix: $[A ∣ I]$ . Apply Gauss-Jordan until the left side becomes $I$ ; the right side becomes $A^{- 1}$ . This is how NumPy's np.linalg.inv works for small matrices. RREF also computes the rank of a matrix (number of pivot columns) and the null space (solutions to $A x = 0$ ). In computer graphics, RREF solves for the coefficients of spline curves that interpolate given control points. In cryptography, certain lattice-based cryptosystems use RREF to find short vectors in high-dimensional lattices.

2.9 The Three Possible Outcomes

Hook. You have solved systems that gave one clean answer. But not every system behaves that well. Some contradict themselves — no answer exists. Others are too loose — infinitely many answers work. The professor called this "the most important part of this entire discussion." Recognizing which outcome you are dealing with, directly from the REF/RREF matrix, is the skill that separates guessing from knowing.

2.9.1 Overview

Intuition. Three friends are trying to meet at a café. Each friend's path is a straight line.

Unique solution: Their paths cross at exactly one café. They meet there.
No solution: Their paths are parallel streets that never cross. They wander forever.
Infinitely many solutions: They are all walking on the same street. Every café on that street works — they cannot decide which one.

The analogy maps directly to the algebraic signatures in REF/RREF. A row of zeros with a nonzero constant is a contradiction ("street does not exist"). A column without a pivot is a free variable ("any café on this street works").

Every system of linear equations falls into exactly one of three categories. The outcome becomes visible once the matrix is in REF or RREF.

Outcome	Visual (2D)	REF/RREF Signature
Unique solution	Two lines intersect at one point	Every variable column has a pivot; no free variables
No solution	Lines are parallel, never meet	A row like $[00 \dots 0 ∣ c]$ with $c \neq = 0$
Infinitely many solutions	Lines coincide (same line)	At least one free variable (column with no pivot); a full zero row at bottom

2.9.2 Unique Solution

This is the ideal case. In REF or RREF, every column corresponding to a variable contains a pivot. There are no free variables. You can read off exactly one value for each unknown.

Example (2D): $2 X + Y = 5$ and $X + Y = 10$ intersect at exactly $(- 5, 15)$ .

Example (3D, from Section 2.7): The system gave $(X_{1}, X_{2}, X_{3}) = (2, 5, 8)$ . Three pivots, three variables, one answer.

2.9.3 No Solution (Inconsistent System)

This occurs when the equations contradict each other. In REF, you see a row where all coefficients are zero but the right-hand side is nonzero.

Signature of inconsistency:

[00 \dots 0 ∣ c], c \neq = 0

This row says $0 \cdot X_{1} + 0 \cdot X_{2} + \dots + 0 \cdot X_{n} = c$ , i.e., $0 = c$ . Since $c \neq = 0$ , this is impossible. No values of the variables can satisfy it.

The last row says $0 \cdot X_{1} + 0 \cdot X_{2} + 0 \cdot X_{3} = 1$ . That cannot happen. Zero cannot be equal to one. When all values before the augmentation are zero and the right-hand side is a real number, that means 0 equals something nonzero. That is a no-solution condition.

Example (2D): $X + Y = 5$ and $X + Y = 10$ .

Augmented matrix:

[1111510]

$R_{2} \leftarrow R_{2} - R_{1}$ :

[101055]

Row 2 says $0 = 5$ — impossible. No solution. The two lines are parallel with different intercepts.

2.9.4 Infinitely Many Solutions

This occurs when at least one variable column has no pivot — that variable is free. There is also a full row of zeros at the bottom ( $0 = 0$ , always true).

When a variable has no pivot, you assign it a parameter $t$ (any real number). You then express all other variables in terms of $t$ . The solution becomes a parametric family.

Procedure:

Identify the free variable(s) — columns without pivots.
Set each free variable equal to a parameter ( $t_{1}, t_{2}, \dots$ ).
Solve for the pivot variables in terms of the parameters using back-substitution.

Worked Example: Parametric solution.

After REF:

200110200540

Row 3 is $0 = 0$ — always true, no constraint.
$X_{3}$ (column 3) has no pivot → free variable. Set $X_{3} = t$ , where $t \in R$ .
Row 2: $X_{2} = 4$ .
Row 1: $2 X_{1} + X_{2} + 2 X_{3} = 5 \Rightarrow 2 X_{1} + 4 + 2 t = 5 \Rightarrow 2 X_{1} = 1 - 2 t \Rightarrow X_{1} = \frac{1 - 2 t}{2}$ .

Solution (parametric form):

X_{1} = \frac{1 - 2 t}{2}, X_{2} = 4, X_{3} = t, for any t \in R

Sense-check: Pick $t = 0$ : $(X_{1}, X_{2}, X_{3}) = (0.5, 4, 0)$ . Row 1: $2 (0.5) + 4 + 2 (0) = 1 + 4 = 5$ ✓. Row 2: $0 + 4 + 0 = 4$ ✓.

Whatever variable does not have a pivot element, take that element as $t$ . Then solve for all the other variables in terms of $t$ .

Visual Intuition. In 2D, the infinite-solution case means the two equations represent the same line. $X + Y = 5$ and $2 X + 2 Y = 10$ — the second is exactly twice the first. Plot them in Desmos: only one line appears because the second equation adds no new information. Every point on that single line satisfies both equations — infinitely many solutions.

In 3D, infinite solutions happen when three planes intersect along a common line (one free variable). They also happen when all three planes are the same plane (two free variables). The number of free variables equals the dimension of the solution space.

Common Pitfalls.

Confusing parallel with coincident. Parallel and distinct lines → no solution. Coincident lines (the same line) → infinitely many solutions. Always check whether the right-hand sides are proportional in the same ratio as the coefficients.
Stopping at "infinitely many" without giving the parametric form. The answer is not just "infinitely many solutions." You must express the solution in terms of the free parameter(s).
Misidentifying which variable is free. The free variable is the one whose column has no pivot — not necessarily the last variable. If columns 2 and 4 have no pivots, both $X_{2}$ and $X_{4}$ are free.
The professor flagged this as the most important concept. The ability to read the three outcomes from REF/RREF is the skill that the exam will test.

Q: Can parallel lines ever give infinitely many solutions?

A: No. Parallel lines that are distinct give no solution — they never meet. But if the lines are coincident, the story changes. Coincident means exactly the same line, with one equation being a multiple of the other. Then every point on that line satisfies both equations. That gives infinitely many solutions. Do not confuse "parallel" with "coincident." Parallel and distinct = no solution. Coincident = infinite solutions.

Several students asked this — the distinction between parallel and coincident is a classic trap.

Exam note: The professor identified this section as the most important in the lecture. Expect exam questions that give you a matrix in REF/RREF. They may ask you to identify the solution type. For the infinite case, they may ask for the parametric form. Practice reading the three signatures until they are automatic.

Recap. Every linear system has exactly one of three outcomes. A unique solution means every column has a pivot. No solution means a row $[0 \dots 0 ∣ c \neq = 0]$ . Infinitely many solutions means at least one free variable. The REF/RREF matrix reveals which one instantly.

Bridge. Solving explicit systems of linear equations with REF/RREF is one use case. But the linear equation also serves a different role in machine learning: as a model whose parameters you fit to data. That is linear regression — and it uses the same matrix machinery in a different way.

Real-World & Domain Connection. The three-outcome classification is the basis of feasibility analysis in operations research. Before optimizing anything, a solver first checks two things. Is the constraint system feasible (does a solution exist)? Is it bounded (unique or infinite)? If the constraints are inconsistent (no solution), the solver reports infeasibility and stops. No amount of optimization can fix contradictory requirements.

In network flow problems (traffic, logistics, data routing), infinite solutions mean slack in the system. You can reroute flow without violating constraints. In robotics, a robot arm's inverse kinematics may have zero, one, or infinitely many joint-angle solutions to reach a target position. The solver must handle all three cases.

2.10 Linear Regression and Model Fitting

Hook. In Sections 2.7–2.9, you solved systems where the coefficients were known and the variables were unknown. Now flip it: the data is known, and the parameters of the model are the unknowns. This is linear regression — the simplest and most widely used machine learning algorithm. The math is identical to what you just learned. Only the names of the unknowns change.

2.10.1 The Setup: Data as Vectors and Matrices

Intuition. You have a cloud of scattered points on a graph — age on the x-axis, salary on the y-axis. You want to draw a single straight line that summarizes the trend. The line will not touch every point — that is impossible. But you can position it so the total distance from all points to the line is as small as possible. Think of stretching a rubber band through a cloud of marbles. It settles into the position of least tension. It touches few marbles directly but stays as close as possible to all of them.

The analogy breaks because the rubber band's path is determined by physical forces. The regression line's position is determined by minimizing squared error. But the visual — a line finding the "center of gravity" of scattered data — is the same.

In machine learning, you do not start with a system of equations to solve. You start with data — rows of observations, each with features (inputs) and a target (output).

Salary (target $y$ )	Age ( $x_{1}$ )	Experience ( $x_{2}$ )
35 lakhs	40	15
75 lakhs	35	17
5 lakhs	22	4
...	...	...

Majority of the times, you have historical data. And using that historical data, you are trying to create a model.

2.10.2 The Model as a Linear Equation

You want to find an equation that relates the inputs to the output:

y = w_{1} x_{1} + w_{2} x_{2} + b

Symbol	Type	Meaning
$y$	scalar	Target / output variable (what you predict, e.g., salary)
$x_{i}$	scalar	Input / predictor variable (known from data, e.g., age)
$w_{i}$	scalar	Weight parameter (unknown, to be learned from data)
$b$	scalar	Bias / intercept (unknown, to be learned)

In the general case with $k$ features:

y = w_{1} x_{1} + w_{2} x_{2} + \dots + w_{k} x_{k} + b

This is a linear equation — every variable $x_{i}$ has degree 1, no products, no nonlinear functions. The parameters $w_{i}$ and $b$ are the unknowns. The data provides the $x$ and $y$ values.

2.10.3 What the Bias Term Does

The bias $b$ is the intercept — the value of $y$ when all inputs are zero. It exists because the output rarely passes through the origin.

Why bias matters — the advertisement example.

Suppose you model sales purely as a multiple of advertisement spend:

sales = 10 \times advertisement

When advertisement = 0, sales = 0. But that is false. Sales happen even without advertising — because of brand recognition, word of mouth, and other unmeasured factors.

With a bias term:

sales = 10 \times advertisement + 200

Now when advertisement = 0, sales = 200. The bias captures the baseline — all the factors your measured variables do not account for.

Without bias, the fitted line is forced through the origin. With bias, the line can shift up or down to better match the data. In almost every real problem, you need a bias term.

2.10.4 Line Fitting and the Minimization of Error

The goal of linear regression: find $w_{1}, w_{2}, b$ so the line passes as close as possible to all data points. You do NOT require the line to touch every point. That is usually impossible when you have more data points than parameters.

The fitting process (conceptual):

Start with random values for $w_{1}, w_{2}, b$ .
For each data point, compute the error. It is the vertical distance between the predicted value ( $y^_{i} = w_{1} x_{i 1} + w_{2} x_{i 2} + b$ ) and the actual value ( $y_{i}$ ).
Square all errors and sum them: $Loss = \sum_{i} (y^_{i} - y_{i})^{2}$ . This is the mean squared error.
Adjust $w_{1}, w_{2}, b$ to reduce the total loss.
Repeat until the loss stops decreasing.

You start with very random values of weight and bias. Then the algorithm tries to see where the data points are and moves in that direction. On the right-hand side, the vertical dashed lines are the errors. The entire idea is to minimize these dashed lines.

2.10.5 Higher-Dimensional Fitting

The same idea extends to any number of dimensions:

2D (1 feature): Fit a line through scattered points.
3D (2 features): Fit a plane through scattered points.
4D+ (3+ features): Fit a hyperplane — a flat linear surface in higher-dimensional space.

A plane fits through all the data points. In higher dimensions, it is a higher-dimensional plane. Still linear fitting — the surface is always flat.

2.10.6 Data as Matrices

For $n$ observations and $k$ features, the data is naturally represented in matrix form.

The target variable $y$ becomes an $n \times 1$ column vector:

y = y_{1} y_{2} ⋮ y_{n}

Each feature becomes an $n \times 1$ column vector. The design matrix $X$ stacks them:

X = x_{11} x_{21} ⋮ x_{n 1} x_{12} x_{22} ⋮ x_{n 2} \dots \dots ⋱ \dots x_{1 k} x_{2 k} ⋮ x_{nk}

Each row is one observation. The model $y = X w + b$ is a system of $n$ linear equations in the $k + 1$ unknowns $w_{1}, \dots, w_{k}, b$ .

Critical distinction: In regression, the data ( $X$ and $y$ ) are known and the parameters ( $w, b$ ) are unknown. In the REF/RREF examples (Sections 2.7–2.9), the coefficients and constants were known, and the variables were unknown. The roles are swapped, but the mathematics is identical: you are solving linear equations.

Scope: When linear regression applies and when it fails.

Applies when: The relationship between features and target is approximately linear. The errors are roughly normally distributed with constant variance. Observations are independent.
Fails when: The true relationship is nonlinear (e.g., exponential growth, periodic patterns). Outliers dominate the fit. Features are highly correlated (multicollinearity — the design matrix $X$ becomes nearly singular, and the parameters blow up).
Overdetermined systems: You typically have far more data points ( $n$ ) than parameters ( $k + 1$ ). The system is overdetermined — no exact solution exists. You find the best approximate solution by minimizing error. This is different from the square systems in Sections 2.7–2.9 where $m = n$ and an exact solution was possible.

Visual Intuition. Open Desmos or any plotting tool. Scatter some points: (1, 2), (2, 3), (3, 5), (4, 4), (5, 7). These five points do not lie on a single straight line. Now draw the best-fit line $y = 1.2 x + 0.8$ . Some points are above it, some below. The vertical distances to the line — the residuals — sum to zero if the line is correctly positioned. The squared residuals are minimized. The line captures the upward trend without passing through any single point exactly.

In 3D (two features), the regression surface is a plane tilting through a cloud of points. The plane's tilt in the $x_{1}$ direction is $w_{1}$ ; its tilt in the $x_{2}$ direction is $w_{2}$ ; its height at the origin is $b$ .

Common Pitfalls.

Forgetting the bias term. Forcing the line through the origin ( $b = 0$ ) almost always gives a worse fit. Always include a bias unless you have a strong domain reason not to.
Thinking the fitted line must pass through data points. It almost never does. The line is a summary of the trend, not an interpolation through every point.
Expecting 100% accuracy. Some residual error is inevitable. The question is whether the error is small enough to be useful, not whether it is zero.
Confusing the roles. In regression, the unknowns are $w$ and $b$ (the model parameters). In the earlier sections, the unknowns were $x_{1}, x_{2}, \dots$ . The same linear algebra applies — only the names have changed.

Q: Where is the bias in a simple equation like

2 X + 3 Y = 6

A: There is none. A simple constraint equation does not have a bias term — it is just a relationship between variables. A predictive model equation adds an explicit bias: $y = w_{1} x_{1} + w_{2} x_{2} + b$ . The bias exists because the output (e.g., sales) depends on factors beyond the measured inputs.

Q: Could sales be affected by unknown parameters beyond advertisement, introducing error?

A: Exactly — that is why bias exists. Bias aggregates the effect of all omitted variables. Adding more relevant features makes the model more sophisticated and typically reduces the bias magnitude. A large bias signals that important predictors are missing.

Q: Does every data point need to satisfy the fitted line exactly?

A: No. The goal is to find a line as close as possible to all points, minimizing the vertical errors. No model is 100% accurate; some residual error is inevitable. The fitted line is a summary of the trend, not a perfect predictor of every individual.

Q: How does linear fitting work in more than 2 dimensions?

A: In 2D you fit a line; in 3D you fit a plane; in 4D+ you fit a hyperplane. All are "linear fitting" because the surface is always flat — no curves. The errors are the vertical (perpendicular-to-hyperplane) distances between the fitted surface and each data point.

Recap. Linear regression flips the role of unknowns. The data (

X, y

) is known, and the parameters (

w, b

) are what you solve for. The model

y = w_{1} x_{1} + \dots + w_{k} x_{k} + b

is a linear equation. Fitting means finding the parameters that minimize the total squared error across all data points.

Bridge. Linear regression uses linear equations as predictive models. But linear equations also appear in a different role. They appear as constraints in optimization problems — deciding how many phones and tablets to manufacture given limited resources. That is linear programming.

Real-World & Domain Connection. Linear regression is the most deployed ML algorithm in industry. The Zillow Zestimate predicts house prices using a linear combination of square footage, bedrooms, bathrooms, location scores, and a bias. Credit scoring models (FICO, VantageScore) use logistic regression — a close cousin — to estimate default probability. They use age, income, credit history, and outstanding debt. Demand forecasting at retailers like Walmart uses linear models to predict weekly sales from past sales, promotions, and seasonality. Medical research uses linear regression to quantify the effect of a treatment while controlling for age, weight, and other covariates. Every one of these is an evaluation of $y = w^{T} x + b$ with learned weights.

2.11 Linear Programming as an Application Context

Hook. You have a factory. You can make tablets or phones. Each product consumes chips, memory, and labor hours — and you have limited quantities of each. How many of each should you make to maximize profit? This is not a single equation to solve. It is a system of linear inequalities bounding a feasible region, with an objective function to optimize. The methods for solving it use the same row operations you just learned.

2.11.1 What Linear Programming Is

Linear programming is a branch of operations research. You solve systems of linear equations (and inequalities) under constraints to optimize an objective — typically maximizing profit or minimizing cost.

Let's say I have some chips, some memory units, and some man-hours. I am trying to make tablets or mobile phones. I have certain restrictions on resources. I cannot make infinitely many products. I try to find what combination of tablets and phones maximizes revenue.

2.11.2 Structure of a Linear Programming Problem

A linear programming problem has three components:

Decision variables: What you control (e.g., number of tablets $T$ , number of phones $P$ ).
Constraints: Linear inequalities from limited resources. For example, if one tablet uses 2 chips, one phone uses 1 chip, and you have 15 chips: $2 T + 1 P \leq 15$ Similar constraints for memory, labor hours, etc.
Objective function: A linear expression to maximize or minimize. For example, if each tablet earns ₹5000 profit and each phone earns ₹3000: $Profit = 5000 T + 3000 P$

The solution method is typically the Simplex algorithm. It moves from one corner point of the feasible region to another. Each step improves the objective until the optimum is reached. Each step is a pivot operation — a row operation — exactly like those in Gaussian elimination.

2.11.3 Distinction from ML Model Fitting

The professor drew a clear boundary between two uses of linear equations:

Context	What you have	What you solve for	Method
REF/RREF (Linear Programming)	Fixed equations with known coefficients	Values of the variables (e.g., how many tablets to make)	Gaussian / Gauss-Jordan / Simplex
ML Model Fitting	Data points (many observations)	Parameters of the model (weights and bias)	Iterative optimization (gradient descent)

In linear programming, you solve a well-defined system of equations and inequalities directly. The coefficients are fixed, and you find the optimal variable values. In machine learning, the linear equation IS the model. You fit its parameters to data, and the system is typically overdetermined (more data points than parameters).

Q: Are REF and RREF mainly for operations research problems, distinct from ML?

A: Yes. REF/RREF solves explicit systems of linear equations — like finding how many phones vs. tablets to manufacture given resource constraints. In ML, the linear equation is the model itself. You fit parameters (weights, bias) to data. You are not solving a fixed system of constraints. The REF/RREF skills build matrix intuition that transfers to ML, but the direct application is in optimization and operations research.

This is a key framing question — the professor wanted students to understand where each tool belongs.

Common Pitfalls.

Confusing constraints with equations. Linear programming uses inequalities ( $\leq, \geq$ ), not just equalities. The feasible region is a polygon (2D) or polytope (higher-D), not just a single point.
Assuming the optimum is always at the origin. The optimum of a linear program is always at a corner point of the feasible region. But it is almost never at the origin unless all resources are zero.
Thinking LP is unrelated to what you learned. The Simplex method literally performs row operations on a tableau — an augmented matrix with extra rows for the objective. It is Gaussian elimination extended for optimization.

Recap. Linear programming extends linear equation solving to optimization under constraints. The Simplex method uses pivoting (row operations) to navigate the feasible region. It is the direct application of REF in operations research. This is distinct from ML model fitting, where the linear equation serves as a predictive model.

Bridge. This concludes the conceptual content of Lecture 2. The remaining sections — Exam Guidance and Key Industry Applications — consolidate what you have learned for exam preparation and real-world context.

Real-World & Domain Connection. Linear programming solvers — Gurobi, CPLEX, and open-source alternatives (HiGHS, GLPK) — power global supply chains. Airline crew scheduling is a massive linear program solved daily. It assigns pilots and flight attendants to thousands of flights while respecting duty-time regulations. Portfolio optimization (allocating capital across assets to maximize return for a given risk) uses quadratic programming, a direct extension. UPS's ORION system saves 100 million miles per year by solving vehicle routing problems — linear programs with integer constraints. All of these use pivoting methods built on the REF structures from Sections 2.7–2.8.

Exam Guidance Summary

Exam note: The professor identified Section 2.9 (three solution types from REF/RREF) as "the most important part of this entire discussion." Expect this to carry significant weight.

What to expect

Mark distribution was not explicitly stated in the session. However, the professor emphasized that solving linear systems using REF and RREF is a core assessed skill.
Expect a mix of conceptual questions and procedural questions. A conceptual question might ask you to identify the three solution types. A procedural question might ask you to perform Gaussian elimination on a 3×3 system.
Practice problems are included in the slide deck. The professor explicitly encouraged you to attempt them and check whether you can do them.

Study strategy

The companion PDF (12 pages) is recommended over the full slide deck (41 slides) for efficient study. It covers the same content in a structured, easier-to-read format.
For the open-book comprehensive exam, the full PPT slide deck will be the primary reference. Know where each topic is located across the slides so you can find it quickly.
Key skills to master:
1. Writing an augmented matrix from a system of equations
2. Performing all three elementary row operations correctly
3. Recognizing REF vs. RREF and converting between them
4. Identifying pivot and free variables from the matrix form
5. Interpreting the three solution types (unique, none, infinite) from REF/RREF
6. Writing the parametric form for infinite-solution cases

High-weight topics

Topic	Section	Exam Likelihood
Three solution types from REF/RREF	2.9	Very High (most important)
Gaussian elimination (REF)	2.7	High
Gauss-Jordan elimination (RREF)	2.8	High
Elementary row operations	2.6	High (foundational)
Augmented matrix construction	2.5	Medium
Linear regression connection	2.10	Medium (conceptual)
Linear programming distinction	2.11	Low–Medium

Key Industry Applications

Large Language Models

GPT-4 (OpenAI): ~1.7 trillion parameters, each a weight in a linear equation $w^{T} x + b = 0$ . Every transformer layer evaluates billions of these equations per input token.
Claude (Anthropic), Llama (Meta), Gemini (Google): All use the same governing linear equation at their core. The "intelligence" emerges from stacking linear transformations with nonlinear activations between them.

Linear Algebra & Visualization Tools

Desmos: Free online graphing calculator used in class to visualize linear equations, their intersections, and the geometric meaning of solutions.
MATLAB / NumPy / LAPACK: Production linear algebra libraries. All represent systems in augmented matrix form $[A ∣ b]$ and apply row operations internally. NumPy's np.linalg.solve(A, b) performs Gaussian elimination with partial pivoting.

Optimization & Operations Research

Gurobi / CPLEX / HiGHS: Commercial and open-source linear programming solvers. Use pivoting methods (built on REF) for supply-chain optimization, production planning, portfolio allocation, and airline crew scheduling. Handle millions of variables and constraints.

Predictive Modeling

Zillow Zestimate: Predicts house prices using a linear combination of square footage, bedrooms, location scores, and a bias term. Every estimate is one evaluation of $y = w^{T} x + b$ .
Credit scoring (FICO, VantageScore): Logistic regression — a close cousin of linear regression — estimates default probability. It uses age, income, credit history, and debt. Weights are learned from historical loan data.
Sales forecasting: Companies model sales as $y = w \cdot ad_spend + b$ . The bias $b$ captures brand value and organic demand — the sales that happen even without advertising.

GPS navigation: Your receiver solves a system of four linear equations (one per visible satellite). It determines your 3D position and clock bias. A direct application of solving $A x = b$ .
Circuit analysis: Kirchhoff's current and voltage laws produce sparse linear systems solved by Gaussian elimination variants.
Structural engineering: Finite element analysis for bridges, buildings, and aircraft produces massive sparse linear systems ( $n > 1 0^{6}$ ). They are solved by iterative methods built on the same row-operation principles.

MFML Lecture 02 notes · Solving Systems of Linear Equations

Mathematical Foundations for Machine Learning· postgraduate· 2026-07-07

Sections Breakdown

1What Is a Linear Equation

Definition, degree-1 form, and the line/plane/hyperplane geometry of linear equations.

2Systems of Linear Equations and the Common Solution

Collections of equations sharing variables; the common solution as an intersection.

3Linear Equations as the Foundation of Machine Learning

The governing equation w^T x + b = 0 and GPT-4's 1.7 trillion parameters.

4Elimination and Substitution Methods

High-school elimination, worked example, and why it fails to scale.

5The Augmented Matrix Representation

Compact [A | b] form: rows are equations, columns are variables.

6Elementary Row Operations

The three legal moves: swap, scale, replace — and what they preserve.

7Row Echelon Form and Gaussian Elimination

REF staircase, the Gaussian elimination algorithm, and back-substitution.

8Reduced Row Echelon Form and Gauss-Jordan Elimination

RREF with normalized pivots and direct readability of the solution.

9The Three Possible Outcomes

Unique, no solution, and infinitely many solutions read from REF/RREF.

10Linear Regression and Model Fitting

Flipping roles: data known, parameters unknown; minimizing squared error.

11Linear Programming as an Application Context

Optimization under inequality constraints via the Simplex pivot method.

12Exam Guidance Summary

What to expect, study strategy, and high-weight topics for the exam.

13Key Industry Applications

LLMs, solvers, predictive modeling, navigation, and engineering uses.

Postgraduate students in Mathematical Foundations for Machine Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review — but if something doesn't make sense, go back to the full explanation in the main content.

2.1 What Is a Linear Equation

Must-know: A linear equation is a weighted sum of variables, each raised only to degree 1, set equal to a constant. It graphs as a line (2D), plane (3D), or hyperplane (nD) — always flat.

$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b$

⚠️ Top pitfall: Thinking "the graph is a line" makes it linear. A circle $(X^{2} + Y^{2} = 1)$ is curved-smooth but nonlinear. The test is algebraic: variables only added, never multiplied or inside a function.

Self-check: Is $X_{1} X_{2} + X_{3} = 10$ linear? Why or why not?

Connects to: 2.2 Systems of equations, 2.3 Neural network governing equation.

2.2 Systems of Linear Equations

Must-know: A system is a set of linear equations sharing variables; the common solution is the point (intersection) satisfying all at once. You need at least as many independent equations as unknowns for a unique answer.

$a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{in} x_{n} = b_{i}, i = 1, \dots, m$

⚠️ Top pitfall: Assuming every system has a solution. Fewer equations than unknowns gives an underdetermined (often infinite) system; contradictory equations give none.

Self-check: With 3 variables, how many independent equations are needed for a unique solution?

Connects to: 2.5 Augmented matrix, 2.9 Three outcomes.

2.3 Linear Equations in Machine Learning

Must-know: Every neural network layer is built on $w^{T} x + b = 0$ — a linear equation. GPT-4's 1.7 trillion parameters are weights in such equations. Training uses gradient descent, NOT Gaussian elimination.

$w^{T} x + b = w_{1} x_{1} + w_{2} x_{2} + \dots + w_{n} x_{n} + b = 0$

⚠️ Top pitfall: Believing the model "solves" the system with row operations. The weights are the unknowns; the training data supplies the equations. Gradient descent fits them iteratively.

Self-check: Why can't we use Gaussian elimination to train a 1.7-trillion-parameter model?

Connects to: 2.1 Linear equation, 2.10 Linear regression.

2.4 Elimination and Substitution

Must-know: Elimination matches a coefficient, subtracts one equation from another to cancel a variable, solves, then back-substitutes. It works for 2–3 equations but becomes unmanageable at scale — the motivation for matrices.

$(2 X + 2 Y) - (2 X + 3 Y) = 6 - 7 \Rightarrow - Y = - 1 \Rightarrow Y = 1$

⚠️ Top pitfall: Forgetting to multiply the right-hand side when scaling an equation. $X + Y = 3$ becomes $2 X + 2 Y = 6$ , never $2 X + 2 Y = 3$ .

Self-check: After eliminating $X$ from a 2-equation system, what must you do to find both variables?

Connects to: 2.5 Augmented matrix, 2.6 Row operations.

2.5 The Augmented Matrix

Must-know: The augmented matrix $[A ∣ b]$ strips variable names: rows = equations, columns (before bar) = variables, last column = constants. Missing variables become zeros, not blanks.

$211 1 - 1 1 11 - 2 5106$

⚠️ Top pitfall: Misaligning columns. Reorder $X_{3} - X_{2} + X_{1} = 10$ to $X_{1} - X_{2} + X_{3} = 10$ before extracting coefficients, or the columns won't match.

Self-check: What does the vertical bar in an augmented matrix represent?

Connects to: 2.4 Elimination, 2.6 Row operations.

2.6 Elementary Row Operations

Must-know: Exactly three legal moves preserve the solution set: row swap ( $R_{i} \leftrightarrow R_{j}$ ), row scaling ( $R_{i} \leftarrow c R_{i}, c \neq = 0$ ), and row replacement ( $R_{i} \leftarrow R_{i} - c R_{j}$ ).

$R_{i} \leftarrow R_{i} - \frac{a _{i c}}{a _{r c}} R_{r}$

⚠️ Top pitfall: Scaling by zero ( $c = 0$ ) destroys the equation. Also, row replacement modifies only row $i$ , never row $j$ — and the constant column must be updated too.

Self-check: Which of the three operations changes the individual equations but keeps the solution set identical?

Connects to: 2.7 Gaussian elimination, 2.8 Gauss-Jordan.

2.7 Row Echelon Form & Gaussian Elimination

Must-know: Gaussian elimination uses row operations to reach REF. REF is a staircase where each pivot is right of the one above and all entries below are zero. Then back-substitute from the last row up.

$* 00 * * 0 * * *$

⚠️ Top pitfall: Stopping before all entries below every pivot are zero. One leftover nonzero means the matrix isn't in REF and back-substitution fails. Cost is $O (n^{3})$ .

Self-check: Why must you swap rows when the pivot position holds a zero?

Connects to: 2.6 Row operations, 2.8 RREF, 2.9 Outcomes.

2.8 Reduced Row Echelon Form & Gauss-Jordan

Must-know: RREF adds two rules to REF: every pivot equals 1, and every pivot column is zero everywhere except the pivot. The solution is then the rightmost column — no back-substitution needed.

$100010001 ∣ ∣ ∣ a b c \Rightarrow X_{1} = a, X_{2} = b, X_{3} = c$

⚠️ Top pitfall: Zeroing above pivots in the wrong order. Always go right-to-left, or later steps reintroduce nonzero entries above left pivots.

Self-check: In RREF, what must every pivot value be, and what fills the rest of its column?

Connects to: 2.7 Gaussian elimination, 2.9 Outcomes.

2.9 The Three Possible Outcomes

Must-know: From REF/RREF read the outcome directly. Unique means every variable column has a pivot. No solution means a row $[0 \dots 0 ∣ c \neq = 0]$ . Infinitely many means at least one free variable plus a zero row. This is the most important section.

$[00 \dots 0 ∣ c], c \neq = 0 \Rightarrow no solution$

⚠️ Top pitfall: Confusing parallel (no solution) with coincident (infinitely many). For infinite cases, you must write the parametric form using the free variable $t$ , not just say "infinitely many."

Self-check: A REF row reads $[000 ∣ 5]$ . What does that tell you about the system?

Connects to: 2.7 REF, 2.8 RREF, 2.11 Linear programming.

2.10 Linear Regression & Model Fitting

Must-know: Linear regression flips the roles: data ( $X, y$ ) is known, parameters ( $w, b$ ) are unknown. Fit $y = w^{T} x + b$ by minimizing the sum of squared errors. The bias $b$ captures the baseline when all inputs are zero.

$Loss = i \sum (y^_{i} - y_{i})^{2}, y^_{i} = w_{1} x_{i 1} + \dots + w_{k} x_{ik} + b$

⚠️ Top pitfall: Forgetting the bias term forces the line through the origin and worsens the fit. Also, the fitted line rarely passes through any data point — that's expected, not a failure.

Self-check: In regression, what are the unknowns — the $x$ 's or the $w$ 's and $b$ ?

Connects to: 2.3 Governing equation, 2.11 Linear programming.

2.11 Linear Programming

Must-know: Linear programming optimizes a linear objective (e.g., profit) subject to linear inequality constraints. The Simplex method pivots on a tableau — the same row operations as Gaussian elimination, applied to optimization.

$maximize 5000 T + 3000 P subject to 2 T + P \leq 15, T, P \geq 0$

⚠️ Top pitfall: Treating LP constraints as equalities. They are inequalities ( $\leq, \geq$ ), so the feasible region is a polytope. The optimum sits at a corner point — not the origin.

Self-check: How does the Simplex method relate to the row operations you learned in 2.6?

Connects to: 2.6 Row operations, 2.9 Feasibility.

Previous LectureLecture 01 · Introduction to Linear Algebra

Next LectureLecture 03 · Groups, Vector Spaces, and Linear Combinations

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

2.1 What Is a Linear Equation

2.1.1 Definition and Core Idea

2.1.2 Formal Form

2.2 Systems of Linear Equations and the Common Solution

2.2.1 Definition

2.2.2 The General Problem

2.3 Linear Equations as the Foundation of Machine Learning

2.3.1 The Governing Equation of Neural Networks

2.3.2 The Scale: GPT-4 and 1.7 Trillion Parameters

2.3.3 Why Solving Matters

2.4 Elimination and Substitution Methods

2.4.1 The High-School Methods

2.4.2 Worked Example: Elimination

2.4.3 Why These Methods Do Not Scale

2.5 The Augmented Matrix Representation

2.5.1 Definition and Construction

2.5.2 Why This Representation Helps

2.5.3 The General Form

2.6 Elementary Row Operations

2.6.1 The Three Allowed Operations

2.6.2 What These Operations Achieve

2.7 Row Echelon Form and Gaussian Elimination

2.7.1 Definition of Row Echelon Form (REF)

2.7.2 Gaussian Elimination — The Process

2.7.3 Worked Example: Gaussian Elimination

2.8 Reduced Row Echelon Form and Gauss-Jordan Elimination

2.8.1 Definition of Reduced Row Echelon Form (RREF)

2.8.2 Gauss-Jordan Elimination — The Process

2.8.3 Continuing the Worked Example to RREF

2.9 The Three Possible Outcomes

2.9.1 Overview

2.9.2 Unique Solution

2.9.3 No Solution (Inconsistent System)

2.9.4 Infinitely Many Solutions

2.10 Linear Regression and Model Fitting

2.10.1 The Setup: Data as Vectors and Matrices

2.10.2 The Model as a Linear Equation

2.10.3 What the Bias Term Does

2.10.4 Line Fitting and the Minimization of Error

2.10.5 Higher-Dimensional Fitting

2.10.6 Data as Matrices

2.11 Linear Programming as an Application Context

2.11.1 What Linear Programming Is

2.11.2 Structure of a Linear Programming Problem

2.11.3 Distinction from ML Model Fitting

Exam Guidance Summary

What to expect

Study strategy

High-weight topics

Key Industry Applications

Large Language Models

Linear Algebra & Visualization Tools

Optimization & Operations Research

Predictive Modeling

Navigation & Engineering

MFML Lecture 02 notes · Solving Systems of Linear Equations

Sections Breakdown

Exam Revision Notes

2.1 What Is a Linear Equation

2.2 Systems of Linear Equations

2.3 Linear Equations in Machine Learning

2.4 Elimination and Substitution

2.5 The Augmented Matrix

2.6 Elementary Row Operations

2.7 Row Echelon Form & Gaussian Elimination

2.8 Reduced Row Echelon Form & Gauss-Jordan

2.9 The Three Possible Outcomes

2.10 Linear Regression & Model Fitting

2.11 Linear Programming

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat