computing the determinant of $A$ requires at most $O(n^3)$ operations Let $A$ be an $n\times n$ matrix, show that computing the determinant of $A$
requires at most $O(n^3)$ operations (addition, multiplication, etc).
We know that $PA=LU$, and I have already proved that the diagonal entries of a upper(or lower) triangular matrix is equal to its determinant. So $\det(A) =\det(P^{-1}LU)$. So I know $L, U$ need $n$, and for $LU$, it requires $n$. 
But how can I say $P^{-1}$ requires $n$? Or is this wrong? Thank you. 
 A: The easy way to demonstrate that determinant can be done in $O(n^3)$ operations is to use the Gauss-Jordan elimination algorithm with full pivoting, multiplying the pivot elements used (including the remaining element at the end) to get the determinant.
Each step takes $O(n^2)$ operations for the row eliminations, plus $O(n^2)$ for determining the right pivot, plus $O(n)$ for row-swapping, normalization of the pivot row, and other cruft; the sum is still $O(n^2)$.  There needs to be $n$ such pivot operations, giving a net complexity of $O(n^3)$.
Actually, you can do much better than that. The Strassen algorithm was the first such one found.  It depends on repeatedly dividing the problem into two smaller matrices, and noting that it takes only seven wisely chosen multiplications to multiply two $2\times 2$ matrices; the net complexity for multiplication, inversion, and determinant becomes $O(n^{\log_2 7})$. The Coppersmith-Winograd algorithm has a complexity of better than $O(n^{2.376})$ and there are also slightly better ones than that.
A: If you can show (or are allowed to assume that) the LU decomposition can be done in at most $O(n^3)$, then just use $$\det(LU) = \det(L)\det(U)$$ And then remains $n-1$ multiplications calculating each determinant. 
(Just multiply together diagonal entries, which is guaranteed to equal the determinant for a triangular matrix as the eigenvalues must be the same as the diagonal entries for such a matrix.)
