# System of linear equations

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/System_of_linear_equations
> Markdown URL: https://mediated.wiki/source/System_of_linear_equations.md
> Source: https://en.wikipedia.org/wiki/System_of_linear_equations
> Source revision: 1355478879
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Several equations of degree 1 to be solved simultaneously

A linear system in three variables determines a collection of [planes](/source/Plane_(mathematics)). The intersection point is the solution.

In [mathematics](/source/Mathematics), a **system of linear equations** (or **linear system**) is a collection of two or more [linear equations](/source/Linear_equation) involving the same [variables](/source/Variable_(math)).[1][2] For example,

- { 3 x + 2 y − z = 1 2 x − 2 y + 4 z = − 2 − x + 1 2 y − z = 0 {\displaystyle {\begin{cases}3x+2y-z=1\\2x-2y+4z=-2\\-x+{\frac {1}{2}}y-z=0\end{cases}}}

is a system of three equations in the three variables *x*, *y*, *z*. A *[solution](/source/Solution_(mathematics))* to a linear system is an assignment of values to the variables such that all the equations are simultaneously satisfied. In the example above, a solution is given by the [ordered triple](/source/Tuple) ( x , y , z ) = ( 1 , − 2 , − 2 ) , {\displaystyle (x,y,z)=(1,-2,-2),} since it makes all three equations valid.

Linear systems are a fundamental part of [linear algebra](/source/Linear_algebra), a subject used in most modern mathematics. Computational [algorithms](/source/Algorithm) for finding the solutions are an important part of [numerical linear algebra](/source/Numerical_linear_algebra), and play a prominent role in [engineering](/source/Engineering), [physics](/source/Physics), [chemistry](/source/Chemistry), [computer science](/source/Computer_science), and [economics](/source/Economics). A [system of non-linear equations](/source/Nonlinear_system) can often be [approximated](/source/Approximation) by a linear system (see [linearization](/source/Linearization)), a helpful technique when making a [mathematical model](/source/Mathematical_model) or [computer simulation](/source/Computer_simulation) of a relatively [complex system](/source/Complex_system).

Very often, and in this article, the [coefficients](/source/Coefficient) and solutions of the equations are constrained to be [real](/source/Real_number) or [complex numbers](/source/Complex_number), but the theory and algorithms apply to coefficients and solutions in any [field](/source/Field_(mathematics)). For other [algebraic structures](/source/Algebraic_structure), other theories have been developed. For coefficients and solutions in an [integral domain](/source/Integral_domain), such as the [ring](/source/Ring_(mathematics)) of [integers](/source/Integer), see [Linear equation over a ring](/source/Linear_equation_over_a_ring). For coefficients and solutions that are polynomials, see [Gröbner basis](/source/Gr%C3%B6bner_basis). For finding the "best" integer solutions among many, see [Integer linear programming](/source/Integer_linear_programming). For an example of a more exotic structure to which linear algebra can be applied, see [Tropical geometry](/source/Tropical_geometry).

## Elementary examples

### Trivial example

The system of one equation in one unknown

- 2 x = 4 {\displaystyle 2x=4}

has the solution

- x = 2. {\displaystyle x=2.}

However, most interesting linear systems have at least two equations.

### Simple nontrivial example

The simplest kind of nontrivial linear system involves two equations and two variables:

- 2 x + 3 y = 6 4 x + 9 y = 15 . {\displaystyle {\begin{alignedat}{5}2x&&\;+\;&&3y&&\;=\;&&6&\\4x&&\;+\;&&9y&&\;=\;&&15&.\end{alignedat}}}

One method for solving such a system is as follows. First, solve the top equation for x {\displaystyle x} in terms of y {\displaystyle y} :

- x = 3 − 3 2 y . {\displaystyle x=3-{\frac {3}{2}}y.}

Now [substitute](/source/Substitution_(algebra)) this expression for *x* into the bottom equation:

- 4 ( 3 − 3 2 y ) + 9 y = 15. {\displaystyle 4\left(3-{\frac {3}{2}}y\right)+9y=15.}

This results in a single equation involving only the variable y {\displaystyle y} . Solving gives y = 1 {\displaystyle y=1} , and substituting this back into the equation for x {\displaystyle x} yields x = 3 2 {\displaystyle x={\frac {3}{2}}} . This method generalizes to systems with additional variables (see "elimination of variables" below, or the article on [elementary algebra](/source/Elementary_algebra)).

## General form

A general system of *m* linear equations with *n* [unknowns](/source/Variable_(mathematics)) and [coefficients](/source/Coefficient) can be written as

- { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m , {\displaystyle {\begin{cases}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{cases}}}

where x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\dots ,x_{n}} are the unknowns, a 11 , a 12 , … , a m n {\displaystyle a_{11},a_{12},\dots ,a_{mn}} are the coefficients of the system, and b 1 , b 2 , … , b m {\displaystyle b_{1},b_{2},\dots ,b_{m}} are the constant terms.[3]

Often the coefficients and unknowns are [real](/source/Real_number) or [complex numbers](/source/Complex_number), but [integers](/source/Integer) and [rational numbers](/source/Rational_number) are also seen, as are polynomials and elements of an abstract [algebraic structure](/source/Algebraic_structure).

### Vector equation

One extremely helpful view is that each unknown is a weight for a [column vector](/source/Column_vector) in a [linear combination](/source/Linear_combination).

- x 1 [ a 11 a 21 ⋮ a m 1 ] + x 2 [ a 12 a 22 ⋮ a m 2 ] + ⋯ + x n [ a 1 n a 2 n ⋮ a m n ] = [ b 1 b 2 ⋮ b m ] {\displaystyle x_{1}{\begin{bmatrix}a_{11}\\a_{21}\\\vdots \\a_{m1}\end{bmatrix}}+x_{2}{\begin{bmatrix}a_{12}\\a_{22}\\\vdots \\a_{m2}\end{bmatrix}}+\dots +x_{n}{\begin{bmatrix}a_{1n}\\a_{2n}\\\vdots \\a_{mn}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}}

This allows all the language and theory of [vector spaces](/source/Vector_space) (or more generally, [modules](/source/Module_(mathematics))) to be brought to bear. For example, the collection of all possible linear combinations of the vectors on the [left-hand side](/source/Sides_of_an_equation) (LHS) is called their *[span](/source/Span_(linear_algebra))*, and the equations have a solution just when the right-hand vector is within that span. If every vector within that span has exactly one expression as a linear combination of the given left-hand vectors, then any solution is unique. In any event, the span has a [basis](/source/Basis_(linear_algebra)) of [linearly independent](/source/Linearly_independent) vectors that do guarantee exactly one expression; and the number of vectors in that basis (its [dimension](/source/Dimension_(linear_algebra))) cannot be larger than *m* or *n*, but it can be smaller. This is important because if we have *m* independent vectors a solution is guaranteed regardless of the right-hand side (RHS), and otherwise not guaranteed.

### Matrix equation

The vector equation is equivalent to a [matrix](/source/Matrix_(mathematics)) equation of the form A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } where *A* is an *m*×*n* matrix, **x** is a [column vector](/source/Column_vector) with *n* entries, and **b** is a column vector with *m* entries.[4]

