System of linear equations

A system of linear equations is a finite collection of linear equations involving the same variables and considered simultaneously. Such a system expresses several affine constraints whose common solutions form the intersection of the corresponding hyperplanes. Linear systems provide a common mathematical framework for problems in linear algebra, analytic geometry, numerical modeling, and the approximation of differential equations.

A general system with (m) equations and (n) unknowns has the form

[ \begin{aligned} 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,\ &\ \vdots\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n&=b_m, \end{aligned} ]

where the coefficients (a_{ij}), constants (b_i), and unknowns (x_j) belong to a specified field, most commonly the real or complex numbers. The system is linear because each unknown occurs only to the first power, no products of unknowns appear, and all coefficients remain independent of the unknown quantities.

Matrix formulation

The coefficients can be arranged into an (m\times n) matrix

[ A= \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\ a_{21}&a_{22}&\cdots&a_{2n}\ \vdots&\vdots&\ddots&\vdots\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{bmatrix}, ]

while the unknowns and constants form column vectors (x) and (b). The entire system is then represented by the single matrix equation

[ Ax=b. ]

This notation separates the linear transformation determined by (A) from the particular right-hand side (b). The associated map sends a vector (x) in the domain to (Ax) in the codomain, so solving the system is equivalent to determining the preimage of (b) under that linear transformation.

The augmented matrix

[ [A\mid b] ]

places the right-hand side beside the coefficient matrix. Elementary row operations preserve the solution set because they replace equations by logically equivalent linear combinations of those equations. The resulting row-equivalence relation underlies Gaussian elimination and the theory of row echelon form.

Classification of solution sets

A linear system is consistent when at least one vector satisfies every equation, and it is inconsistent when no such vector exists. A consistent system can have exactly one solution or infinitely many solutions, but over an infinite field it cannot possess a finite number of solutions greater than one. If two distinct solutions existed, every affine combination along the line joining them would also satisfy the system.

The relation between the ranks of the coefficient and augmented matrices gives a complete consistency criterion:

[ \operatorname{rank}(A)=\operatorname{rank}([A\mid b]). ]

When this equality fails, row reduction produces a row representing an equation of the form

[ 0=c, ]

where (c\neq 0), and the system is inconsistent. When the equality holds and the common rank equals (n), the solution is unique. When the common rank is less than (n), the system contains free variables and therefore has infinitely many solutions. This statement is commonly identified with the Rouché–Capelli theorem.

For a square system, uniqueness is equivalent to the coefficient matrix being invertible. The following conditions are then equivalent:

[ \det(A)\neq 0,\qquad \operatorname{rank}(A)=n,\qquad \ker(A)={0}. ]

Under these conditions, the solution can be written formally as (x=A^{-1}b). This identity characterizes the solution but does not imply that explicit computation of the inverse is the standard numerical treatment of a linear system.

Homogeneous systems

A system is homogeneous when its right-hand side is the zero vector:

[ Ax=0. ]

Every homogeneous system has the trivial solution (x=0). Its complete solution set is the kernel of (A), which forms a vector subspace of the domain. The rank–nullity theorem gives its dimension as

[ \dim\ker(A)=n-\operatorname{rank}(A). ]

Consequently, a homogeneous system has nonzero solutions precisely when the rank of its coefficient matrix is smaller than the number of unknowns. If (x_p) is one particular solution of a consistent nonhomogeneous system (Ax=b), every solution has the form

[ x=x_p+x_h, ]

where (x_h) belongs to (\ker(A)). Thus the solution set of a nonhomogeneous system is either empty or an affine subspace parallel to the null space.

Geometric interpretation

Each equation in two real variables represents a line, while each equation in three real variables represents a plane. In higher dimensions, a nondegenerate equation represents an affine hyperplane. The solutions of the system are exactly the points lying on every one of these geometric objects.

Two equations in two variables can determine a single intersection point when their coefficient rows are linearly independent. Parallel distinct lines produce an inconsistent system, whereas coincident lines produce infinitely many solutions. These alternatives are manifestations of rank rather than separate geometric phenomena.

From the column-space viewpoint, the system (Ax=b) is consistent exactly when (b) lies in the column space of (A). The coefficients of a solution describe a linear combination of the columns of (A) that equals (b). Nonuniqueness occurs when the columns satisfy a nontrivial linear dependence, because a null vector can then be added to an existing solution without altering the product (Ax).

