Systems of linear equations

A system of linear equations is a set of m linear equations in n variables. Solving the system means finding values that we can substitute for our n variables so that all the equations are true at the same time.

Definition of a system of linear equations

You have almost certainly met a simple pair of simultaneous equations like this:

$\begin{array}{ccccc} a_{11} x & + & a_{12} y & = & b_{1} \\ a_{21} x & + & a_{22} y & = & b_{2} \end{array}$

where a₁₁,…,a₂₂, b₁, b₂ are given real numbers and x and y are variables. Just like an ordinary linear equation, this system can have different numbers of solutions – none, one or infinitely many. For a system of linear equations, deciding how many solutions there are and finding them is harder than for a single linear equation.

The definition of a system of linear equations:

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

where a₁₁, …, a_mn, b₁, …, b_m are real numbers. This is called a system of m linear equations in the n unknowns x₁, …, x_n with coefficients a₁₁, …, a_mn. A specific example of a system of linear equations might look like this:

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

If some a_ij is negative, though, it is usual to write the system in this form:

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

It is still true that a₁₂ = −2 and a₂₄ = −10.

Matrix form

We can convert this system into matrix form. We define three matrices in all: one for the coefficients, one for the right-hand sides of the equations and one for the variables themselves. The matrices look like this:

$A = (\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}), b = (\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{m} \end{matrix}), x = (\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix})$

Matrix A contains the coefficients of the original equations and is called the “coefficient matrix”, matrix b contains the right-hand sides of the equations and matrix x contains the variables. We can then write the whole system as a single equation:

$A x = b$

This equation makes sense because the left-hand side is a product of two matrices and the right-hand side is a matrix, and their dimensions match. Let’s try multiplying out the left-hand side. We multiply an m × n matrix by an n × 1 matrix, so the result is an m × 1 matrix with m rows and one column. So far so good.

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

$a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n}$

This sum gives the first element of the new matrix, which is the value b₁. Putting that into the equation, we have:

$a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1}$

This is exactly the first equation of our system. We would carry on in the same way for the other rows. We also define the augmented matrix, which is the coefficient matrix with the matrix b attached as an extra column:

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

Next we are interested in the rank of this augmented matrix. We write the rank of the original coefficient matrix as rank(A) and the rank of the augmented matrix as rank(A|b). How are these ranks related? If we attach the column b to the matrix A, there are two possibilities. If the new column is a linear combination of the columns of A, the rank does not change. If it is not a linear combination of them, the rank goes up by one.

Rouché–Capelli theorem

The rank of the augmented matrix matters because of an important theorem, the Rouché–Capelli theorem (also called the Frobenius theorem): The system Ax = b has a solution if and only if the rank of the coefficient matrix equals the rank of the augmented matrix: rank(A) = rank(A|b).

Let’s show that the theorem holds in at least one direction: if x = β is a solution of Ax = b, then rank(A) = rank(A|b). If these ranks are equal, the column b must be a linear combination of the columns of A. Let’s write it out. The matrix β has the form:

$β = (\begin{matrix} β_{1} \\ β_{2} \\ ⋮ \\ β_{n} \end{matrix})$

We are claiming that if we substitute β₁ for x₁ and so on, all the equations in the system are true:

$\begin{array}{ccccccccc} a_{11} β_{1} & + & a_{12} β_{2} & + & \dots & + & a_{1 n} β_{n} & = & b_{1} \\ a_{21} β_{1} & + & a_{22} β_{2} & + & \dots & + & a_{2 n} β_{n} & = & b_{2} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m 1} β_{1} & + & a_{m 2} β_{2} & + & \dots & + & a_{m n} β_{n} & = & b_{m} \end{array}$

Now let’s rewrite the equations a little. Looking at the first column, we always have the values a₁₁, a₂₁, …, a_m1, all multiplied by the same value β₁. If we put that column into a matrix of its own, we can take out the common factor β₁ in front of the matrix, which gives:

$(\begin{matrix} a_{11} β_{1} \\ a_{21} β_{1} \\ ⋮ \\ a_{m 1} β_{1} \end{matrix}) = β_{1} (\begin{matrix} a_{11} \\ a_{21} \\ ⋮ \\ a_{m 1} \end{matrix})$

We can now rewrite the whole system in this way:

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

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

We have now shown that if the matrix β is to be a solution of the system, the right-hand side of the system, the matrix b, must be a linear combination of the columns of the coefficient matrix. And if the column b is a linear combination of the columns of A, then A must have the same rank as (A|b).

It is also true that if rank(A) = rank(A|b) = k and k equals the number of unknowns, that is k = n, then the system has exactly one solution. If k < n, the system has infinitely many solutions and we need n − k parameters to write them down.

Elementary row operations

The previous equation also shows that if we carry out elementary row operations on the matrix (A|b), the solutions of the system do not change. If we added the first row to the second row, we would get the equation:

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

