Appearance
Solving Systems — Gaussian Elimination and Linear Independence
The previous chapter asked: what does a matrix do to space? This chapter asks the natural follow-up: if you know what a matrix did, can you work backwards to find what went in?
That is the problem of solving a system of linear equations — given a matrix and an output vector , find every vector such that . It is one of the oldest problems in mathematics and one of the most useful in engineering.
By the end of this chapter you will be able to:
- Translate a system of linear equations into a matrix equation .
- Solve that system using Gaussian elimination (row reduction).
- Recognize when a system has no solution, exactly one solution, or infinitely many.
- Define linear independence and explain what it means geometrically.
- Read the rank of a matrix and understand what it reveals.
The Collision Puzzle
Imagine you are writing a physics engine for a game. Two objects collide in a frictionless 1D channel. You have sensors on the channel walls that measure the combined momentum of both objects at several moments, but cannot measure each object individually. After three sensor readings you have three measurements — and two unknowns (the velocity of object A, the velocity of object B).
Let and be the velocities you are trying to find. Your three sensor equations might look like this:
Three equations, two unknowns. Clearly some of these equations overlap, and the system either has a solution or is inconsistent. You could solve it by hand using substitution — but that approach falls apart when you have 20 unknowns, or 200. What you need is a systematic, automatable procedure. That procedure is Gaussian elimination.
From Equations to Matrices
A system of linear equations and a matrix equation are the same thing, written differently. The system above is exactly:
The matrix contains the coefficients, is the unknowns vector, and is the right-hand side. This is the standard form .[^1]
To solve it, we work with the augmented matrix: the coefficient matrix with the right-hand side appended as an extra column, separated by a vertical bar.[^2]
Each row of the augmented matrix represents one equation. Our goal is to manipulate these rows until the solution becomes obvious — ideally until the left side looks like the identity matrix and the right column just reads off the answers.
The Three Legal Moves
We are allowed exactly three types of operations on the rows, and all three preserve the solution set — meaning the manipulated system has exactly the same solutions as the original.[^3]
| Operation | Notation | What it does |
|---|---|---|
| Swap two rows | Reorder the equations | |
| Multiply a row by a nonzero scalar | Scale an equation | |
| Add a multiple of one row to another | Eliminate a variable |
Think of these as legally rewriting a contract. You can rearrange the clauses, multiply both sides of a clause by a constant, or combine two clauses into one equivalent clause — but the underlying agreement never changes. Whatever satisfied the original system satisfies the new one, and vice versa.
TIP
These operations are reversible. Swap rows back; multiply by the reciprocal; subtract what you added. That reversibility is precisely why the solution set is preserved.
Gaussian Elimination — The Forward Pass
The strategy of Gaussian elimination is to drive zeros into the lower-left triangle of the matrix, one column at a time, until the rows form a staircase pattern.[^3]
Let us work through a clean 3-variable example:
Step 1: Make the pivot in column 1 equal to 1.
Divide by 2:
Step 2: Eliminate column 1 below the pivot.
Add to , and add to :
The first column is clean below the pivot. Move to column 2.
Step 3: Make the pivot in column 2 equal to 1.
Multiply by 2:
Step 4: Eliminate column 2 below the pivot.
Subtract from :
Step 5: Make the pivot in column 3 equal to 1.
Multiply by :
This is row echelon form (REF). Notice the staircase of leading 1s (called pivots):
1 * * | *
0 1 * | *
0 0 1 | *Each row's first nonzero entry sits one column to the right of the row above it.[^3] The lower triangle is all zeros. From here, the solution is visible — you just have to read it out.
Back-Substitution
From REF, the third row says directly. Substitute into the second row:
Substitute both into the first row:
The solution is .
Reduced Row Echelon Form
Alternatively, you can continue eliminating above the pivots as well, not just below. This extra backward sweep produces reduced row echelon form (RREF).[^3]
Starting from the REF above, eliminate above each pivot from right to left:
The solution is now immediate: , , . The left side has become the identity matrix. This complete form — eliminate both below and above each pivot — is called Gauss-Jordan elimination, and it is what most software implementations produce.[^3]
INFO
In practice, numerical software (NumPy, MATLAB, game engine math libraries) uses LU decomposition rather than literal row reduction for performance, but the underlying theory is identical: they are systematically eliminating off-diagonal entries.
When Things Go Wrong
Gaussian elimination always terminates, but it does not always produce a unique solution. The augmented matrix tells you exactly what went wrong — and there are only two ways it can.
Case 1 — No Solution (Inconsistent System)
Suppose row reduction produces a row that looks like this:
That row reads: , which simplifies to . That is a contradiction — no choice of can satisfy it. The system has no solution.[^2]
Geometrically, in 2D: two parallel lines that never intersect.
y
| /
| / <- line 1
|
| <- line 2 (parallel, offset)
|
---+----------> xThe equations describe parallel lines (same slope, different intercepts). They share no point.
Case 2 — Infinitely Many Solutions (Dependent System)
Suppose row reduction produces an all-zero row:
The zero row reads — no contradiction, but also no new information. We have three variables and only two useful equations. The third variable is a free variable: you can pick any value for , and then and are determined by it:
This is a parametric solution: an entire line of solutions in 3D, parameterized by . Geometrically, the three planes share a common line rather than a single point.
WARNING
A zero row in the augmented matrix's coefficient side means your original equations were redundant — one equation was a linear combination of the others and carried no new information. The system is underdetermined: more unknowns than independent equations.
The number of pivots you find during elimination is the key metric. In the underdetermined example above, only 2 of the 3 columns have pivots. That number has a name.
Linear Independence — No Redundant Equations
The reason a zero row appears is that one of your original equations was redundant — it could be derived from the others. This is exactly the concept of linear dependence.
A set of vectors is linearly dependent if there exist scalars (not all zero) such that:[^4]
In plain English: you can reach the zero vector by a non-trivial combination of the vectors. The vectors are linearly independent if the only solution to this equation is all scalars equal to zero — meaning no vector in the set can be written as a combination of the others.[^4]
The Geometric Picture
The concept snaps into place visually.
Two vectors in 2D. Pick any two non-parallel arrows. No matter how you scale and add them, you cannot make them cancel to zero (unless you use zero scale on both). They are linearly independent. But if one arrow points in the same direction as the other — parallel, or anti-parallel — you can scale one to match the negative of the other, and they cancel. Linear dependence.
Independent: Dependent:
^ / ^ ^
| / | |
|/ <-- two directions | | <-- same direction, different lengths
----+----> ---+---->Two vectors in 2D are linearly independent if and only if they are not parallel.[^4]
Three vectors in 3D. Three independent vectors point in genuinely different directions and span all of 3D space. Three dependent vectors are coplanar — they all lie in the same plane, and one of them can be reached by combining the other two. The third adds no new direction.
Independent (span 3D): Dependent (coplanar):
/| ^ ^ ^
/ | | | | /
/ | | | | / <- all three lie flat in one plane
/ | | |/
---+----+----> ---+---->Three vectors in 3D are linearly independent if and only if they are not coplanar.[^4]
TIP
Quick test: set up the matrix whose columns are your vectors, then row-reduce. If every column ends up with a pivot, the columns are linearly independent. If any column lacks a pivot — it is a free variable column — that column is a linear combination of the pivot columns, and the set is dependent.[^4]
Independence and the Null Space
Linear independence is another way of asking about the null space. The columns of are linearly independent if and only if has only the trivial solution .[^4] If there is a non-trivial solution — some nonzero that maps to zero — then the non-zero components of are the coefficients of the dependent combination. This is the same null space introduced in Chapter 5, now seen from the perspective of the columns.
Rank — Counting Independent Directions
Every time you perform Gaussian elimination, you count pivots. That count is the rank of the matrix.[^5]
Rank measures how many genuinely independent directions the matrix's columns span. It answers: how many dimensions does the transformation actually fill?
For a matrix with columns:
| rank = | Every column is a pivot column. Columns are linearly independent. |
|---|---|
| rank | At least one column is redundant. The columns span fewer dimensions than . |
Example. Consider:
Row-reducing this matrix yields:
Two pivots. Rank = 2. The third column is a linear combination of the first two (in fact, column 3 = ). The matrix maps all of 3D space into a 2D plane — one dimension is lost.
Rank and Invertibility
A square matrix is invertible if and only if it has rank — that is, full rank.[^5] If rank is less than , at least one dimension is collapsed, information is destroyed, and no inverse can recover it. This is the same condition seen in Chapter 5 through the lens of the null space.
Full rank means the null space contains only . Less than full rank means the null space is larger — there are non-trivial vectors that map to zero.
The Rank-Nullity Theorem
The relationship between rank and null space has a precise statement.[^5]
where is the number of columns of and nullity is the dimension of the null space.
Every column is either a pivot column or a free variable column. Pivot columns contribute to the rank; free variable columns contribute to the nullity. Together they account for all columns, so the two counts must sum to .
Think of it this way: the input space has dimensions. Some of those dimensions get "mapped to useful output" (rank), and the rest "collapse into zero" (nullity). The total is always .
Rank-nullity in action
For the matrix above: rank = 2, number of columns = 3.
Nullity = 3 − 2 = 1. The null space is 1-dimensional: a line of vectors that maps to .
You can find that line by solving . From the RREF above (with the augmented column of zeros), the free variable is , giving , . So the null space is spanned by .
Check: ✓
Chapter Recap
Four ideas to carry forward:
is the central question. Any system of linear equations can be written this way. The augmented matrix packages all the information for row reduction.
Gaussian elimination solves it. Apply the three row operations to drive the matrix to row echelon form, then back-substitute (or continue to RREF for a clean read-off). The procedure always terminates and reveals whether the system has a unique solution, no solution, or infinitely many.
Linear independence means no redundancy. Vectors are linearly independent when none of them can be built from the others. In elimination, independent columns have pivots; dependent columns do not. Geometrically, independent vectors point in genuinely different directions.
Rank counts the independent directions. Rank equals the number of pivot columns. It tells you how many dimensions the transformation fills. Full rank means invertible; less than full rank means information is lost. Rank and nullity together always sum to the number of columns.
The next chapter introduces the determinant — a single number that summarizes whether a matrix has full rank, how much it stretches or squishes area and volume, and which direction it orients space.
References
[^1]: "Gaussian Elimination." Wikipedia. https://en.wikipedia.org/wiki/Gaussian_elimination
[^2]: "11.6: Solving Systems with Gaussian Elimination." Algebra and Trigonometry 1e (OpenStax), Mathematics LibreTexts. https://math.libretexts.org/Bookshelves/Algebra/Algebra_and_Trigonometry_1e_(OpenStax)/11:_Systems_of_Equations_and_Inequalities/11.06:_Solving_Systems_with_Gaussian_Elimination
[^3]: Hartman, G. "1.3: Elementary Row Operations and Gaussian Elimination." Fundamentals of Matrix Algebra, Mathematics LibreTexts. https://math.libretexts.org/Bookshelves/Linear_Algebra/Fundamentals_of_Matrix_Algebra_(Hartman)/01:_Systems_of_Linear_Equations/1.03:_Elementary_Row_Operations_and_Gaussian_Elimination
[^4]: Margalit, D. and Rabinoff, J. "Linear Independence." Interactive Linear Algebra, Georgia Tech. https://textbooks.math.gatech.edu/ila/linear-independence.html
[^5]: Austin, D. "2.4: Linear Independence." Understanding Linear Algebra, Mathematics LibreTexts. https://math.libretexts.org/Bookshelves/Linear_Algebra/Understanding_Linear_Algebra_(Austin)/02:_Vectors_matrices_and_linear_combinations/2.04:_Linear_independence