Fact-checked by Grok 2 weeks ago

System of linear equations

A system of linear equations consists of two or more linear equations that share the same variables, where each equation is expressed in the form a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b, with coefficients a_i, variables x_i, and a constant b.^[1]^[2] A solution to the system is a set of values for the variables that simultaneously satisfies every equation in the collection.^[3] Such systems arise naturally in mathematical modeling and are fundamental to linear algebra, with solutions existing if the system is consistent, potentially unique, infinite, or none depending on the equations' relationships.^[4] Systems of linear equations can be compactly represented using matrix notation, where the coefficients form a matrix A, the variables a vector \mathbf{x}, and the constants a vector \mathbf{b}, yielding the equation A\mathbf{x} = \mathbf{b}.^[5] This matrix form facilitates computational solutions and reveals geometric interpretations, such as the intersection of hyperplanes in n-dimensional space.^[6] The study of these systems dates back over 4,000 years, with early methods for solving small systems appearing in Babylonian clay tablets around 2000 BCE and more systematic approaches in Chinese mathematics by 200 BCE, as documented in The Nine Chapters on the Mathematical Art.^[5]^[7] Solving methods for systems of linear equations include direct techniques like Gaussian elimination, which transforms the augmented matrix into row echelon form for back-substitution, and substitution or elimination for smaller systems.^[8]^[9] For larger or sparse systems, iterative methods such as Jacobi or Gauss-Seidel are employed, especially in numerical applications.^[10] These approaches ensure efficient computation, with Gaussian elimination attributed to Carl Friedrich Gauss in the early 19th century, though precursors existed in ancient texts.^[9] In practice, systems of linear equations model diverse real-world phenomena, including electrical circuit analysis, economic input-output models, and chemical reaction balances.^[6] For instance, in engineering, they solve for forces in truss structures or optimize resource allocation in operations research.^[11] Their ubiquity underscores their role as a cornerstone of applied mathematics, enabling precise predictions and optimizations across sciences.

Basic Concepts

Definition

A linear equation in n variables x_1, x_2, \dots, x_n is an equation that can be expressed in the form

a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b,

where the coefficients a_1, a_2, \dots, a_n and the constant term b are real numbers, and not all coefficients a_i are zero.^[12] This form represents a first-degree polynomial equation in the variables, with each term being either a constant or the product of a constant and a single variable raised to the first power.^[13] A system of linear equations is a collection of one or more linear equations involving the same set of variables, where the goal is typically to find values of the variables that satisfy all equations simultaneously.^[4] The variables serve as unknowns, while the coefficients and constants are given real numbers, assuming familiarity with basic algebraic operations over the real numbers without prior knowledge of advanced structures like matrices.^[14] In standard notation, the scalar form introduced here uses lowercase letters for variables and subscripts for coefficients, with boldface reserved for vector or matrix representations in subsequent discussions.^[15]

Elementary Examples

A system of linear equations can consist of a single equation, which is considered a trivial case. For instance, the equation x = 5 in one variable has a unique solution, x = 5, as it directly specifies the value of the variable.^[2] A simple nontrivial example involves two equations in two variables, such as

\begin{cases} x + y = 3 \\ 2x - y = 0 \end{cases}

To solve this using substitution, first isolate one variable from the second equation: y = 2x. Substitute into the first equation: x + 2x = 3, which simplifies to $3x = 3, so x = 1. Then, y = 2(1) = 2. The unique solution is x = 1, y = 2.^[16] In small-scale systems, the number of equations relative to variables affects the solutions. An underdetermined system, like one equation in two variables such as x + y = 3, has infinitely many solutions, parameterized as y = 3 - x for any x.^[17] Conversely, an overdetermined system, like two equations in one variable such as x = 1 and x = 2, has no solution due to the contradiction.^[17]

Mathematical Representation

General Form

A system of m linear equations in n variables x_1, x_2, \dots, x_n over a field, typically the real numbers \mathbb{R} or complex numbers \mathbb{C}, takes the general form

\begin{align*} a_{11} x_1 + a_{12} x_2 + \dots + a_{1n} x_n &= b_1 \\ a_{21} x_1 + a_{22} x_2 + \dots + a_{2n} x_n &= b_2 \\ &\vdots \\ a_{m1} x_1 + a_{m2} x_2 + \dots + a_{mn} x_n &= b_m, \end{align*}

where the a_{ij} (for i = 1, \dots, m and j = 1, \dots, n) are the coefficients belonging to the field, and the b_i (for i = 1, \dots, m) are the constant terms also in the field.^[1] This representation generalizes the elementary cases of two or three equations to arbitrary dimensions, allowing for overdetermined (m > n), underdetermined (m < n), or square (m = n) systems, with solutions sought in the field's vector space.^[18] To facilitate analysis, the system can be compactly represented using the augmented coefficient matrix [A \mid b], formed by juxtaposing the m \times n coefficient matrix A = (a_{ij}) with the m \times 1 column vector b = (b_i):

[A \mid b] = \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} & \mid & b_1 \\ a_{21} & a_{22} & \dots & a_{2n} & \mid & b_2 \\ \vdots & \vdots & \ddots & \vdots & \mid & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} & \mid & b_m \end{pmatrix}.

