#include <stdio.h>
#include "matrix.h"

/* This file defines functions to calculate determinant of a matrix:
 * 	A function that calculates determinant of a permutation matrix
 * 	A function that calculates determinant of an arbitrary matrix
 */



/* Computes the determinant of permutation matrix P.
 * It is +1, or -1 since every row and column of P has exactly one non-zero entry,
 * and that is equal to 1.
 */
float compute_det_permutation(float P[][N], int n)
{
	float Q[N][N]; // stores a submatrix of P
	int i; // P[0][i] = 1

	if (n == 1) // P = [1]
		return 1;

	i = find_nonzero_column(P, n);

	// Drop first row and ith column of P and copy into Q
	for (int j = 0; j < n-1; j++)
		for (int k = 0; k < n-1; k++)
			if (k < i)
				Q[j][k] = P[j+1][k];
			else
				Q[j][k] = P[j+1][k+1];
	
	// determinant of P equals determinant of Q times (-1)^i
	if (i % 2 == 1) // i is odd
		return -compute_det_permutation(Q, n-1);
	else
		return compute_det_permutation(Q, n-1);
}


/* Computes the determinant of size n matrix
 * stored in array A using recursion. 
 */
float determinant(float A[][N], int n)
{
	int i;
	float B[N][N]; // stores a submatrix of A

	if (n == 1) // 1 x 1 matrix
		return A[0][0];

	if (A[0][0] == 0) {
		i = find_nonzero_row(A, n);
		if (i >= n) // no non-zero row
			return 0; // determinant is 0
		add_row(A[0], A[i], 1, n); // add row #i to row #0
	}

	for (int t = 1; t < n; t++) // make first column of A[t] zero
		add_row(A[t], A[0], -A[t][0] / A[0][0], n);

	// Drop the first row and column of A
	copy_matrix(B, 0, A, 1, n-1);

	/* The determinant of A equals the determinant of B times
	 * A[0][0].
	 */
	return A[0][0] * determinant(B, n-1);
}