Determinante matriz de orden 'N'

[juancaa]

Bueno, no hace mucho hice un algoritmo para calcular el determinante de una matriz de orden 'N' en C, se centra basicamente en la deifinicion del calculo del determinante de una matriz de orden 'N'.

Para aquellos que os interese aqui os dejo mi codigo, aunque creo que no contiene errores no estoy seguro, podeis probarlo y decirme que tal, a mi no me ha dado problemas:

Código [Seleccionar] Expandir

#include <stdio.h>
#define N 100
int sgn (int x);
int read_dim (int *dim);
int matrix_adj (int matrix[N][N], int matrix_aux[N][N], int dim, int m, int n);
int det_matrix_N (int matrix[N][N], int dim);
int det_matrix_adj (int matrix[N][N], int dim, int m, int n);

main() {
int i, j, dim, det, matrix[N][N];
while (!read_dim(&dim))
printf("Dimension no valida (<100).");
printf("\nIntroduzca elementos matriz...\n");
for (i=1; i<=dim; i++) {
printf("Elementos fila %d: ", i);
for (j=0; j<dim; j++)
scanf("%d", &matrix[i-1][j]);
}
if (dim!=1)
det=det_matrix_N(matrix,dim);
else
det=matrix[0][0];
printf("\nDeterminante = %d.\n\n", det);
}

int sgn (int x) {
if (x%2==0) return(1);
return(-1);
}
int read_dim (int *dim) {
int nl;
char aux;
printf("\nIntroduzca dimension matriz cuadrada (<100): ");
nl=scanf("%d", &(*dim));
if (nl!=1) {
scanf("%c", &aux);
while (aux!='\n')
scanf("%c", &aux);
}
if ( (*dim>=100) || (*dim<=0) )
return(0);
return(1);
}
int matrix_adj (int matrix[N][N], int matrix_aux[N][N], int dim, int m, int n) {
int i, j, p, q;
for (j=0, q=0; j<dim; j++)
if (j!=n) {
for (i=0, p=0; i<dim; i++)
if (i!=m) {
matrix_aux[p][q]=matrix[i][j];
p++;
}
q++;
}
return(dim-1);
}
int det_matrix_N (int matrix[N][N], int dim) {
int i, j, dim_aux, det;
for (i=0, j=0, det=0, dim_aux=dim; i<dim; i++)
det+=sgn(i+j)*matrix[i][j]*det_matrix_adj(matrix,dim_aux,i,j);
return(det);
}
int det_matrix_adj (int matrix[N][N], int dim, int m, int n) {
int matrix_aux[N][N];
if ( (matrix_adj(matrix,matrix_aux,dim,m,n)) == 1 )
return(matrix_aux[0][0]);
return(det_matrix_N(matrix_aux,dim-1));
}


Un saludo y espero que os sirva!!

[ghastlyX]

Mirándolo por encima la idea es correcta, como no haya algún bug tonto parece que tu código es correcto (no lo he ejecutado). Te comento un par de cosas a tener en cuenta:

Para matrices relativamente pequeñas, tu código puede tener overflow puesto que el determinante implica muchos productos. Para evitar esto completamente tendrías que utilizar algún tipo de BigInts.

Más importante es la complejidad de tu algoritmo. El algoritmo de calcular el determinante por adjuntos es útil para hacerlo a mano con matrices pequeñas, pero es muy ineficiente probar todos los adjuntos, ya que deja una complejidad de O(n!), de modo que a partir de matrices de orden 13 o 14, olvídate de que acabe en un tiempo razonable tu programa. Puedes acelerar tu programa siguiendo el mismo algoritmo utilizando programación dinámica donde el estado es por qué fila de la matriz estás y una máscara de bits que indican qué filas puedes utilizar. Esto da un total de n2ⁿ estados que necesitan tratarse haciendo un bucle en cada uno, luego la complejidad total subiría a O(n²2ⁿ), menor que la anterior, aunque igualmente grande.

La manera buena para calcular el determinante es cúbica y se puede hacer de varias maneras. Por ejemplo por eliminación gaussiana o por descomposición LU de la matriz.