One morning before work, I figured I’d implement a function to compute the determinant of a matrix using the Gaussian elimination to row echelon form technique, using the JavaScript language.

In machine learning scenarios, the determinant is most often used to check if a matrix inverse exists. If the determinant is 0, the inverse doesn’t exist. If the determinant is anything else, the inverse does exist.

There are several algorithms that can be used to compute a matrix determinant. Based on my experience, two of the most common are the LU/LUP decomposition technique and the Gaussian elimination to row echelon form technique. For my implementation, I used the row echelon form technique. (Note: there’s a similar matrix algebra technique called Gauss-Jordan elimination to reduced row echelon form, but that technique is usually used to compute a matrix inverse).

Maybe the best way to understand is by looking at a concrete example of a 7-by-7 matrix that’s in row echelon form:

3.8  3.7  8.2  7.6  1.5  2.2  8.3
0.0  0.0  5.4  3.8  1.8  0.0  4.9
0.0  0.0  0.0  8.4  3.3  6.3  2.6
0.0  0.0  0.0  0.0  0.0  5.7  0.5
0.0  0.0  0.0  0.0  0.0  2.3  8.1
0.0  0.0  0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0  0.0  0.0

A square matrix is in row echelon form when a.) if there are any rows of all zeros, they are all on the bottom, b.) if you start at the upper left corner, and draw a border so that the 0.0 entries are below, then you get a staircase shape (that isn’t necessarily symmetric). The word “echelon” can be traced back to the Latin word for “stairs”.

The source matrix is converted to row echelon form using three operations:

1.) Any two rows can be swapped.
2.) Any row (or a multiple of it) can be added to another row.
3.) Any row can be multiplied by a constant.

If two rows are swapped, the determinant is multiplied by -1 (i.e., changes sign). If you multiply a row by a constant k, the determinant is also multiplied by k. If you add a multiple of one row to another, the determinant does not change.

The output of my demo is:

Begin matrix determinant using
Gaussian elimination to row echelon form
technique using JavaScript

Source matrix:
  2.0   9.0
  1.0   8.0

Determinant = 7.0000

Source matrix:
  5.0   9.0   7.0
  3.0   8.0  -1.0
 -2.0   1.0   6.0

Determinant = 234.0000

Source matrix:
  1.0  -4.0   3.0   0.0
  2.0   8.0   6.0  -1.0
  9.0   7.0   5.0  -1.0
 -1.0   0.0   2.0   3.0

Determinant = -1103.0000

Source matrix:
  1.0   4.0   3.0   0.0
  2.0   8.0   6.0   0.0
  9.0   7.0   5.0   1.0
 -1.0   0.0  -2.0  -3.0

Determinant = 0.0000

End demo

A good way to warm my brain up to start a day.

I have a weird liking for the JavaScript language. It is very risky and mistakes can be difficult to detect, which means the language requires a lot of attention. When I code with JavaScript, I always ask myself, “What could possibly go wrong?”

Bottom: Here is the “Lastavica”, a small ship (36 passengers) that cruises the Croatia coast. I went on this ship last year. It was very nice. There were no tour groups from Atlanta and no poolside brawls.

Demo code. Replace “lt” (less than), “gt”, “lte”, “gte” with Boolean operator symbols. (My lame blog editor chokes on symbols).

// matrix_determinant_echelon.js
// Gaussian elimination to row echelon form
// implemented for node.js

// ----------------------------------------------------------

function matDeterminantEchelon(A)
{
  // compute determinant of matrix
  let n = A.length;  // assume square

  // small n shortcuts
  if (n == 1) 
    return A[0][0];

  if (n == 2) 
    return (A[0][0] * A[1][1]) - (A[0][1] * A[1][0]);

  if (n == 3) {
    let a = (A[1][1] * A[2][2]) - (A[1][2] * A[2][1]);
    let b = (A[1][0] * A[2][2]) - (A[1][2] * A[2][0]);
    let c = (A[1][0] * A[2][1]) - (A[1][1] * A[2][0]);
    return (A[0][0] * a) - (A[0][1] * b) + (A[0][2] * c);
  }

  // otherwise, use Gaussian elimination
  let det = 1.0;

  // make a copy of A
  let B = [];
  for (let i = 0; i "lt" n; ++i) {
    B[i] = [];
    for (let j = 0; j "lt" n; ++j) {
      B[i][j] = A[i][j];
    }
  }

  // main loop
  for (let i = 0; i "lt" n; ++i) {
    let pr = i;  // find pivot row
    for (let k = i+1; k "lt" n; ++k) {
      if (Math.abs(B[k][i]) "gt" Math.abs(B[pr][i])) {
        pr = k;
      }
    }

    if (pr != i) {  // swap rows pr and i
      for (let k = 0; k "lt" n; ++k) {
        let tmp = B[i][k];
        B[i][k] = B[pr][k];
        B[pr][k] = tmp;
      }
      det *= -1.0;  // a row swap flips sign
    }

    if (Math.abs(B[i][i]) "lt" 1.0e-8) // short-circuit
      return 0.0;

    det *= B[i][i];  // theory

    for (let k = i+1; k "lt" n; ++k) {  // elim below pivot
      let scale = B[k][i] / B[i][i];
      for (let c = 0; c "lt" n; ++c) {
        B[k][c] -= scale * B[i][c];
      }
    }

  } // main loop
  return det;
}

