text:
System of linear equations
From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. Please help to improve this article by introducing more precise citations. (October 2015) (Learn how and when to remove this template message)
A linear system in three variables determines a collection of planes. The intersection point is the solution.
In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same set of variables.[1] For example,
3 x + 2 y − z = 1 2 x − 2 y + 4 z = − 2 − x + 1 2 y − z = 0 {\displaystyle {\begin{alignedat}{7}3x&&\;+\;&&2y&&\;-\;&&z&&\;=\;&&1&\\2x&&\;-\;&&2y&&\;+\;&&4z&&\;=\;&&-2&\\-x&&\;+\;&&{\tfrac {1}{2}}y&&\;-\;&&z&&\;=\;&&0&\end{alignedat}}}
is a system of three equations in the three variables x, y, z. A solution to a linear system is an assignment of values to the variables such that all the equations are simultaneously satisfied. A solution to the system above is given by
x = 1 y = − 2 z = − 2 {\displaystyle {\begin{alignedat}{2}x&\,=\,&1\\y&\,=\,&-2\\z&\,=\,&-2\end{alignedat}}}
since it makes all three equations valid. The word "system" indicates that the equations are to be considered collectively, rather than individually.
In mathematics, the theory of linear systems is the basis and a fundamental part of linear algebra, a subject which is used in most parts of modern mathematics. Computational algorithms for finding the solutions are an important part of numerical linear algebra, and play a prominent role in engineering, physics, chemistry, computer science, and economics. A system of non-linear equations can often be approximated by a linear system (see linearization), a helpful technique when making a mathematical model or computer simulation of a relatively complex system.
Very often, the coefficients of the equations are real or complex numbers and the solutions are searched in the same set of numbers, but the theory and the algorithms apply for coefficients and solutions in any field. For solutions in an integral domain like the ring of the integers, or in other algebraic structures, other theories have been developed, see Linear equation over a ring. Integer linear programming is a collection of methods for finding the "best" integer solution (when there are many). Gröbner basis theory provides algorithms when coefficients and unknowns are polynomials. Also tropical geometry is an example of linear algebra in a more exotic structure.
Contents
[hide]
1 Elementary example
2 General form
2.1 Vector equation
2.2 Matrix equation
3 Solution set
3.1 Geometric interpretation
3.2 General behavior
4 Properties
4.1 Independence
4.2 Consistency
4.3 Equivalence
5 Solving a linear system
5.1 Describing the solution
5.2 Elimination of variables
5.3 Row reduction
5.4 Cramer's rule
5.5 Matrix solution
5.6 Other methods
6 Homogeneous systems
6.1 Solution set
6.2 Relation to nonhomogeneous systems
7 See also
8 Notes
9 References
9.1 Textbooks
10 External links
Elementary example[edit]
The simplest kind of 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 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=3/2} . This method generalizes to systems with additional variables (see "elimination of variables" below, or the article on elementary algebra.)
General form[edit]
A general system of m linear equations with n unknowns 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{aligned}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}&=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}&=b_{2}\\&\ \ \vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}&=b_{m},\end{aligned}}}
where x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\ldots ,x_{n}} are the unknowns, a 11 , a 12 , … , a m n {\displaystyle a_{11},a_{12},\ldots ,a_{mn}} are the coefficients of the system, and b 1 , b 2 , … , b m {\displaystyle b_{1},b_{2},\ldots ,b_{m}} are the constant terms.
Often the coefficients and unknowns are real or complex numbers, but integers and rational numbers are also seen, as are polynomials and elements of an abstract algebraic structure.
Vector equation[edit]
One extremely helpful view is that each unknown is a weight for a column vector in a 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}}+\cdots +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 (or more generally, modules) to be brought to bear. For example, the collection of all possible linear combinations of the vectors on the left-hand side is called their span, 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 of linearly independent vectors that do guarantee exactly one expression; and the number of vectors in that basis (its dimension) 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, and otherwise not guaranteed.
Matrix equation[edit]
The vector equation is equivalent to a matrix 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 with n entries, and b is a column vector with m entries.
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 is now expressed as the rank of the matrix.
Solution set[edit]
The solution set for the equations x − y = −1 and 3x + y = 9 is the single point (2, 3).
A solution of a linear system is an assignment of values to the variables x1, x2, ..., xn such that each of the equations is satisfied. The set of all possible solutions is called the solution set.
A linear system may behave in any one of three possible ways:
The system has infinitely many solutions.
The system has a single unique solution.
The system has no solution.
Geometric interpretation[edit]
For a system involving two variables (x and y), each linear equation determines a line on the xy-plane. Because a solution to a linear system must satisfy all of the equations, the solution set is the intersection of these lines, and is hence either a line, a single point, or the empty set.
For three variables, each linear equation determines a plane in 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.[2]
For n variables, each linear equation determines a hyperplane in n-dimensional space. The solution set is the intersection of these hyperplanes, and is a flat, which may have any dimension lower than n.
General behavior[edit]
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.
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.
In the first case, the 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, or if it is inconsistent and has no more equations than unknowns.
Properties[edit]
Independence[edit]
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.
The equations x − 2y = −1, 3x + 5y = 8, and 4x + 3y = 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[edit]
See also: Consistent and inconsistent equations
The equations 3x + 2y = 6 and 3x + 2y = 12 are inconsistent.
A linear system is inconsistent if it has no solution, and otherwise it is said to be consistent. When the system is inconsistent, it is possible to derive a 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 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 3x + 2y = 2, which can be subtracted from the third equation to yield 0 = 1. Note that any two of these equations have a common solution. The same phenomenon can occur for any number of equations.
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, any system of equations (overdetermined or otherwise) is inconsistent if the rank of the augmented matrix is greater than the rank of the 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 are an infinitude of solutions. The rank of a system of equations (i.e. 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 that is at most equal to [the number of variables] + 1.
Equivalence[edit]
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[edit]
There are several algorithms for solving a system of linear equations.
Describing the solution[edit]
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 the solution may be described as a vector 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, the number of which is equal to the 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[edit]
The simplest method for solving a system of linear equations is to repeatedly eliminate variables. This method can be described as follows:
In the first equation, solve for one of the variables in terms of the others.
Substitute this expression into the remaining equations. This yields a system of equations with one fewer equation and one fewer unknown.
Repeat until the system is reduced to a single linear equation.
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{alignedat}{7}x&&\;+\;&&3y&&\;-\;&&2z&&\;=\;&&5&\\3x&&\;+\;&&5y&&\;+\;&&6z&&\;=\;&&7&\\2x&&\;+\;&&4y&&\;+\;&&3z&&\;=\;&&8&\end{alignedat}}}
Solving the first equation for x gives x = 5 + 2z − 3y, and plugging this into the second and third equation yields
− 4 y + 12 z = − 8 − 2 y + 7 z = − 2 {\displaystyle {\begin{alignedat}{5}-4y&&\;+\;&&12z&&\;=\;&&-8&\\-2y&&\;+\;&&7z&&\;=\;&&-2&\end{alignedat}}}
Solving the first of these equations for y yields y = 2 + 3z, and plugging this into the second equation yields z = 2. We now have:
x = 5 + 2 z − 3 y y = 2 + 3 z z = 2 {\displaystyle {\begin{alignedat}{7}x&&\;=\;&&5&&\;+\;&&2z&&\;-\;&&3y&\\y&&\;=\;&&2&&\;+\;&&3z&&&&&\\z&&\;=\;&&2&&&&&&&&&\end{alignedat}}}
Substituting z = 2 into the second equation gives y = 8, and substituting z = 2 and y = 8 into the first equation yields x = −15. Therefore, the solution set is the single point (x, y, z) = (−15, 8, 2).
Row reduction[edit]
Main article: Gaussian elimination
In row reduction (also known as Gaussian elimination), the linear system is represented as an augmented matrix:
[ 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 until it reaches reduced row echelon form. There are three types of elementary row operations:
Type 1: Swap the positions of two rows.
Type 2: Multiply a row by a nonzero scalar.
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 and Gauss-Jordan 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}}}
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[edit]
Main article: 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. 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 {\,\left|{\begin{matrix}5&3&-2\\7&5&6\\8&4&3\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix}}\right|\,}},\;\;\;\;y={\frac {\,\left|{\begin{matrix}1&5&-2\\3&7&6\\2&8&3\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix}}\right|\,}},\;\;\;\;z={\frac {\,\left|{\begin{matrix}1&3&5\\3&5&7\\2&4&8\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix}}\right|\,}}.}
For each variable, the denominator is the determinant of the 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]
Matrix solution[edit]
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 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 pseudoinverse of A, denoted A † {\displaystyle A^{\dagger }} , as follows:
x = A † b + ( I − A † A ) w {\displaystyle {\mathbf {x} }=A^{\dagger }{\mathbf {b} }+(I-A^{\dagger }A){\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^{\dagger }{\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^{\dagger }} 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}}+(I-A^{-1}A){\mathbf {w}}=A^{-1}{\mathbf {b}}+(I-I){\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[edit]
While systems of three or four equations can be readily solved by hand (see 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. Secondly, the algorithm does not exactly do Gaussian elimination, but it computes the 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 positive definite matrix can be solved twice as fast with the Cholesky decomposition. Levinson recursion is a fast method for Toeplitz matrices. Special methods exist also for matrices with many zero elements (so-called sparse matrices), 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.
There is also a quantum algorithm for linear systems of equations.[3]
Homogeneous systems[edit]
See also: 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 \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\,\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{\textbf {x}}={\textbf {0}}}
where A is an m × n matrix, x is a column vector with n entries, and 0 is the zero vector with m entries.
Solution set[edit]
Every homogeneous system has at least one solution, known as the zero solution (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 (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:
If u and v are two vectors representing solutions to a homogeneous system, then the vector sum u + v is also a solution to the system.
If u is a vector representing a solution to a homogeneous system, and r is any scalar, then ru is also a solution to the system.
These are exactly the properties required for the solution set to be a linear subspace of Rn. In particular, the solution set to a homogeneous system is the same as the null space of the corresponding matrix A. Numerical solutions to a homogeneous system can be found with a singular value decomposition.
Relation to nonhomogeneous systems[edit]
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{\textbf {x}}={\textbf {b}}\qquad {\text{and}}\qquad A{\textbf {x}}={\textbf {0}}{\text{.}}}
Specifically, if p is any specific solution to the linear system Ax = b, then the entire solution set can be described as
{ p + v : v is any solution to A x = 0 } . {\displaystyle \left\{{\textbf {p}}+{\textbf {v}}:{\textbf {v}}{\text{ is any solution to }}A{\textbf {x}}={\textbf {0}}\right\}.}
Geometrically, this says that the solution set for Ax = b is a translation of the solution set for Ax = 0. Specifically, the flat for the first system can be obtained by translating the linear subspace for the homogeneous system by the vector p.
This reasoning only applies if the system Ax = b has at least one solution. This occurs if and only if the vector b lies in the image of the linear transformation A.
See also[edit]
Arrangement of hyperplanes
Iterative refinement
Coates graph
LAPACK (the free standard package to solve linear equations numerically; available in Fortran, C, C++)
Linear equation over a ring
Linear least squares
Matrix decomposition
Matrix splitting
NAG Numerical Library (NAG Library versions of LAPACK solvers)
Simultaneous equations
Moore–Penrose pseudoinverse
Notes[edit]
Jump up ^ The subject of this article is basic in mathematics, and is treated in many textbooks. Among them, Lay 2005, Meyer 2001, and Strang 2005 contain the material of this article.
Jump up ^ Charles G. Cullen (1990). Matrices and Linear Transformations. MA: Dover. p. 3. ISBN 978-0-486-66328-9.
Jump up ^ Quantum algorithm for solving linear systems of equations, by Harrow et al..
References[edit]
See also: Linear algebra § Further reading
Textbooks[edit]
Axler, Sheldon Jay (1997), Linear Algebra Done Right (2nd ed.), Springer-Verlag, ISBN 0-387-98259-0
Lay, David C. (August 22, 2005), Linear Algebra and Its Applications (3rd ed.), Addison Wesley, ISBN 978-0-321-28713-7
Meyer, Carl D. (February 15, 2001), Matrix Analysis and Applied Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), ISBN 978-0-89871-454-8
Poole, David (2006), Linear Algebra: A Modern Introduction (2nd ed.), Brooks/Cole, ISBN 0-534-99845-3
Anton, Howard (2005), Elementary Linear Algebra (Applications Version) (9th ed.), Wiley International
Leon, Steven J. (2006), Linear Algebra With Applications (7th ed.), Pearson Prentice Hall
Strang, Gilbert (2005), Linear Algebra and Its Applications
External links[edit]
Media related to System of linear equations at Wikimedia Commons
[hide]
v
t
e
Linear algebra
Basic concepts
Scalar
Vector
Vector space
Scalar multiplication
Vector projection
Linear span
Linear map
Linear projection
Linear independence
Linear combination
Basis
Column space
Row space
Orthogonality
Kernel
Eigenvalues and eigenvectors
Outer product
Inner product space
Dot product
Transpose
Gram–Schmidt process
Linear equations
Vector algebra
Cross product
Triple product
Seven-dimensional cross product
Multilinear algebra
Geometric algebra
Exterior algebra
Bivector
Multivector
Matrices
Block
Decomposition
Invertible
Minor
Multiplication
Rank
Transformation
Cramer's rule
Gaussian elimination
Algebraic constructions
Dual
Direct sum
Function space
Quotient
Subspace
Tensor product
Numerical
Floating point
Matrix Laboratory
Numerical stability
Basic Linear Algebra Subprograms (BLAS)
Sparse matrix
Comparison of linear algebra libraries
Comparison of numerical analysis software
Category
Outline
Portal
Wikibook
Wikiversity
Retrieved from "https://en.wikipedia.org/w/index.php?title=System_of_linear_equations&oldid=840527904"
Categories:
Equations
Linear algebra
Numerical linear algebra
Hidden categories:
Articles lacking in-text citations from October 2015
All articles lacking in-text citations
All articles with unsourced statements
Articles with unsourced statements from March 2017
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
In other projects
Wikimedia Commons
Languages
Alemannisch
العربية
Aragonés
Azərbaycanca
Башҡортса
Беларуская
Беларуская (тарашкевіца)
Български
Bosanski
Català
Čeština
Deutsch
Eesti
Ελληνικά
Español
Esperanto
Euskara
فارسی
Fiji Hindi
Français
Galego
한국어
हिन्दी
Hrvatski
Bahasa Indonesia
Íslenska
Italiano
עברית
Latina
Latviešu
Magyar
Македонски
Nederlands
日本語
Norsk
Norsk nynorsk
Occitan
ਪੰਜਾਬੀ
پنجابی
Polski
Português
Română
Русский
සිංහල
Simple English
سنڌي
Slovenčina
Slovenščina
کوردی
Српски / srpski
Srpskohrvatski / српскохрватски
Suomi
Svenska
தமிழ்
ไทย
Türkçe
Українська
اردو
Tiếng Việt
Winaray
粵語
中文
53 more
Edit links
This page was last edited on 10 May 2018, at 13:33.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

values: jump-to-nav mw-jump

value: td

values: Wikipedia:WikiProject Fact and Reference Check

value: i

value: small

values: plainlinks metadata ambox ambox-style ambox-More_footnotes

values:
/wiki/Plane_(mathematics)
mw-redirect
Plane (mathematics)

values:
/wiki/Variable_(math)
mw-redirect
Variable (math)

attrs: columnalign rowspacing columnspacing displaystyle

values: right left right left right left right left right left right left right left

values: 0em 0em 0em 0em 0em 0em 0em 0em 0em 0em 0em 0em 0em 0em

values: vertical-align: -4.338ex; width:21.219ex; height:9.676ex;

values:
right left right left
3pt
0em 0em 0em 0em
true

values: vertical-align: -3.838ex; width:8.279ex; height:8.843ex;

values:
/wiki/Integer_linear_programming
mw-redirect
Integer linear programming

values: right left right left right left right left right left

values: vertical-align: -2.338ex; width:14.73ex; height:5.843ex;

values: vertical-align: -0.338ex; width:1.33ex; height:1.676ex;

values: vertical-align: -0.671ex; width:1.155ex; height:2.009ex;

values: vertical-align: -1.838ex; width:12.232ex; height:5.176ex;

values: vertical-align: -2.505ex; width:23.356ex; height:6.176ex;

values: vertical-align: -0.671ex; width:5.416ex; height:2.509ex;

values: vertical-align: -0.838ex; width:7.916ex; height:2.843ex;

values: 0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em

values: vertical-align: -6.005ex; width:37.074ex; height:13.176ex;

values: vertical-align: -0.671ex; width:13.528ex; height:2.009ex;

values: vertical-align: -0.671ex; width:16.315ex; height:2.009ex;

values: vertical-align: -0.671ex; width:12.988ex; height:2.509ex;

values:
/wiki/Column_vector
mw-redirect
Column vector

values: vertical-align: -6.338ex; width:51.085ex; height:13.843ex;

values:
/wiki/Span_(linear_algebra)
mw-redirect
Span (linear algebra)

values:
/wiki/Linearly_independent
mw-redirect
Linearly independent

values:
/wiki/Dimension_(linear_algebra)
mw-redirect
Dimension (linear algebra)

values: {\displaystyle A{\mathbf {x}}={\mathbf {b}}}

values: vertical-align: -0.338ex; width:7.738ex; height:2.176ex;

values: vertical-align: -6.505ex; width:58.716ex; height:14.176ex;

values:
/wiki/Line_(mathematics)
mw-redirect
Line (mathematics)

values:
/wiki/N-dimensional_space
mw-redirect
N-dimensional space

values: vertical-align: -0.671ex; width:33.894ex; height:2.509ex;

values: vertical-align: -3.838ex; width:14.729ex; height:8.843ex;

values: vertical-align: -3.838ex; width:12.921ex; height:8.843ex;

values: vertical-align: -0.838ex; width:23.332ex; height:2.843ex;

values: vertical-align: -0.838ex; width:9.947ex; height:2.843ex;

values: vertical-align: -2.338ex; width:18.27ex; height:5.843ex;

values: vertical-align: -0.671ex; width:32.553ex; height:2.509ex;

values: vertical-align: -2.005ex; width:39.109ex; height:5.343ex;

values: vertical-align: -3.838ex; width:18.27ex; height:8.843ex;

values: vertical-align: -2.338ex; width:17.458ex; height:5.843ex;

values: vertical-align: -3.838ex; width:17.108ex; height:8.843ex;

attrs: columnalign rowspacing columnspacing columnlines

values: vertical-align: -4.505ex; width:20.17ex; height:10.176ex;

values:
/wiki/Elementary_row_operations
mw-redirect
Elementary row operations

values:
/wiki/Reduced_row_echelon_form
mw-redirect
Reduced row echelon form

values:
/wiki/Gauss-Jordan_elimination
mw-redirect
Gauss-Jordan elimination

values: vertical-align: -9.838ex; width:109.213ex; height:20.843ex;

values: vertical-align: -3.838ex; width:18.915ex; height:8.843ex;

values: vertical-align: -9.171ex; width:61.533ex; height:19.509ex;

values: This claim needs references to reliable sources. (March 2017)

values:
noprint Inline-Template Template-Fact
white-space:nowrap;

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

values: vertical-align: -0.338ex; width:10.071ex; height:2.676ex;

values: vertical-align: -0.338ex; width:4.076ex; height:2.676ex;

values:
/wiki/Matrix_inverse
mw-redirect
Matrix inverse

values:
/wiki/Moore-Penrose_pseudoinverse
mw-redirect
Moore-Penrose pseudoinverse

values: vertical-align: -0.338ex; width:2.705ex; height:2.676ex;

values: vertical-align: -0.838ex; width:23.742ex; height:3.176ex;

values: {\displaystyle {\mathbf {x}}=A^{\dagger }{\mathbf {b}}+(I-A^{\dagger }A){\mathbf {w}}}

values: vertical-align: -0.338ex; width:1.931ex; height:1.676ex;

values: {\displaystyle {\mathbf {w}}={\mathbf {0}}}

values: vertical-align: -0.338ex; width:6.366ex; height:2.176ex;

values: vertical-align: -0.338ex; width:11.164ex; height:2.676ex;

values: {\displaystyle AA^{\dagger }{\mathbf {b}}={\mathbf {b}}.}

values: vertical-align: -0.838ex; width:55.567ex; height:3.176ex;

values: Quantum algorithm for linear systems of equations

values: vertical-align: -6.005ex; width:35.951ex; height:13.176ex;

values: {\displaystyle A{\textbf {x}}={\textbf {0}}}

values: vertical-align: -0.338ex; width:7.589ex; height:2.176ex;

values:
/wiki/Zero_vector
mw-redirect
Zero vector

values:
/wiki/Singular_matrix
mw-redirect
Singular matrix

values:
/wiki/Vector_(mathematics)
mw-redirect
Vector (mathematics)

values:
/wiki/Euclidean_subspace
mw-redirect
Euclidean subspace

values:
/wiki/Kernel_(matrix)
mw-redirect
Kernel (matrix)

values: Edit section: Relation to nonhomogeneous systems

values: vertical-align: -0.338ex; width:29.012ex; height:2.176ex;

values: vertical-align: -0.838ex; width:38.273ex; height:2.843ex;

values:
/wiki/Linear_transformation
mw-redirect
Linear transformation

values:
/wiki/Simultaneous_equations
mw-redirect
Simultaneous equations

values:
nofollow
external text
https://arxiv.org/abs/0811.3171

values:
reflist mw-references-wrap
list-style-type: decimal;

values: commons:Category:System of linear equations

values:
/wiki/Column_space
mw-redirect
Column space

values:
navbox-image
6
width:1px;padding:0px 0px 0px 2px

values:
/wiki/Floating_point
mw-redirect
Floating point

values: Comparison of numerical analysis software

values:
/wiki/Outline_of_linear_algebra
mw-redirect
Outline of linear algebra

values: nowraplinks hlist collapsible autocollapse navbox-inner

values: Category:Articles lacking in-text citations from October 2015

values: Category:All articles lacking in-text citations

values: Category:All articles with unsourced statements

values: Category:Articles with unsourced statements from March 2017

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/System_of_linear_equations
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: Guidance on how to use and edit Wikipedia

values: About the project, what you can do, where to find things

values: A list of recent changes in the wiki [ctrl-alt-r]

values: portal navigation p-interaction p-interaction-label

values: List of all English Wikipedia pages containing links to this page [ctrl-alt-j]

values: Recent changes in pages linked from this page [ctrl-alt-k]

values:
/wiki/Wikipedia:File_Upload_Wizard
Upload files [ctrl-alt-u]
u

values: A list of all special pages [ctrl-alt-q]

values: Permanent link to this revision of the page

values: Link to connected data repository item [ctrl-alt-g]

values: Printable version of this page [ctrl-alt-p]

values: portal navigation p-wikibase-otherprojects p-wikibase-otherprojects-label

values:
interlanguage-link interwiki-als
display: none;

values: نظام معادلات خطية – Arabic

values:
interlanguage-link interwiki-an
display: none;

values:
interlanguage-link interwiki-az
display: none;

values: Һыҙыҡлы алгебраик тигеҙләмәләр системаһы – Bashkir

values:
interlanguage-link interwiki-ba
display: none;

values: Сістэма лінейных алгебраічных ураўненняў – Belarusian

values:
interlanguage-link interwiki-be
display: none;

values: Сыстэма лінейных альгебраічных раўнаньняў – Belarusian (Taraškievica orthography)

values:
interlanguage-link interwiki-be-x-old
display: none;

values: Система линейни уравнения – Bulgarian

values:
interlanguage-link interwiki-bg
display: none;

values:
interlanguage-link interwiki-bs
display: none;

values:
interlanguage-link interwiki-ca
display: none;

values:
interlanguage-link interwiki-cs
display: none;

values:
interlanguage-link interwiki-de
display: none;

values:
interlanguage-link interwiki-et
display: none;

values: Σύστημα γραμμικών εξισώσεων – Greek

values:
interlanguage-link interwiki-el
display: none;

values: Sistema de ecuaciones lineales – Spanish

values: Sistemo de linearaj ekvacioj – Esperanto

values:
interlanguage-link interwiki-eo
display: none;

values:
interlanguage-link interwiki-eu
display: none;

values: دستگاه معادلات خطی – Persian

values:
interlanguage-link interwiki-fa
display: none;

values:
interlanguage-link interwiki-hif
display: none;

values:
interlanguage-link interwiki-gl
display: none;

values: 연립 일차 방정식 – Korean

values:
interlanguage-link interwiki-ko
display: none;

values: रैखिक समीकरण निकाय – Hindi

values:
interlanguage-link interwiki-hr
display: none;

values:
interlanguage-link interwiki-is
display: none;

values:
interlanguage-link interwiki-it
display: none;

values: מערכת משוואות ליניאריות – Hebrew

values:
interlanguage-link interwiki-la
display: none;

values: Систем на линеарни равенки – Macedonian

values: Stelsel van lineaire vergelijkingen – Dutch

values:
interlanguage-link interwiki-nl
display: none;

values:
interlanguage-link interwiki-ja
display: none;

values: Lineært likningssystem – Norwegian Nynorsk

values:
interlanguage-link interwiki-nn
display: none;

values:
interlanguage-link interwiki-oc
display: none;

values: ਰੇਖੀ ਸਮੀਕਰਨਾਂ ਦਾ ਤੰਤਰ – Punjabi

values:
interlanguage-link interwiki-pa
display: none;

values: لینیر ایکوایشنز دا پربندھ – Western Punjabi

values:
interlanguage-link interwiki-pnb
display: none;

values:
interlanguage-link interwiki-pl
display: none;

values: Sistema de equações lineares – Portuguese

values:
interlanguage-link interwiki-ro
display: none;

values: Система линейных алгебраических уравнений – Russian

values: ඒකජ සමීකරණ පද්ධතිය – Sinhala

values:
interlanguage-link interwiki-si
display: none;

values: System of linear equations – Simple English

values: سِڌِر مساواتُن جو سرشتو – Sindhi

values:
interlanguage-link interwiki-sd
display: none;

values:
interlanguage-link interwiki-sk
display: none;

values:
interlanguage-link interwiki-sl
display: none;

values: سیستمی ھاوکێشەی ھێڵی – Central Kurdish

values:
interlanguage-link interwiki-ckb
display: none;

values: Систем линеарних једначина – Serbian

values:
interlanguage-link interwiki-sr
display: none;

values: Sistem linearnih jednačina – Serbo-Croatian

values:
interlanguage-link interwiki-sh
display: none;

values:
interlanguage-link interwiki-fi
display: none;

values:
interlanguage-link interwiki-sv
display: none;

values: நேரியல் சமன்பாடுகளின் தொகுப்பு – Tamil

values:
interlanguage-link interwiki-ta
display: none;

values: ระบบสมการเชิงเส้น – Thai

values:
interlanguage-link interwiki-th
display: none;

values:
interlanguage-link interwiki-tr
display: none;

values: Система лінійних алгебраїчних рівнянь – Ukrainian

values:
interlanguage-link interwiki-uk
display: none;

values: یکلخت لکیری مساوات کا نظام – Urdu

values:
interlanguage-link interwiki-vi
display: none;

values:
interlanguage-link interwiki-war
display: none;

values:
interlanguage-link interwiki-zh-yue
display: none;

values: All languages (initial selection from common choices by you and others)

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-System_of_linear_equations rootpage-System_of_linear_equations skin-vector action-view