Systems of Linear Equations

General representation of a system of linear equations

Generally allows a linear system with m equations and n unknowns by appropriate transformations always bring in the following form:

$\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} = b_{m} \end{matrix}$

Matrix form of the linear equation system

The linear system of equations can be represented by a coefficient matrix A in matrix notation:

$(\begin{matrix} a_{11} a_{12} \dots a_{1 n} \\ a_{21} a_{22} \dots a_{2 n} \\ ⋮ \\ a_{m 1} a_{m 2} \dots a_{m n} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix})$

or short:

$A \cdot x = b$

For the definition of the equation system, an indication of the unknown is not required. With the extended coefficient matrix the system of equations can be written as follows:

$(A | b) = (\begin{matrix} a_{11} a_{12} \dots a_{1 n} \\ a_{21} a_{22} \dots a_{2 n} \\ ⋮ \\ a_{m 1} a_{m 2} \dots a_{m n} \end{matrix} | \begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix})$

To find the solution of a linear system of equations, the following three elementary row transformations are useful. The solution set does not change when the following operations:

interchanging two rows
multiplying a row by a nonzero number
adding a line (or multiple of a row) to another row

Solution of the linear system

If the extended coefficient matrix brought to triangular form (row echelon form) by means of elementary transformations, the solution can be read directly.

$(\begin{matrix} a_{11} a_{12} \dots a_{1 n} \\ 0 a_{22} \dots a_{2 n} \\ ⋮ \\ 0 0 \dots 0 a_{m n} \end{matrix} | \begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix})$

Gaussian Elimination Method

The Gaussian algorithm is based on equivalent transformations of the system of linear equations. The transformations: row interchange, multiplication of rows with non-zero factors and addition of multiples of a row with a different transform the system of equations to be solved in a simple form.

Step-by-step example for the Gaussian Elimination Method

The coefficient matrix in the example is:

$(\begin{matrix} 4.89 & 7.02 & 3.55 \\ 0.29 & 2.57 & 7.53 \\ 2.86 & 6.90 & 8.22 \end{matrix} | \begin{matrix} 1.22 \\ 1.61 \\ 2.32 \end{matrix})$

Calculation of the row echelon form (Gaussian elimination)

Division of line 1 by the element a_1,1=4.89

$(\begin{matrix} 1.00 & 1.44 & 0.73 \\ 0.29 & 2.57 & 7.53 \\ 2.86 & 6.90 & 8.22 \end{matrix} | \begin{matrix} 0.25 \\ 1.61 \\ 2.32 \end{matrix})$

Subtraction of the 1st line from the following lines. The 1st line is multiplied by the leading element of the following lines.

$(\begin{matrix} 1.00 & 1.44 & 0.73 \\ 0.00 & 2.15 & 7.32 \\ 0.00 & 2.79 & 6.14 \end{matrix} | \begin{matrix} 0.25 \\ 1.54 \\ 1.61 \end{matrix})$

Division of line 2 by the element a_2,2=2.15

$(\begin{matrix} 1.00 & 1.44 & 0.73 \\ 0.00 & 1.00 & 3.40 \\ 0.00 & 2.79 & 6.14 \end{matrix} | \begin{matrix} 0.25 \\ 0.71 \\ 1.61 \end{matrix})$

Subtraction of the 2nd line from the following lines. The 2nd line is multiplied by the leading element of the following lines.

$(\begin{matrix} 1.00 & 1.44 & 0.73 \\ 0.00 & 1.00 & 3.40 \\ 0.00 & 0.00 & -3.35 \end{matrix} | \begin{matrix} 0.25 \\ 0.71 \\ -0.39 \end{matrix})$

Division der Zeile 3 durch das Element a_3,3=-3.35

$(\begin{matrix} 1.00 & 1.44 & 0.73 \\ 0.00 & 1.00 & 3.40 \\ 0.00 & 0.00 & 1.00 \end{matrix} | \begin{matrix} 0.25 \\ 0.71 \\ 0.12 \end{matrix})$

Calculation of the reduced row echelon form (Jordan-Algorithm)

Subtraction of 1.44 times of line 2 from line 1

$(\begin{matrix} 1.00 & 0.00 & -4.15 \\ 0.00 & 1.00 & 3.40 \\ 0.00 & 0.00 & 1.00 \end{matrix} | \begin{matrix} -0.78 \\ 0.71 \\ 0.12 \end{matrix})$

Subtraction of 3.40 times the line 3 from the line 2

$(\begin{matrix} 1.00 & 0.00 & -4.15 \\ 0.00 & 1.00 & 0.00 \\ 0.00 & 0.00 & 1.00 \end{matrix} | \begin{matrix} -0.78 \\ 0.32 \\ 0.12 \end{matrix})$

Subtraction of -4.15 times of line 3 from line 1

$(\begin{matrix} 1.00 & 0.00 & 0.00 \\ 0.00 & 1.00 & 0.00 \\ 0.00 & 0.00 & 1.00 \end{matrix} | \begin{matrix} -0.29 \\ 0.32 \\ 0.12 \end{matrix})$