This matrix encodes the entire system without altering its solution set, serving as a foundational tool for further manipulations, though row operations to solve it are addressed elsewhere.^[19] The focus here remains on finite systems, as infinite systems of linear equations, which arise in functional analysis or infinite-dimensional spaces, fall outside this scope.^[18] The study of such systems traces back to ancient civilizations, notably the Babylonians around 1800 BCE, who inscribed practical problems leading to simultaneous linear equations on clay tablets, often involving ratios in trade, agriculture, or geometry, and solved them using methods akin to substitution.^[9] These early tablet-based approaches demonstrate an intuitive grasp of balancing equations for real-world applications, predating formal algebraic notation by millennia.^[20]

Vector and Matrix Forms

A system of linear equations can be expressed in a compact vector and matrix form, transforming the expanded scalar equations into a single matrix equation \mathbf{Ax} = \mathbf{b}. Here, \mathbf{A} is the coefficient matrix whose entries are the coefficients of the variables from the original system, \mathbf{x} is the column vector containing the unknown variables, and \mathbf{b} is the column vector of constant terms.^[21] This notation assumes the general form of the system, where each equation is a linear combination of variables equal to a constant.^[22] The structure of the coefficient matrix \mathbf{A}, which is m \times n for a system of m equations in n variables, organizes the coefficients such that each row corresponds to the coefficients of one equation, and each column corresponds to the coefficients of one variable across all equations.^[23] The vector \mathbf{x} is n \times 1, listing the variables x_1, x_2, \dots, x_n, while \mathbf{b} is m \times 1, listing the constants b_1, b_2, \dots, b_m. The equation \mathbf{Ax} = \mathbf{b} is defined through standard matrix-vector multiplication, where the i-th entry of \mathbf{Ax} equals the i-th entry of \mathbf{b}./02%3A_Matrix_Arithmetic/2.04%3A_Vector_Solutions_to_Linear_Systems) For illustration, consider a system of two equations in two variables:

\begin{align*} 2x_1 + 3x_2 &= 5, \\ 4x_1 + x_2 &= 3. \end{align*}

In matrix form, this becomes

\begin{pmatrix} 2 & 3 \\ 4 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 5 \\ 3 \end{pmatrix}.

The first row of \mathbf{A} captures the coefficients 2 and 3 from the first equation, the second row captures 4 and 1 from the second, the first column relates to x_1, and the second to x_2.^[24] This vector and matrix representation offers advantages in algebraic manipulation, as it condenses multiple equations into one, enabling unified operations on the system, and enhances computational efficiency when implemented in algorithms or software for handling larger systems.^[25] It presupposes an understanding of matrix multiplication, which directly corresponds to the linear combinations in the general scalar form of the equations.^[21]

Solution Sets

Geometric Interpretation

In two dimensions, each linear equation in two variables represents a straight line in the plane. The solution to a system of such equations corresponds to the intersection points of these lines: a unique solution occurs when the lines intersect at a single point, infinitely many solutions arise when the lines are coincident (overlapping completely), and no solution exists when the lines are parallel and distinct.^[26] Extending to three dimensions, each linear equation defines a plane in space. The solution set for a system is the common intersection of these planes, which may result in a single point (unique solution), a line (infinitely many solutions along that line), or no intersection at all if the planes do not meet.^[27] In higher dimensions, this geometric view generalizes to hyperplanes, where each equation specifies an (n-1)-dimensional hyperplane in n-dimensional space. The solution set of the system is the intersection of these hyperplanes, forming an affine subspace whose dimension depends on the dependencies among the equations; for instance, consistent systems yield intersections ranging from a point to higher-dimensional flats.^[28] This parametric representation aligns with the vector form of solutions, depicting the set as a translate of the null space of the coefficient matrix.^[27]

Classification of Solutions

The solutions to a system of linear equations Ax = b, where A is an m \times n matrix over a field such as the real numbers, can be classified into three categories based on the ranks of the coefficient matrix A and the augmented matrix [A \mid b]. A system has no solution if the rank of A is strictly less than the rank of [A \mid b], indicating inconsistency because the right-hand side b introduces additional linear independence not present in the rows of A. The system has a unique solution if the rank of A equals the rank of [A \mid b] and both equal n (the number of variables), meaning A has full column rank and the system is determined. It has infinitely many solutions if the rank of A equals the rank of [A \mid b] but is less than n, corresponding to an underdetermined system where the solution set forms an affine subspace of dimension n - r, with r the common rank. This classification is formalized by the Rouché–Capelli theorem, which states that a system Ax = b is consistent (has at least one solution) if and only if \operatorname{rank}(A) = \operatorname{rank}([A \mid b]), and the dimension of the solution set is then n - \operatorname{rank}(A). A brief proof sketch relies on row reduction: performing Gaussian elimination on [A \mid b] yields a row echelon form where the number of nonzero rows gives \operatorname{rank}([A \mid b]). If this rank exceeds \operatorname{rank}(A) (computed similarly from A alone), a row with zeros in the coefficient part but nonzero in the augmented part signals inconsistency. Otherwise, back-substitution reveals either a unique solution (when there are n pivots) or free variables leading to infinitely many solutions (fewer than n pivots). Determining this classification computationally is polynomial-time efficient over the reals or rationals, as Gaussian elimination computes the ranks in O(n^3) arithmetic operations in the worst case for square systems, though more refined analyses yield O(mn \min(m,n)) for general m \times n matrices.

Key Properties

Linear Independence

