Calcular el determinante de una matriz por Gauss

Problema: se da una matriz $A$ de tamaño $N \times N$. Calcular su determinante.

Algoritmo

Usamos las ideas del método de Gauss para resolver sistemas de ecuaciones lineales

Realizaremos los mismos pasos que en la solución de sistemas de ecuaciones lineales, excluyendo solo la división de la línea actual por $a_{ij}$. Estas operaciones no cambiarán el valor absoluto del determinante de la matriz. Cuando intercambiamos dos líneas de la matriz, sin embargo, el signo del determinante puede cambiar.

Después de aplicar Gauss sobre la matriz, recibimos una matriz diagonal, cuyo determinante es simplemente el producto de los elementos de la diagonal. El signo, como se mencionó antes, se puede determinar por el número de filas intercambiadas (si es impar, entonces el signo del determinante debe invertirse). Así, podemos usar el algoritmo de Gauss para calcular el determinante de la matriz en complejidad $O(N^3)$.

Cabe señalar que si en algún momento no hallamos una celda no nula en la columna actual, el algoritmo debe detenerse y devolver 0.

Implementación

const double EPS = 1E-9;
int n;
vector < vector<double> > a (n, vector<double> (n));
 
double det = 1;
for (int i=0; i<n; ++i) {
	int k = i;
	for (int j=i+1; j<n; ++j)
		if (abs (a[j][i]) > abs (a[k][i]))
			k = j;
	if (abs (a[k][i]) < EPS) {
		det = 0;
		break;
	}
	swap (a[i], a[k]);
	if (i != k)
		det = -det;
	det *= a[i][i];
	for (int j=i+1; j<n; ++j)
		a[i][j] /= a[i][i];
	for (int j=0; j<n; ++j)
		if (j != i && abs (a[j][i]) > EPS)
			for (int k=i+1; k<n; ++k)
				a[j][k] -= a[i][k] * a[j][i];
}
 
cout << det;

Problemas de práctica

• Codeforces - Wizards and Bets