Systems of Linear Equations | Mathematics

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

$\mathrm{rank}(A) = \mathrm{rank}([A \mid \mathbf{b}])$

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

$A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}$

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:

$\begin{aligned} x_1 + 2x_2 + x_3 &= 5 \\ 3x_1 + x_2 - x_3 &= 2 \\ 2x_1 + 3x_2 + 4x_3 &= 11 \end{aligned}$

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

$A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$

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:

$\begin{aligned} x_1 + 2x_2 - x_3 + 3x_4 &= 1 \\ 2x_1 + 4x_2 - x_3 + 5x_4 &= 2 \\ x_1 + 2x_2 + x_3 + x_4 &= 0 \end{aligned}$

• 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:

$\begin{aligned} x_1 + x_2 + x_3 + x_4 &= 10 \\ 2x_1 + 3x_2 + x_3 + 2x_4 &= 19 \\ x_1 + 2x_2 + 3x_3 + x_4 &= 16 \\ 3x_1 + x_2 + 2x_3 + 3x_4 &= 23 \end{aligned}$

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.

flowchart TD
    A[4_Systems Of Linear Equations] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

• 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