La fórmula para el determinante de una matriz de $n$ por $n$ dada por la expansión de menores involucra $n!$ términos. Como tal, calcular el determinante de una matriz dada con entradas enteras a través de la expansión de menores toma un número de pasos que está limitado por debajo por $n!$. (En la práctica, el número de pasos requeridos depende del tamaño de las entradas de la matriz).
Sin embargo, el determinante de dicha matriz también se puede calcular mediante la Eliminación Gaussiana; conocemos cómo afecta cada operación elemental de fila al determinante de una matriz y si llevamos un registro de los pasos de reducción de fila que realizamos en el proceso de la eliminación Gaussiana, podemos reconstruir casi de inmediato el determinante de la matriz original a partir de estos datos. El número de pasos que toma reducir por fila una matriz con entradas enteras es $O(n^3)$ y por lo tanto este método de calcular el determinante de una matriz toma $O(n^3)$ pasos.
Contraponiendo los dos métodos anteriores, se observa que el problema computacional bajo discusión parece ser muy consumidor de tiempo desde una perspectiva pero es mucho más rápido desde otra perspectiva. En este sentido, el problema es análogo al de calcular una suma parcial de una serie telescópica. Y sin embargo, no está del todo claro para mí cómo ver la "cancelación implícita" de la fórmula que proviene de la expansión por menores. De hecho, la fórmula tiene una similitud superficial con la de la fórmula para el permanente de una matriz, cuyo cálculo es #P-completo. El hecho de que la mitad de los términos del determinante tengan signos negativos delante hace que la fórmula del determinante se parezca más a una suma telescópica que a la fórmula del permanente, pero no mucho.
¿Existe una forma de ver el hecho de que el determinante de una matriz está acotado por un polinomio en la dimensión de la matriz y el tamaño de las entradas directamente desde la fórmula dada por la expansión por menores?