Writing out the second row, we get:

$β_{1} (a_{21} + a_{11}) + β_{2} (a_{22} + a_{12}) + \dots + β_{n} (a_{2 n} + a_{1 n}) = b_{1} + b_{2}$

Expanding the brackets:

$β_{1} a_{21} + β_{1} a_{11} + β_{2} a_{22} + β_{2} a_{12} + \dots + β_{n} a_{2 n} + β_{n} a_{1 n} = b_{1} + b_{2}$

Now we just rearrange the terms a little:

$(β_{1} a_{11} + β_{2} a_{12} + \dots + β_{n} a_{1 n}) + (β_{1} a_{21} + β_{2} a_{22} + \dots + β_{n} a_{2 n}) = b_{1} + b_{2}$

The first bracket is really the first row and the second bracket is the original second row. We know that the first row equals b₁ and the second row equals b₂, from the original equations. So we can write b₁ for the first bracket and b₂ for the second:

$b_{1} + b_{2} = b_{1} + b_{2} .$

In the same way, we can multiply a whole row by a constant c ≠ 0 without changing the solutions of the system. Watch out, though: we cannot carry out column operations.

A system with one solution

Let’s use an example to see how to solve a system that has exactly one solution. Take this system of equations:

$\begin{array}{ccccccc} 2 x_{1} & + & 3 x_{2} & + & 7 x_{3} & = & 47 \\ 3 x_{1} & + & 8 x_{2} & + & x_{3} & = & 50 \\ 3 x_{2} & + & 3 x_{3} & = & 27 \end{array}$

The matrix A looks like this:

$A = (\begin{matrix} 2 & 3 & 7 \\ 3 & 8 & 1 \\ 0 & 3 & 3 \end{matrix})$

Now we work out the rank of this matrix:

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

We see that rank(A) = 3. It follows that rank(A|b) = 3 as well, because a 3 × 4 matrix can have rank three at most. The system has three unknowns, so it has exactly one solution. How do we find it?

Gaussian elimination

Gaussian elimination means reducing the augmented matrix to row echelon form. Once the matrix is in row echelon form, we can read off the value of one variable. When we have found the value of one variable, we can start substituting it into the other equations.

The matrix (A|b) is:

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

We reduce it to row echelon form. We carry out the same operations as in the previous step, but this time we apply them to the fourth column too:

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

Because we used only elementary row operations, this matrix describes an equivalent system of equations – a system with the same solution set. Let’s write the system out in ordinary form, using the coefficients from our last matrix:

$\begin{array}{ccccccc} 6 x_{1} & + & 9 x_{2} & + & 21 x_{3} & = & 141 \\ 21 x_{2} & - & 57 x_{3} & = & - 123 \\ 78 x_{3} & = & 312 \end{array}$

Now we start from the last equation. It tells us that 78x₃ = 312. What must x₃ be? This is a simple linear equation, so

$\begin{array}{rcl} 78 x_{3} & = & 312 \\ x_{3} & = & \frac{312}{78} \\ x_{3} & = & 4 \end{array}$

We have the value of the first variable, x₃. We substitute it into the second equation, which gives:

$\begin{array}{rcl} 21 x_{2} - 57 x_{3} & = & - 123 \\ 21 x_{2} - 57 \cdot 4 & = & - 123 \\ 21 x_{2} & = & - 123 + 228 \\ 21 x_{2} & = & 105 \\ x_{2} & = & \frac{105}{21} \\ x_{2} & = & 5 \end{array}$

Finally, we substitute both values into the first equation:

$\begin{array}{rcl} 6 x_{1} + 9 x_{2} + 21 x_{3} & = & 141 \\ 6 x_{1} + 9 \cdot 5 + 21 \cdot 4 & = & 141 \\ 6 x_{1} + 45 + 84 & = & 141 \\ 6 x_{1} & = & 12 \\ x_{1} & = & 2 \end{array}$

The value of x₁ is two. We now have the complete solution, and can write x = (x₁, x₂, x₃) = (2, 5, 4). As you can see, Gaussian elimination is a simple but effective way 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, the system has infinitely many solutions. Let’s take a simple example:

$\begin{array}{cccccc} 4 x_{1} & + & x_{2} & = & 5 \\ 12 x_{1} & + & 3 x_{2} & = & 15 \end{array}$

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

$\begin{array}{cccccc} 4 x_{1} & + & x_{2} & = & 5 \\ 0 x_{1} & + & 0 x_{2} & = & 0 \end{array}$

Now the number of variables is two, n = 2, the rank of the coefficient matrix is one, rank(A) = 1, and the rank of the augmented matrix is also one, rank(A|b) = 1. Since k < n, the system has infinitely many solutions. How do we find them?