In the context of a system of linear equations represented by the matrix equation Ax = b, where A is an m \times n matrix, the linear independence of the rows or columns of A plays a fundamental role in determining the structure of the solution set. A set of vectors, such as the rows or columns of A, is linearly independent if the only solution to the equation c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \dots + c_k \mathbf{v}_k = \mathbf{0} is the trivial solution where all coefficients c_i = 0, meaning no nontrivial linear combination yields the zero vector.^[29] This property ensures that none of the vectors can be expressed as a linear combination of the others.^[30] For the rows of A, which correspond to the individual equations in the system, linear independence implies that there are no redundant equations; each equation provides unique information not derivable from the others. Similarly, linear independence of the columns of A reflects the independence among the variables' coefficients. If the rows (or columns) are fully linearly independent—meaning the rank of A equals the minimum of m and n—this structural property supports the potential for a unique solution in square systems or constrains the solution space in rectangular ones.^[31] In particular, for a square n \times n matrix A, the columns are linearly independent if and only if the determinant of A is nonzero, as a zero determinant indicates a nontrivial solution to Ax = 0.^[32] Consider a $2 \times 2 system with coefficient matrix A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}. The columns \begin{pmatrix} a \\ c \end{pmatrix} and \begin{pmatrix} b \\ d \end{pmatrix} are linearly independent precisely when \det(A) = ad - bc \neq 0, ensuring the homogeneous system Ax = 0 has only the trivial solution and the original system has a unique solution for any b.^[33] This example illustrates how linear independence directly ties to solvability. Linear independence also connects to the concepts of basis and span in describing the solution space of the homogeneous system Ax = 0, whose solutions form the null space of A. A basis for the null space is a linearly independent set of vectors that spans the entire null space, and the dimension of this solution space (nullity) is n minus the dimension of the column space of A, where the column space dimension equals the number of linearly independent columns (the rank). Thus, greater independence among the columns reduces the dimension of the solution space, potentially to zero for full rank.^[34] The row space similarly has a basis consisting of linearly independent rows, spanning all linear combinations of the equations.^[35]

Consistency and Uniqueness

A system of linear equations Ax = b, where A is an m \times n matrix and b is an m-dimensional vector, is consistent if it possesses at least one solution. The necessary and sufficient condition for consistency is that the rank of the coefficient matrix A equals the rank of the augmented matrix [A \mid b], denoted as

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

This result, known as the Rouché–Capelli theorem, determines whether the vector b lies in the column space of A. If the ranks differ, the system is inconsistent and has no solutions./01%3A_Systems_of_Equations/1.05%3A_Rank_and_Homogeneous_Systems) For a consistent system, the solution is unique if and only if \operatorname{rank}(A) = n, where n is the number of variables. In this case, the columns of A are linearly independent, ensuring the solution set consists of exactly one point. If \operatorname{rank}(A) < n, the solution set is infinite, forming an affine subspace of dimension n - \operatorname{rank}(A). This full-rank condition on A serves as a prerequisite for uniqueness in consistent systems./01%3A_Systems_of_Equations/1.05%3A_Rank_and_Homogeneous_Systems) Two systems of linear equations are equivalent if they share the same solution set. Elementary row operations applied to the augmented matrix preserve this solution set, meaning that any system obtained via such operations is equivalent to the original. Consequently, two systems are equivalent if and only if their augmented matrices are row equivalent. In finite-dimensional spaces, the Fredholm alternative provides a foundational dichotomy for solvability: for the operator defined by A, either the homogeneous equation Ax = 0 has only the trivial solution (implying a unique solution for every b), or it has non-trivial solutions (implying solvability of Ax = b only when b is orthogonal to the left kernel of A, with infinitely many solutions otherwise). For consistent systems, solvability is guaranteed by the rank condition, aligning with this alternative.^[36]

Solution Methods

Gaussian Elimination

Gaussian elimination is a systematic algorithm for solving systems of linear equations by applying elementary row operations to the augmented matrix, transforming it into an upper triangular form known as row echelon form, followed by back-substitution to find the solution values. This method, attributed to Carl Friedrich Gauss for its popularization in solving linear systems during his work on least squares in the early 19th century, preserves the solution set of the original system throughout the process.^[37]^[38] The algorithm relies on three types of elementary row operations: (1) interchanging two rows, (2) multiplying all entries in a row by a nonzero scalar, and (3) adding a scalar multiple of one row to another row. These operations are reversible and correspond to multiplying the augmented matrix on the left by elementary matrices, ensuring equivalence to the original system./01%3A_Systems_of_Linear_Equations/1.03%3A_Elementary_Row_Operations_and_Gaussian_Elimination)^[39] The forward elimination phase proceeds column by column, starting from the left. For each pivot column k (where k = 1, 2, \dots, n for an n \times n system), the entry in row k, column k is used as the pivot if nonzero; otherwise, rows are swapped to find a nonzero pivot. Below the pivot, entries are eliminated by subtracting appropriate multiples of the pivot row from subsequent rows, resulting in zeros beneath each pivot and producing an upper triangular matrix. This step reduces the system to a form where each equation involves fewer variables.^[40]^[41] Once in row echelon form, back-substitution solves the system starting from the last equation, which involves only the last variable, and proceeds upward, substituting values into previous equations to solve sequentially for the remaining variables. If the system has no solution, inconsistencies like a row of zeros with a nonzero right-hand side appear during elimination; if infinite solutions exist, zero rows indicate underdetermined systems.^[37]^[40] Consider the 3×3 system:

\begin{cases} 2x + y - z = 8 \\ -3x - y + 2z = -11 \\ -2x + y + 2z = -3 \end{cases}

The augmented matrix is

\begin{pmatrix} 2 & 1 & -1 & | & 8 \\ -3 & -1 & 2 & | & -11 \\ -2 & 1 & 2 & | & -3 \end{pmatrix}.

