System of linear equations

In linear algebra, a system of linear equations (LGS for short) is a set of linear equations with one or more unknowns that are all supposed to be satisfied simultaneously.

For example, a corresponding system for three unknowns $x_{1},\ x_{2},\ x_{3}$ looks like this:

${\begin{matrix}3x_{1}&+&2x_{2}&-&x_{3}&=&1\\2x_{1}&-&2x_{2}&+&4x_{3}&=&-2\\-x_{1}&+&{1 \over 2}x_{2}&-&x_{3}&=&0\end{matrix}}$

For $x_{1}=1,\ x_{2}=-2,\ x_{3}=-2$ all three equations are fulfilled, it is a solution of the system. Thus, in contrast to the solution of a single equation (consisting of a single number), a solution here must consist of an n-tuple, in this case a triplet of numbers. This is also called a solution vector.

In general, a linear system of equations with equations and unknowns can always be put into the following form:

${\begin{matrix}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{matrix}}$

Linear systems of equations are called homogeneous if all $b_{i}$ equal to 0, otherwise inhomogeneous. Homogeneous systems of equations always have at least the so-called trivial solution, in which all variables are equal to 0. In the case of inhomogeneous systems of equations, on the other hand, there may be no solution at all.

Geometric interpretation

With the help of the scalar product of vectors, each of the m equations of a linear system of equations can be interpreted geometrically as the normal form of a hyperplane in an n-dimensional vector space, where n is the number of variables or unknowns. Special cases of hyperplanes are straight lines in the plane and planes in space.

The i-th equation of a linear system of equations (i = 1,...,m)

$a_{i1}x_{1}+a_{i2}x_{2}+\cdots +a_{in}x_{n}=b_{i}$

can be represented as

${\vec {n}}_{i}\cdot {\vec {x}}=b_{i}$ with a normal vector ${\vec {n}}_{i}={\begin{pmatrix}a_{i1}\\a_{i2}\\\vdots \\a_{in}\end{pmatrix}}\qquad$ and a position vector $\qquad {\vec {x}}={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}$ .

Thus the solvability of a linear system of equations can be traced back to an intersection problem of hyperplanes: The set of common points of all hyperplanes is sought.

Example

Linear systems of equations often arise as models of practical tasks. A typical example from school mathematics is as follows:

"A father and a son are 62 years old together. Six years ago, the father was four times as old as the son was then. How old is each?"

It can also be described by the following system of linear equations:

${\begin{matrix}I.&v+s&=&62\\{\mathit {II.}}&v-6&=&4\cdot (s-6)\end{matrix}}$

The variable here represents the father's age and the variable that of the son. In a first step, the system of equations is usually put into a standard form in which only terms with variables are on the left-hand side and the pure numbers are on the right-hand side. In this example, the second equation is multiplied out and converted.

${\begin{matrix}I.&v&+&s&=&62\\{\mathit {II}}.&v&-&4s&=&-18\end{matrix}}$

To solve this system of equations, a variety of solution methods can be used (see solution methods). The addition method is used here as an example. To first eliminate the variable , the first equation is subtracted from the second.

${\begin{aligned}v-4s-(v+s)&=-18-62\\-5s&=-80\\\end{aligned}}$

The resulting equation is solved for the variable dividing both sides by This gives the age the son, who is 16 years old. This value for is put back into the first equation.

$v+16=62$

By solving the equation according to the variable , the age of the father can be calculated, who is 46 years old.

The task can also be solved geometrically by interpreting the two lines of the linear equation system as straight line equations. In doing so, the variable v is designated as x and the variable s as y and both equations are solved for y:

${\begin{matrix}I.&y&=&-x&+62\\{\mathit {II}}.&y&=&0,25x&+4,5\end{matrix}}$

The intersection of the two lines is the point $\textstyle (46\mid 16)$ where the first coordinate corresponds to the father's age and the second to the son's age (see graph).

The graphs of the question intersecting at point A(46;16).

Matrix form

For the treatment of linear systems of equations it is useful to combine all coefficients $a_{ij}$ into a matrix the so-called coefficient matrix:

$A={\begin{pmatrix}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{pmatrix}}$

Furthermore, all unknowns and the right-hand side of the equation system can also be combined into single-column matrices (these are column vectors):

$x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}};\qquad b={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{pmatrix}}$

Thus, a linear system of equations using matrix-vector multiplication can be written as follows

$A\cdot x=b.$

Both the coefficients $a_{ij}$ the unknowns $x_{j}$ as well as the $b_{i}$ originate from the same body . In particular

$A\in K^{{{m}\times {n}}},$ $b\in K^{{m}}$ and $x\in K^{{n}}.$

To define a linear system of equations, it is not necessary to specify the unknowns. It is sufficient to specify the expanded coefficient matrix, which is created when a column with the right-hand side equation system is added to the coefficient matrix