Let’s look at the equations. The second equation is true for all x₁, x₂, so only the first equation matters. In fact, all the pairs x₁, x₂ that satisfy the first equation make up the set of all solutions of the system. So we solve the equation 4x₁ + x₂ = 5. We rearrange it to the form x₂ = 5 − 4x₁.

Next we use a parameter. We choose a parameter t and try to express the pair x₁, x₂ in terms of t, so that we could write, for example, that all pairs of the form (t, t + 2) are solutions of a system. That is, pairs such as (1, 3) or (14, 16). The point is to express one variable in terms of another, so that we know that whatever value x₁ takes, x₂ will be, say, three times as large. As a starting point we choose x₁.

So we set t = x₁. If x₁ has the value t, what value does x₂ have? We can see from the previous equation that x₂ = 5 − 4x₁. So if x₁ = t, then x₂ = 5 − 4t. We can therefore write that all pairs of the form (t, 5 − 4t) are solutions of the system.

We can check this. If we substitute one for t, we get x₁ = 1 and x₂ = 5 − 4 · 1 = 1. Substituting these values into the equation gives 4 · 1 + 1 = 5, which is correct.

If we substitute five for t, we get x₁ = 5 and x₂ = 5 − 4 · 5 = −15. Substituting into the equation gives 4 · 5 − 15 = 5. That works too.

General and particular solutions

A solution of a system of equations written using parameters is called a general solution. A specific solution, obtained by substituting specific numbers for the parameters, is called a particular solution.

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

If we have a coefficient matrix A and an augmented matrix (A|b) with equal ranks, rank(A) = rank(A|b) = k, then we need n − k parameters to express the general solution. Notice that if n = k, we need zero parameters. That is the case where the system has exactly one solution – no parameter is needed.

Example

Solve the following system of linear equations:

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

First we work out the ranks of A and (A|b). We reduce the augmented matrix to row echelon form, which gives us the rank of both matrices. Let’s start. (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 by two again.)

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

From this last matrix we can see that rank(A) = rank(A|b) = k = 2. The number of unknowns is n = 4, so we need n − k = 2 parameters. Let’s write out the equations from the last matrix:

$\begin{array}{ccccccccc} 3 x_{1} & - & 2 x_{2} & + & 4 x_{3} & + & 5 x_{4} & = & 1 \\ - x_{1} & - & 6 x_{3} & = & 0 \end{array}$

From the second equation we get

$\begin{array}{rcl} - x_{1} - 6 x_{3} & = & 0 \\ - x_{1} & = & 6 x_{3} \\ x_{1} & = & - 6 x_{3} \end{array}$

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

$\begin{array}{rcl} 3 (- 6 t) - 2 x_{2} + 4 t + 5 x_{4} & = & 1 \\ - 18 t - 2 x_{2} + 4 t + 5 x_{4} & = & 1 \\ - 14 t - 2 x_{2} + 5 x_{4} & = & 1 \\ - 2 x_{2} & = & 1 + 14 t - 5 x_{4} \\ x_{2} & = & - \frac{1}{2} - 7 t + \frac{5}{2} x_{4} \end{array}$

Now we bring in the second parameter, s = x₄. Then we can write

$x_{2} = - \frac{1}{2} - 7 t + \frac{5}{2} s$

This gives the general solution of the system:

$(x_{1}, x_{2}, x_{3}, x_{4}) = (- 6 t, - \frac{1}{2} - 7 t + \frac{5}{2} s, t, s)$

We can try some particular solutions. For example, s = t = 0. Then we get $(x_{1}, x_{2}, x_{3}, x_{4}) = (0, - \frac{1}{2}, 0, 0)$ . Substituting into the original equations:

we get:

$\begin{array}{ccccccccc} 0 & - & 2 \cdot (- \frac{1}{2}) & + & 0 & + & 0 & = & 1 \\ 0 & - & 4 \cdot (- \frac{1}{2}) & + & 0 & + & 0 & = & 2 \\ 0 & - & 8 \cdot (- \frac{1}{2}) & + & 0 & + & 0 & = & 4 \end{array}$

After removing the zero terms and multiplying out the fractions, we get:

$\begin{array}{rcl} 1 & = & 1 \\ 2 & = & 2 \\ 4 & = & 4 \end{array}$

Let’s try another particular solution: s = 2, t = 1. Then we get:

$\begin{array}{rcl} x_{1} & = & - 6 \\ x_{2} & = & - \frac{1}{2} - 7 + 5 = - \frac{5}{2} \\ x_{3} & = & 1 \\ x_{4} & = & 2 \end{array}$

Substituting into the equations:

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

Simplifying:

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

And finally we get:

$\begin{array}{rcl} 1 & = & 1 \\ 2 & = & 2 \\ 4 & = & 4 \end{array}$

It looks as though the general solution is correct.

Chapters: Systems of linear equations, Cramer’s rule, Homogeneous systems of linear equations

« Previous: Determinants

Next: Cramer’s rule »