First, normalize the first pivot by dividing row 1 by 2:

\begin{pmatrix} 1 & 1/2 & -1/2 & | & 4 \\ -3 & -1 & 2 & | & -11 \\ -2 & 1 & 2 & | & -3 \end{pmatrix}.

Eliminate below: add 3×row 1 to row 2 and 2×row 1 to row 3:

\begin{pmatrix} 1 & 1/2 & -1/2 & | & 4 \\ 0 & 1/2 & 1/2 & | & 1 \\ 0 & 2 & 1 & | & 5 \end{pmatrix}.

For column 2, multiply row 2 by 2:

\begin{pmatrix} 1 & 1/2 & -1/2 & | & 4 \\ 0 & 1 & 1 & | & 2 \\ 0 & 2 & 1 & | & 5 \end{pmatrix}.

Subtract 2×row 2 from row 3:

\begin{pmatrix} 1 & 1/2 & -1/2 & | & 4 \\ 0 & 1 & 1 & | & 2 \\ 0 & 0 & -1 & | & 1 \end{pmatrix}.

Multiply row 3 by -1:

\begin{pmatrix} 1 & 1/2 & -1/2 & | & 4 \\ 0 & 1 & 1 & | & 2 \\ 0 & 0 & 1 & | & -1 \end{pmatrix}.

Back-substitution yields z = -1, y = 2 - z = 3, x = 4 - (1/2)y + (1/2)z = 2. The solution is x=2, y=3, z=-1.^[42]^[40] Pivot positions are the locations of the leading nonzero entries in each nonzero row of the row echelon form, indicating the rank of the coefficient matrix and the number of basic variables. Columns without pivots correspond to free variables, which can take arbitrary values in underdetermined systems, parametrizing the solution set. Identifying pivots during elimination reveals the structure of the solution space.^[37]^[41] For numerical stability in floating-point arithmetic, partial pivoting is incorporated by selecting the row with the largest absolute value in the current column as the pivot row before elimination, minimizing error growth due to division by small pivots. This strategy ensures the algorithm is backward stable in most practical cases, though complete pivoting (both row and column swaps) may be used for greater robustness at higher computational cost.^[43]^[44]

Matrix-Based Solutions

One fundamental matrix-based approach to solving the system Ax = b, where A is an n \times n square matrix and b is a column vector, relies on the matrix inverse. If A is invertible, the unique solution is given by x = A^{-1} b.^[45] A square matrix A is invertible if and only if its determinant satisfies \det A \neq 0.-03:_Invertibility_bases_and_coordinate_systems/3.01:_Invertibility) This condition ensures that the linear transformation represented by A is bijective, mapping \mathbb{R}^n onto itself without collapse.^[46] For small matrices, the inverse can be explicitly computed using the adjugate (or classical adjoint) matrix, which is the transpose of the cofactor matrix of A. The formula is A^{-1} = \frac{1}{\det A} \adj A, where the cofactor C_{ij} of entry a_{ij} is (-1)^{i+j} times the determinant of the submatrix obtained by deleting row i and column j.^[47] This method is practical for n \leq 3 due to the recursive nature of cofactor computation, which grows factorially in complexity for larger n. For example, for a $2 \times 2 matrix A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, the adjugate is \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}, yielding A^{-1} = \frac{1}{ad - bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} provided ad - bc \neq 0.^[48] For larger systems, direct inversion is often avoided in favor of factorizations like LU decomposition, where A = LU with L lower triangular (unit diagonal) and U upper triangular. To solve Ax = b, first solve Ly = b for y via forward substitution (O(n^2) operations), then solve Ux = y via back substitution (also O(n^2)).^[49] The LU factorization itself requires O(n^3) operations, typically via Gaussian elimination without pivoting if A is strongly diagonally dominant.^[50] This approach is particularly efficient when solving multiple systems with the same A but different b, as the factorization is computed once and reused. Computationally, forming the explicit inverse A^{-1} demands O(n^3) floating-point operations, comparable to LU factorization, but it is generally less stable and more sensitive to rounding errors in finite precision arithmetic.^[51] For large n, factorizations like LU are preferred over inversion because they enable solving each additional system in O(n^2) time after the initial O(n^3) preprocessing, avoiding the full cost of inversion for repeated solves.^[51]

Determinant Methods

Determinant methods for solving systems of linear equations rely on computing ratios of determinants to find explicit formulas for the unknowns, applicable specifically to square systems with a unique solution. The origins of this approach trace back to Gottfried Wilhelm Leibniz, who in a 1693 letter to the Marquis de l'Hôpital outlined a technique for resolving systems of linear equations using what we now recognize as determinants, allowing solutions without direct computation of the full expansion but through proportional relations among coefficients.^[52] This early insight laid the groundwork for later formalizations, emphasizing the determinant's role in determining solvability. In 1750, Swiss mathematician Gabriel Cramer extended and systematized the method in his work Introduction à l'analyse des lignes courbes algébriques, providing a general rule for expressing each unknown as a ratio of determinants derived from the coefficient matrix.^[53] Cramer's rule states that for a system Ax = b, where A is an n \times n invertible matrix, x is the n \times 1 vector of unknowns, and b is the n \times 1 constant vector, the i-th component of the solution is given by

x_i = \frac{\det(A_i)}{\det(A)},

where A_i is the matrix obtained by replacing the i-th column of A with b. This formula leverages the properties of determinants to isolate each variable directly. To derive Cramer's rule for the $2 \times 2 case, consider the system

