6
$\begingroup$

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$?

  • 0
    "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.2011-08-15

1 Answers 1

7

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?