$\left({\begin{array}{c|c}A&b\end{array}}\right)=\left({\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{array}}\right)$

Solubility

A vector is a solution of the linear system of equations if $A\cdot x=b$ holds. Whether and how many solutions a system of equations has varies. For linear systems of equations over an infinite body three cases can occur:

The linear system of equations has no solution, i.e. the solution set is the empty set.
The linear system of equations has exactly one solution, i.e. the solution set contains exactly one element.
The linear system of equations has infinitely many solutions. In this case, the solution set contains an infinite number of n-tuples that satisfy all equations of the system.

Over a finite body, the number of solutions is a power of the thickness of .

Examples of solvability with geometric interpretation (intersection of two straight lines in the plane)

The two equations of the linear system of equations are each interpreted as the normal form of a straight line equation in the plane.

Clear solution:

${\begin{matrix}2x_{1}&-x_{2}&=&4\\x_{1}&+3x_{2}&=&-5\\\end{matrix}}$

The two equations of the straight line are:

${\begin{pmatrix}2\\-1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=4\quad$ and $\quad {\begin{pmatrix}1\\3\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=-5$ .

The two normal vectors are not collinear, so the two straight lines are neither parallel nor identical and therefore intersect at a point.

The intersection $\textstyle (1\mid -2)$ means that the solutions are $x_{1}=1\$ and $\ x_{2}=-2$ solution set is $\textstyle L=\{1,-2\}$ .

No solution:

${\begin{matrix}2x_{1}&-x_{2}&=&4\\4x_{1}&-2x_{2}&=&1\\\end{matrix}}$

The corresponding straight line equations are

${\begin{pmatrix}2\\-1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=4\quad$ and $\quad {\begin{pmatrix}4\\-2\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=1$ .

The normal vectors are collinear. Since the two straight lines are not identical, they are parallel.

There are therefore no intersection points and therefore no solution. The solution set is empty: $\textstyle L=\{\}$ .

An infinite number of solutions:

${\begin{matrix}2x_{1}&-x_{2}&=&4\\4x_{1}&-2x_{2}&=&8\\\end{matrix}}$

The two equations of the straight line are:

${\begin{pmatrix}2\\-1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=4\quad$ and $\quad {\begin{pmatrix}4\\-2\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=8$ .

The normal vectors are collinear, the two straight lines are identical.

There are therefore infinitely many intersections and thus also infinitely many solutions. The solution set is $\textstyle L=\{(x\mid y)\mid 2x_{1}-x_{2}=4\}$ .

Corresponding considerations can also be applied to planes in space or hyperplanes in n-dimensional vector space.

Solvability criteria

A linear system of equations is solvable if the rank of the coefficient matrix is equal to the rank of the extended coefficient matrix $(A\mid b)$ (Kronecker-Capelli theorem). If the rank of the coefficient matrix is equal to the rank of the extended coefficient matrix and also equal to the number of unknowns, the system of equations has exactly one solution.

For a quadratic system of equations, i.e. in the case m=n (see below), the determinant provides information about the solvability. The system of equations is uniquely solvable exactly when the value of the determinant of the coefficient matrix is not equal to zero. However, if the value is equal to zero, the solvability depends on the values of the secondary determinants. For these, one column of the coefficient matrix is replaced by the column of the right-hand side (the vector ). Only if all secondary determinants have the value zero can the system have an infinite number of solutions, otherwise the system of equations is unsolvable.

In particular, systems of equations with more equations than unknowns, so-called overdetermined systems of equations, often have no solution. For example, the following system of equations has no solution because $x_{1}$ cannot satisfy both equations:

${\begin{matrix}3x_{1}&=&2\\4x_{1}&=&2\end{matrix}}$

Approximate solutions of overdetermined equation systems are then usually defined and determined via the balancing calculation.

That a linear system of equations has infinitely many solutions can only occur if there are fewer linearly independent equations as unknowns and the underlying body contains infinitely many elements. For example, the following system of equations (consisting of only one equation) has infinitely many solutions, namely all vectors with $x_{2}=1-x_{1}:$

$x_{1}+x_{2}=1$

Solution set

The solution set of a linear system of equations consists of all vectors for which Ax=b is satisfied:

$L=\left\{x\mid Ax=b\right\}$

If there is a homogeneous linear system of equations, its solution set forms a subvector space of $K^{n}.$ Thus the superposition property holds, according to which for one or more solutions $x_{i}\in K^{n}$ also their linear combinations $\textstyle \sum \alpha _{i}\,x_{i}$ (with any α $\alpha _{i}\in K$ ) are solutions of the system of equations. The solution set is therefore also called the solution space and is identical to the kernel of the matrix If denotes the rank of the matrix then according to the rank theorem the dimension of the solution space is equal to the defect $d=n-r$ the matrix

If the solution set of an inhomogeneous linear system of equations is non-empty, then it is an affine subspace of $K^{n}.$ It then has the form v+U, where is the solution space of the associated homogeneous system of equations and any solution of the inhomogeneous system of equations. Consequently, an inhomogeneous system of equations is uniquely solvable exactly when the zero vector is the only solution ("trivial solution") of the homogeneous system of equations. In particular, either $L=\emptyset$ or $\operatorname {dim}(L)=n-r$ with $r=\operatorname {Rang}(A).$

The solution set of a linear system of equations does not change when one of the three elementary row transformations is performed:

Swap two lines
Multiplying a row by a non-zero number
Adding a row (or the multiple of a row) to another row

The solution set of a quadratic linear system of equations does not change even if the system of equations is multiplied by a regular matrix.

Determination via the extended coefficient matrix

The form of the solution set can basically be determined with the help of the extended coefficient matrix by putting it into step form with the help of elementary row transformations (see Gaussian method):

$\left({\begin{array}{cccccc|c}a_{11}&a_{12}&\cdots &a_{1k}&\cdots &a_{1n}&b_{1}\\0&a_{22}&\cdots &a_{2k}&\cdots &a_{2n}&b_{2}\\\vdots &\ddots &\ddots &\vdots &\ddots &\vdots &\vdots \\0&\cdots &0&a_{kk}&\cdots &a_{kn}&b_{k}\\\vdots &\ddots &\vdots &0&\cdots &0&\vdots \\0&\cdots &0&0&\cdots &0&b_{m}\\\end{array}}\right)$

In order to always obtain exactly this form, one must sometimes also carry out column swaps. Column swaps change the order of the variables, which must be taken into account at the end. Furthermore, it is also assumed here that the coefficients $a_{jj},j=1,\dotsc ,k$ not zero.

The number of solutions can then be read from the $b_{i}$

If at least one of the $b_{k+1},\dotsc ,b_{m}$ non-zero, there is no solution.
If all are $b_{k+1},\dotsc ,b_{m}$ equal to zero (or $k=m$ ), then holds:

If then the system of equations is uniquely solvable.
If there are infinitely many solutions. The solution space has the dimension .

By further elementary row transformations (see Gauss-Jordan method) the matrix can be brought into the following form:

$\left({\begin{array}{ccccccc|c}1&0&\cdots &0&a_{1,k+1}&\cdots &a_{1n}&b_{1}\\0&1&\ddots &0&a_{2,k+1}&\cdots &a_{2n}&b_{2}\\\vdots &\ddots &\ddots &\vdots &\vdots &\ddots &\vdots &\vdots \\0&\cdots &0&1&a_{k,k+1}&\cdots &a_{kn}&b_{k}\\\vdots &\ddots &\vdots &0&\cdots &\cdots &0&\vdots \\0&\cdots &0&0&\cdots &\cdots &0&b_{m}\\\end{array}}\right)$

If there is a solution at all ( $b_{k+1},\dotsc ,b_{m}=0$ ), the solution set :

$L=\left\{{\begin{array}{c|c}\left({\begin{array}{c}b_{1}\\\vdots \\b_{k}\\0\\\vdots \\0\\\end{array}}\right)+\left({\begin{array}{cccc}-a_{1,k+1}&-a_{1,k+2}&\cdots &-a_{1n}\\\vdots &\ddots &\ddots &\vdots \\-a_{k,k+1}&-a_{k,k+2}&\cdots &-a_{kn}\\1&0&\cdots &0\\0&1&\ddots &\vdots \\\vdots &\ddots &\ddots &0\\0&\cdots &\cdots &1\\\end{array}}\right)\cdot {\begin{pmatrix}s_{k+1}\\s_{k+2}\\\vdots \\s_{n}\end{pmatrix}}&{\begin{pmatrix}s_{k+1}\\s_{k+2}\\\vdots \\s_{n}\end{pmatrix}}\in K^{n-k}\end{array}}\right\}$

Here $s={\begin{pmatrix}s_{k+1}\\s_{k+2}\\\vdots \\s_{n}\end{pmatrix}}$ is the vector of free variables.

Forms of systems of equations

Linear systems of equations can exist in forms in which they can be easily solved. In many cases, arbitrary systems of equations are given an appropriate form by means of an algorithm in order to subsequently find a solution.

Square

We speak of a quadratic system of equations when the number of unknowns is equal to the number of equations. A system of equations of this form can be solved uniquely if the rows or columns are linearly independent (solution methods are discussed below).

Step shape, stair shape

In the step form (also row step form, row normal form, step form, stair step form or stair normal form), the number of unknowns is reduced by at least one in each row, which then also no longer occurs in the following rows. By applying the Gaussian elimination method, any system of equations can be brought into this form.

Example (the coefficients of omitted elements are $0$ ):

${\begin{matrix}6x_{1}&+&3x_{2}&+&4x_{3}&=&1\\&&&-&5x_{3}&=&10\end{matrix}}$

Linear systems of equations in step form can be solved by inserting them backwards (back substitution). Starting with the last line, the unknown is calculated and the result obtained is inserted into the line above in order to calculate the next unknown.

Solution of the above example:

Resolve the second line to $x_{3}:$

$x_{3}={\frac {10}{-5}}=-2$

Insert $x_{3}$ into the first line:

$6x_{1}+3x_{2}+4\cdot (-2)=1$

Resolve the first line to $x_{2}:$

$x_{2}=-2x_{1}+3$

With $x_{1}=t$ all vectors of the form are ${\begin{pmatrix}t\\-2t+3\\-2\end{pmatrix}}$ solutions of the system of equations.

Triangular shape

The triangular form is a special case of the step form, where each line has exactly one less unknown than the previous one. This means that all coefficients $a_{{ii}}$ the main diagonal $0$ are different from The triangular form arises when using the Gaussian elimination method if the system of equations has exactly one solution.

Example (the coefficients of omitted elements are $0$ ):

${\begin{matrix}6x_{1}&+&3x_{2}&+&4x_{3}&=&1\\&&8x_{2}&+&5x_{3}&=&-1\\&&&-&2x_{3}&=&6\end{matrix}}$

Like linear systems of equations in step form, those in triangular form can also be solved by substituting backwards.

Reduced step form

The reduced step form (also normalised row step form) is a special case of the step form. In this form, the first unknowns of each row occur only once and have the coefficient The reduced step form of a linear system of equations is unique: there is therefore exactly one reduced step form for each linear system of equations. By applying the Gauss-Jordan algorithm, any system of linear equations can be transformed into this form.

Example (the coefficients of omitted elements are $0$ ):

${\begin{matrix}x_{1}&&&&&+&4x_{4}&=&-1\\&&x_{2}&&&-&5x_{4}&=&-9\\&&&&x_{3}&-&7x_{4}&=&10\end{matrix}}$

The solution of the linear system of equations can now be read off directly: Provided $x_{4}=t$ set and the system of equations is solved recursively, all vectors of the form $(-4t-1,5t-9,7t+10,t)^{T}$ as solutions.

Other forms

Relevant in practice are the special cases of sparse matrices (very large matrices with relatively few non-zero elements) and band matrices (likewise large matrices whose non-vanishing elements are concentrated around the main diagonal), which can be handled with specially adapted solution methods (see below).

Solution procedure

The methods for solving systems of linear equations are divided into iterative and direct methods. Examples of direct methods are the substitution method, the equation method and the addition method for simple systems of equations as well as the Gaussian elimination method based on the addition method, which brings a system of equations to step form. A variant of the Gaussian method is the Cholesky decomposition, which only works for symmetrical, positive definite matrices. The QR decomposition requires twice as much effort as the Gaussian method, but is more stable. Cramer's rule uses determinants to generate formulae for solving a quadratic linear system of equations if it is uniquely solvable. However, it is not suitable for numerical calculation due to the high computational effort involved.

Iterative methods are, for example, the Gauss-Seidel and Jacobi methods, which belong to the class of splitting methods. These do not converge for every matrix and are very slow for many practical problems. More modern methods are, for example, preconditioned Krylov subspace methods, which are very fast especially for large sparse matrices, as well as multigrid methods for solving systems that originate from the discretisation of certain partial differential equations.

In applications (e.g. geodesy), measurements of different types are often made and, to reduce the effect of measurement errors, more measurements are made than unknowns to be determined. Each measurement provides an equation for determining the unknowns. If these equations are not all linear, the system of equations is linearised using known approximations of the unknowns. Then, instead of the actual unknowns, their small deviations from the approximate values are to be determined. As a rule, the equations contradict each other if there are more equations than unknowns, so that there is no strict solution. As a way out, a solution is then usually determined by balancing using the method ofleast squares, which typically does not fulfil any equation exactly, but gives an optimal approximation of the "true" measured quantities under reasonable assumptions about the measurement errors.

The best currently known asymptotic upper bound on arithmetic operations to solve an arbitrary system of linear equations is provided by a practically inapplicable algorithm by Don Coppersmith and Shmuel Winograd in 1990 that solves an $n\times n$ system in O(n2^,376). It is clear that at least O(n2) operations are necessary; but not whether this lower bound can also be achieved.

Almost singular linear systems of equations can be solved passably in a numerical way by singular value decomposition.

System of linear equations

Geometric interpretation

Example

Matrix form

Solubility

Solvability criteria

Solution set

Determination via the extended coefficient matrix

Forms of systems of equations

Square

Step shape, stair shape

Triangular shape

Reduced step form

Other forms

Solution procedure

Search by letter