Calculate Determinant Matrix with Javascript

Yesterday, I had difficulty doing a kata (challenge in codewars). I started getting used to doing 1 kata 1 day as part of my learning algorithm and data structures.

I also have a hard time understanding recursion. When I encountered a recursion problem for calculating the determinant matrix, I started trying to analyze it to find a solution.

Here is the question :

Write a function that accepts a square matrix (N x N 2D array) and returns the determinant of the matrix.

How to take the determinant of a matrix -- it is simplest to start with the smallest cases:

A 1x1 matrix |a| has determinant a.

A 2x2 matrix [ [a, b], [c, d] ] or

|a  b|
|c  d|

has determinant: a*d - b*c.

The determinant of an n x n sized matrix is calculated by reducing the problem to the calculation of the determinants of n matrices of n-1 x n-1 size.

For the 3x3 case, [ [a, b, c], [d, e, f], [g, h, i] ] or

|a b c|  
|d e f|  
|g h i|  

the determinant is: a * det(a_minor) - b * det(b_minor) + c * det(c_minor) where det(a_minor) refers to taking the determinant of the 2x2 matrix created by crossing out the row and column in which the element a occurs:

|- - -|
|- e f|
|- h i|  

Note the alternation of signs.

The determinant of larger matrices are calculated analogously, e.g. if M is a 4x4 matrix with first row [a, b, c, d], then:

det(M) = a * det(a_minor) - b * det(b_minor) + c * det(c_minor) - d * det(d_minor)

Solution

1. Define the function

/**
 * Calculate determinant on matrix
 * @param m: matrix [[]]
 * @returns determinant: number
 */
function determinant(m) {}

In this definition we have matrix parameters for determinant function and the desired result is a number

2. Know the dimensions of the matrix

const n = m.length;

Because it has been ascertained that the input matrix is always square or has the same N, what we need to know is NxN or what order the input matrix is.

3. Solve the easy-to-know possibilities first

if (n == 1) return m[0][0];

if (n == 2) {
    return m[0][0] * m[1][1] - m[0][1] * m[1][0];
}

Based on what has been told in the problem, if the matrix is of the order 1x1, then the result will be the matrix elements themselves. For matrices of order 2x2, we can directly calculate it with a*d - b*c for [[a, b], [c, d]].

4. Create a minor function inside determinant function

function minor(matrix, row, col) {
    return matrix
      .map((r, i) => r.filter((_, j) => i !== row && j !== col))
      .filter((r, i) => i !== row);
}

For the case of matrices of order greater than 2. In the problem, we are told to use the minor method, which is to make a 2x2 matrix outside of the rows and columns of elements being calculated. To do this we need to map the original matrix and filter out the rows and columns other than the rows and columns of elements calculated in row one.

5. Calculate and return determinant

let det = 0;

for (let col = 0; col < n; col++) {
    det += m[0][col] * determinant(minor(m, 0, col)) * (col % 2 === 0 ? 1 : -1);
}

return det;

After that, calculate the determinant using the minor method by calling the minor function for each of the first row elements based on the hint given by the question.

The full code can be seen as follows :

/**
 * Calculate determinant on matrix
 * @param m: matrix [[]]
 * @returns determinant: number
 */
function determinant(m) {
    const n = m.length;

    if (n == 1) return m[0][0];

    if (n == 2) {
        return m[0][0] * m[1][1] - m[0][1] * m[1][0];
    }

    function minor(matrix, row, col) {
        return matrix
            .map((r, i) => r.filter((_, j) => i !== row && j !== col))
            .filter((r, i) => i !== row);
    }

    let det = 0;

    for (let col = 0; col < n; col++) {
        det += m[0][col] * determinant(minor(m, 0, col)) * (col % 2 === 0 ? 1 : -1);
    }

    return det;
}

For tests :

/* Tests */
console.log(determinant([[1]])); // 1
console.log(
    determinant([
        [1, 2],
        [3, 4],
    ]),
); // -2
console.log(
    determinant([
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]),
); // 0
console.log(
    determinant([
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 16],
    ]),
); // 0