Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
    
Sure, I specified integer entries for a reason. –  Jonah Sinick Nov 14 '11 at 17:22
    
@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
add comment

The most important property of the determinant is that it's multiplicative, which is what makes row reduction work. (Note that the permanent isn't.) This is not a trivial consequence of the permutation expansion of the determinant; working from the permutation expansion one can deduce multiplicativity combinatorially but it is, in my opinion, more work than necessary.

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.

share|improve this answer
    
don't forget that Det is very similar to Perm while one is in P the other is #P-complete. –  Kaveh May 15 '13 at 8:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.