Skip to content
Home

System of Linear Equations

Overview of systems of linear equations: definitions, structure, solution types and common methods, brief history, and practical applications across science and engineering.

Author: Created: Updated:

A system of linear equations is a set of two or more linear relations that share the same variables. Each equation expresses a straight-line relationship between variables and constants. Systems arise when several constraints must be satisfied simultaneously and provide the foundation for much of linear algebra and applied mathematics. For basic context see mathematics, and for the single-equation building blocks see linear equations. The unknown quantities in these equations are the variables they have in common.

Image gallery

3 Images
Secretsharing-3-point
simple.wikipedia.org · CC BY-SA 3.0

Characteristics and canonical forms

Systems can be written in several equivalent ways: as a list of equations, in augmented matrix form, or compactly using matrix notation A x = b. Important characteristics include the number of equations versus variables, coefficient structure (sparse or dense), and whether coefficients are numbers from real, complex, or other fields. The solution set falls into one of three categories: a single unique solution, no solution (inconsistent), or infinitely many solutions (dependent).

Common solution methods

People solve linear systems with hand and computer techniques. Elementary approaches include substitution and elimination for small systems. Systematic methods used in classrooms and software include Gaussian elimination, Gauss-Jordan reduction, LU decomposition, and methods drawing on determinants like Cramer's rule (limited to square nonsingular systems). For large or structured systems, iterative methods such as Jacobi, Gauss–Seidel, and conjugate gradient are important in numerical computing.

Brief history and development

Solving simultaneous linear relations dates back to ancient civilizations that solved multiple unknowns in practical problems. The algebraic formalism evolved over centuries into modern matrix and vector representations, which clarified existence and uniqueness through rank and linear independence concepts. The 19th and 20th centuries saw the rise of systematic linear algebra and numerical analysis to handle increasingly complex and large-scale systems.

Applications and examples

Systems of linear equations model many practical problems: circuit analysis, structural mechanics, economic equilibrium, image processing, and data fitting. A simple example is two equations in two unknowns such as x + 2y = 5 and 3x - y = 4, which can be solved by elimination to find the pair (x,y) that satisfies both constraints simultaneously. In engineering and science, large systems produced by discretizing physical models are solved with optimized numerical libraries.

Distinctions and notable facts

  • Rank determines consistency: if the augmented matrix has greater rank than the coefficient matrix, the system is inconsistent.
  • Square systems (same number of independent equations and unknowns) may be nonsingular (unique solution) or singular (no or many solutions).
  • Practical computation emphasizes stability, sparsity, and efficiency when choosing algorithms for large-scale problems.

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)

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

can be represented as

{\displaystyle {\vec {n}}_{i}\cdot {\vec {x}}=b_{i}}with a normal vector {\displaystyle {\vec {n}}_{i}={\begin{pmatrix}a_{i1}\\a_{i2}\\\vdots \\a_{in}\end{pmatrix}}\qquad }and a position vector {\displaystyle \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:

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

The variable vhere represents the father's age and the variable sthat 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.

{\displaystyle {\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 v, the first equation is subtracted from the second.

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

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

{\displaystyle v+16=62}

By solving the equation according to the variable v, 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:

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

The intersection of the two lines is the point {\displaystyle \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).
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 A,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 K. 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 Aequation system is added to the coefficient matrix b

{\displaystyle \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 xis a solution of the linear system of equations if A\cdot x=bholds. Whether and how many solutions a system of equations has varies. For linear systems of equations over an infinite body three cases can occur: K

  • 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 K.

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:

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

The two equations of the straight line are:

{\displaystyle {\begin{pmatrix}2\\-1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=4\quad }and {\displaystyle \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 {\displaystyle \textstyle (1\mid -2)}means that the solutions are {\displaystyle x_{1}=1\ }and {\displaystyle \ x_{2}=-2}solution set is {\displaystyle \textstyle L=\{1,-2\}}.

  • No solution:

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

The corresponding straight line equations are

{\displaystyle {\begin{pmatrix}2\\-1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=4\quad }and {\displaystyle \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: {\displaystyle \textstyle L=\{\}}.

  • An infinite number of solutions:

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

The two equations of the straight line are:

{\displaystyle {\begin{pmatrix}2\\-1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=4\quad }and {\displaystyle \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 {\displaystyle \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 Aequal 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 b). 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 Kcontains 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 x,for which Ax=bis satisfied:

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

If there is a homogeneous linear system of equations, its solution set Lforms 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 {\displaystyle \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 A.If rdenotes the rank of the matrix A,then according to the rank theorem the dimension of the solution space is equal to the defect {\displaystyle d=n-r}the matrix A.

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 Uis the solution space of the associated homogeneous system of equations and vany 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-rwith 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:

  1. Swap two lines
  2. Multiplying a row by a non-zero number
  3. 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):

{\displaystyle \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 {\displaystyle 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 {\displaystyle b_{k+1},\dotsc ,b_{m}}non-zero, there is no solution.
  • If all are {\displaystyle b_{k+1},\dotsc ,b_{m}}equal to zero (or {\displaystyle k=m}), then holds:
    • If k=nthen the system of equations is uniquely solvable.
    • If k<nthere are infinitely many solutions. The solution space has the dimension n - k.

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

{\displaystyle \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 ( {\displaystyle b_{k+1},\dotsc ,b_{m}=0}), the solution set L:

{\displaystyle 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 {\displaystyle 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 {\displaystyle 0}):

{\displaystyle {\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:

  1. Resolve the second line to x_{3}:

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

  1. Insert x_{3}into the first line:

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

  1. Resolve the first line to x_{2}:

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

  1. With x_{1}=tall 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 {\displaystyle 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 {\displaystyle 0}):

{\displaystyle {\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 1.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 {\displaystyle 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}=tset 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 nsystem 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.

Related articles

Author

AlegsaOnline.com System of Linear Equations

URL: https://en.alegsaonline.com/art/95722

Share

Sources