How To Programmatically Solve Linear Equation using Gaussian Elimination

Gaussian Elimination also known as row reduction process that uses these operations:

• Swapping two rows,
• Multiplying a row by a nonzero scalar,
• Adding a multiple of one row to another.

Using these operations, the goal is to transformed the matrix into echelon form.

Echelon form is more less an upper triangular matrix which has zeros below the main diagonal (from top left to botton right) and it is also unique. Here is an example.

$$\begin{bmatrix} 2 & 1 & -1\\ -3 & -1 & 2\\ -2 & 1 & 2\\ \end{bmatrix} \begin{bmatrix} 8\\ -11\\ 3\\ \end{bmatrix} \longrightarrow \begin{bmatrix} 2 & 1 & -1\\ 0 & \frac{1}{2} & \frac{1}{2}\\ 0 & 0 & -1\\ \end{bmatrix} \begin{bmatrix} 8\\ 1\\ 1\\ \end{bmatrix}$$

How to get the echelon form programatically?

Remember we can do operation mentioned above, from that we can make a generic like:

$$L_i = L_i - \phi L_{i+1}$$

where $L$ is the row and $i$ is the row index and $\phi$ is a scaling factor obtained from

$$\phi = \frac{e_{(j,i)}}{e_{(i,i)}}$$

where $j$ is the column index.

Step 1:

for example reducing the $L_2$ from the matrix above

the $\phi$ will be the element at 0,0 and 1,0:

$$\phi = \frac{e_{0,0}}{e_{1,0}} = \frac{-3}{1}$$

then do operation

$$L_2 = L_2 - \frac{-3}{1} L_1$$

so the $L_2$ becomes

$$\begin{bmatrix} 2 & 1 & -1\\ 0 & \frac{1}{2} & \frac{1}{2}\\ -2 & 1 & 2\\ \end{bmatrix} \begin{bmatrix} 8\\ 1\\ 3\\ \end{bmatrix}$$

After that do same operation for the $L_3$,

calculate the $\phi$

$$\phi = \frac{e_{0,0}}{e_{2,0}} = \frac{2}{-2}$$

then $L_3$ becomes,

$$\begin{bmatrix} 2 & 1 & -1\\ 0 & \frac{1}{2} & \frac{1}{2}\\ 0 & 2 & 1\\ \end{bmatrix} \begin{bmatrix} 8\\ 1\\ 5\\ \end{bmatrix}$$

Why not do $L_3=L_3+L_1$ directly?

It's because we need to do the same operation for all rows, otherwise it will be hard to code

Step 2

Now, it's done for the second column, move to the third columns.

This time what is the $\phi$ will be ?

$$\phi = \frac{e_{1,1}}{e_{2,1}} = \frac{2}{\frac{1}{2}}$$

Do we need to operate the first row?

NO, because we only need to make zeros below the main diagonal.

now the $L_3$ will be

$$\begin{bmatrix} 2 & 1 & -1\\ 0 & \frac{1}{2} & \frac{1}{2}\\ 0 & 0 & -1\\ \end{bmatrix} \begin{bmatrix} 8\\ 1\\ 1\\ \end{bmatrix}$$

Is it finished?

Yes, because it's all zeros below the main diagonal

Step 3

Now, we can get the value of Z and from that we do back substitution for Y and X