Systems of Linear Equations

Attempt these from memory before reading.

• What are the three possible outcomes for a linear system?
• What does it mean for a matrix to be in row echelon form? Reduced form?
• What does pivoting protect against, and why is it needed at all?
• State the rank-nullity theorem and say what it predicts for an $m \times n$ system.
• When is the least-squares solution the right answer?

Check your answers against the text. Prompt 2 is the practical core: every claim about existence and uniqueness in this page is read off a row echelon form, so knowing what you are allowed to conclude from one is the skill.

Gaussian elimination is usually taught as a procedure with steps. It is better understood as applying a sequence of invertible row operations, each of which is multiplication by a simple matrix.

Each $E_i$ is invertible, so the product $E_k \cdots E_1$ is invertible, and an invertible map does not change the solution set. That is why elimination is allowed to work at all: every row operation produces a system with exactly the same solutions.

Reading the product the other way gives the LU decomposition:

where $L$ is lower triangular with the multipliers on its entries. So LU is not a separate technique from elimination — it is the elimination recorded, which is why factoring once and solving many times is cheaper than eliminating from scratch for every right-hand side.

Why pivoting is needed. Dividing by a pivot that is small — or zero — is what breaks elimination. Swapping rows to bring the largest available entry to the pivot position costs nothing and avoids dividing by something tiny. In exact arithmetic it is unnecessary; in floating point it is the difference between an answer and noise, because a tiny pivot amplifies rounding error into every entry below it.

A system of $m$ linear equations in $n$ unknowns can be written as $A\mathbf{x} = \mathbf{b}$ Where $A \in \mathcal{M}_{m \times n}(\mathbb{R})$, $\mathbf{x} \in \mathbb{R}^n$ And $\mathbf{b} \in \mathbb{R}^m$.

Gaussian elimination transforms the augmented matrix $[A \mid \mathbf{b}]$ into row echelon Form (REF) using elementary row operations:

1. Swap two rows ($R_i \leftrightarrow R_j$).
2. Multiply a row by a non-zero scalar ($R_i \to \alpha R_i$).
3. Add a multiple of one row to another ($R_i \to R_i + \alpha R_j$).

A matrix is in REF if:

• All zero rows are at the bottom.
• The leading entry (pivot) of each non-zero row is strictly to the right of the pivot above.
• All entries below a pivot are zero.

Reduced row echelon form (RREF) additionally requires:

• Each pivot is 1.
• Each pivot is the only non-zero entry in its column.

Theorem 4.1. Every matrix has a unique RREF. Two matrices are row-equivalent if and only if they Have the same RREF.

Theorem 4.2 (Rouché—Capelli). The system $A\mathbf{x} = \mathbf{b}$ is consistent (has at least one Solution) if and only if

If consistent, the solution set has $\dim(\mathrm{null}(A))$ free parameters, where $\dim(\mathrm{null}(A)) = n - \mathrm{rank}(A)$.

Proof. Let the RREF of $[A \mid \mathbf{b}]$ have $r = \mathrm{rank}(A)$ pivots in the coefficient Columns. The system is inconsistent if and only if the last non-zero row is $[0 \cdots 0 \mid 1]$ which occurs precisely when the augmented column contains a pivot, i.e., when $\mathrm{rank}([A \mid \mathbf{b}]) \gt r$.

If consistent, the $r$ pivot variables are determined by the $n - r$ free variables, yielding $n - \mathrm{rank}(A)$ degrees of freedom. $\blacksquare$

An LU decomposition of $A \in \mathcal{M}_{n \times n}(\mathbb{R})$ writes $A = LU$ where $L$ is Lower triangular with 1s on the diagonal, and $U$ is upper triangular.

Theorem 4.3. If Gaussian elimination can be performed on $A$ without row exchanges, then $A$ Admits an LU decomposition.