// ----------------------------------------------------------

function matShow(A, dec, wid)
{
  let small = 1.0 / Math.pow(10, dec);
  let nr = A.length;
  let nc = A[0].length;
  for (let i = 0; i "lt" nr; ++i) {
    for (let j = 0; j "lt" nc; ++j) {
      let x = A[i][j];
      if (Math.abs(x) "lt" small) x = 0.0;
      let xx = x.toFixed(dec);
      let s = xx.toString().padStart(wid, ' ');
      process.stdout.write(s);
      process.stdout.write(" ");
    }
    process.stdout.write("\n");
  }
}

// ----------------------------------------------------------

function loadTxt(fn, delimit, usecols, comment)
{
  // load matrix from text file
  // ex: let A = loadTxt("my_data.txt", ",", [0,1], "#");
  let all = FS.readFileSync(fn, "utf8");  // giant string
  all = all.trim();  // strip final crlf in file
  let lines = all.split("\n");  // array of lines

  // count number non-comment lines
  let nRows = 0;
  for (let i = 0; i "lt" lines.length; ++i) {
    if (!lines[i].startsWith(comment))
      ++nRows;
  }
  let nCols = usecols.length;
  let result = matMake(nRows, nCols, 0.0); 
 
  let r = 0;  // into lines
  let i = 0;  // into result[][]
  while (r "lt" lines.length) {
    if (lines[r].startsWith(comment)) {
      ++r;  // next row
    }
    else {
      let tokens = lines[r].split(delimit);
      for (let j = 0; j "lt" nCols; ++j) {
        result[i][j] = parseFloat(tokens[usecols[j]]);
      }
      ++r;
      ++i;
    }
  }

  return result;
}

// ----------------------------------------------------------

function main()
{
  console.log("\nBegin matrix determinant using "); +
  console.log("Gaussian elimination to row echelon form ");
  console.log("technique using JavaScript ");

  // first example, 2x2
  let A = [];
  A[0] = [ 2.0, 9.0 ];
  A[1] = [1.0, 8.0 ];

  console.log("\nSource matrix: ");
  matShow(A, 1, 5);

  let detA = matDeterminantEchelon(A);
  console.log("\nDeterminant = " + 
    detA.toFixed(4).toString());

  // second example
  let B = [];
  B[0] = [ 5.0, 9.0, 7.0 ];
  B[1] = [ 3.0, 8.0, -1.0 ];
  B[2] = [ -2.0, 1.0, 6.0 ];

  console.log("\nSource matrix: ");
  matShow(B, 1, 5);

  let detB = matDeterminantEchelon(B);
  console.log("\nDeterminant = " + 
    detB.toFixed(4).toString());

  // third example
  let C = [];
  C[0] = [ 1.0, -4.0, 3.0, 0.0 ];
  C[1] = [ 2.0, 8.0, 6.0, -1.0 ]; 
  C[2] = [ 9.0, 7.0, 5.0, -1.0 ];
  C[3] = [ -1.0, 0.0, 2.0, 3.0 ];

  console.log("\nSource matrix: ");
  matShow(C, 1, 5);

  let detC = matDeterminantEchelon(C);
  console.log("\nDeterminant = " + 
    detC.toFixed(4).toString());

  // fourth example
  let D = [];
  D[0] = [ 1.0, 4.0, 3.0, 0.0 ];
  D[1] = [ 2.0, 8.0, 6.0, 0.0 ];  // r1 = 2.0 * r0
  D[2] = [ 9.0, 7.0, 5.0, 1.0 ];
  D[3] = [ -1.0, 0.0, -2.0, -3.0 ];

  console.log("\nSource matrix: ");
  matShow(D, 1, 5);

  let detD = matDeterminantEchelon(D);
  console.log("\nDeterminant = " + 
    detD.toFixed(4).toString());

  console.log("\nEnd demo");
}

main();