Systems of linear equations

A linear system of equations is a set of m linear equations about n variables. By solving the equations, we get values that we can substitute in for our n variables so that all the equations make sense.

Definition of a system of linear equations

You must have come across some simple system of the type

$$ \begin{array}{ccccc} a_{11}x &+&a_{12}y &=& b_1\\ a_{21}x &+&a_{22}y &=&b_2\\ \end{array} $$

where $a_{11},…,a_{22}, b_1, b_2$ are the given real numbers and x and y are the variables. This system of equations can have different numbers of solutions - none, one or infinitely many, just like a classical linear equation. In the case of a system of linear equations, the question of the number of solutions and finding them is more complicated than in the case of a simple linear equation.

Definition of a system of linear equations:

$$ \begin{array}{ccccccccc} a_{11}x_1&+&a_{12}x_2&+&\ldots&+&a_{1n}x_n&=&b_1\\ a_{21}x_1&+&a_{22}x_2&+&\ldots&+&a_{2n}x_n&=&b_2\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ a_{m1}x_1&+&a_{m2}x_2&+&\ldots&+&a_{mn}x_n&=&b_n\\ \end{array} $$

where $a_{11}, …, a_{mn}, b_1, …, b_m$ are real numbers. This system is then called a system m of linear equations of n unknowns x₁, …, x_n with coefficients $a_{11}, …, a_{mn}$. A concrete example of a system of linear equations might look like this:

$$ \begin{array}{ccccccccc} 3x_1&+&-2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&+&4x_2&+&2x_3&+&-10x_4&=&2\\ 11x_1&+&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

But if any a_ij is negative, it is customary to write it in this form:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&+&4x_2&+&2x_3&-&10x_4&=&2\\ 11x_1&+&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

However, it is still true that a₁₂ = −2 and a₂₄ = −10.

Matrix notation

We can convert this system into matrix form. We define a total of three matrices, one for the coefficients, one for the right-hand side of the equations, and one for the variables themselves. The matrices will then look like this:

$$ A= \begin{pmatrix} a_{11}&a_{12}&…&a_{1n}\\ a_{21}&a_{22}&…&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&…&a_{mn} \end{pmatrix}, \quad b= \begin{pmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{pmatrix}, \quad x= \begin{pmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{pmatrix} $$

The matrix A contains the coefficients of the original equations and is called the "system matrix", the matrix b contains the right-hand sides of the equations, and the matrix x contains the variables. Then we can write the whole system of equations as the equation

$$Ax,=,b$$

This equation makes sense because on the left-hand side we have the product of two matrices and on the right-hand side we have a matrix, and their dimensions are the same. We can try multiplying the left side. We multiply a matrix of type m × n by a matrix of type n × 1, so the resulting matrix will be of type m × 1, with m rows and one column. For now, that's fine.

Now we perform the classic matrix multiplication algorithm, starting with the first row of the matrix A and the first column of the matrix x (there is no other column). We get:

$$a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n$$

With this sum, we have obtained the first element of the new matrix, the value of b₁. Plugging the whole thing into the equation, we have:

$$a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n = b_1$$

We have obtained exactly the first equation of our system of equations. We would continue in the same way for the other rows. We still define the extended system matrix, which is the system matrix to which we add the matrix b as follows:

$$ B=(A|b)= \begin{pmatrix} a_{11}&a_{12}&…&a_{1n}&b_1\\ a_{21}&a_{22}&…&a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{m1}&a_{m2}&…&a_{mn}&b_m \end{pmatrix} $$

Next, we will be interested in the rank of this extended system matrix. We denote the rank of the original unexpanded system matrix by rank(A), and the rank of the expanded one by rank(A|b). What is the relationship between these ranks? If we add a column b to the matrix A, two situations can occur: if this new column is a linear combination of the columns of the matrix A, then the rank does not change. If it was not a linear combination, then the rank will be one more.

Frobenius Theorem

The rank of the augmented matrix will be important to us because an important theorem, Frobenius' theorem, holds: a system of equations Ax = B has a solution if and only if the rank of the system matrix is equal to the rank of the augmented system matrix: rank(A) = rank(A|b).

Let's try to show that this theorem is true in at least one direction - if x = β is a solution of the equation Ax = b, then rank(A) = rank(A|b). If these ranks are equal, then it must hold that the column b is a linear combination of the columns of the matrix A. Let's break this down. The matrix β has the form:

$$ \beta=\begin{pmatrix} \beta_1\\ \beta_2\\ \vdots\\ \beta_n \end{pmatrix} $$

And we claim that if we substitute β₁ etc. after x₁, then all the equations in the system of equations are valid:

$$ \begin{array}{ccccccccc} a_{11}\beta_1&+&a_{12}\beta_2&+&\ldots&+&a_{1n}\beta_n&=&b_1\\ a_{21}\beta_1&+&a_{22}\beta_2&+&\ldots&+&a_{2n}\beta_n&=&b_2\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ a_{m1}\beta_1&+&a_{m2}\beta_2&+&\ldots&+&a_{mn}\beta_n&=&b_m\\ \end{array} $$

Now let's rewrite the equations a bit. If we look at the first column, we find that there are always values of $a_{11}, a_{21}, …, a_{m1}$, which we multiply by the same value of β₁. If we isolate the column into a separate matrix, we can put the rank of β₁ in front of the matrix, giving us:

$$ \begin{pmatrix} a_{11}\beta_1\\ a_{21}\beta_1\\ \vdots\\ a_{m1}\beta_1 \end{pmatrix} =\beta_1 \begin{pmatrix} a_{11}\\ a_{21}\\ \vdots\\ a_{m1} \end{pmatrix} $$

We can now rewrite the whole system in this way:

$$ \beta_1\begin{pmatrix} a_{11}\a_{21}\a_vdots\a_{m1} \end{pmatrix} + \beta_2\begin{pmatrix} a_{12}\a_{22}\a_vdots\a_{m2} \end{pmatrix} +...+ \beta_n\begin{pmatrix} a_{1n}\a_{2n}\a_{2n}\a_{vdots\a_{mn}\end{pmatrix} \begin{pmatrix} b_1\b_2\vdots\a_m \end{pmatrix} $$

For this equation to hold, the column matrices on the left-hand side must be a linear combination of the matrix on the right-hand side, and the values of β₁, …, β_n must be their coefficients.

Thus, we have proved that for a matrix β to be a solution to a system of equations, the right-hand side of the system, the matrix b, must be a linear combination of the columns of the matrix of the system. And if a column from the matrix b is a linear combination of the columns of the matrix A, then the matrix A must have the same value as the matrix (A|b).

At the same time, if rank(A) = rank(A|b) = k and k are equal to the number of unknowns, i.e. k = n, then the system has exactly one solution. If k < n, then the system has infinitely many solutions and we will need n − k parameters to write it down.

Elementary linear modifications

Next, we can see from the previous equation that if we make elementary row adjustments to the matrix (A|b), the solution of the system of equations will not change. If we added the first row to the second row, we would get Eq:

$$ \beta_1\begin{pmatrix} a_{11}\a_{21}+a_{11}\a_{11}\a_vdots\a_{m1} \end{pmatrix} + \beta_2\begin{pmatrix} a_{12}\a_{22}+a_{12}\a_{12}\a_vdots\a_{m2} \end{pmatrix} +...+ \beta_n \begin{pmatrix} a_{1n}\\a_{2n}+a_{1n}\a_{1n}\a_{vdots\a_{mn} \end{pmatrix} \begin{pmatrix} b_1\a_2+b_1\a_vdots\a_{m} \end{pmatrix} $$

If we break down the second line, we get:

$$\beta_1(a_{21}+a_{11})+\beta_2(a_{22}+a_{12})+\ldots+\beta_n(a_{2n}+a_{1n})=b_1+b_2$$

Multiply the parentheses:

$$\beta_1a_{21}+\beta_1a_{11}+\beta_2a_{22}+\beta_2a_{12}+\ldots+\beta_na_{2n}+\beta_na_{1n}=b_1+b_2$$

Now we're just going to rearrange it a little bit:

$$(\beta_1a_{11}+\beta_2a_{12}+\ldots+\beta_na_{1n})+(\beta_1a_{21}+\beta_2a_{22}+\ldots+\beta_na_{2n})=b_1+b_2$$

We actually have the first line in the first parenthesis and the original second line in the second parenthesis. We know that the first row is equal to b₁ and the second row is equal to b₂. We know this from the original equations. So we can write b₁ after the first bracket and b₂ after the second bracket:

$$b_1+b_2=b_1+b_2.$$

Similarly, we can multiply the entire row by the constant c ≠ 0 and not change the validity of the system of equations. Note, however, that we cannot make column adjustments.

A system with one solution

We will use an example to show how to solve a system that has exactly one solution. Let us have such a system of equations:

$$ \begin{array}{ccccccc} 2x_1&+&3x_2&+&7x_3&=&47\\ 3x_1&+&8x_2&+&x_3&=&50\\ &&3x_2&+&3x_3&=&27\\ \end{array} $$

The matrix A will look like this:

$$ A=\begin{pmatrix} 2&3&7\\ 3&8&1\\ 0&3&3 \end{pmatrix} $$

Now we calculate the rank of this matrix:

$$ \begin{pmatrix} 2&3&7\\ 3&8&1\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 6&16&2\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&7&-19\\ 0&3&3 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&21&-57\\ 0&21&21 \end{pmatrix} \sim \begin{pmatrix} 6&9&21\\ 0&21&-57\\ 0&0&78 \end{pmatrix} $$

We see that rank(A) = 3. It also implies that rank(A|b) = 3, since a matrix of type 3 × 4 can have a maximum rank of three. The system has three unknowns, so the whole system has exactly one solution. How do we find it?

Gaussian elimination method

Gaussian elimination involves modifying the augmented matrix of the system to a stepwise form. By converting the matrix to a stepwise form, we are able to find the value of one variable. Once we find the value of one variable, we can start plugging that value into the other equations.

The matrix (A|b) has the form:

$$ (A|b)=\begin{pmatrix} 2&3&7&47\\ 3&8&1&50\\ 0&3&3&27 \end{pmatrix} $$

Let's convert it to a stepped form. We will make the same adjustments as in the previous step, only this time we will apply them to the fourth column:

$$\begin{eqnarray} \begin{pmatrix} 2&3&7&47\\ 3&8&1&50\\ 0&3&3&27 \end{pmatrix} &\sim& \begin{pmatrix} 6&9&21&141\\ 6&16&2&100\\ 0&3&3&27 \end{pmatrix} \\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&7&-19&-41\\ 0&3&3&27 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&21&-57&-123\\ 0&21&21&189 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&9&21&141\\ 0&21&-57&-123\\ 0&0&78&312 \end{pmatrix}\\ \end{eqnarray}$$

Since we have made elementary row adjustments, this matrix describes an equivalent system of equations - a system that has the same set of solutions. Let's rewrite the system from matrix notation to ordinary notation, using the coefficients from our last matrix:

$$ \begin{array}{ccccccc} 6x_1&+&9x_2&+&21x_3&=&141\\ &&21x_2&-&57x_3&=&-123\\ &&&&78x_3&=&312\\ \end{array} $$

Now we come out of the last equation. This tells us that 78x₃ = 312. What value must x₃ have ? This is a simple linear equation, so

$$\begin{eqnarray} 78x_3&=&312\\ x_3&=&\frac{312}{78}\\ x_3&=&4 \end{eqnarray}$$

We have the value of the first variable, x₃. We plug that value into the second equation. We get the equation:

$$\begin{eqnarray} 21x_2-57x_3&=&-123\\ 21x_2-57\cdot4&=&-123\\ 21x_2&=&-123+228\\ 21x_2&=&105\\ x_2&=&\frac{105}{21}\\ x_2&=&5 \end{eqnarray}$$

And finally, we plug the two calculated values into the first equation:

$$\begin{eqnarray} 6x_1+9x_2+21x_3&=&141\\ 6x_1+9\cdot5+21\cdot4&=&141\\ 6x_1+45+84&=&141\\ 6x_1&=&12\\ x_1&=&2 \end{eqnarray}$$

The value of the variable x₁ is equal to two. At this point we have a complete solution. We can write that x = (x₁, x₂, x₃) = (2, 5, 4). As you can see, the Gaussian elimination method is a simple but effective method to solve a system of linear equations.

Infinitely many solutions

If rank(A) = rank(A|b) = k and k is less than the number of unknowns, k < n, then the system has infinitely many solutions. Consider a simple example:

$$ \begin{array}{cccccc} 4x_1&+&x_2&=&5\\ 12x_1&+&3x_2&=&15\\ \end{array} $$

We see that the second equation is equal to three times the first equation. If we multiply the first equation by minus three and add it to the second line, we get:

$$ \begin{array}{cccccc} 4x_1&+&x_2&=&5\\ 0x_1&+&0x_2&=&0\\ \end{array} $$

At this point we have the number of variables equal to two, n = 2, the rank of the system matrix is equal to one, rank(A) = 1, and the rank of the augmented matrix is also equal to one, rank(A|b) = 1. It is true that k < n, so the system has infinitely many solutions. How do we find these solutions?

Let's look at the equations. The second equation is satisfied for all x₁, x₂, so we will only be interested in the first equation. In fact, all pairs of x₁, x₂, which satisfy the first equation, will form the set of all solutions of the given system of equations. So we compute the solution to 4x₁ + x₂ = 5. We modify the equation to form x₂ = 5 − 4x₁.

Next, we'll use the parameter. We choose the parameter t. Now we will try to express the pair x₁, x₂ using the parameter t so that we can write that, for example, all pairs of the form (t, t + 2) are solutions of the system. That is, pairs like (1, 3) or (14, 16). The point is to express the value of one variable using another variable so that we know that if the value of x₁ is such and such a poppy, the value of x₂ will be three times as large, for example. We choose x₁ as the starting point.

Thus, we set the equality t = x₁. If the variable x₁ has the value t, what value will the variable x₂ have ? We can see this from the previous equation, it will have the value x₂ = 5 − 4x₁. Thus if x₁ = t, then x₂ = 5 − 4t. We can thus write that all pairs of the form (t, 5 − 4t) are solutions of the system of equations.

We can check this. If we substitute one after t, we have: x₁ = 1 and x₂ = 5 − 4 · 1 = 1. Substituting these values into the equation: 4 · 1 + 1 = 5, the equation fits.

If we put five after t, we have: x₁ = 5, x₂ = 5 − 4 · 5 = −15. After plugging them into the equation, we have: 4 · 5 − 15 = 5. It fits.

General and partial solutions

A solution to a system of equations that is written using parameters is called a general solution. A specific solution, i.e., if we substitute specific numbers after the parameters, is called a partial solution.

So from the previous example: (x₁, x₂) = (t, 5 − 4t) is the general solution of the system of equations, (1, 1) and (5, −15) are the partial solutions.

If we have a system matrix A and an extended system matrix (A|b) and their ranks are equal, rank(A) = rank(A|b) = k, then we need n − k parameters to express the general solution. Note that if n = k, then we need zero parameters. This is the case when the system has exactly one solution - no parameter is then needed.

Example

Solve the following system of linear equations:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&-&4x_2&+&2x_3&+&10x_4&=&2\\ 11x_1&-&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

First, we calculate the rank of the matrices A and (A|b). We convert the augmented matrix to a stepwise form, from which we find the rank of both matrices. We go to edit. (We multiply the first row by two, then add the first and second rows and subtract this result from the third row. Next, we subtract the first row from the second row and finally divide the first row back by two.)

$$\begin{eqnarray} (A|b)=\begin{pmatrix} 3&-2&4&5&1\\ 5&-4&2&10&2\\ 11&-8&10&20&4 \end{pmatrix} &\sim& \begin{pmatrix} 6&-4&8&10&2\\ 5&-4&2&10&2\\ 11&-8&10&20&4 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&-4&8&10&2\\ 5&-4&2&10&2\\ 0&0&0&0&0 \end{pmatrix}\\ &\sim& \begin{pmatrix} 6&-4&8&10&2\\ -1&0&-6&0&0\\ 0&0&0&0&0 \end{pmatrix}\\ &\sim& \begin{pmatrix} 3&-2&4&5&1\\ -1&0&-6&0&0\\ 0&0&0&0&0 \end{pmatrix}\\ \end{eqnarray}$$

From this last matrix we can already see that rank(A) = rank(A|b) = k = 2. The number of unknowns is n = 4, so we will need n − k = 2 parameters. Let's express the equations according to the last matrix:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ -x_1&&&-&6x_3&&&=&0\\ \end{array} $$

From the second equation we get

$$\begin{eqnarray} -x_1-6x_3&=&0\\ -x_1&=&6x_3\\ x_1&=&-6x_3 \end{eqnarray}$$

We choose the first parameter, t = x₃. Then we can write that x₁ = −6t. We can plug this into the first equation:

$$\begin{eqnarray} 3(-6t)-2x_2+4t+5x_4&=&1\\ -18t-2x_2+4t+5x_4&=&1\\ -14t-2x_2+5x_4&=&1\\ -2x_2&=&1+14t-5x_4\\ x_2&=&-\frac12-7t+\frac52x_4 \end{eqnarray}$$

We plug in the second parameter, s = x₄. Then we can write that

$$x_2=-\frac12-7t+\frac52s$$

This gives us the general solution of the system:

$$(x_1, x_2, x_3, x_4) = (-6t, -\frac12-7t+\frac52s, t, s)$$

We can try some partial solutions. For example, s = t = 0. Then we get: $(x_1, x_2, x_3, x_4) = (0, -\frac12, 0, 0)$. After plugging in the original equations:

$$ \begin{array}{ccccccccc} 3x_1&-&2x_2&+&4x_3&+&5x_4&=&1\\ 5x_1&-&4x_2&+&2x_3&+&10x_4&=&2\\ 11x_1&-&8x_2&+&10x_3&+&20x_4&=&4\\ \end{array} $$

we get the equations:

$$ \begin{array}{ccccccccc} 0&-&2\frac12&+&0x_3&+&0x_4&=&1\\ 0x_1&-&4\frac12&+&0x_3&+&0x_4&=&2\\ 0x_1&-&8\frac12&+&0x_3&+&0x_4&=&4\\ \end{array} $$

After removing the zero elements and multiplying the fractions, we get:

$$\begin{eqnarray} 1&=&1\\ 2&=&2\\ 4&=&4 \end{eqnarray}$$

Let's try another partial solution: s = 2, t = 1. Then we get:

$$\begin{eqnarray} x_1&=&-6\\ x_2&=&-\frac12-7+5=-\frac52\\ x_3&=&1\\ x_4&=&2 \end{eqnarray}$$

Substitute into the equations:

$$ \begin{array}{ccccccccc} -18&-&2(-\frac52)&+&4&+&10&=&1\\ -30&-&4(-\frac52)&+&2&+&20&=&2\\ -66&-&8(-\frac52)&+&10&+&40&=&4\\ \end{array} $$

Modify:

$$ \begin{array}{ccccccccc} -4&+&5&=&1\\ -8&+&10&=&2\\ -16&+&20&=&4\\ \end{array} $$

And finally we get:

$$\begin{eqnarray} 1&=&1\\ 2&=&2\\ 4&=&4 \end{eqnarray}$$

The resulting general solution seems to be correct.

Links and resources

• O. Krupková, Linear Algebra I [PDF]
• Systems of linear equations, fav.zcu.cz, [PDF]