A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] , x = [ x 1 x 2 ⋮ x n ] , b = [ b 1 b 2 ⋮ b m ] . {\displaystyle 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}},\quad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}.} The number of vectors in a basis for the span of the columns vectors in A is now expressed as the *[rank](/source/Rank_(linear_algebra))* of the matrix.

## Solution set

The solution set for the equations *x* − *y* = −1 and 3*x* + *y* = 9 is the single point (2, 3).

A *[solution](/source/Solution_(mathematics))* of a linear system is an assignment of values to the variables x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\dots ,x_{n}} such that each of the equations is satisfied. The [set](/source/Set_(mathematics)) of all possible solutions is called the *[solution set](/source/Solution_set)*.[5]

A linear system may behave in any one of three possible ways:

1. The system has *infinitely many solutions*.

1. The system has a *unique solution*.

1. The system has *no solution*.

### Geometric interpretation

For a system involving two variables (*x* and *y*), each linear equation determines a [line](/source/Line_(mathematics)) on the *xy*-[plane](/source/Cartesian_coordinate_system). Because a solution to a linear system must satisfy all of the equations, the solution set is the [intersection](/source/Intersection_(set_theory)) of these lines, and is hence either a line, a single point, or the [empty set](/source/Empty_set).

For three variables, each linear equation determines a [plane](/source/Plane_(mathematics)) in [three-dimensional space](/source/Three-dimensional_space), and the solution set is the intersection of these planes. Thus the solution set may be a plane, a line, a single point, or the empty set. For example, as three parallel planes do not have a common point, the solution set of their equations is empty; the solution set of the equations of three planes intersecting at a point is single point; if three planes pass through two points, their equations have at least two common solutions; in fact the solution set is infinite and consists in all the line passing through these points.[6]

For *n* variables, each linear equation determines a [hyperplane](/source/Hyperplane) in [*n*-dimensional space](/source/N-dimensional_space). The solution set is the intersection of these hyperplanes, and is a [flat](/source/Flat_(geometry)), which may have any dimension lower than *n*.

### General behavior

The solution set for two equations in three variables is, in general, a line.

In general, the behavior of a linear system is determined by the relationship between the number of equations and the number of unknowns. Here, "in general" means that a different behavior may occur for specific values of the coefficients of the equations.

- In general, a system with fewer equations than unknowns has infinitely many solutions, but it may have no solution. Such a system is known as an [underdetermined system](/source/Underdetermined_system).

- In general, a system with the same number of equations and unknowns has a single unique solution.

- In general, a system with more equations than unknowns has no solution. Such a system is also known as an [overdetermined system](/source/Overdetermined_system).

In the first case, the [dimension](/source/Dimension) of the solution set is, in general, equal to *n* − *m*, where *n* is the number of variables and *m* is the number of equations.

The following pictures illustrate this trichotomy in the case of two variables:

- One equation Two equations Three equations

The first system has infinitely many solutions, namely all of the points on the blue line. The second system has a single unique solution, namely the intersection of the two lines. The third system has no solutions, since the three lines share no common point.

It must be kept in mind that the pictures above show only the most common case (the general case). It is possible for a system of two equations and two unknowns to have no solution (if the two lines are parallel), or for a system of three equations and two unknowns to be solvable (if the three lines intersect at a single point).

