Calculate Determinant Matrix with Javascript
Tags: javascript, recursion, linearalgebra, codewars
Published: 2023-08-16 06:22:26

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
```