Gaussian elimination procedure

There are two boxes - one with apples, the other with plums. It is known that there are twice more apples than plums and total number of fruits is 300. How many apples and how many plums are in those two boxes?

Let us introduce notations:

$x$ - number of apples,

$y$ - number of plums.

In terms of these new notations this problem takes the following form.

$$\left\{ \begin{array}{ccc} x & = & 2y\\ x+y & = & 300\end{array}\right.$$ (1.1)

This is a simple example of a system of linear equations. This system has two equations and two unknowns. After replacing $x$ with $2y$ in the second equation we obtain

$$3y=300$$

which leads to $y=100.$ From the first equation we have $x=200.$

Now consider more general system of linear equations.

$$\left\{ \begin{array}{ccccccccc} a_{11}x_{1}&+&a_{12}x_{2}&+... ...}x_{2}&+&\ldots &+&a_{mn}x_{n} & = & b_{m}, \end{array}\right.$$ (1.2)

where $a_{ij}$ and $b_{i}$ are real numbers for all $1\leq i\leq n$ and $1\leq j\leq m.$

To solve () we could follow the same idea that led us to the solution of (). It is one of legitimate ways of handling this type of problems and it has some valuable theoretical aspects as we will see later. However, following this scenario we would face many computational difficulties. That is one of the main reason of adopting technique that is well known as "Gaussian Elimination Procedure"^1.1.

To describe Gaussian Elimination Procedure we write system () in a different way. We preserve only the information that is essential for achieving our goal of finding solutions. This information is provided only by coefficients $a_{ij}$ and $b_{i}$ with $i=1,2,\dots,n$ and $j=1,2,\dots,m.$ All other symbols in () we can drop and replace all "$=$" with a vertical line. That leads us to the following table of numbers.

$$\left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n}... ..._{1},\\ b_{2},\\ \vdots \\ b_{m} \end{array}\right. \right)$$ (1.3)

We need to work only with this table of numbers in order to find solutions for (). This table of numbers is called augmented matrix of system (). The following operations over the rows of the augmented matrix do not change essentially the original system. In other words, they preserve the set of solutions.

Elementary Row Operations

i.

Any two rows can be interchanged.

ii.

Any row can be multiplied by a non zero number. Multiplication is performed entry-wise, i.e. each entry in the row is multiplied by the same number.

iii.

Any row can be replaced by its sum with any other row. Addition between two rows is performed entry-wise. That means any two entries with the same second index $j$ are added to each other.

Now we play a game with augmented matrix (). Rules of this game are defined by elementary row operations. The goal is to zero as many coefficients $a_{ij}$ as possible with $i<j.$ Those coefficients are in the lower left corner of the augmented matrix. There is abandon of strategies in playing this game. One of them is based on Gaussian Elimination Procedure. Although it is not the most efficient among the strategies it is very simple.

Gaussian Elimination Procedure

i.

By interchanging rows make sure that the leading element in the first row is not zero, $a_{11}\not=0.$

ii.

Multiply the first row with $\frac{1}{a_{11}}.$

iii.

Replace each $i$-th row for $i\geq2$ by its sum with the first row multiplied by $-a_{ij},$ where $j=1$ for the first invocation of the procedure.

 $$

iv. Repeat the previous steps (i, ii, iii) for the matrix in the lower left corner defined by coefficient with indices $\{ ij\}$ where $i\geq2$ and $j\geq 2.$

Under Gaussian Elimination Procedure the augmented matrix becomes "triangular" in the sense that coefficients in the lower left corner are zeroes. Let us take a closer look at the transformations of augmented matrix on different steps of Gaussian Elimination Procedure.

After the first step of Gaussian Elimination Procedure we make sure that the leading element in the first row is not zero. Our matrix looks as in Fig. .

Figure: Leading element in the first row is not zero

Then we multiply the fist row by $\frac{1}{a_{11}}$ (Fig. ).

Figure: After multiplying the fist row by $\frac{1}{a_{11}}$

Now we can "kill" all elements below "$1$" in the first column of the matrix. It is done by replacing each $i$-th $(i>1)$ row by its sum with the first row multiplied by $-a_{i1}.$ Let us introduce notations, $\bar a_{ij} = a_{ij} - a_{i1}\cdot \frac{a_{1j}}{a_{11}}.$ Then our new matrix will be of the following form.

Figure: All elements below $1$ are zeroes

Now we repeat the same steps (i, ii, iii) for the matrix in the lower right corner,i.e., the matrix with entries $a_{ij},$ where $i>1$ and $j>1.$ Let us illustrate Gaussian Elimination Procedure with examples.

Example 1.1  

Solve the system of linear equations.

