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.

In Friedberg's Linear Algebra, the author points out that the evaluation of the determinant of an $n\times n$ matrix by cofactor expansion along any row requires over $n!$ multiplications, whereas evaluating the determinant of an $n\times n$ matrix by elementary row operations can be shown to require only $(n^3+2n-3)/3$ multiplications.

I cannot even figure out the case when $n=2$. The key point, I think, is the exact algorithm of evaluating by elementary row operations. But I temporarily have no idea how to go on.

Here is my question:

How can I deduce the number $(n^3+2n-3)/3$?

share|improve this question
    
"The key point, I think, is the exact algorithm of evaluating by elementary row operations." - right, so count the number of operations you need to turn your matrix into a triangular matrix, and then remember that (up to sign and depending on the number of swaps you did) the determinant of the original matrix is the same as the product of the diagonal elements of the triangular matrix you ended up with. –  J. M. Aug 15 '11 at 3:50

1 Answer 1

up vote 7 down vote accepted

Assuming the $(1,1)$ entry is non-zero, you have to do $n$ multiplications to use the first row to wipe out the $(2,1)$ element, another $n$ to wipe out $(3,1)$, etc.: all told, $n(n-1)$ operations to wipe out the first column. Then you have to do $((n-1)^3+2(n-1)-3)/3$ multiplications to get the determinant of the $(n-1)\times (n-1)$ matrix, and one more multiplication to finish things off. Does it add up right?

share|improve this answer

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.