10. Solving a system of linear equations

A system of k linear equations with variables x_{1}, x_{2},\ldots, x_{n} is simply a set of k equations, in which the variables appear without any powers or multiplication between them:

    \[\begin{cases} a_{1,1}x_1+a_{2,1}x_2+\ldots+a_{n,1}x_n=b_1\\ a_{1,2}x_1+a_{2,2}x_2+\ldots+a_{n,2}x_n=b_2\\ \ldots\\ a_{1,k}x_1+a_{2,k}x_2+\ldots+a_{n,k}x_n=b_k \end{cases},\]

where a_{i,j},b_j are some real numbers. E.g. the following is a system of 3 linear equations with four variables:

    \[\begin{cases}x_{1}+3x_{2}+x_{3}+5x_{4}=2\\ 2x_{1}+7x_{2}+9x_{3}+2x_{4}=4\\ 4x_{1}+13x_{2}+11x_{3}+12x_{4}=8\end{cases}\]

A solution of such a system of linear equations is a tuple of four numbers (four is the number of variables in this case), which satisfies all the equations in the system (after substitution of those numbers under the variables). E.g. (2,0,0,0) in our case. But a system can have more than one solutions. For example, (22,-7,1,0) is also a solution to the above system. More precisely a system of linear equations can have 0, 1, or infinitely many solutions.

A general solution of a system of linear equations is just a description of a set of all its solutions (which sometimes may mean saying that there are no solutions at all, or pointing out the only one). How to find a general solution? We will use so called Gaussian elimination method. Less formally we will call it transformation of our system of equations into a echelon form.

The first step is to write down a matrix of a given system of equations. A matrix is simply an rectangular table with numbers. Matrices will play more and more important role in this course, but now we can just think of a matrix of a system of equations as of an abbreviated notation of the system itself. Simply we write down the coefficients separating the column of free coefficients with a line:

    \[\left[\begin{array}{cccc|c}1 & 3 & 1 & 5 & 2\\ 2 & 7 & 9 & 2 & 4\\ 4 & 13 & 11 & 12 & 8\end{array}\right]\]

Next we make some operations on this matrix. Those operations simplify the matrix, but we shall make sure that they do not change the set of solutions of the corresponding system of equations. Therefore only three types of operations are permitted:

  • subtracting from a row another row multiplied by a number (corresponds to subtracting an equation from another one),
  • swapping two rows (corresponds to swapping two equations)
  • multiplying a row by a non-zero number (corresponds to multiplying both sides of an equation by a non-zero number)

And our aim is to achieve a staircase-like echelon form of a matrix (meaning that you can draw a stairs through a matrix, under which you will have only zeros). It means that in each corresponding equation there will be less variables than in the previous one.

What should we do to achieve such a form? The best method is to generate the echelon from the left side using the first row. Under 1 in the left upper corner we would like to have zeros. To achieve this, we have to subtract the first row multiplied by 2 from the second one and also subtract the first row multiplied by 4 from the third one. So:

    \[\underrightarrow{w_{2}-2w_{1}, w_{3}-4w_{1}} \left[\begin{array}{cccc|c}1 & 3 & 1 & 5 & 2\\ 0 & 1 & 7 & -8 & 0\\ 0 & 1 & 7 & -8 & 0\end{array}\right]\]

So now we would like to have a zero under 1 in the second row. Therefore we subtract the second row from the third:

    \[\underrightarrow{w_{3}-w_{2}} \left[\begin{array}{cccc|c}1 & 3 & 1 & 5 & 2\\ 0 & 1 & 7 & -8 & 0\\ 0 & 0 & 0 & 0 & 0\end{array}\right]\]

And so we have achieved an echelon form! We have leading coefficient in the first row on the first variable and a leading coefficient in the second row on the second variable.

The next step is to reduce the matrix (transform it into a reduced echelon form). We would like to have zeros also above the leading coefficients. In our case we only need to do something with 3 on the second place in the first row. To have a zero there we have to subtract the second row multiplied by 3 from the first one.

    \[\underrightarrow{w_{1}-3w_{2}} \left[\begin{array}{cccc|c}1 & 0 & -20 & 29 & 2\\ 0 & 1 & 7 & -8 & 0\\ 0 & 0 & 0 & 0 & 0\end{array}\right],\]

We need also to make sure that the leading coefficients are always ones (sometimes we have to multiply a row by a fraction number). But in our case it is already done. We have achieved a reduced echelon form. To have a general solution it suffices to write down corresponding equations moving the free variables to the right side of the equations:

    \[\begin{cases}x_{1}=2+20x_{3}-29 x_{4}\\ x_{2}=-7x_{3}+8x_{4} \end{cases}\]

We can also write it in parametrized form substituting to a vector (x_1,x_2,x_3,x_4) all we know in the general solution, so: \{(2+20x_{3}-29 x_{4}, -7x_{3}+8x_{4}, x_{3},x_{4})\colon x_3,x_4\in\mathbb{R}\}. Notice that by substituting x_3 and x_4 by any real numbers we will get a tuple (sequence of four numbers) which is a solution to our system of equations (it has infinitely many solutions). E.g. substituting x_3=1,x_4=0 we get the solution (22,-7,1,0), which was mentioned above.

Finally let us introduce some terminology. A system of linear equations is:

  • homogeneous if all constant terms are zero,
  • inconsistent if it has no solutions.

For example the following set:

    \[\begin{cases} x+y=2\\x-2y=-1\end{cases}\]

is not homogeneous, has exactly one solution, so it is not inconsistent. Meanwhile:

    \[\begin{cases} x+y+z=0\\x-y-z=0\\2x+y=0\end{cases}\]

is homogeneous and has exactly one solution, so is not inconsistent. On the other hand, the following set of equations is inconsistent:

    \[\begin{cases} x+y+z=0\\-2x-2y-2z=-1\end{cases}\]

Note that a system of linear equations can have exactly one, infinitely many or no solutions.