$$\left\{ \begin{array}{ccccccc} 2\cdot x_1 &+& 4\cdot x_2 &+... ...=& 1 \\ x_1 &+& 3\cdot x_2 &+& x_3 &=& 2 \end{array}\right.$$

Solution. First, we write the augmented matrix for this system.

$$\left( \begin{array}{ccc} 2 & 4 & 8 \\ 1 & 1 & 1 \\ 1 &... ...\vert \begin{array}{c} 14\\ 3\\ 5 \end{array}\right. \right)$$

After dividing each element in the first row by $2$ we get the following matrix.

$$\left( \begin{array}{ccc} 1 & 2 & 4 \\ 1 & 1 & 1 \\ 1 &... ...t\vert \begin{array}{c} 7\\ 3\\ 5 \end{array}\right. \right)$$

Now we replace the second and the first row by their sums with the first row multiplied by "$-1$". That lead to the matrix.

$$\left( \begin{array}{ccc} 1 & 2 & 4 \\ 0 & -1 & -3 \\ 0... ...vert \begin{array}{c} 7\\ -4\\ -2 \end{array}\right. \right)$$

After replacing the third row by its sum with the second row the Gaussian Elimination Procedure is completed.

$$\left( \begin{array}{ccc} 1 & 2 & 4 \\ 0 & -1 & -3 \\ 0... ...vert \begin{array}{c} 7\\ -4\\ -6 \end{array}\right. \right)$$

We can put back variables $(x_1, x_2, x_3)$ and solve the system "backwards" starting from the last equation.

$$\left\{ \begin{array}{ccccccc} x_1 &+& 2\cdot x_2 &+& 4 \cd... ...x_3 &=& -4 \\ && && - 6 \cdot x_3 &=& -6 \end{array}\right.$$

The last equation implies that $x_3=1.$ Then we are moving "backwards" in terms of the equations of this system. The second line gives us $x_2 = 1,$ and finally the first line leads us to $x_1=1.$ The system has the only solution

$$\begin{array}{ccc} x_1&=&1\\ x_2&=&1\\ x_3&=&1 \end{array}$$

In other words, the solution is the string of numbers $(1,1,1).$ If a linear system has at least one solution then it is called consistent.

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$

Example 1.2  

Solve the system of linear equations.

$$\left\{ \begin{array}{ccccccc} 2\cdot x_1& +& 4\cdot x_2& +... ... 3 \\ && 2\cdot x_2& +& 6 \cdot x_3 &=& 2 \end{array}\right.$$

Solution. First, we write the augmented matrix for this system.

$$\left( \begin{array}{ccc} 2 & 4 & 8 \\ 1 & 1 & 1 \\ 0 &... ...t\vert \begin{array}{c} 8\\ 3\\ 2 \end{array}\right. \right)$$

After dividing each element in the first row by $2$ we get the following matrix.

$$\left( \begin{array}{ccc} 1 & 2 & 4 \\ 1 & 1 & 1 \\ 0 &... ...t\vert \begin{array}{c} 4\\ 3\\ 2 \end{array}\right. \right)$$

We replace the second row by its sum with the first row multiplied by "$-1$".

$$\left( \begin{array}{ccc} 1 & 2 & 4 \\ 0 & -1 & -3 \\ 0... ...vert \begin{array}{c} 4\\ -1\\ 2 \end{array}\right. \right)$$

After replacing the third row by its sum with the second row multiplied by "$2$" we get the matrix.

$$\left( \begin{array}{ccc} 1 & 2 & 4 \\ 0 & -1 & -3 \\ 0... ...vert \begin{array}{c} 4\\ -1\\ 0 \end{array}\right. \right)$$

Gaussian Elimination Procedure is completed. We reduce the original system to the following form.

$$\left\{ \begin{array}{ccccccc} x_1 &+& 2\cdot x_2 &+& 4 \cd... ...3 &=& 4 \\ && - x_2 &-& 3\cdot x_3 &=& -1 \end{array}\right.$$

This system has infinitely many solutions. Indeed, the variable $x_3$ can take any real value. Mathematical representation of this fact looks as follows.

$$x_3 =t, \mbox{ where } t \mbox{ can be any number.}$$

Now the second equation of our system implies that

$$x_2 = 1 - 3\cdot t.$$

Finally, the first equation gives us.

$$x_1 = 4 - 2 \cdot (1 - 3\cdot t) - 4 \cdot t = 2 + 2 \cdot t.$$

Our system has infinitely many solutions presented as

$$\begin{array}{ccc} x_1&=&2 + 2 \cdot t\\ x_2&=&1 - 3\cdot t\\ x_3&=&t \end{array}$$

where $t$ is an arbitrary number. This is called a general solution of the system.

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$

Example 1.3  

Solve the system of linear equations.

$$\left\{ \begin{array}{ccccccc} 2\cdot x_1 &+& 4\cdot x_2 &+... ... 3 \\ && 2\cdot x_2 &+& 6 \cdot x_3 &=& 1 \end{array}\right.$$

Solution. First, we write the augmented matrix for this system.

$$\left( \begin{array}{ccc} 2 & 4 & 8 \\ 1 & 1 & 1 \\ 0 &... ...t\vert \begin{array}{c} 8\\ 3\\ 1 \end{array}\right. \right)$$

It is left as an exercise for the reader to follow the same steps as in the previous two examples. Upon completion of Gaussian Elimination Procedure we obtain the following augmented matrix.

$$\left( \begin{array}{ccc} 1 & 2 & 4 \\ 0 & -1 & -3 \\ 0... ...vert \begin{array}{c} 4\\ -1\\ -1 \end{array}\right. \right)$$

According to the last line of the augmented matrix $-1$ is equal to $0$ which is nonsense. That means the system does not have any solutions. Such systems are called inconsistent.

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \diamond$

Any linear system falls in one of the following categories.

The system has the only solution.

The system has infinitely many solutions.

The system is inconsistent. That means it does not have any solutions.

Gaussian Elimination Procedure gives us a simple and effective way of dealing with a linear system. After a finite number of steps we are able to write the complete solution for a system or to conclude that the system is inconsistent.