Algorithm. Store the multipliers $m_{ij}$ (used to eliminate entry $a_{ij}$) in the lower Triangular portion. The resulting upper triangular matrix is $U$ And the multipliers form $L$.

Worked Example. Find the LU decomposition of

To solve $A\mathbf{x} = \mathbf{b}$ First solve $L\mathbf{y} = \mathbf{b}$ (forward substitution), Then $U\mathbf{x} = \mathbf{y}$ (back substitution).

When a pivot is zero (or very small), we swap rows to bring the largest available entry in the Current column into the pivot position. This is partial pivoting, and it improves numerical Stability.

Problem. Solve the system using Gaussian elimination with partial pivoting:

When $A\mathbf{x} = \mathbf{b}$ is overdetermined (more equations than unknowns) and inconsistent, We seek $\mathbf{x}$ that minimises $\lVert A\mathbf{x} - \mathbf{b} \rVert^2$.

Theorem 4.4 (Normal Equations). The least squares solution $\hat{\mathbf{x}}$ satisfies

If $A$ has full column rank, then $A^T A$ is invertible and $\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}$.

Proof. The error vector $\mathbf{e} = A\mathbf{x} - \mathbf{b}$ is minimised when $\mathbf{e} \perp \mathrm{col}(A)$ I.e., when $A^T \mathbf{e} = \mathbf{0}$. This gives $A^T(A\mathbf{x} - \mathbf{b}) = \mathbf{0}$ Or $A^T A \mathbf{x} = A^T \mathbf{b}$. If $A$ has full column rank, then $\ker(A) = \{\mathbf{0}\}$ So $\ker(A^T A) = \ker(A) = \{\mathbf{0}\}$ Meaning $A^T A$ is invertible. $\blacksquare$

Problem. Find the least squares line $y = ax + b$ fitting the data points $(1, 1)$, $(2, 1)$, $(3, 3)$.

Problem. Solve the system:

• Partial pivoting is not optional for numerical work. Without it, Gaussian elimination can produce catastrophically wrong results due to rounding errors.
• The normal equations can be ill-conditioned. For better numerical stability, use QR decomposition to solve least squares problems instead of forming $A^T A$.
• Not every system has a solution. Always check consistency via the Rouche—Capelli theorem before attempting to solve.
• When a system has infinitely many solutions, the solution set is an affine subspace, not a vector space. The general solution is $\mathbf{x} = \mathbf{x}_p + \mathbf{x}_h$ where $\mathbf{x}_p$ is a particular solution and $\mathbf{x}_h$ is any element of the null space. The null space is a vector space, but the affine shift by $\mathbf{x}_p$ means the solution set does not contain $\mathbf{0}$ (unless $\mathbf{x}_p = \mathbf{0}$).
• Do not confuse the number of equations with the number of unknowns. A system with more equations than unknowns (overdetermined) may have no solution, exactly one solution, or infinitely many solutions. A system with fewer equations than unknowns (underdetermined) may have no solution or infinitely many solutions, but never exactly one solution.

Each elementary row operation corresponds to a geometric operation on the system of equations. In $\mathbb{R}^3$, each equation $a_1 x + a_2 y + a_3 z = b$ defines a plane. The solution to the system is the intersection of all these planes.

• Swapping rows reorders the equations, which does not change the solution set.
• Multiplying a row by a scalar rescales an equation without changing its solution set.
• Adding a multiple of one row to another replaces one plane with a new plane that passes through the line of intersection of the two original planes.

Gaussian elimination systematically rotates and translates the planes so that their intersection becomes apparent. After reduction to row echelon form, the last equation involves only one variable, the second-to-last involves at most two variables, and so on. Back substitution then recovers all variables one at a time, starting from the simplest equation.

When the system is inconsistent, the row reduction produces a contradiction (such as $0 = 1$), meaning the planes have no common point of intersection. When there are free variables, the planes intersect in a line, plane, or higher-dimensional flat, reflecting the infinitely many solutions.