A system of linear equations behave differently from the general case if the equations are *[linearly dependent](/source/Linear_independence)*, or if it is *[inconsistent](#Consistency)* and has no more equations than unknowns.

## Properties

### Independence

The equations of a linear system are **independent** if none of the equations can be derived algebraically from the others. When the equations are independent, each equation contains new information about the variables, and removing any of the equations increases the size of the solution set. For linear equations, logical independence is the same as [linear independence](/source/Linear_independence).

The equations *x* − 2*y* = −1, 3*x* + 5*y* = 8, and 4*x* + 3*y* = 7 are linearly dependent.

For example, the equations

- 3 x + 2 y = 6 and 6 x + 4 y = 12 {\displaystyle 3x+2y=6\;\;\;\;{\text{and}}\;\;\;\;6x+4y=12}

are not independent — they are the same equation when scaled by a factor of two, and they would produce identical graphs. This is an example of equivalence in a system of linear equations.

For a more complicated example, the equations

- x − 2 y = − 1 3 x + 5 y = 8 4 x + 3 y = 7 {\displaystyle {\begin{alignedat}{5}x&&\;-\;&&2y&&\;=\;&&-1&\\3x&&\;+\;&&5y&&\;=\;&&8&\\4x&&\;+\;&&3y&&\;=\;&&7&\end{alignedat}}}

are not independent, because the third equation is the sum of the other two. Indeed, any one of these equations can be derived from the other two, and any one of the equations can be removed without affecting the solution set. The graphs of these equations are three lines that intersect at a single point.

### Consistency

See also: [Consistent and inconsistent equations](/source/Consistent_and_inconsistent_equations)

The equations 3*x* + 2*y* = 6 and 3*x* + 2*y* = 12 are inconsistent.

A linear system is **inconsistent** if it has no solution, and otherwise, it is said to be **consistent**.[7] When the system is inconsistent, it is possible to derive a [contradiction](/source/Contradiction) from the equations, that may always be rewritten as the statement 0 = 1.

For example, the equations

- 3 x + 2 y = 6 and 3 x + 2 y = 12 {\displaystyle 3x+2y=6\;\;\;\;{\text{and}}\;\;\;\;3x+2y=12}

are inconsistent. In fact, by subtracting the first equation from the second one and multiplying both sides of the result by 1/6, we get 0 = 1. The graphs of these equations on the *xy*-plane are a pair of [parallel](/source/Parallel_(geometry)) lines.

It is possible for three linear equations to be inconsistent, even though any two of them are consistent together. For example, the equations

- x + y = 1 2 x + y = 1 3 x + 2 y = 3 {\displaystyle {\begin{alignedat}{7}x&&\;+\;&&y&&\;=\;&&1&\\2x&&\;+\;&&y&&\;=\;&&1&\\3x&&\;+\;&&2y&&\;=\;&&3&\end{alignedat}}}

are inconsistent. Adding the first two equations together gives 3*x* + 2*y* = 2, which can be subtracted from the third equation to yield 0 = 1. Any two of these equations have a common solution. The same phenomenon can occur for any number of equations.

Animated row-normal-plane view of two inconsistent systems of three equations in three variables. The first has proportional coefficient rows with incompatible constants; the second has a dependent third coefficient row with an incompatible constant

In general, inconsistencies occur if the left-hand sides of the equations in a system are linearly dependent, and the constant terms do not satisfy the dependence relation. A system of equations whose left-hand sides are linearly independent is always consistent.

Putting it another way, according to the [Rouché–Capelli theorem](/source/Rouch%C3%A9%E2%80%93Capelli_theorem), any system of equations (overdetermined or otherwise) is inconsistent if the [rank](/source/Rank_(linear_algebra)) of the [augmented matrix](/source/Augmented_matrix) is greater than the rank of the [coefficient matrix](/source/Coefficient_matrix). If, on the other hand, the ranks of these two matrices are equal, the system must have at least one solution. The solution is unique if and only if the rank equals the number of variables. Otherwise the general solution has *k* free parameters where *k* is the difference between the number of variables and the rank; hence in such a case there is an infinitude of solutions. The rank of a system of equations (that is, the rank of the augmented matrix) can never be higher than [the number of variables] + 1, which means that a system with any number of equations can always be reduced to a system that has a number of [independent equations](/source/Independent_equation) that is at most equal to [the number of variables] + 1.

### Equivalence

Two linear systems using the same set of variables are **equivalent** if each of the equations in the second system can be derived algebraically from the equations in the first system, and vice versa. Two systems are equivalent if either both are inconsistent or each equation of each of them is a linear combination of the equations of the other one. It follows that two linear systems are equivalent if and only if they have the same solution set.

## Solving a linear system

There are several [algorithms](/source/Algorithm) for [solving](/source/Equation_solving) a system of linear equations.

### Describing the solution

When the solution set is finite, it is reduced to a single element. In this case, the unique solution is described by a sequence of equations whose left-hand sides are the names of the unknowns and right-hand sides are the corresponding values, for example ( x = 3 , y = − 2 , z = 6 ) {\displaystyle (x=3,\;y=-2,\;z=6)} . When an order on the unknowns has been fixed, for example the [alphabetical order](/source/Alphabetical_order) the solution may be described as a [vector](/source/Vector_space) of values, like ( 3 , − 2 , 6 ) {\displaystyle (3,\,-2,\,6)} for the previous example.

To describe a set with an infinite number of solutions, typically some of the variables are designated as **free** (or **independent**, or as **parameters**), meaning that they are allowed to take any value, while the remaining variables are **dependent** on the values of the free variables.

For example, consider the following system:

- x + 3 y − 2 z = 5 3 x + 5 y + 6 z = 7 {\displaystyle {\begin{alignedat}{7}x&&\;+\;&&3y&&\;-\;&&2z&&\;=\;&&5&\\3x&&\;+\;&&5y&&\;+\;&&6z&&\;=\;&&7&\end{alignedat}}}

The solution set to this system can be described by the following equations:

- x = − 7 z − 1 and y = 3 z + 2 . {\displaystyle x=-7z-1\;\;\;\;{\text{and}}\;\;\;\;y=3z+2{\text{.}}}

Here *z* is the free variable, while *x* and *y* are dependent on *z*. Any point in the solution set can be obtained by first choosing a value for *z*, and then computing the corresponding values for *x* and *y*.

Each free variable gives the solution space one [degree of freedom](/source/Degree_of_freedom), the number of which is equal to the [dimension](/source/Dimension) of the solution set. For example, the solution set for the above equation is a line, since a point in the solution set can be chosen by specifying the value of the parameter *z*. An infinite solution of higher order may describe a plane, or higher-dimensional set.

Different choices for the free variables may lead to different descriptions of the same solution set. For example, the solution to the above equations can alternatively be described as follows:

- y = − 3 7 x + 11 7 and z = − 1 7 x − 1 7 . {\displaystyle y=-{\frac {3}{7}}x+{\frac {11}{7}}\;\;\;\;{\text{and}}\;\;\;\;z=-{\frac {1}{7}}x-{\frac {1}{7}}{\text{.}}}

Here *x* is the free variable, and *y* and *z* are dependent.

### Elimination of variables

The simplest method for solving a system of linear equations is to repeatedly eliminate variables. This method can be described as follows:

1. In the first equation, solve for one of the variables in terms of the others.

1. Substitute this expression into the remaining equations. This yields a system of equations with one fewer equation and unknown.

1. Repeat steps 1 and 2 until the system is reduced to a single linear equation.

1. Solve this equation, and then back-substitute until the entire solution is found.

For example, consider the following system:

- { x + 3 y − 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle {\begin{cases}x+3y-2z=5\\3x+5y+6z=7\\2x+4y+3z=8\end{cases}}}

Solving the first equation for *x* gives x = 5 + 2 z − 3 y {\displaystyle x=5+2z-3y} , and plugging this into the second and third equation yields

- { y = 3 z + 2 y = 7 2 z + 1 {\displaystyle {\begin{cases}y=3z+2\\y={\tfrac {7}{2}}z+1\end{cases}}}

Since the LHS of both of these equations equal *y*, equating the RHS of the equations. We now have:

- 3 z + 2 = 7 2 z + 1 ⇒ z = 2 {\displaystyle {\begin{aligned}3z+2={\tfrac {7}{2}}z+1\\\Rightarrow z=2\end{aligned}}}

Substituting *z* = 2 into the second or third equation gives *y* = 8, and the values of *y* and *z* into the first equation yields *x* = −15. Therefore, the solution set is the ordered triple ( x , y , z ) = ( − 15 , 8 , 2 ) {\displaystyle (x,y,z)=(-15,8,2)} .

### Row reduction

Main article: [Gaussian elimination](/source/Gaussian_elimination)

In **row reduction** (also known as **Gaussian elimination**), the linear system is represented as an [augmented matrix](/source/Augmented_matrix)[8]

- [ 1 3 − 2 5 3 5 6 7 2 4 3 8 ] . {\displaystyle \left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]{\text{.}}}

This matrix is then modified using [elementary row operations](/source/Elementary_row_operations) until it reaches [reduced row echelon form](/source/Reduced_row_echelon_form). There are three types of elementary row operations:[8]

- **Type 1**: Swap the positions of two rows.

- **Type 2**: Multiply a row by a nonzero [scalar](/source/Scalar_(mathematics)).

- **Type 3**: Add to one row a scalar multiple of another.

Because these operations are reversible, the augmented matrix produced always represents a linear system that is equivalent to the original.

There are several specific algorithms to row-reduce an augmented matrix, the simplest of which are [Gaussian elimination](/source/Gaussian_elimination) and [Gauss–Jordan elimination](/source/Gauss%E2%80%93Jordan_elimination). The following computation shows Gauss–Jordan elimination applied to the matrix above:

- [ 1 3 − 2 5 3 5 6 7 2 4 3 8 ] ∼ [ 1 3 − 2 5 0 − 4 12 − 8 2 4 3 8 ] ∼ [ 1 3 − 2 5 0 − 4 12 − 8 0 − 2 7 − 2 ] ∼ [ 1 3 − 2 5 0 1 − 3 2 0 − 2 7 − 2 ] ∼ [ 1 3 − 2 5 0 1 − 3 2 0 0 1 2 ] ∼ [ 1 3 − 2 5 0 1 0 8 0 0 1 2 ] ∼ [ 1 3 0 9 0 1 0 8 0 0 1 2 ] ∼ [ 1 0 0 − 15 0 1 0 8 0 0 1 2 ] . {\displaystyle {\begin{aligned}\left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]&\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\2&4&3&8\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\0&-2&7&-2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&-2&7&-2\end{array}}\right]\\&\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&0&9\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&0&0&-15\\0&1&0&8\\0&0&1&2\end{array}}\right].\end{aligned}}}

