In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables. For example,
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
since it makes all three equations valid. The word "system" indicates that the equations should be considered collectively, rather than individually.
Linear systems are the basis and a fundamental part of linear algebra, a subject used in most 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, and in this article, 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. Tropical geometry is another example of linear algebra in a more exotic structure.
Elementary examples
Trivial example
The system of one equation in one unknown
has the solution
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:
One method for solving such a system is as follows. First, solve the top equation for in terms of :
Now substitute this expression for x into the bottom equation:
This results in a single equation involving only the variable . Solving gives , and substituting this back into the equation for yields . 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
where are the unknowns, are the coefficients of the system, and 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
One extremely helpful view is that each unknown is a weight for a column vector in a linear combination.
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
The vector equation is equivalent to a matrix equation of the form
where A is an m×n matrix, x is a column vector with n entries, and b is a column vector with m entries.
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. 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.