Systems of Linear Equations

Definition

A system of linear equations is a collection of $m$ equations in $n$ unknowns $x_1,\dots ,x_n$:

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n& =b_1,\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n& =b_2,\\ & ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n& =b_m.\end{array}$$

Intuition

Each equation defines a hyperplane in ${\mathbb{R}}^n$; the solution set is the intersection of all those hyperplanes. The system either has no solution (planes don’t all meet), exactly one solution (planes meet at a point), or infinitely many (planes overlap along a line or subspace) — the rank of $\mathrm{A}$ determines which case holds.

Formal Description

In matrix form, the system is written as $\mathrm{Ax}=\mathrm{b}$, where $\mathrm{A}\in {\mathbb{R}}^{\mathrm{m}\times \mathrm{n}}$ is the coefficient matrix, $\mathrm{x}\in {\mathbb{R}}^{\mathrm{n}}$ is the vector of unknowns, and $\mathrm{b}\in {\mathbb{R}}^{\mathrm{m}}$ is the right-hand side vector.

Existence and uniqueness of solutions depends on the rank of $\mathrm{A}$ and the augmented matrix $[\mathrm{A}\mid \mathrm{b}]$:

• No solution (inconsistent): $\mathrm{rank}(\mathrm{A})<\mathrm{rank}([\mathrm{A}\mid \mathrm{b}])$.
• Unique solution: $\mathrm{rank}(\mathrm{A})=\mathrm{rank}([\mathrm{A}\mid \mathrm{b}])=\mathrm{n}$.
• Infinitely many solutions: $\mathrm{rank}(\mathrm{A})=\mathrm{rank}([\mathrm{A}\mid \mathrm{b}])<\mathrm{n}$.

For a square system ($m=n$), a unique solution exists if and only if $\mathrm{A}$ is invertible (i.e., $\det (\mathrm{A})\ne 0$), in which case $\mathrm{x}={\mathrm{A}}^{-1}\mathrm{b}$.

Applications

• Foundation of virtually every quantitative field: physics, engineering, data fitting, and optimisation all reduce to solving $\mathrm{Ax}=\mathrm{b}$.
• Underpins LU Decomposition and Computing Inverses.

Trade-offs

• Consistency must be checked before assuming a solution exists; blind application of a solver may silently return a least-squares approximation rather than an exact solution.
• Direct inversion ($\mathrm{x}={\mathrm{A}}^{-1}\mathrm{b}$) is numerically inferior to factorisation-based methods for large $n$.
• Rank determination is sensitive to floating-point errors; a numerically small pivot may reflect near-singularity.

Links

• Gaussian Elimination
• LU Decomposition
• Computing Inverses