Gaussian Elimination

Overview


The Gaussian eliminatoin method is a method for soliving systems of linear equations such as
{% a_{11} x_1 + a_{12} x_2 + a_{13} x_3 + ... + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + a_{23} x_3 + ... + a_{2n} x_n = b_2 \\ ... \\ a_{n1} x_1 + a_{n2} x_2 + a_{n3} x_3 + ... + a_{nn} x_n = b_1 %}

Example


The simplest way to undersand the Gaussian Elimination is to follow an example.
{% x -2y + z = 0 \\ 2x + y - 3z = 5 \\ 4x - 7y + z = -1 %}
The method of elimination tries to successly eliminate variables from the given equations. This is done by adding multiples of one equation to another. In the example given, you can eliminate x from the last equation by subtracting 4 times the first equation from it. You get the following:
{% x -2y + z = 0 \\ 2x + y - 3z = 5 \\ y - 3z = -1 %}
Now notice that we can eliminate x from the second equation by the same method.
{% x -2y + z = 0 \\ 5y - 5z = 5 \\ y - 3z = -1 %}
No notice that y can be eliminated from the last equation by subtracting 1/5 of the second equation. This reveals that the value of z is equal to 1.

Typically, to simplify how this process is written, the above equations are written in the following form, where we suppress the variable names.

{% \begin{bmatrix} 1 & -2 & 1 & | & 0 \\ 2 & 1 & -3 & | & 5 \\ 4 & -7 & 1 & | & -1 \\ \end{bmatrix} %}
Now we just add multiples of one row to the others.

Example Code


For the given example, we will represent the above equations using a matrix representation.
{% A \vec{v} = \vec{u} %} 



let A = [[1,-2,1],
             [2,1,-3],
             [4,-7,1]];

let u = [[0],[5],[-1]];


We can use the addToRow method in the linear-algebra module to add one row to another. So we can add -4 times the first row to the last row 


let la = await import('/lib/linear-algebra/v1.0.0/linear-algebra.mjs');

let firstRow = A[0];
let mult = firstRow.map(p=>-4*p);
la.addToRow(A,2, mult);
Try it!


Then we apply the same transformation to the u vector. 


let firstRow = u[0];
let mult = firstRow.map(p=>-4*p);
la.addToRow(u,2, mult);
Try it!

Matrix Inverse


The Gaussian Elimination method is used to compute the matrix inverse, using Elementary Operations. The inverse can be used to solve the equations simply.
{% A\vec{x} = \vec{b} %}
{% E_1 E_2 ... E_n A\vec{x} = E_1 E_2 ... E_n \vec{b} %}
when the elementary operations convert A into the Identity matrix
{% E_1 E_2 ... E_n A = I %}
we then have
{% \vec{x} = E_1 E_2 ... E_n \vec{b} %}
or
{% E_1 E_2 ... E_n = A^{-1} %}
where each {% E_i %} is an elementary operation. (see Aggarwal)

Contents