Problem. Solve the system:

Gaussian elimination is the systematic process of untangling a web of simultaneous constraints. Each equation in a linear system defines a hyperplane in some high-dimensional space, and a solution is a point where all hyperplanes intersect. Row reduction is the algebraic equivalent of rotating and sliding these hyperplanes until they reveal their intersection evidently. When you swap rows, you are re-ordering which constraint you address first. When you multiply a row by a scalar, you are rescaling a constraint without changing the solution set. When you add a multiple of one row to another, you are using one equation to eliminate a variable from another — the same logic as solving two equations with two unknowns by substitution.

The deeper insight is that row reduction preserves the solution space while simplifying its description. The row echelon form makes the structure of the solution set transparent: pivot columns identify the dependent variables, free columns identify the independent degrees of freedom, and the rank tells you the dimension of the solution space. This is why the same technique extends to function spaces and operator theory, where infinite-dimensional systems of equations arise logically.

The first row is the one to internalise, because the shape of the coefficient matrix does not determine the outcome. Two systems can look identical in shape and differ in every way that matters — which is why the answer is read from the echelon form of the augmented matrix.

The least-squares row is the bridge to the next idea: when $Ax = b$ has no solution, asking for the best $x$ is still a sensible question, and the normal equations answer it.

• Sparse elimination. For matrices from real problems, most entries are zero, and the ordering of elimination determines how much fill-in appears. Choosing a good ordering is NP-hard in general, so heuristics — minimum degree, nested dissection — are where the practical gains live.
• Iterative methods. For very large systems, factorisation is too expensive and Krylov subspace methods (conjugate gradient, GMRES) are used instead; their convergence theory is where the research is.
• Randomised linear algebra. Sketching a large system down to a smaller one and solving that, with probability bounds on the error.
• Rounding-error analysis. The classic backward-error results are decades old, and extending them to structured and low-rank matrices is active.
• Complexity. Whether Gaussian elimination is optimal, and the exponent of matrix multiplication, connect this page to the open problem on the matrices page.

Mix these with Linear Independence, Span, Basis and Dimension, Matrices, Eigenvalues and Eigenvectors, Singular Value Decomposition and Inner Product Spaces.

1. (Dimension.) A consistent system with rank $r$ in $n$ unknowns has $n - r$ free parameters. Derive that from rank-nullity rather than from elimination, and say what the null space is.
2. (Matrices.) Show that a system is uniquely solvable exactly when the coefficient matrix is invertible, and that this is equivalent to a non-zero determinant and to full rank. Three statements, one fact.
3. (LU.) Carry out elimination on a $3\times3$ matrix and read the multipliers off into $L$. Verify $A = LU$ by multiplication, and explain why $U$ has the pivots on its diagonal.
4. (Eigenvalues.) Show that the eigenvalues of a triangular matrix are its diagonal entries, and explain why that makes reduction to triangular form the standard route to eigenvalues.
5. (Inner products.) Derive the normal equations $A^TAx = A^Tb$ from the geometry: the residual $b - Ax$ must be orthogonal to the column space. Then explain why orthogonality, rather than “as close as possible”, is the real condition.
6. (Numerical analysis.) Construct a $2\times2$ system where elimination without pivoting produces a wildly wrong answer, and show that partial pivoting fixes it. One small pivot is enough.

• Matrices: The coefficient matrix of a linear system determines its solvability via rank and determinant.
• Linear Transformations: A system $A\mathbf{x} = \mathbf{b}$ can be viewed as finding the preimage of $\mathbf{b}$ under the linear transformation defined by $A$.
• Singular Value Decomposition: The pseudoinverse derived from the SVD provides the minimum-norm least squares solution to inconsistent systems.

• Quantum Mechanics
• Graph Theory

• Eigenvalues and Eigenvectors
• Inner Product Spaces
• Linear Independence, Span, Basis, and Dimension
• Matrices