\begin{cases} a x + b y = e \\ c x + d y = f \end{cases},

with coefficient matrix A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} and determinant \det(A) = ad - bc. Solving explicitly via substitution, express x from the first equation: x = \frac{e - b y}{a} (assuming a \neq 0). Substitute into the second: c \left( \frac{e - b y}{a} \right) + d y = f. Multiply through by a: c(e - b y) + d a y = f a, which simplifies to c e - c b y + d a y = f a, or y (d a - c b) = f a - c e. Thus,

y = \frac{a f - c e}{a d - b c} = \frac{\det \begin{pmatrix} a & e \\ c & f \end{pmatrix}}{\det(A)},

where the numerator is the determinant of the matrix with the second column of A replaced by \begin{pmatrix} e \\ f \end{pmatrix}. Similarly, solving for x yields

x = \frac{e d - b f}{a d - b c} = \frac{\det \begin{pmatrix} e & b \\ f & d \end{pmatrix}}{\det(A)},

confirming the rule for n=2.^[54] The rule extends naturally to n \times n systems through the multilinearity and alternating properties of the determinant, which ensure that the solution components arise analogously from replacing columns and scaling by the overall determinant. For larger n, \det(A) and each \det(A_i) can be computed via cofactor expansion along a row or column, recursively reducing to smaller determinants until $1 \times 1 cases. This generalization maintains the explicit formula while relying on the determinant's geometric interpretation as a signed volume scaling factor, linking back to the system's invertibility condition \det(A) \neq 0, which equivalently implies linear independence of the columns.-11:_Appendices/04:_Determinants_and_Cramers_Rule_for_n_x_n_Matrices) Despite its theoretical elegance, Cramer's rule has significant limitations. It applies only to square systems where \det(A) \neq 0, precluding use for underdetermined, overdetermined, or singular cases. Computationally, evaluating n+1 determinants via naive cofactor expansion incurs O(n!) time complexity per determinant due to the recursive nature involving n! permutations in the Leibniz formula, rendering it impractical for n > 4 or $5 in most applications.^[55] Modern alternatives like Gaussian elimination achieve O(n^3) efficiency, but Cramer's rule remains valuable for theoretical proofs and small-scale explicit solutions.

Iterative and Other Approaches

Iterative methods offer approximate solutions to systems of linear equations through successive refinements, making them suitable for large, sparse matrices where direct methods may be computationally prohibitive due to storage and time requirements. These approaches typically start with an initial guess and update the solution vector until a convergence criterion is met, often leveraging matrix splittings to ensure stability and efficiency.^[56] The Jacobi iteration method decomposes the coefficient matrix A as A = D + E, where D is the diagonal part and E is the remainder, leading to the iteration x^{(k+1)} = D^{-1} (b - E x^{(k)}). Introduced by Carl Gustav Jacob Jacobi in 1845, this method is particularly effective for sparse systems and converges when A is strictly diagonally dominant, meaning the absolute value of each diagonal entry exceeds the sum of the absolute values of the off-diagonal entries in its row.^[10]^[56] The Gauss-Seidel method improves upon Jacobi by updating variables sequentially and using the most recent values within each iteration, formulated as solving for each component x_i^{(k+1)} from the i-th equation while substituting prior updates. First described by Carl Friedrich Gauss in a 1823 letter and published by Philipp Ludwig von Seidel in 1874, it also converges for strictly diagonally dominant matrices and typically requires fewer iterations than Jacobi for compatible systems, though it is not easily parallelizable.^[10]^[56] For systems where A is symmetric positive definite, the conjugate gradient method generates a sequence of conjugate directions to minimize the quadratic form associated with the error, converging in at most n steps for an n \times n matrix. Developed by Magnus R. Hestenes and Eduard Stiefel in 1952, this Krylov subspace method is widely used for its optimal convergence properties in finite precision, avoiding explicit matrix factorizations.^[57] Other approaches include graph-theoretic techniques, which model the sparsity of A as an undirected graph to guide ordering, partitioning, or preconditioning in iterative solvers, enhancing efficiency for structured sparse systems like those from finite element discretizations.^[56] Additionally, QR decomposition factors A = QR with orthogonal Q and upper triangular R, enabling solution via forward substitution after orthogonalization, as developed through Householder transformations in the late 1950s; it serves as a stable "other" method for dense or moderately sparse systems despite higher costs for very large scales.^[58] In engineering applications, such as circuit simulation, iterative methods like Gauss-Seidel address large sparse systems from modified nodal analysis by exploiting the hierarchical structure of voltages and currents, reducing computational demands in transient and frequency-domain analyses compared to direct solvers.^[59]

Homogeneous Systems

Characteristics

A homogeneous system of linear equations consists of a set of equations where the right-hand side is the zero vector, expressed in matrix form as Ax = 0, with A an m \times n coefficient matrix and x an n \times 1 vector of variables.^[60] This form arises naturally in contexts such as finding dependencies among vectors or equilibrium conditions in applied problems.^[61] Such a system always admits at least one solution, known as the trivial solution, where x = 0.^[62] Nontrivial solutions, where at least one component of x is nonzero, exist if and only if the determinant of A is zero when A is square, indicating linear dependence among the rows or columns of A.^[63] The set of all solutions to Ax = 0 forms the null space, or kernel, of the matrix A, denoted \ker(A) or Nul(A), which is a subspace of \mathbb{R}^n.^[64] The dimension of this null space, called the nullity of A, equals n - \rank(A), where \rank(A) is the rank of A, providing a measure of the "degrees of freedom" in the solution set.^[65] A basis for the kernel consists of a linearly independent set of vectors that spans the entire solution space, obtained by solving the system and identifying vectors corresponding to free variables.^[66]

