# Computational complexity of computing the determinant

The formula for the determinant of an $n$ by $n$ matrix given by expansion of minors involves $n!$ terms. As such, computing the determinant of a given matrix of with integer entries via expansion by minors takes a number of steps is bounded below by $n!$ . (In practice the number of steps required depends on the size of the matrix entries).

However, the determinant of such a matrix can also be computed by Gaussian Elimination; we know how each elementary row operation affects the determinant of a matrix and if we keep track of the row reduction steps which we perform in the process of performing Gaussian elimination we can almost immediately reconstruct the determinant of the original matrix from this data. The number of steps that it takes to row reduce a matrix with integer entries is $O(n^3)$ and so this method of computing the determinant of a matrix takes $O(n^3)$ steps.

Juxtaposing the two methods above, one sees that the computational problem under discussion looks to be very time consuming from one perspective but is much faster from another perspective. In this respect the problem is analogous to that of computing a partial sum of a telescoping series. And yet it's not at all clear to me how see the "implicit cancellation" from the formula that comes from expansion by minors. Indeed, the formula bears a strong superficial similarity with that of the formula for the permanent of a matrix, the computation of which is #P-complete. The fact that half of the terms of the determinant have negative signs in front of them makes the formula for the determinant look more like a telescoping sum than the formula for the permanent, but not by very much.

Is there a way to see the fact that the determinant of a matrix is bounded by a polynomial in the dimension of the matrix and size of the entries directly from the formula given by expansion by minors?

-
I don't think so. You're essentially trying to shoehorn one (slow) algorithm into another (fast) one. Remember that in the fast algorithm, we have exploited $\det(\mathbf A\mathbf B)=\det\,\mathbf A\det\,\mathbf B$... – J. M. Nov 13 '11 at 2:44
There seems to be an algorithm for computing the determinant based on the minor expansion which uses dynamic programming techniques and has a running time of $O(n^4)$: books.google.com/… – Bill Cook Nov 13 '11 at 20:31
From what I read, this algorithm avoids division. So in certain contexts the expense of $n^4$ instead of $n^3$ is justified. – Bill Cook Nov 13 '11 at 20:35
A bit OT, but if you count every $+$, $-$ and $\cdot$ as one operation, then there is a very nice closed form expression for the number of operations involved in the recursive minor expansion. A famous number is involved too... – WimC Mar 14 '12 at 12:13

Actually the computation of the determinant of a matrix is not bounded by a polynomial in the dimension of the matrix and size of the entries. Try calculating the determinant of an $n\times n$ matrix with $n^2$ distinct indeterminates as entries (in a polynomial ring or field of rational functions in that many indeterminates); the result has $n!$ terms. Gaussian elimination only works over a field, but as the example shows even then it is not reasonable to assume constant-time arithmetic without more information. In fact the $O(n^3)$ estimate is only realistic over finite fields.
@Jonah: Apologies, I shouldn't have missed that. However Gaussian elimination of matrices with integer entries requires introduction of rational numbers whose representation can rapidly grow. Certainly constant-time arithmetic is not realistic for rational numbers. I think the $O(n^4)$ estimate for integer matrices are all-integer techniques, with maybe some control of coefficient growth included. I don't think rational Gaussian elimination compares favourable to that result. – Marc van Leeuwen Nov 17 '11 at 14:46
Really this multiplicativity is about functoriality: the determinant is just the action of the exterior power functor $\Lambda^n(-)$ on endomorphisms $T : V \to V$ of $n$-dimensional vector spaces. Again, the permanent doesn't arise in this way. There is extra structure here and it isn't trivially deducible from the permutation expansion but requires some actual thought about where the determinant comes from and why people care about it in the first place.