In mathematics, a system of linear equations (or linear system) is a collection of one or more

^{''n''}. 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

linear equation
In mathematics, a linear equation is an equation that may be put in the form
a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coefficie ...

s involving the same variables.
For example,
:$\backslash begin\; 3x+2y-z=1\backslash \backslash \; 2x-2y+4z=-2\backslash \backslash \; -x+\backslash fracy-z=0\; \backslash end$
is a system of three equations in the three variables . 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 the ordered triple
:$(x,y,z)=(1,-2,-2),$
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
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...

, a subject which is used in most parts of modern mathematics. Computational algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s for finding the solutions are an important part of numerical linear algebra, and play a prominent role in engineering
Engineering is the use of scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad range of more speciali ...

, physics
Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which relat ...

, chemistry
Chemistry is the scientific study of the properties and behavior of matter. It is a natural science that covers the elements that make up matter to the compounds made of atoms, molecules and ions: their composition, structure, properties, ...

, computer science, and economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analyzes ...

. A system of non-linear equations can often be approximated by a linear system (see linearization), a helpful technique when making a mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used in the natural sciences (such as physics, ...

or computer simulation
Computer simulation is the process of mathematical modelling, performed on a computer, which is designed to predict the behaviour of, or the outcome of, a real-world or physical system. The reliability of some mathematical models can be dete ...

of a relatively complex system
A complex system is a system composed of many components which may interact with each other. Examples of complex systems are Earth's global climate, organisms, the human brain, infrastructure such as power grid, transportation or communication ...

.
Very often, the coefficients of the equations are real or complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the f ...

s 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
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...

of the integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

s, or in other algebraic structures, other theories have been developed, see Linear equation over a ring
In algebra, linear equations and systems of linear equations over a field are widely studied. "Over a field" means that the coefficients of the equations and the solutions that one is looking for belong to a given field, commonly the real or the ...

. Integer linear programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...

is a collection of methods for finding the "best" integer solution (when there are many). Gröbner basis
In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring over a field . A Gröbn ...

theory provides algorithms when coefficients and unknowns are polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An examp ...

s. Also tropical geometry is an example of linear algebra in a more exotic structure.
Elementary examples

Trivial example

The system of one equation in one unknown :$2x\; =\; 4$ has the solution :$x\; =\; 2.$ However, a linear system is commonly considered as having at least two equations.Simple nontrivial example

The simplest kind of nontrivial linear system involves two equations and two variables: :$\backslash begin\; 2x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 3y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 6\; \&\; \backslash \backslash \; 4x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 9y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 15\&.\; \backslash end$ One method for solving such a system is as follows. First, solve the top equation for $x$ in terms of $y$: :$x\; =\; 3\; -\; \backslash fracy.$ Now substitute this expression for ''x'' into the bottom equation: :$4\backslash left(\; 3\; -\; \backslash fracy\; \backslash right)\; +\; 9y\; =\; 15.$ This results in a single equation involving only the variable $y$. Solving gives $y\; =\; 1$, and substituting this back into the equation for $x$ yields $x\; =\; 3/2$. This method generalizes to systems with additional variables (see "elimination of variables" below, or the article on elementary algebra.)General form

A general system of ''m'' linear equations with ''n'' unknowns and coefficients can be written as :$\backslash begin\; a\_\; x\_1\; +\; a\_\; x\_2\; +\backslash dots\; +\; a\_\; x\_n\; +\; b\_1\; =\; 0\; \backslash \backslash \; a\_\; x\_1\; +\; a\_\; x\_2\; +\; \backslash dots\; +\; a\_\; x\_n\; +\; b\_2\; =\; 0\; \backslash \backslash \; \backslash vdots\backslash \backslash \; a\_\; x\_1\; +\; a\_\; x\_2\; +\; \backslash dots\; +\; a\_\; x\_n\; +\; b\_m\; =\; 0,\; \backslash end$ where $x\_1,\; x\_2,\backslash dots,x\_n$ are the unknowns, $a\_,a\_,\backslash dots,a\_$ are the coefficients of the system such that $a\_\; +\; a\_\; +\; \backslash dots\; +\; a\_\backslash neq\; 0$, and $b\_1,b\_2,\backslash dots,b\_m$ are the constant terms. Often the coefficients and unknowns are real orcomplex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the f ...

s, but integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

s and rational numbers are also seen, as are polynomials and elements of an abstract algebraic structure.
Vector equation

One extremely helpful view is that each unknown is a weight for a column vector in a linear combination. :$x\_1\backslash begina\_\backslash \backslash a\_\backslash \backslash \; \backslash vdots\; \backslash \backslash a\_\backslash end\; +\; x\_2\backslash begina\_\backslash \backslash a\_\backslash \backslash \; \backslash vdots\; \backslash \backslash a\_\backslash end\; +\; \backslash dots\; +\; x\_n\backslash begina\_\backslash \backslash a\_\backslash \backslash \; \backslash vdots\; \backslash \backslash a\_\backslash end\; +\backslash beginb\_1\backslash \backslash b\_2\backslash \backslash \; \backslash vdots\; \backslash \backslash b\_m\backslash end\; =\; 0$ This allows all the language and theory of ''vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but c ...

s'' (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
Span may refer to:
Science, technology and engineering
* Span (unit), the width of a human hand
* Span (engineering), a section between two intermediate supports
* Wingspan, the distance between the wingtips of a bird or aircraft
* Sorbitan este ...

'', 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
Basis may refer to:
Finance and accounting
* Adjusted basis, the net cost of an asset after adjusting for various tax-related items
* Basis point, 0.01%, often used in the context of interest rates
* Basis trading, a trading strategy consisting ...

'' of linearly independent
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts ar ...

vectors that do guarantee exactly one expression; and the number of vectors in that basis (its ''dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordina ...

'') 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

The vector equation is equivalent to amatrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

equation of the form
:$A\backslash mathbf=\backslash mathbf$
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=\; \backslash begin\; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash end,\backslash quad\; \backslash mathbf=\; \backslash begin\; x\_1\; \backslash \backslash \; x\_2\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; x\_n\; \backslash end,\backslash quad\; \backslash mathbf=\; \backslash begin\; b\_1\; \backslash \backslash \; b\_2\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; b\_m\; \backslash end$
The number of vectors in a basis for the span is now expressed as the '' rank'' of the matrix.
Solution set

A solution of a linear system is an assignment of values to the variables such that each of the equations is satisfied. Theset
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...

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

For a system involving two variables (''x'' and ''y''), each linear equation determines aline
Line most often refers to:
* Line (geometry), object with zero thickness and curvature that stretches to infinity
* Telephone line, a single-user circuit on a telephone communication system
Line, lines, The Line, or LINE may also refer to:
Arts ...

on the ''xy''- plane. Because a solution to a linear system must satisfy all of the equations, the solution set is the intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...

of these lines, and is hence either a line, a single point, or the empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...

.
For three variables, each linear equation determines a plane in three-dimensional space
Three-dimensional space (also: 3D space, 3-space or, rarely, tri-dimensional space) is a geometric setting in which three values (called ''parameters'') are required to determine the position of an element (i.e., point). This is the informal ...

, 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.
For ''n'' variables, each linear equation determines a hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its '' ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hype ...

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

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, thedimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordina ...

of the solution set is, in general, equal to , 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:
:
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

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 aslinear independence
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts ar ...

.
For example, the equations
:$3x+2y=6\backslash ;\backslash ;\backslash ;\backslash ;\backslash text\backslash ;\backslash ;\backslash ;\backslash ;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
:$\backslash begin\; x\; \&\&\backslash ;\; -\; \backslash ;\&\&\; 2y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; -1\; \&\; \backslash \backslash \; 3x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 5y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 8\; \&\; \backslash \backslash \; 4x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 3y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 7\; \&\; \backslash end$
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

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 acontradiction
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle ...

from the equations, that may always be rewritten as the statement .
For example, the equations
:$3x+2y=6\backslash ;\backslash ;\backslash ;\backslash ;\backslash text\backslash ;\backslash ;\backslash ;\backslash ;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 . The graphs of these equations on the ''xy''-plane are a pair of parallel
Parallel is a geometric term of location which may refer to:
Computing
* Parallel algorithm
* Parallel computing
* Parallel metaheuristic
* Parallel (software), a UNIX utility for running programs in parallel
* Parallel Sysplex, a cluster of I ...

lines.
It is possible for three linear equations to be inconsistent, even though any two of them are consistent together. For example, the equations
:$\backslash begin\; x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 1\; \&\; \backslash \backslash \; 2x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 1\; \&\; \backslash \backslash \; 3x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 2y\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 3\; \&\; \backslash end$
are inconsistent. Adding the first two equations together gives , which can be subtracted from the third equation to yield . 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 he 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 he 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 severalalgorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s for 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,\; \backslash ;y=-2,\backslash ;\; z=6)$. When an order on the unknowns has been fixed, for example the alphabetical order the solution may be described as avector
Vector most often refers to:
* Euclidean vector, a quantity with a magnitude and a direction
* Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathemat ...

of values, like $(3,\; \backslash ,-2,\backslash ,\; 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:
:$\backslash begin\; x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 3y\; \&\&\backslash ;\; -\; \backslash ;\&\&\; 2z\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 5\; \&\; \backslash \backslash \; 3x\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 5y\; \&\&\backslash ;\; +\; \backslash ;\&\&\; 6z\; \&\&\backslash ;\; =\; \backslash ;\&\&\; 7\; \&\; \backslash end$
The solution set to this system can be described by the following equations:
:$x=-7z-1\backslash ;\backslash ;\backslash ;\backslash ;\backslash text\backslash ;\backslash ;\backslash ;\backslash ;y=3z+2\backslash 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
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordina ...

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=-\backslash fracx\; +\; \backslash frac\backslash ;\backslash ;\backslash ;\backslash ;\backslash text\backslash ;\backslash ;\backslash ;\backslash ;z=-\backslash fracx-\backslash frac\backslash 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: # 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 unknown. # Repeat steps 1 and 2 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: :$\backslash begin\; x+3y-2z=5\backslash \backslash \; 3x+5y+6z=7\backslash \backslash \; 2x+4y+3z=8\; \backslash end$ Solving the first equation for ''x'' gives , and plugging this into the second and third equation yields :$\backslash begin\; y=3z+2\backslash \backslash \; y=\backslash tfracz+1\; \backslash end$ Since the LHS of both of these equations equal ''y'', equating the RHS of the equations. We now have: :$\backslash begin\; 3z+2=\backslash tfracz+1\backslash \backslash \; \backslash Rightarrow\; z=2\; \backslash end$ 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)$.Row reduction

In row reduction (also known as Gaussian elimination), the linear system is represented as an augmented matrix: :$\backslash left;\; href="/html/ALL/s/begin\; 1\_\_3\_\_-2\_\_5\_\backslash \backslash \; 3\_\_5\_\_6\_\_7\_\backslash \backslash \; 2\_\_4\_\_3\_\_8\; \backslash end\backslash right.html"\; ;"title="begin\; 1\; 3\; -2\; 5\; \backslash \backslash \; 3\; 5\; 6\; 7\; \backslash \backslash \; 2\; 4\; 3\; 8\; \backslash end\backslash right">begin\; 1\; 3\; -2\; 5\; \backslash \backslash \; 3\; 5\; 6\; 7\; \backslash \backslash \; 2\; 4\; 3\; 8\; \backslash end\backslash right$ This matrix is then modified usingelementary row operations In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multip ...

until it reaches reduced row echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian e ...

. 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:
:$\backslash begin\backslash left;\; href="/html/ALL/s/begin\; 1\_\_3\_\_-2\_\_5\_\backslash \backslash \; 3\_\_5\_\_6\_\_7\_\backslash \backslash \; 2\_\_4\_\_3\_\_8\; \backslash end\backslash right.html"\; ;"title="begin\; 1\; 3\; -2\; 5\; \backslash \backslash \; 3\; 5\; 6\; 7\; \backslash \backslash \; 2\; 4\; 3\; 8\; \backslash end\backslash right">begin\; 1\; 3\; -2\; 5\; \backslash \backslash \; 3\; 5\; 6\; 7\; \backslash \backslash \; 2\; 4\; 3\; 8\; \backslash end\backslash right$
The last matrix is in reduced row echelon form, and represents the system , , . 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

Cramer's rule is an explicit formula for the solution of a system of linear equations, with each variable given by a quotient of twodeterminant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...

s. For example, the solution to the system
:$\backslash begin\; x\; \&\backslash ;\; +\; \&\backslash ;\; 3y\; \&\backslash ;\; -\; \&\backslash ;\; 2z\; \&\backslash ;\; =\; \&\backslash ;\; 5\; \backslash \backslash \; 3x\; \&\backslash ;\; +\; \&\backslash ;\; 5y\; \&\backslash ;\; +\; \&\backslash ;\; 6z\; \&\backslash ;\; =\; \&\backslash ;\; 7\; \backslash \backslash \; 2x\; \&\backslash ;\; +\; \&\backslash ;\; 4y\; \&\backslash ;\; +\; \&\backslash ;\; 3z\; \&\backslash ;\; =\; \&\backslash ;\; 8\; \backslash end$
is given by
:$x=\backslash frac\; ,\backslash ;\backslash ;\backslash ;\backslash ;\; y=\backslash frac\; ,\backslash ;\backslash ;\backslash ;\backslash ;\; z=\backslash frac\; .$
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.
Matrix solution

If the equation system is expressed in the matrix form $A\backslash mathbf=\backslash mathbf$, 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 :$\backslash mathbf=A^\backslash mathbf$ where $A^$ 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 inverse of ''A'', denoted $A^+$, as follows: :$\backslash mathbf=A^+\; \backslash mathbf\; +\; \backslash left(I\; -\; A^+\; A\backslash right)\backslash mathbf$ where $\backslash mathbf$ 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 $\backslash mathbf=\backslash mathbf$ satisfy $A\backslash mathbf=\backslash mathbf$ — that is, that $AA^+\; \backslash mathbf=\backslash mathbf.$ 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^+$ simply equals $A^$ and the general solution equation simplifies to :$\backslash mathbf=A^\backslash mathbf\; +\; \backslash left(I\; -\; A^A\backslash right)\backslash mathbf\; =\; A^\backslash mathbf\; +\; \backslash left(I-I\backslash right)\backslash mathbf\; =\; A^\backslash mathbf$ as previously stated, where $\backslash mathbf$ has completely dropped out of the solution, leaving only a single solution. In other cases, though, $\backslash mathbf$ remains and hence an infinitude of potential values of the free parameter vector $\backslash mathbf$ give an infinitude of solutions of the equation.Other methods

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 theLU decomposition
In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix decomposition). The product sometimes includes a ...

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
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

positive definite matrix can be solved twice as fast with the Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for effic ...

. 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 method
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pr ...

s. For some sparse matrices, the introduction of randomness improves the speed of the iterative methods.
There is also a quantum algorithm for linear systems of equations.Quantum algorithm for solving linear systems of equations, by Harrow et al.Homogeneous systems

A system of linear equations is homogeneous if all of the constant terms are zero: :$\backslash begin\; a\_\; x\_1\; \&\&\backslash ;\; +\; \backslash ;\&\&\; a\_\; x\_2\; \&\&\backslash ;\; +\; \backslash cdots\; +\; \backslash ;\&\&\; a\_\; x\_n\; \&\&\backslash ;\; =\; \backslash ;\&\&\&\; 0\; \backslash \backslash \; a\_\; x\_1\; \&\&\backslash ;\; +\; \backslash ;\&\&\; a\_\; x\_2\; \&\&\backslash ;\; +\; \backslash cdots\; +\; \backslash ;\&\&\; a\_\; x\_n\; \&\&\backslash ;\; =\; \backslash ;\&\&\&\; 0\; \backslash \backslash \; \&\&\; \&\&\; \&\&\; \&\&\; \&\&\; \backslash vdots\backslash ;\backslash \; \&\&\&\; \backslash \backslash \; a\_\; x\_1\; \&\&\backslash ;\; +\; \backslash ;\&\&\; a\_\; x\_2\; \&\&\backslash ;\; +\; \backslash cdots\; +\; \backslash ;\&\&\; a\_\; x\_n\; \&\&\backslash ;\; =\; \backslash ;\&\&\&\; 0.\; \backslash \backslash \; \backslash end$ A homogeneous system is equivalent to a matrix equation of the form :$A\backslash mathbf=\backslash mathbf$ where ''A'' is an matrix, x is a column vector with ''n'' entries, and 0 is thezero vector
In mathematics, a zero element is one of several generalizations of the number zero to other algebraic structures. These alternate meanings may or may not reduce to the same thing, depending on the context.
Additive identities
An additive iden ...

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 anon-singular matrix
In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that
:\mathbf = \mathbf = \mathbf_n \
where denotes the -by- identity matrix and the multiplicat ...

() 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 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 ''r''u is also a solution to the system.
These are exactly the properties required for the solution set to be a linear subspace
In mathematics, and more specifically in linear algebra, a linear subspace, also known as a vector subspaceThe term ''linear subspace'' is sometimes used for referring to flats and affine subspaces. In the case of vector spaces over the reals, ...

of Rsingular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...

.
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\backslash mathbf=\backslash mathbf\backslash qquad\; \backslash text\backslash qquad\; A\backslash mathbf=\backslash mathbf.$ Specifically, if p is any specific solution to the linear system , then the entire solution set can be described as :$\backslash left\backslash .$ Geometrically, this says that the solution set for is atranslation
Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. The English language draws a terminological distinction (which does not exist in every language) between ''translat ...

of the solution set for . Specifically, the flat for the first system can be obtained by translating the linear subspace
In mathematics, and more specifically in linear algebra, a linear subspace, also known as a vector subspaceThe term ''linear subspace'' is sometimes used for referring to flats and affine subspaces. In the case of vector spaces over the reals, ...

for the homogeneous system by the vector p.
This reasoning only applies if the system has at least one solution. This occurs if and only if the vector b lies in the image of the linear transformation
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pre ...

''A''.
See also

Notes

References

* * * * *Further reading

* * * * * * *External links

* {{authority control Equations Linear algebra Numerical linear algebra