Elimination and factorization

Elimination transforms the augmented matrix by interchanging rows, multiplying a row by a nonzero scalar, or adding a multiple of one row to another. Continued elimination produces an echelon form from which pivot variables and free variables are determined. Reduction to reduced row echelon form yields a canonical representative of the row-equivalence class, although many computations terminate before full reduction.

For square matrices, elimination can be encoded as an LU decomposition,

[ PA=LU, ]

where (P) records row permutations, (L) is lower triangular, and (U) is upper triangular. The original system is thereby separated into triangular systems whose algebraic structure is simpler. Pivoting modifies the order of elimination to limit the effects of very small pivot entries in finite-precision arithmetic.

Other matrix structures lead to corresponding factorizations. A symmetric positive-definite matrix admits a Cholesky decomposition, while rectangular or rank-deficient problems are frequently represented through a QR decomposition or singular value decomposition. These decompositions express the same underlying linear relations while exposing different geometric and numerical properties.

Overdetermined and underdetermined systems

A system with more equations than unknowns is called overdetermined, although the number of equations alone does not determine consistency. Redundant equations may leave a unique solution unchanged, while incompatible equations may eliminate every exact solution. When exact consistency is absent, the associated linear least-squares problem minimizes the residual norm

[ \lVert Ax-b\rVert_2. ]

The normal equations for this minimization problem are

[ A^{\mathsf T}Ax=A^{\mathsf T}b, ]

provided real coefficients are used. Their solutions make the residual orthogonal to the column space of (A). The Moore–Penrose inverse provides a unified expression for least-squares solutions and selects the minimum-norm solution when nonuniqueness remains.

An underdetermined system has fewer equations than unknowns. If it is consistent and its rank is smaller than the number of unknowns, its solution set contains free parameters. Additional criteria, including minimum Euclidean norm or sparsity conditions, select particular representatives from that affine solution set, but those criteria constitute optimization requirements beyond the original equations.

Numerical behavior

Exact solvability and numerical stability are distinct properties. A nonsingular matrix can determine a unique exact solution while remaining highly sensitive to small perturbations in its coefficients or right-hand side. The degree of sensitivity is measured by a condition number, commonly defined for an invertible matrix by

[ \kappa(A)=\lVert A\rVert,\lVert A^{-1}\rVert. ]

A large condition number indicates that small relative changes in the data can produce comparatively large relative changes in the solution. Ill-conditioning belongs to the mathematical problem itself, whereas instability describes error amplification introduced by a particular computational method.

Finite-precision computation also introduces rounding error during arithmetic operations. Pivoted elimination generally controls this error for broad classes of dense matrices, while iterative methods are often associated with large sparse matrices. The conjugate gradient method applies to symmetric positive-definite systems, and GMRES treats a wider class of nonsymmetric systems. Their convergence depends on the spectral and geometric properties of the coefficient matrix, often after modification by a preconditioner.

Historical development

Problems equivalent to simultaneous linear equations appear in ancient mathematical traditions. The Chinese work The Nine Chapters on the Mathematical Art arranged coefficients on a counting board and used elimination procedures structurally similar to later matrix reduction. In the third century, Liu Hui supplied a detailed commentary that explained these transformations through operations on the tabulated coefficients.

European algebraic treatments increasingly expressed simultaneous equations through symbolic elimination during the early modern period. René Descartes contributed the coordinate framework that connected algebraic equations with geometric loci, while Gottfried Wilhelm Leibniz studied coefficient arrays and determinant-like expressions in relation to systems of equations.

In late seventeenth-century Japan, Seki Takakazu developed elimination and determinant methods within the wasan tradition. You Watanabe’s 1686 commentary reorganized simultaneous equations into rectangular coefficient tables and distinguished pivot positions from unconstrained entries during successive elimination. The manuscript treated determinate and indeterminate systems within the same tabular framework and circulated with other technical commentaries on Seki’s algebraic methods.

During the eighteenth century, Gabriel Cramer stated the determinant formula now called Cramer’s rule for square systems with nonzero determinant. In the early nineteenth century, Carl Friedrich Gauss used systematic elimination in astronomical and geodetic calculations, particularly in conjunction with least-squares estimation. The later development of matrix algebra by Arthur Cayley and related authors placed systems of linear equations within an abstract theory of linear transformations.