System of linear equations

A solution to a linear system is an assignment of values to the variables such that all the equations are simultaneously satisfied.

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 general system of m linear equations with n unknowns and coefficients can be written as where

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.

The number of vectors in a basis for the span is now expressed as the rank of the matrix.

[6] For n variables, each linear equation determines a hyperplane in n-dimensional space.

Here, "in general" means that a different behavior may occur for specific values of the coefficients of the 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.

[7] 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.

A system of equations whose left-hand sides are linearly independent is always consistent.

An infinite solution of higher order may describe a plane, or higher-dimensional set.

For example, the solution to the above equations can alternatively be described as follows: Here x is the free variable, and y and z are dependent.

The simplest method for solving a system of linear equations is to repeatedly eliminate variables.

This method can be described as follows: For example, consider the following system: Solving the first equation for x gives

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 is an explicit formula for the solution of a system of linear equations, with each variable given by a quotient of two determinants.

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.

remains and hence an infinitude of potential values of the free parameter vector

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.

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.

A completely different approach is often taken for very large systems, which would otherwise take too much time or memory.

For some sparse matrices, the introduction of randomness improves the speed of the iterative methods.

[12] A system of linear equations is homogeneous if all of the constant terms are zero: A homogeneous system 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 0 is the zero vector with m entries.

In particular, the solution set to a homogeneous system is the same as the null space of the corresponding matrix A.