Connection to General Systems

Homogeneous systems form the foundational component of solutions to more general, inhomogeneous linear systems of the form Ax = b, where A is an m \times n coefficient matrix and b \neq 0 is a nonzero constant vector. The general solution to such an inhomogeneous system, when consistent, is expressed as the sum of a particular solution x_p to the inhomogeneous equation and the general solution x_h to the corresponding homogeneous equation Ax = [0](/page/0): x = x_p + x_h. This decomposition arises from the linearity of the system, ensuring that if x_p satisfies Ax_p = b and x_h satisfies Ax_h = [0](/page/0), then A(x_p + x_h) = b. The linearity principle, known as the superposition principle, underpins this relationship by stating that for a linear system, the solution to a linear combination of inputs is the corresponding linear combination of the individual solutions. In the context of systems of equations, this means that the response to the sum of forcing terms (as in multiple inhomogeneous systems) equals the sum of the responses to each, allowing the homogeneous part to capture the "free" variations around any particular solution. This principle extends naturally from the properties of vector spaces and linear transformations. A prominent application of homogeneous systems appears in eigenvalue problems, where the equation Ax = \lambda x can be rewritten as (A - \lambda I)x = 0, forming a homogeneous system whose nontrivial solutions exist when \lambda is an eigenvalue of A. This formulation highlights how homogeneous systems model self-consistent scalings or invariances in linear transformations, with the solution space determining the eigenspace associated with each eigenvalue. For a consistent inhomogeneous system Ax = b, the solution set forms an affine subspace whose dimension equals the dimension of the solution space of the corresponding homogeneous system Ax = 0, which is the nullity of A (dimension of the null space). This equality follows from the rank-nullity theorem, as the solution set is a coset of the null space translated by a particular solution, preserving the geometric structure and degrees of freedom.

References

