Calculando o determinante de uma matriz por Gauss

Problema: Dada uma matriz $A$ de tamanho $N x N$. Calcule seu determinante.

Algoritmo

Usamos as idéias do método de Gauss para resolver sistemas de equações lineares

Executaremos as mesmas etapas da solução de sistemas de equações lineares, excluindo apenas a divisão da linha atual em $a_{ij}$. Essas operações não irão alterar o valor absoluto do determinante da matriz. No entanto, quando trocamos duas linhas da matriz o sinal do determinante pode mudar.

Após aplicar Gauss na matriz, recebemos uma matriz diagonal, cujo determinante é apenas o produto dos elementos na diagonal. O sinal, como mencionado anteriormente, pode ser determinado pelo número de linhas trocadas (se ímpares, o sinal do determinante deve ser revertido). Assim, podemos usar o algoritmo de Gauss para calcular o determinante da matriz com complexidade $O(N^3)$.

Observe que, em algum momento, se não encontrarmos uma célula diferente de zero na coluna atual, o algoritmo deverá parar e retornar 0.

Implementação

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