The solution of the linear equation system is now given in the right column.

$\begin{matrix} x_{1} & = & -0.29 \\ x_{2} & = & 0.32 \\ x_{3} & = & 0.12 \end{matrix}$

Cramers Rule

The Cramers rule uses determiants to solve a system of linear equations. For the case of a linear (N×N) system of equations with det(A) not equal to 0, the solution can be expressed in the following form:

$x = A^{-1} b$

$x_{i} = \frac{1}{det A} | \begin{matrix} a_{11} \dots b_{1} \dots a_{1 n} \\ a_{21} \dots b_{2} \dots a_{2 n} \\ ⋮ \\ a_{n 1} \dots b_{n} \dots a_{n n} \end{matrix} |$

$x_{i} = \frac{D_{i}}{D}$

The determinant in the numerator D_i from D = det A is shown by the i-th column in D is replaced by b.

Example for the application of the Cramers Rule

The coefficient matrix in the example is:

$(\begin{matrix} 9.07 & 2.2 & 5.37 \\ 7.92 & 3.82 & 0.47 \\ 0.33 & 9.06 & 7.81 \end{matrix} | \begin{matrix} 8.09 \\ 1.51 \\ 0.39 \end{matrix})$

The solution of the equation system is:

$x_{1} = \frac{1}{det(A)} | \begin{matrix} 8.09 & 2.20 & 5.37 \\ 1.51 & 3.82 & 0.47 \\ 0.39 & 9.06 & 7.81 \end{matrix} | = \frac{246.83}{474.79} = 0.52$

$x_{2} = \frac{1}{det(A)} | \begin{matrix} 9.07 & 8.09 & 5.37 \\ 7.92 & 1.51 & 0.47 \\ 0.33 & 0.39 & 7.81 \end{matrix} | = \frac{-379.94}{474.79} = -0.80$

$x_{3} = \frac{1}{det(A)} | \begin{matrix} 9.07 & 2.20 & 8.09 \\ 7.92 & 3.82 & 1.51 \\ 0.33 & 9.06 & 0.39 \end{matrix} | = \frac{454.03}{474.79} = 0.96$

Further solution methods for small systems of equations

Addition Method

In the addition method, the equations are added, so that for each addition step, a variable is eliminated. To each one of the equations to be transformed so that the corresponding variable drops out during the addition.

Example: Addition Method

$4 \cdot x - 2 \cdot y = 9$

$4 \cdot x + y = 3$

$4 \cdot x - 2 \cdot y = 9$

$8 \cdot x + 2 \cdot y = 6$

$12 \cdot x = 15$

$x = \frac{15}{12} = \frac{5}{4}$

$y = \frac{4}{2} \cdot x - \frac{9}{2}$

$y = \frac{4}{2} \cdot \frac{5}{4} - \frac{9}{2} = \frac{5}{2} - \frac{9}{2} = - 2$

1. Transformation: Multiply the second equation by 2

2. Transformation: addition of equations eliminated the variable y.

3. Forming: Division by 12 gives the solution the variable x.

4. Transformation: Resolving the first equation for y.

5. Forming: Inserting the solution for x in the equation is the solution for y.

Equating Method

Example: Equating Method

$4 \cdot x - 2 \cdot y = 9$

$4 \cdot x + y = 3$

$y = 2 x - \frac{9}{2}$

$y = 3 - 4 x$

$3 - 4 x = 2 x - \frac{9}{2}$

$6 x = 3 + \frac{9}{2} = \frac{15}{2}$

$x = \frac{15}{12} = \frac{5}{4}$

$y = \frac{4}{2} \cdot \frac{5}{4} - \frac{9}{2} = \frac{5}{2} - \frac{9}{2} = - 2$

1. Transformation: Dissolving both equations for y.

2. Forming: Equating equations.

3. Forming: Solving for x gives the solution for the variable x.

4. Forming: Insert of the solution for x in the equation for y results the solution for y.

Elimination of variables

Example: Elimination of variables

$4 \cdot x - 2 \cdot y = 9$

$4 \cdot x + y = 3$

$y = 2 x - \frac{9}{2}$

$4 x + 2 x - \frac{9}{2} = 3$

$6 x = 3 + \frac{9}{2} = \frac{15}{2}$

$x = \frac{15}{12} = \frac{5}{4}$

$y = \frac{4}{2} \cdot \frac{5}{4} - \frac{9}{2} = \frac{5}{2} - \frac{9}{2} = - 2$

1. Forming: Resolving equation for y.

2. Forming: Insertion in the other equation.

3. Forming: Solving for x gives the solution for the variable x.

4. Forming: Inserting the solution for x to y results in the resolution equation, the solution for y.

More Calculators

Here is a list of of further useful calculators and sites:

Index Linear Equations Linear Equation Systems Calculator 2x2 systems Calculator 3x3 systems Calculator NxN Cramer's rule Calculator NxN Gauss method Matrix Determinant