[1]
[PDF] Chapter 1 Systems of Linear Equations - San Jose State University
A system of linear equations is a collection of linear equations involving the same variables. A linear equation is of the form a1x1 + a2x2 + ... + anxn = b.
[2]
Systems of Linear Equations
A system of linear equations is a collection of several linear equations. A solution is a list of numbers that make all equations true simultaneously.
[3]
[PDF] 1 Linear Equations - UC Berkeley math
A system of linear equations is a collection of one or more linear equations. A solution of the system is a list of values that makes each equation a true ...
[4]
Systems of linear equations
A system of linear equations consists of two or more linear equations considered simultaneously. A system is consistent if there is at least one solution.
[5]
[PDF] A Brief History of Linear Algebra - University of Utah Math Dept.
Around 4000 years ago, the people of Babylon knew how to solve a simple 2X2 system of linear equations with two unknowns. Around 200 BC, the Chinese published ...
[6]
[PDF] Chapter II: Solving Systems of Linear Equations - Applied Mathematics
Where do systems of linear equations come up? Everywhere! They appear straightforwardly in analytic geometry (intersection of lines and planes),.
[7]
[PDF] Linear Equations 1.1. - Harvard Mathematics Department
The history of linear algebra is more than 4000 years old. Around 2000 BC, the. Babylonians solved single equations. From 250BC is the Archimedes cattle problem ...
[8]
[PDF] Chapter 1 Systems of Linear Equations
The method of Gaussian elimination with back substitution to solve sys- tem of linear equations can be refined by first further reducing the augmented matrix to ...<|control11|><|separator|>
[9]
[PDF] Mathematicians of Gaussian Elimination - CIS UPenn
Gaussian elimination is universally known as “the” method for solving simultaneous linear equations. As. Leonhard Euler remarked, it is the.
[10]
[PDF] Iterative methods for linear systems of equations: A brief historical ...
The journey begins with Gauss who developed the first known method that can be termed iterative. The early 20th century saw good progress of these methods which ...
[11]
Algebra - Applications of Linear Equations - Pauls Online Math Notes
Nov 16, 2022 · In this section we discuss a process for solving applications in general although we will focus only on linear equations here.
[12]
[PDF] LINEAR EQUATIONS Math 21b, O. Knill
A linear equation is ax+by=c (two variables) or ax+by+cz=d (three variables). A system of linear equations is a collection of such equations.
[13]
Introduction to Linear Systems of Equations - UTSA
Jan 20, 2022 · A linear equation is an equation in which each term is either a ... Such an equation is equivalent to equating a first-degree polynomial to zero.
[14]
Lecture 1 - Introduction to Linear Algebra
Definition. A system of linear equations (also called a "linear system") is a collection of one or more linear equations involving the same variables.
[15]
MFG Linear Equations
Second, a linear equation can have one variable or many: y=−5 y = − 5 is a linear equation in one variable, while y=4x y = 4 x is a linear equation in two ...
[16]
[PDF] Systems of Linear Equations; Matrices - Higher Education | Pearson
2x - y = 0. (B); no solution. 10. x + y = 3. 2x - y = 0. (D); x = 1, y = 2. 11 ... x - y = -3 x = 1, y = 4. 20. 3x - y = 7. 2x + 3y = 1 x = 2, y = -1. Solve ...<|control11|><|separator|>
[17]
[PDF] 11.1 Linear Systems
A linear system is a collection of linear equations involving the same variables. A solution makes all equations true. For example, 5x + 3y − 4z 15 4x − 8y + 5 ...
[18]
[PDF] System of linear equations
Mar 12, 2013 · Often the coefficients and unknowns are real or complex numbers, but integers and rational numbers are also seen, as are polynomials and.
[19]
8.2: Systems of Linear Equations- Augmented Matrices
Oct 2, 2022 · This matrix is called an augmented matrix because the column containing the constants is appended to the matrix containing the coefficients.Theorem 8.2. Row Operations · Definition 8.4. · Example 8.2.1
[20]
[PDF] Unit 2: Gauss-Jordan elimination - Harvard Mathematics Department
Systems of linear equations have already been tackled four thousand years ago by Babylonian mathematicians. 1 They were able to solve simple systems of ...
[21]
Matrix Equations
Four Ways of Writing a Linear System ; As a system of equations: M · 2 x 1 ; As a vector equation ( x 1 v 1 + x 2 v 2 + ··· + x n v n = b ):. x 1 K · 2 ; As a matrix ...
[22]
3.6 Systems of linear equations
2 Matrix form of a linear system. Every system of linear equations can be written in matrix form: the above system is equivalent to saying that A ⁢ x = b ...
[23]
[PDF] 7.1 Matrix Equation Form of a System
A system of m linear equations in n unknowns (note that m and n need not be equal) can be written as Ax = b where A is the m × n coefficient matrix of the ...
[24]
Representing Systems of Linear Equations using Matrices
A matrix is a set of numbers arranged in rows and columns, used to represent systems of linear equations. For example, the system of equations 2 x + 3 y = 5 ...
[25]
Matrix Equations - Ximera - The Ohio State University
Matrices and vectors can be used to rewrite systems of equations as a single equation, and there are advantages to doing this. 3.3The Superposition Principle.<|control11|><|separator|>
[26]
Systems of Linear Equations - Department of Mathematics at UTSA
Nov 14, 2021 · Simple nontrivial example. The simplest kind of nontrivial linear system involves two equations and two variables: 2 x + 3 y = 6 4 x + ...
[27]
[PDF] Part I: Geometry - APRIL robotics lab - University of Michigan
‣ A single linear equation yields a hyper-plane. ‣ N-1 simultaneous linear equations yields a line. Saturday, September 10, 11. Page 12. Checkpoint. • A point ...
[28]
[PDF] Summer Bootcamp: Linear Algebra - NC State ISE
Geometric Interpretation: Hyperplanes in Rn. Each linear equation in the system Ax = b represents a hyperplane in Rn. A hyperplane is an. (n − 1)-dimensional ...
[29]
[PDF] MULTILINEAR ALGEBRA 1.1 Background
Feb 1, 2011 · Linear independence. A collection of vectors, vi, i = 1,...,k, is linearly independent if the map. (1.1.1). R k → V , (c1,...,ck) → c1v1 + ...
[30]
[PDF] Math 2331 – Linear Algebra - 1.7 Linear Independence
Each linear dependence relation among the columns of A corresponds to a nontrivial solution to Ax = 0. The columns of matrix A are linearly independent if and ...
[31]
Linear Independence
E 2 3 0 F = 2 E 1 0 0 F + 3 E 0 1 0 F + 0 E 0 0 1 F , and the pivot columns are linearly independent: E 0 0 0 F = x 1 E 1 0 0 F + x 2 E 0 1 0 F + x 4 E 0 0 1 F ...
[32]
Testing for Linear Dependence of Vectors - Oregon State University
A set of n vectors of length n is linearly independent if the matrix with these vectors as columns has a non-zero determinant.
[33]
[PDF] Introduction to Linear Algebra, 5th Edition
Independence or dependence is the key point. The vectors go into the columns of an n by n matrix: Independent columns: Ax = 0 has one solution. A is an ...
[34]
Basis and Dimension
A basis of a subspace is a set of vectors that spans the subspace and is linearly independent. The dimension of a subspace is the number of vectors in any of ...
[35]
[PDF] Linear Independence, span, basis, dimension
The span of a set of vectors is the subspace of all their linear combinations. A basis spans and is linearly independent. A subspace's dimension is the number ...
[36]
A proof of the Fredholm alternative - Terry Tao
Apr 10, 2011 · In the finite-dimensional case, the Fredholm alternative is an immediate consequence of the rank-nullity theorem, and the finite rank case ...Missing: systems citation
[37]
[PDF] Gaussian Elimination - MIT OpenCourseWare
Oct 14, 2013 · These notes concern the most fundamental and elementary matrix computation: solving systems of linear equations. The ideas should be familiar to ...
[38]
[PDF] Meyer.pdf
Mar 4, 2018 · ... Gaussian elimination in honor of the German mathematician Carl Gauss,. 1 whose extensive use of it popularized the method. Because this ...<|control11|><|separator|>
[39]
[PDF] matrices and gauss-jordan - Harvard Mathematics Department
The elimination process consists of three possible steps which are called elementary row operations: Swap two rows. Scale a row. Subtract a multiple of a row ...
[40]
[PDF] Gaussian Elimination - Purdue Math
May 2, 2010 · 1. The process by which a matrix is brought via elemen- tary row operations to row-echelon form is known as. Gauss-Jordan elimination ...
[41]
[PDF] Gaussian elimination
Oct 2, 2019 · The procedure consists of a series of simple steps called elementary row operations, described in Definition 3.2 below. ... Gaussian elimination ...Missing: textbook | Show results with:textbook
[42]
[PDF] Gaussian elimination. Row echelon form. Gauss-Jordan reduction.
Gaussian elimination is a modification of the elimination method that allows only so-called elementary operations. Elementary operations for systems of linear ...
[43]
[PDF] Lecture 7 - Gaussian Elimination with Pivoting
Gaussian elimination with pivoting involves partial pivoting, which exchanges rows to avoid zero pivots, and uses the largest pivot for stability.
[44]
[PDF] A summary Partial pivoting - CS@Cornell
Gaussian elimination with partial pivoting is almost always backward stable in practice. There are some artificial examples where “pivot growth” breaks ...
[45]
The Inverse of a Matrix — Linear Algebra, Geometry, and Computation
Theorem. If A is an invertible n×n matrix, then for each b in Rn, the equation Ax=b has the unique solution A−1b.The Inverse Of A Matrix · Computing The Matrix Inverse · The Invertible Matrix...
[46]
[PDF] 2.5 Inverse Matrices - MIT Mathematics
To invert a 3 by 3 matrix A, we have to solve three systems of equations: Ax1 = e1 and. Ax2 = e2 = (0, 1, 0) and Ax3 = e3 = (0, 0, 1). Gauss-Jordan finds A−1 ...
[47]
[PDF] 3.2 Determinants and Matrix Inverses
One consequence of these theorems is that a square matrix A is invertible if and only if det A 6= 0. Moreover, determinants are used to give a formula for A−1 ...
[48]
Determinants, The Adjoint, and Inverses | Discover Linear Algebra
Matrix A is invertible. Every linear system that has A as a coefficient matrix has one unique solution. The homogeneous system Ax = 0 has only the trivial ...
[49]
LU Decomposition for Solving Linear Equations - CS 357
Knowing the LU decomposition for a matrix A allows us to solve the linear system A x = b using a combination of forward and back substitution. In equations this ...
[50]
[PDF] 7.2 Solving a System With An LU-Factorization
... LU where L is lower triangular and U is upper triangular. In that case, for a system Ax = b that we are trying to solve for x we have. Ax = b. ⇒. (LU)x = b.
[51]
[PDF] Golub and Van Loan - EE IIT Bombay
Matrix Anal. Applic. 11, 521-530. I.S. Dhillon (1998}. "Reliable Computation of the Condition Number of a Tridiagonal Matrix in O(n). Time," SIAM J. Matrix Anal ...
[52]
Matrices and determinants - MacTutor History of Mathematics
In 1693 Leibniz wrote to de l'Hôpital. He explained that the system ... systems of linear equations without actually calculating it, by using determinants.
[53]
[PDF] Cramer's Rule Is Due to Cramer - Rutgers University
Aug 16, 2024 · What is known as Cramer's rule is a formula expressing solutions of a system of n linear equations with n unknowns as a ratio of two ...
[54]
7.8 Solving Systems with Cramer's Rule - College Algebra 2e
Dec 21, 2021 · Using Cramer's Rule to Solve a System of Two Equations in Two Variables. We will now introduce a final method for solving systems of equations ...
[55]
[PDF] Old and New Proofs of Cramer's Rule 1 History, notations and tools
Abstract. In spite of its high computational cost, Cramer's Rule for solving systems of linear equations is of historical and theoretical importance.
[56]
[PDF] Iterative Methods for Sparse Linear Systems Second Edition
In the six years that passed since the publication of the first edition of this book, iterative methods for linear systems have made good progress in ...
[57]
[PDF] Methods of Conjugate Gradients for Solving Linear Systems 1
In the present paper, the conjugate gradient rou- tines are developed for the symmetric and non- symmetric cases. The principal results are described in section ...
[58]
[PDF] QR decomposition: History and its Applications - Duke People
Dec 17, 2010 · QR decomposition is A = QR, where Q is unitary and R is upper triangular with positive diagonal entries. It's the matrix version of Gram- ...Missing: seminal | Show results with:seminal
[59]
Iterative Solution of Linear Systems in Circuit Simulation - SpringerLink
An overview is given of iterative techniques for the solution of linear systems which occur during the simulation of electronic circuits.
[60]
[PDF] Matrices 3. Homogeneous and Inhomogeneous Systems
Definition. The linear system Ax = b is called homogeneous if b = 0; otherwise, it is called inhomogeneous. Theorem 1. Let A ...
[61]
Homogeneous and Nonhomogeneous Systems
A homogeneous system of linear equations is one in which all of the constant terms are zero. A homogeneous system always has at least one solution, namely the ...
[62]
Homogeneous Systems of Equations
Suppose that a system of linear equations is homogeneous. Then the system is consistent and one solution is found by setting each variable to zero. ... Since this ...
[63]
Systems of Linear Equations - Oregon State University
Let's define the determinant of a 2x2 system of linear equations to be the determinant of the matrix of coefficients A of the system. For this system.
[64]
[PDF] Math 2331 – Linear Algebra - 4.2 Null Spaces, Column Spaces ...
Null Space The null space of an m × n matrix A, written as Nul A, is the set of all solutions to the homogeneous equation Ax = 0.
[65]
Linear Algebra, Part 3: Kernels or Null Spaces (Mathematica)
The dimension of the kernel (null space) of a matrix A is called the nullity of A and is denoted by nullity(A) = n - r, where r is rank of matrix A.
[66]
[PDF] 5.4 Independence, Span and Basis - University of Utah Math Dept.
The kernel or nullspace of an m × n matrix A is the vector space of all solutions x to the homogeneous system Ax = 0. In symbols, kernel(A) = nullspace(A) = {x ...