System of Linear Equations

A system of linear equations is a collection of equations involving the same unknowns, each appearing only in a first-degree term with a fixed coefficient. A solution assigns values to all unknowns so that every equation holds simultaneously. Such systems are fundamental objects of linear algebra, connecting algebraic calculation with the structure of matrices and vector spaces. They may have no solution, exactly one solution, or multiple solutions, depending on their coefficients and right-hand sides. (web.mit.edu)

Definition and matrix notation

A system of $m$ linear equations in $n$ unknowns has the form

The coefficients $a_{ij}$ and constants $b_i$ are specified; the values $x_j$ are sought. Typically these quantities are real numbers or complex numbers, although the algebraic theory applies over any field. Products between unknowns, such as $x_1x_2$, and powers such as $x_1^2$, are excluded.

Using a matrix, the system becomes

where $A$ is the $m\times n$ coefficient matrix, $x$ is the column of unknowns, and $b$ is the right-hand-side column. The augmented matrix $[A\mid b]$ records both coefficients and constants. This notation separates the system’s structure from its particular right-hand side and permits systematic elimination. (ocw.mit.edu)

For example,

has the solution $x=2,\ y=1$. Adding the equations gives $3x=6$, after which substitution determines $y$.

Geometric interpretation

In real two-dimensional geometry, a linear equation with at least one nonzero coefficient describes a line. Solving two such equations means finding their common points: intersecting lines yield one solution, distinct parallel lines yield none, and coincident lines yield infinitely many. In three dimensions, a nondegenerate equation describes a plane; several planes may intersect at a point, along a line, or in a larger common set. (ocw.mit.edu)

In $n$ dimensions, each nondegenerate equation defines a hyperplane. A complementary interpretation reads $Ax=b$ as a linear combination of the columns of $A$. A solution exists precisely when $b$ belongs to their span, called the column space. Equivalently, $b$ must lie in the image of the linear map represented by $A$. (web.mit.edu)

Consistency, rank, and solution structure

A system is consistent if it has at least one solution, and inconsistent otherwise. Its consistency is characterized by matrix rank:

If the common rank is $r$, there are $n-r$ free parameters. A consistent system has a unique solution when $r=n$. When $r<n$, it has infinitely many solutions over the real or complex numbers. Over a finite field with $q$ elements, it instead has $q^{n-r}$ solutions. (ocw.mit.edu)

A homogeneous system has $b=0$ and always admits the zero solution. Its solutions form a linear subspace of the ambient vector space, called the nullspace or kernel of $A$. The rank–nullity theorem gives its dimension as $n-r$. If $x_p$ is one solution of a nonhomogeneous system, every solution has the form

Thus a nonempty solution set is a translate of the nullspace, an affine space rather than necessarily a subspace. (web.mit.edu)

Systems with more equations than unknowns are overdetermined, while those with fewer are underdetermined. These labels alone do not establish consistency: redundant equations can make an overdetermined system consistent, while contradictory equations can make an underdetermined system inconsistent. (ocw.mit.edu)

Exact solution methods

Gaussian elimination transforms the augmented matrix using three solution-preserving operations: exchanging rows, multiplying a row by a nonzero scalar, and adding a multiple of one row to another. Echelon form exposes pivot variables and free variables; back substitution then recovers the solutions. Continuing to reduced row-echelon form makes their parameterization explicit. A row expressing $0=c$, with $c\ne0$, establishes inconsistency. (ocw.mit.edu)

For a square matrix, a unique solution for every right-hand side exists exactly when $A$ is invertible, equivalently when its determinant is nonzero. The formula $x=A^{-1}b$ uses the inverse matrix, but numerical solvers usually factor $A$ instead of explicitly forming its inverse. LU factorization, with row permutations when required, reduces the calculation to triangular systems and allows the factors to be reused for different right-hand sides. (ocw.mit.edu)

Numerical computation and approximation

Numerical linear algebra distinguishes mathematical solvability from computational accuracy. Floating-point arithmetic introduces rounding errors. An ill-conditioned system can amplify small perturbations in its data, so a small residual $b-A\hat{x}$ does not necessarily imply that the computed vector $\hat{x}$ is close to the exact solution. Condition estimates and backward-error analysis quantify different aspects of this uncertainty. (netlib.org)

Large systems involving a sparse matrix often use iterative methods that repeatedly improve an approximation without storing dense factors. Their effectiveness depends on matrix structure and convergence properties. (netlib.org)

When no exact solution exists, a least-squares formulation minimizes

This is central to ordinary least squares. Full column rank guarantees a unique minimizer. Orthogonal factorizations and singular value decomposition provide computational approaches, including rank-deficient cases. For a consistent underdetermined system, an additional minimum-norm criterion selects one solution from the family of exact solutions. (netlib.org)