Working with matrices is a common task in machine learning. Most of my colleagues, and me too, have a personal library set of matrix routines. I was dusting off my personal matrix library recently and, just for fun, decided to implement a Determinant() function using recursion. A recursive approach is only viable for small matrices — approximately 10 x 10 or smaller. For larger matrices, you should use a (very complex) technique that involves matrix decomposition.

I am not a fan of recursion and I rarely use it except when working with tree data structures, and even then I avoid recursion when possible. So my recursive implementation of Determinant() was mostly for mental exercise.

If M =

 3  6
 2  7

then Det(M) = (3 * 7) – (6 * 2) = 9. If M =

 1  2  3
 4  5  6
 7  8  9

Det(M) =  (+1) * 1 *  det 5  6
                          8  9

        + (-1) * 2 *  det 4  6
                          7  9

        + (+1) * 3 *  det 4  5
                          7  8

and do on.

Anyway, after thrashing around for a few minutes, I came up with the following C# implementation of a recursive function to compute the determinant of a matrix:

static double Det(double[][] m)
{
  double sum = 0.0;
  int sign;  // -1 or +1

  if (m.Length == 1)
    return m[0][0];
  else if (m.Length == 2)
    return (m[0][0] * m[1][1]) - (m[0][1] * m[1][0]);

  for (int j = 0; j less-than m.Length; ++j) // each col of m
  {
    double[][] small = new double[m.Length-1][];  // n-1 x n-1
    for (int i = 0; i less-than small.Length; ++i)
      small[i] = new double[m.Length-1];

    for (int r = 1; r less-than m.Length; ++r)  // start row [1]
    {
      for (int c = 0; c less-than m.Length; ++c)
      {
        if (c less-than j)
          small[r - 1][c] = m[r][c];
        else if (c greater-than j)
          small[r - 1][c - 1] = m[r][c];
        else // if (c == j)
          ; // skip this col
      } // c
    } // r

    if (j % 2 == 0)
      sign = +1;
    else
      sign = -1;

    sum += sign * m[0][j] * Det(small); // recursive call
  } // j
  return sum;
}

My personal matrix library has a non-recursive Determinant() function that uses Crout’s matrix decomposition technique.

Moral of the story: working with matrices is rather tricky but it’s an essential skill for machine learning.

Three determined puppies. Left: This is “Llama” and she is determined to get her owner’s attention. Center: This is my dog “Riley”. I was taking a nap and when I woke up, Riley was determined to get praise for chewing up my “Chess Life” magazine and three random socks. Right: This determined puppy walks softly and carries a big stick.