Systems of Linear Equations and Gaussian Elimination

Matrix form

A system of $m$ linear equations in $n$ unknowns is $A\mathbf x = \mathbf b$ with $A \in \mathbb R^{m\times n}$. The augmented matrix $[A \mid \mathbf b]$ carries all the information.

Geometrically, each equation in $\mathbb R^3$ is a plane; the solution set is their intersection. Column view: $\mathbf b$ must be a combination of the columns of $A$.

Elementary row operations

1. Swap two rows.
2. Multiply a row by a non-zero scalar.
3. Add a multiple of one row to another.

They do not change the solution set (each is reversible), the row space, the null space or the rank. Each corresponds to left-multiplication by an invertible elementary matrix.

Echelon forms

Row echelon form (REF): all zero rows at the bottom; each row's leading entry (pivot) is to the right of the pivot above it; entries below each pivot are zero.

Reduced row echelon form (RREF): additionally, every pivot is 1 and is the only non-zero entry in its column. RREF is unique; REF is not.

$$\text{REF: }\begin{pmatrix}\boxed{2} & 1 & -1 & 3\\ 0 & \boxed{3} & 2 & 1\\ 0 & 0 & 0 & \boxed{5}\end{pmatrix} \qquad \text{RREF: }\begin{pmatrix}1 & 0 & * & 0\\ 0 & 1 & * & 0\\ 0 & 0 & 0 & 1\end{pmatrix}$$

The number of pivots is the rank. Columns with pivots correspond to basic variables; the rest are free variables.

Gaussian elimination

1. Forward elimination: for each column, pick a pivot, and subtract multiples of the pivot row to create zeros below it.
2. Back substitution: solve the triangular system from the last equation upwards.

Gauss–Jordan continues to RREF, eliminating above the pivots too, so the solution can be read off directly.

Pivoting and stability

A zero (or tiny) pivot forces a row swap. Partial pivoting — choosing the entry of largest absolute value in the column as the pivot — keeps multipliers bounded by 1 and controls round-off error. In matrix terms this gives $PA = LU$ (see LU and SVD).

Cost: about $\frac{2}{3}n^3$ flops for elimination and $n^2$ for each triangular solve.

When does a solution exist? (Rouché–Capelli)

Let $r = \operatorname{rank}(A)$ and $r' = \operatorname{rank}([A\mid\mathbf b])$, with $n$ unknowns.

For a square system, a unique solution exists for every $\mathbf b$ iff $\det A \ne 0$ iff $A$ is invertible.

Homogeneous systems

$A\mathbf x = \mathbf 0$ is always consistent ($\mathbf x = \mathbf 0$). Non-trivial solutions exist iff $\operatorname{rank}(A) < n$ — in particular whenever there are more unknowns than equations, or when $A$ is square with $\det A = 0$. The solution set is the null space, of dimension $n - \operatorname{rank}(A)$.

Structure of all solutions: if $\mathbf x_p$ is any particular solution of $A\mathbf x = \mathbf b$, then every solution is $\mathbf x_p + \mathbf x_h$ with $\mathbf x_h$ in the null space. The solution set is a translated subspace (an affine set), never a subspace unless $\mathbf b = \mathbf 0$.

Cramer's rule

For a square system with $\det A \ne 0$: $x_i = \dfrac{\det A_i}{\det A}$, where $A_i$ is $A$ with column $i$ replaced by $\mathbf b$. Elegant for $2\times 2$ and $3\times 3$ problems, impractical for large ones.

Computing the inverse

Row-reduce $[A \mid I] \to [I \mid A^{-1}]$. If a zero row appears on the left, $A$ is singular. In numerical work you almost never form $A^{-1}$ explicitly — solving $A\mathbf x = \mathbf b$ by elimination or LU is cheaper and more accurate.

Over- and under-determined systems in data science

• More equations than unknowns ($m > n$, e.g. regression with many data points): usually inconsistent; we find the least-squares solution $\hat{\mathbf x} = (A^\top A)^{-1}A^\top\mathbf b$ — see projections.
• Fewer equations than unknowns: infinitely many solutions; the minimum-norm one is $A^+\mathbf b$ via the pseudo-inverse (see SVD).

Quick revision