In machine learning, one of the main prerequisites is Linear Algebra. In Linear Algebra, the first lesson you learn is about linear systems of equations and solving these systems. In this blog post, I hope to explain how these equations can be solved by the Gaussian Method and how we can implement the Gaussian Method using JavaScript.
Two terms that are vital to the understanding of solving systems of equations are linear combinations and linear equations.
Note that the notation \( v \in \mathbb{R} \) means that \( v \) is a real number, which denotes that \(v \) can be any rational number .
A linear combination is an expression that has the following form,
\[ a_1x_1 + a_2x_2 + a_3x_3 + ... + a_nx_n \]
The numbers \( a_1, a_2, a_3, ... , a_n \in \mathbb{R} \) are the coefficients of the variables \( x_1, x_2, x_3, ... , x_n \)
For example, this expression can be considered as a linear combination,
\[ \frac{1}{5}x + y - z \]
The coefficents of this expression are \( \frac{1}{5}, +1, -1 \) and the variables are \( x, y, z\)
A linear equation has the following form,
\[ a_1x_1 + a_2x_2 + a_3x_3 + ... + a_nx_n = d \]
This expression states that the linear combination equates to a constant \( d \in \mathbb{R} \) A solution to this equation is a \( n \) tuple \( (s_1, s_2, s_3, .. , s_n ) \in \mathbb{R}^n \) which when substituted to the linear equation equate to the constant \( d \). as follows, .
\[ a_1s_1 + a_2s_2 + a_3s_3 + ... + a_ns_n = d \]
Extending this notation, we can denote an entire system of such linear equations,
\[ a_1x_1 + a_2x_2 + a_3x_3 + ... + a_nx_n = d_1 \]
\[ b_1x_1 + b_2x_2 + b_3x_3 + ... + b_nx_n = d_2 \]
\[ ... \]
\[ c_1x_1 + c_2x_2 + c_3x_3 + ... + c_nx_n = d_n \]
Gaussian Method
Also known as Gaussian Elimination or row reduction, which was named after Carl Friedrich Gauss , is used to solve linear equations in a step-by-step manner. We use Gauss's method to transform the system of equations to a more straightforward form known as the echelon form.
His theorem proves that a system of linear equations can be transformed by the following 3 operations,
- an equation is swapped by another
- an equation has both sides multiplied by a non-zero constant
- an equation is replaced by the sum of itself and a multiple of another
and the transformed system and the original system of equations would both have the same set of solutions.
Example
Consider the following linear equations system; using the Gaussian method operations, we transform this system to its echelon form,
\[ \frac{1}{4}x + y - z = 0 \] \[ x + 4y + 2z = 12 \] \[ 2x - 3y - z = 3 \]
First we will clear out the fraction in the \( 1^{st} \) equation, by multiplying the equation by \( 4 \). This will be the result,
\[ x + 4y - 4z = 0 \] \[ x + 4y + 2z = 12 \] \[ 2x - 3y - z = 3 \]
Secondly we need to cancel the \( x \) terms in the \( 2^{nd} \) and \( 3^{rd} \) equations.
To cancel the \( 2^{nd} \) equation's \( x \) term we need to multiply the \(1^{st} \) equation by \( -1 \) and add it to the \(2^{nd}\) equation. This will be the result,
\[ x + 4y - 4z = 0 \] \[ 6z = 12 \] \[ 2x - 3y - z = 3 \]
To cancel the \( 3^{rd} \) equation's \( x \) we can multiply the \( 1^{st} \) equation by \( -2 \) and add it to the \( 3^{rd} \) equation. This will be the result,
\[ x + 4y - 4z = 0 \] \[ 6z = 12 \] \[-11y + 7z = 3 \]
Now we can swap the \( 2^{nd} \) and \( 3^{rd} \) rows to form the echelon form of the linear equations.
\[ x + 4y - 4z = 0 \] \[-11y + 7z = 3 \] \[ 6z = 12 \]
Using the derived echelon form, we can first solve for \( z \) and by substituting \( z \) we can solve for \(y\). Once we know the values for \(z\) and \(y\) we can find the value for \(x\).
The solution tuple would be as follows, \[ (x,y,z) = (4,1,2)\]
Systems without any solution
Sometimes, there can be a set of linear expressions that don’t have a solution at all. Using the Gaussian Method we can identify whether the system of equations have a solution or not.
Consider the following example,
\[ x + y + z = 6 \] \[ x + 2y + z = 8 \] \[ 2x + 3y + 2z = 13 \]
We can simplify this system by multiplying the \( 1^{st} \) equation by \(-1\) and adding it to the \(2^{nd}\) equation, to cancel out the \(x\) term in the \( 2^{nd} \) equation. We can also cancel out the \(x\) term in the \(3^{rd}\) equation by multiplying the \(1^{st}\) equation by \(-1\) and adding it to the \(3^{rd}\) equation. We would end up with the following system of equations.
\[ x + y + z = 6 \] \[ y = 2 \] \[ y = 1 \]
To cancel the \(y\) term in the \(3^{rd}\) equation, we can multiply the \(2^{nd}\) equation by \(-1\) and add it to the \(3^{rd}\) equation, which would give us a system of equations like so,
\[ x + y + z = 6 \] \[ y = 2 \] \[ 0 = -1 \]
Since there is an inconsistency in the derived system of equations (or the echelon form), since \(0\) is not equal to \(-1\), we know that this system of equations doesn’t have any solution. Therefore we cannot find a solution tuple that would be able to satisfy all the \(3\) equations of the system. Thus, we state that this system of equations has no solution.
Systems with many solutions
The opposite can also be true. There can be systems with many solutions for solving the system of linear equations. Consider the following system of equations,
\[ -x - y + 3z = 3 \] \[ -y + 4z = 6 \] \[ -4y +16z = 24 \]
When you simplify the equations to echelon form, this is result,
\[ -x - y + 3z = 3 \] \[ -y + 4z = 6 \] \[ 0 = 0 \]
There is no equation to derive the value of \(z\), therefore we can replace \(z\) by any value, to get a solution to the set of equations. For example, if \(z\) is \(0\), the solution tuple is,
\[ (x,y,z) = (3, -6, 0) \]
and if \(z\) is \(1\), the solution tuple is,
\[ (x,y,z) = (2, -2, 1) \]
By changing the value \(z\) we can get multiple solution tuples. Therefore this system of linear equations have more than one solution.
Implementing the Gaussian Method using JavaScript
We can write a simple JavaScript program to derive the echelon form of a system of equations. I will go through the process of how I implemented the Gaussian Method. It is a simple implementation of the Gaussian Method where there is no row swapping.
The Gaussian Method is broken down into 2 functions in this implementation.
The first function is the 'normalize' function. This function takes a 2-D array as the coefficients of the equations known as the matrix, the row index, and the row's pivot index. The pivot index's value divides all the row elements, making the pivot index's value/coefficient be 1, thus normalizing the row.
function normalize(mat, index, pivot){
let newMat = Object.assign([], mat);
let multiplier = 1/(newMat[index][pivot]);
for (let i = 0; i < newMat[index].length; i++){
if (newMat[index][i] != 0){
newMat[index][i] *= multiplier;
}
}
return newMat;
}
The second function is the 'change' function. This would eliminate the coefficients of the other rows, thus simplifying the system of equations.
function change(mat, index, pivot){
if ((index+1) >= mat.length){
return;
}
let newMat = Object.assign([], mat);
for (i = (index+1); i < newMat.length; i++){
multiplier = newMat[i][pivot] * -1;
for (j = 0; j < newMat[i].length; j++){
newMat[i][j] = newMat[i][j] + (newMat[index][j] * multiplier);
}
}
return newMat;
}
I have created a 'echolonForm' function, which uses both of these functions to convert a system of equations into their echelon form.
function echolonForm(mat){
let pivots = mat.length-1;
for (let pivot = 0; pivot < pivots; pivot++){
mat = normalize(mat, pivot, pivot);
mat = change(mat, pivot, pivot);
}
return mat;
}
Let's see this implementation in action!
We will take the following system of linear equations, \[ -x - y + 3z = 3 \] \[ -y + 4z = 6 \] \[ -4y +16z = 24 \]
The corresponding 2-D array of coefficients for this is as follows, \[ [[-1,-1,3,3],[0,-1,4,6],[0,-4,16,24]] \]
mat = [[-1,-1,3,3],[0,-1,4,6],[0,-4,16,24]]
console.log(echolonForm(mat));
// output: [ [ 1, 1, -3, -3 ], [ 0, 1, -4, -6 ], [ 0, 0, 0, 0 ] ]
If we transfer the coefficients into equations, we would get this set of equations,
\[ -x - y + 3z = 3 \] \[ y - 4z = -6 \] \[ 0 = 0 \]
The entire code implementation can be found in this JS Fiddle ( Link )
Thank you for reading this article this far! If you have any questions, please write them below.
If you like a challenge, try to implement the Gaussian Method with row swapping. Here is the row swapping function to get you started!
function swap(mat, row1, row2){
let newMat = Object.assign([], mat);
let tempArr = Object.assign([], newMat[row1]);
newMat[row1] = Object.assign([], newMat[row2]);
newMat[row2] = tempArr;
return newMat;
}
Good luck on your journey in learning Machine Learning!