Animated row-normal-plane view of row reduction of the system above

The last matrix is in reduced row echelon form, and represents the system *x* = −15, *y* = 8, *z* = 2. A comparison with the example in the previous section on the algebraic elimination of variables shows that these two methods are in fact the same; the difference lies in how the computations are written down.

### Cramer's rule

Main article: [Cramer's rule](/source/Cramer's_rule)

**Cramer's rule** is an explicit formula for the solution of a system of linear equations, with each variable given by a quotient of two [determinants](/source/Determinant).[9] For example, the solution to the system

- x + 3 y − 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle {\begin{alignedat}{7}x&\;+&\;3y&\;-&\;2z&\;=&\;5\\3x&\;+&\;5y&\;+&\;6z&\;=&\;7\\2x&\;+&\;4y&\;+&\;3z&\;=&\;8\end{alignedat}}}

is given by

- x = | 5 3 − 2 7 5 6 8 4 3 | | 1 3 − 2 3 5 6 2 4 3 | , y = | 1 5 − 2 3 7 6 2 8 3 | | 1 3 − 2 3 5 6 2 4 3 | , z = | 1 3 5 3 5 7 2 4 8 | | 1 3 − 2 3 5 6 2 4 3 | . {\displaystyle x={\frac {\,{\begin{vmatrix}5&3&-2\\7&5&6\\8&4&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;y={\frac {\,{\begin{vmatrix}1&5&-2\\3&7&6\\2&8&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;z={\frac {\,{\begin{vmatrix}1&3&5\\3&5&7\\2&4&8\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}}.}

For each variable, the denominator is the determinant of the [matrix of coefficients](/source/Matrix_of_coefficients), while the numerator is the determinant of a matrix in which one column has been replaced by the vector of constant terms.

Though Cramer's rule is important theoretically, it has little practical value for large matrices, since the computation of large determinants is somewhat cumbersome. (Indeed, large determinants are most easily computed using row reduction.) Further, Cramer's rule has very poor numerical properties, making it unsuitable for solving even small systems reliably, unless the operations are performed in rational arithmetic with unbounded precision.[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*]

### Matrix solution

If the equation system is expressed in the matrix form A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } , the entire solution set can also be expressed in matrix form. If the matrix *A* is square (has *m* rows and *n*=*m* columns) and has full rank (all *m* rows are independent), then the system has a unique solution given by

- x = A − 1 b {\displaystyle \mathbf {x} =A^{-1}\mathbf {b} }

where A − 1 {\displaystyle A^{-1}} is the [inverse](/source/Matrix_inverse) of *A*. More generally, regardless of whether *m*=*n* or not and regardless of the rank of *A*, all solutions (if any exist) are given using the [Moore–Penrose inverse](/source/Moore%E2%80%93Penrose_inverse) of *A*, denoted A + {\displaystyle A^{+}} , as follows:

- x = A + b + ( I − A + A ) w {\displaystyle \mathbf {x} =A^{+}\mathbf {b} +\left(I-A^{+}A\right)\mathbf {w} }

where w {\displaystyle \mathbf {w} } is a vector of free parameters that ranges over all possible *n*×1 vectors. A necessary and sufficient condition for any solution(s) to exist is that the potential solution obtained using w = 0 {\displaystyle \mathbf {w} =\mathbf {0} } satisfy A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } — that is, that A A + b = b . {\displaystyle AA^{+}\mathbf {b} =\mathbf {b} .} If this condition does not hold, the equation system is inconsistent and has no solution. If the condition holds, the system is consistent and at least one solution exists. For example, in the above-mentioned case in which *A* is square and of full rank, A + {\displaystyle A^{+}} simply equals A − 1 {\displaystyle A^{-1}} and the general solution equation simplifies to

- x = A − 1 b + ( I − A − 1 A ) w = A − 1 b + ( I − I ) w = A − 1 b {\displaystyle \mathbf {x} =A^{-1}\mathbf {b} +\left(I-A^{-1}A\right)\mathbf {w} =A^{-1}\mathbf {b} +\left(I-I\right)\mathbf {w} =A^{-1}\mathbf {b} }

as previously stated, where w {\displaystyle \mathbf {w} } has completely dropped out of the solution, leaving only a single solution. In other cases, though, w {\displaystyle \mathbf {w} } remains and hence an infinitude of potential values of the free parameter vector w {\displaystyle \mathbf {w} } give an infinitude of solutions of the equation.

### Other methods

Further information: [Numerical solution of linear systems](/source/Numerical_solution_of_linear_systems)

While systems of three or four equations can be readily solved by hand (see [Cracovian](/source/Cracovian)), computers are often used for larger systems. The standard algorithm for solving a system of linear equations is based on Gaussian elimination with some modifications. Firstly, it is essential to avoid division by small numbers, which may lead to inaccurate results. This can be done by reordering the equations if necessary, a process known as [*pivoting*](/source/Pivot_element). Secondly, the algorithm does not exactly do Gaussian elimination, but it computes the [LU decomposition](/source/LU_decomposition) of the matrix *A*. This is mostly an organizational tool, but it is much quicker if one has to solve several systems with the same matrix *A* but different vectors **b**.

If the matrix *A* has some special structure, this can be exploited to obtain faster or more accurate algorithms. For instance, systems with a [symmetric](/source/Symmetric_matrix) [positive definite](/source/Positive-definite_matrix) matrix can be solved twice as fast with the [Cholesky decomposition](/source/Cholesky_decomposition). [Levinson recursion](/source/Levinson_recursion) is a fast method for [Toeplitz matrices](/source/Toeplitz_matrix). Special methods exist also for matrices with many zero elements (so-called [sparse matrices](/source/Sparse_matrix)), which appear often in applications.

A completely different approach is often taken for very large systems, which would otherwise take too much time or memory. The idea is to start with an initial approximation to the solution (which does not have to be accurate at all), and to change this approximation in several steps to bring it closer to the true solution. Once the approximation is sufficiently accurate, this is taken to be the solution to the system. This leads to the class of [iterative methods](/source/Iterative_method). For some sparse matrices, the introduction of randomness improves the speed of the iterative methods.[10] One example of an iterative method is the [Jacobi method](/source/Jacobi_method), where the matrix A {\displaystyle A} is split into its diagonal component D {\displaystyle D} and its non-diagonal component L + U {\displaystyle L+U} . An initial guess x ( 0 ) {\displaystyle {\mathbf {x}}^{(0)}} is used at the start of the algorithm. Each subsequent guess is computed using the iterative equation:

- x ( k + 1 ) = D − 1 ( b − ( L + U ) x ( k ) ) {\displaystyle {\mathbf {x}}^{(k+1)}=D^{-1}({\mathbf {b}}-(L+U){\mathbf {x}}^{(k)})}

When the difference between guesses x ( k ) {\displaystyle {\mathbf {x}}^{(k)}} and x ( k + 1 ) {\displaystyle {\mathbf {x}}^{(k+1)}} is sufficiently small, the algorithm is said to have *converged* on the solution.[11]

There is also a [quantum algorithm for linear systems of equations](/source/Quantum_algorithm_for_linear_systems_of_equations).[12]

## Homogeneous systems

See also: [Homogeneous differential equation](/source/Homogeneous_differential_equation)

A system of linear equations is **homogeneous** if all of the constant terms are zero:

- a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = 0 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = 0 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = 0. {\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;=\;&&&0\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;=\;&&&0\\&&&&&&&&&&\vdots \;\ &&&\\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;=\;&&&0.\\\end{alignedat}}}

A homogeneous system is equivalent to a matrix equation of the form

- A x = 0 {\displaystyle A\mathbf {x} =\mathbf {0} }

where *A* is an *m* × *n* matrix, **x** is a column vector with *n* entries, and **0** is the [zero vector](/source/Zero_vector) with *m* entries.

### Homogeneous solution set

Every homogeneous system has at least one solution, known as the *zero* (or *trivial*) solution, which is obtained by assigning the value of zero to each of the variables. If the system has a [non-singular matrix](/source/Non-singular_matrix) (det(*A*) ≠ 0) then it is also the only solution. If the system has a singular matrix then there is a solution set with an infinite number of solutions. This solution set has the following additional properties:

1. If **u** and **v** are two [vectors](/source/Vector_(mathematics)) representing solutions to a homogeneous system, then the vector sum **u** + **v** is also a solution to the system.

1. If **u** is a vector representing a solution to a homogeneous system, and *r* is any [scalar](/source/Scalar_(mathematics)), then *r***u** is also a solution to the system.

These are exactly the properties required for the solution set to be a [linear subspace](/source/Linear_subspace) of **R***n*. In particular, the solution set to a homogeneous system is the same as the [null space](/source/Kernel_(matrix)) of the corresponding matrix *A*.

### Relation to nonhomogeneous systems

There is a close relationship between the solutions to a linear system and the solutions to the corresponding homogeneous system:

- A x = b and A x = 0 . {\displaystyle A\mathbf {x} =\mathbf {b} \qquad {\text{and}}\qquad A\mathbf {x} =\mathbf {0} .}

Specifically, if **p** is any specific solution to the linear system *A***x** = **b**, then the entire solution set can be described as

- { p + v : v is any solution to A x = 0 } . {\displaystyle \left\{\mathbf {p} +\mathbf {v} :\mathbf {v} {\text{ is any solution to }}A\mathbf {x} =\mathbf {0} \right\}.}

Geometrically, this says that the solution set for *A***x** = **b** is a [translation](/source/Translation_(geometry)) of the solution set for *A***x** = **0**. Specifically, the [flat](/source/Flat_(geometry)) for the first system can be obtained by translating the [linear subspace](/source/Euclidean_subspace) for the homogeneous system by the vector **p**.

This reasoning only applies if the system *A***x** = **b** has at least one solution. This occurs if and only if the vector **b** lies in the [image](/source/Image_(mathematics)) of the [linear transformation](/source/Linear_transformation) *A*.

## See also

- [Arrangement of hyperplanes](/source/Arrangement_of_hyperplanes) – Partition of space by a hyperplanes

- [Coates graph](/source/Coates_graph) – Mathematical graph for solving linear systems

- [Iterative refinement](/source/Iterative_refinement) – Method to improve accuracy of numerical solutions to systems of linear equations

- [LAPACK](/source/LAPACK) – Software library for numerical linear algebra

- [Linear equation over a ring](/source/Linear_equation_over_a_ring)

- [Linear least squares](/source/Linear_least_squares_(mathematics)) – Least squares approximation of linear functions to dataPages displaying short descriptions of redirect targets

- [Matrix decomposition](/source/Matrix_decomposition) – Representation of a matrix as a product

- [Matrix splitting](/source/Matrix_splitting) – Representation of a matrix as a sum

- [NAG Numerical Library](/source/NAG_Numerical_Library) – Software library of numerical-analysis algorithms

- [Rybicki Press algorithm](/source/Rybicki_Press_algorithm) – Algorithm for inverting a matrix

- [Simultaneous equations](/source/Simultaneous_equations) – Set of equations to be solved togetherPages displaying short descriptions of redirect targets

## References

### Footnotes

1. **[^](#cite_ref-FOOTNOTEAnton19872BurdenFaires1993324GolubVan_Loan199687Harper197657_1-0)** [Anton (1987)](#CITEREFAnton1987), p. 2; [Burden & Faires (1993)](#CITEREFBurdenFaires1993), p. 324; [Golub & Van Loan (1996)](#CITEREFGolubVan_Loan1996), p. 87; [Harper (1976)](#CITEREFHarper1976), p. 57.

1. **[^](#cite_ref-2)** ["System of Equations"](https://www.britannica.com/science/system-of-equations). *Britannica*. Retrieved August 26, 2024.

1. **[^](#cite_ref-FOOTNOTEBeauregardFraleigh197365_3-0)** [Beauregard & Fraleigh (1973)](#CITEREFBeauregardFraleigh1973), p. 65.

1. **[^](#cite_ref-FOOTNOTEBeauregardFraleigh197365–66_4-0)** [Beauregard & Fraleigh (1973)](#CITEREFBeauregardFraleigh1973), pp. 65–66.

1. **[^](#cite_ref-5)** ["Systems of Linear Equations"](https://math.berkeley.edu/~arash/54/notes/01_01.pdf) (PDF). *math.berkeley.edu*. Retrieved February 3, 2025.

1. **[^](#cite_ref-FOOTNOTECullen19903_6-0)** [Cullen (1990)](#CITEREFCullen1990), p. 3.

1. **[^](#cite_ref-FOOTNOTEWhitelaw1991[httpsbooksgooglecombooksid6M_kDzA7-qICpgPA70_70]_7-0)** [Whitelaw (1991)](#CITEREFWhitelaw1991), p. [70](https://books.google.com/books?id=6M_kDzA7-qIC&pg=PA70).

1. ^ [***a***](#cite_ref-FOOTNOTEBeauregardFraleigh197368_8-0) [***b***](#cite_ref-FOOTNOTEBeauregardFraleigh197368_8-1) [Beauregard & Fraleigh (1973)](#CITEREFBeauregardFraleigh1973), p. 68.

1. **[^](#cite_ref-FOOTNOTESterling2009[httpsbooksgooglecombooksidPsNJ1alC-bsCpgPA235_235]_9-0)** [Sterling (2009)](#CITEREFSterling2009), p. [235](https://books.google.com/books?id=PsNJ1alC-bsC&pg=PA235).

1. **[^](#cite_ref-10)** Hartnett, Kevin (March 8, 2021). ["New Algorithm Breaks Speed Limit for Solving Linear Equations"](https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/). *[Quanta Magazine](/source/Quanta_Magazine)*. Retrieved March 9, 2021.

1. **[^](#cite_ref-11)** ["Jacobi Method"](https://mathworld.wolfram.com/JacobiMethod.html).

1. **[^](#cite_ref-FOOTNOTEHarrowHassidimLloyd2009_12-0)** [Harrow, Hassidim & Lloyd (2009)](#CITEREFHarrowHassidimLloyd2009).

### Bibliography

- Anton, Howard (1987), *Elementary Linear Algebra* (5th ed.), New York: [Wiley](/source/John_Wiley_%26_Sons), [ISBN](/source/ISBN_(identifier)) [0-471-84819-0](https://en.wikipedia.org/wiki/Special:BookSources/0-471-84819-0)

- Beauregard, Raymond A.; Fraleigh, John B. (1973), [*A First Course In Linear Algebra: with Optional Introduction to Groups, Rings, and Fields*](https://archive.org/details/firstcourseinlin0000beau), Boston: [Houghton Mifflin Company](/source/Houghton_Mifflin_Company), [ISBN](/source/ISBN_(identifier)) [0-395-14017-X](https://en.wikipedia.org/wiki/Special:BookSources/0-395-14017-X)

- Burden, Richard L.; Faires, J. Douglas (1993), [*Numerical Analysis*](https://archive.org/details/numericalanalysi00burd) (5th ed.), Boston: [Prindle, Weber and Schmidt](https://en.wikipedia.org/w/index.php?title=Prindle,_Weber_and_Schmidt&action=edit&redlink=1), [ISBN](/source/ISBN_(identifier)) [0-534-93219-3](https://en.wikipedia.org/wiki/Special:BookSources/0-534-93219-3)

- Cullen, Charles G. (1990), *Matrices and Linear Transformations*, MA: Dover, [ISBN](/source/ISBN_(identifier)) [978-0-486-66328-9](https://en.wikipedia.org/wiki/Special:BookSources/978-0-486-66328-9)

- Golub, Gene H.; Van Loan, Charles F. (1996), *Matrix Computations* (3rd ed.), Baltimore: [Johns Hopkins University Press](/source/Johns_Hopkins_University_Press), [ISBN](/source/ISBN_(identifier)) [0-8018-5414-8](https://en.wikipedia.org/wiki/Special:BookSources/0-8018-5414-8)

- Harper, Charlie (1976), *Introduction to Mathematical Physics*, New Jersey: [Prentice-Hall](/source/Prentice-Hall), [ISBN](/source/ISBN_(identifier)) [0-13-487538-9](https://en.wikipedia.org/wiki/Special:BookSources/0-13-487538-9)

- Harrow, Aram W.; Hassidim, Avinatan; Lloyd, Seth (2009), "Quantum Algorithm for Linear Systems of Equations", *Physical Review Letters*, **103** (15) 150502, [arXiv](/source/ArXiv_(identifier)):[0811.3171](https://arxiv.org/abs/0811.3171), [Bibcode](/source/Bibcode_(identifier)):[2009PhRvL.103o0502H](https://ui.adsabs.harvard.edu/abs/2009PhRvL.103o0502H), [doi](/source/Doi_(identifier)):[10.1103/PhysRevLett.103.150502](https://doi.org/10.1103%2FPhysRevLett.103.150502), [PMID](/source/PMID_(identifier)) [19905613](https://pubmed.ncbi.nlm.nih.gov/19905613), [S2CID](/source/S2CID_(identifier)) [5187993](https://api.semanticscholar.org/CorpusID:5187993)

- Sterling, Mary J. (2009), *Linear Algebra for Dummies*, Indianapolis, Indiana: Wiley, [ISBN](/source/ISBN_(identifier)) [978-0-470-43090-3](https://en.wikipedia.org/wiki/Special:BookSources/978-0-470-43090-3)

- Whitelaw, T. A. (1991), *Introduction to Linear Algebra* (2nd ed.), CRC Press, [ISBN](/source/ISBN_(identifier)) [0-7514-0159-5](https://en.wikipedia.org/wiki/Special:BookSources/0-7514-0159-5)

## Further reading

- Anton, Howard (2005). *Elementary Linear Algebra (Applications Version)* (9th ed.). Wiley International.

- Axler, Sheldon Jay (1997). *Linear Algebra Done Right* (2nd ed.). Springer-Verlag. [ISBN](/source/ISBN_(identifier)) [0-387-98259-0](https://en.wikipedia.org/wiki/Special:BookSources/0-387-98259-0).

- Lay, David C. (August 22, 2005). *Linear Algebra and Its Applications* (3rd ed.). Addison Wesley. [ISBN](/source/ISBN_(identifier)) [978-0-321-28713-7](https://en.wikipedia.org/wiki/Special:BookSources/978-0-321-28713-7).

- Meyer, Carl D. (February 15, 2001). [*Matrix Analysis and Applied Linear Algebra*](https://web.archive.org/web/20010301161440/http://matrixanalysis.com/DownloadChapters.html). Society for Industrial and Applied Mathematics (SIAM). [ISBN](/source/ISBN_(identifier)) [978-0-89871-454-8](https://en.wikipedia.org/wiki/Special:BookSources/978-0-89871-454-8). Archived from [the original](http://www.matrixanalysis.com/DownloadChapters.html) on March 1, 2001.

- Poole, David (2006). *Linear Algebra: A Modern Introduction* (2nd ed.). Brooks/Cole. [ISBN](/source/ISBN_(identifier)) [0-534-99845-3](https://en.wikipedia.org/wiki/Special:BookSources/0-534-99845-3).

- Leon, Steven J. (2006). *Linear Algebra With Applications* (7th ed.). Pearson Prentice Hall.

- [Strang, Gilbert](/source/Gilbert_Strang) (2005). *Linear Algebra and Its Applications*.

- Peng, Richard; Vempala, Santosh S. (2024). "Solving Sparse Linear Systems Faster than Matrix Multiplication". *Comm. ACM*. **67** (7): 79–86. [arXiv](/source/ArXiv_(identifier)):[2007.10254](https://arxiv.org/abs/2007.10254). [doi](/source/Doi_(identifier)):[10.1145/3615679](https://doi.org/10.1145%2F3615679).

## External links

- Media related to [System of linear equations](https://commons.wikimedia.org/wiki/Category:System_of_linear_equations) at Wikimedia Commons

v t e Linear algebra Outline Glossary Template:Matrix classes Linear equations Linear equation System of linear equations Determinant Minor Cauchy–Binet formula Cramer's rule Gaussian elimination Gauss–Jordan elimination Overcompleteness Strassen algorithm Matrices Matrix Matrix addition Matrix multiplication Basis transformation matrix Characteristic polynomial Spectrum Trace Eigenvalue, eigenvector and eigenspace Cayley–Hamilton theorem Jordan normal form Weyr canonical form Rank Inverse, Pseudoinverse Adjugate, Transpose Dot product Symmetric matrix, Skew-symmetric matrix Orthogonal matrix, Unitary matrix Hermitian matrix, Antihermitian matrix Positive-(semi)definite Pfaffian Projection Spectral theorem Perron–Frobenius theorem Diagonal matrix, Triangular matrix, Tridiagonal matrix Block matrix Sparse matrix Hessenberg matrix, Hessian matrix Vandermonde matrix Stochastic matrix, Toeplitz matrix, Circulant matrix, Hankel matrix (0,1)-matrix List of matrices Matrix decompositions Cholesky decomposition LU decomposition QR decomposition Polar decomposition Spectral theorem Singular value decomposition Higher-order singular value decomposition Schur decomposition Schur complement Haynsworth inertia additivity formula Reducing subspace Relations and computations Matrix equivalence Matrix congruence Matrix similarity Matrix consimilarity Row equivalence Elementary row operations Householder transformation Least squares Linear least squares Gram–Schmidt process Woodbury matrix identity Vector spaces Vector space Linear combination Linear span Linear independence Basis, Hamel basis Change of basis Dimension theorem for vector spaces Hamel dimension Examples of vector spaces Linear map Shear mapping Squeeze mapping Linear subspace Row and column spaces, Null space Rank–nullity theorem Nullity theorem Cyclic subspace Dual space, Linear functional Category of vector spaces Structures Topological vector space Normed vector space Inner product space Euclidean space Orthogonality Orthogonal complement Orthogonal projection Orthogonal group Pseudo-Euclidean space Null vector Indefinite orthogonal group Orientation Improper rotation Symplectic structure Multilinear algebra Multilinear algebra Tensor Tensors (classical) Component-free treatment of tensors Outer product Tensor algebra Exterior algebra Symmetric algebra Clifford algebra Geometric algebra Bivector Multivector Gamas's theorem Affine and projective Affine space Affine transformation, Affine group, Affine geometry Affine coordinate system, Flat (geometry) Cartesian coordinate system Euclidean group Poincaré group Galilean group Projective space Projective transformation Projective geometry Projective linear group Quadric Numerical linear algebra Numerical linear algebra Floating-point arithmetic Numerical stability Basic Linear Algebra Subprograms Sparse matrix Comparison of linear algebra libraries Category

Authority control databases GND

---
Adapted from the Wikipedia article [System of linear equations](https://en.wikipedia.org/wiki/System_of_linear_equations) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/System_of_linear_equations?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.