Teorema de Laplace em C

Numa postagem antiga, eu apresentei a implementação do teorema de Laplace em Java, que é utilizado para o cálculo de determinantes (Teorema de Laplace em Java). Nesta postagem, apresento o mesmo algoritmo codificado na linguagem C.

O teorema de Laplace utiliza uma expansão em cofatores para realizar o cálculo de determinantes. Entretanto, não é um método eficiente para isso, pois sua complexidade no tempo é de O(n!). Isto é, ele é de ordem exponencial (na prática, é pior do que uma exponencial).

Como esta postagem é complementar, então não irei prolongá-la. Caso o leitor queira mais informações, sugiro que o mesmo acesse a postagem do algoritmo em Java. A postagem contém informações que não requer conhecimentos de Java para compreender.

Algoritmo

O algoritmo a seguir escolhe sempre a primeira linha no cálculo do determinante. É recomendado conhecer previamente o Teorema de Laplace antes de analisar o algoritmo.

#include <stdio.h>
#include <stdlib.h>
//Código por Henrique Felipe (GitHub: HenriqueIni) 
//Supõe-se que a matriz 'a' é válida e de ordem n x n
double detLaplace(int n, double a[n][n]){
    if(n == 1){
        //Caso base: matriz 1x1
        return a[0][0];
    }else{
        double det = 0;
        int i, row, col, j_aux, i_aux;
        
        //Escolhe a primeira linha para calcular os cofatores
        for(i = 0; i < n; i++){
            //ignora os zeros (zero vezes qualquer número é igual zero)
            if (a[0][i] != 0) {
                double aux[n - 1][n - 1];
                i_aux = 0;
                j_aux = 0;
                //Gera as matrizes para calcular os cofatores
                for(row = 1; row < n; row++){
                    for(col = 0; col < n; col++){
                        if(col != i){
                            aux[i_aux][j_aux] = a[row][col];
                            j_aux++;
                        }
                    }
                    i_aux++;
                    j_aux = 0;
                }
                double factor = (i % 2 == 0)? a[0][i] : -a[0][i];
                det = det + factor * detLaplace(n - 1, aux);
            }
        }
        return det;
    }
}
//Testes
int main() {
    double a[5][5] = {{1,8,3,5,0},
                      {0,-1,7,9,1},
                      {0,0,3,2,4},
                      {0,0,0,-6,-1},
                      {0,0,0,0,2}};
    printf("%.16f\n", detLaplace(5, a));
    double b[3][3] = {{2,-2,-1},
                      {3,-4,1},
                      {1,1,5}};
    printf("%.16f\n", detLaplace(3, b));
    return 0;
}

Referências

• DANTE, L. R. Matemática, Volume único. 1ª edição. São Paulo: Ática, 2005.
• MELO, J. P. B. C.; FILHO, V. S. Álgebra Linear. Universidade Cruzeiro do Sul - LFTC