The minimum number of arithmetic operations to compute the determinant

Question

Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$? For example, $n=5$.

Answer 1

It is known that the number of arithmetic operations necessary to compute the determinant of an $n\times n$ matrix is $n^{\omega+o(1)}$, where $\omega$ is the matrix multiplication constant. See for example this table on Wikipedia, as well as its footnotes and references. Note that the asymptotic complexity of matrix inversion is also the same as matrix multiplication in this same sense.

The equivalence is quite effective. In particular, you can recursively compute the determinant of a $n\times n$ matrix by working on $(n/2) \times (n/2)$ blocks using the Schur complement:

$$ \text{$D$ invertible}\qquad\implies\qquad\det \begin{pmatrix}A&B\\C&D\end{pmatrix} = \det(D) \det(A-BD^{-1}C). $$

Thus, you can compute an $n\times n$ determinant by computing two $(n/2)\times (n/2)$ determinants, inverting one $(n/2)\times (n/2)$ matrix, multiplying two pairs of $(n/2)\times (n/2)$ matrices, and some simpler operations. Expanding the determinant calls recursively, the complexity ends up being dominated by the matrix multiplication and inversion.

This works well even for small $n$ and even without using sub-cubic matrix multiplication algorithms. (Of course, it ends up being more-or-less equivalent to Gaussian elimination.) For example, for $n=4$, we can compute $\det(D)$ with two multiplications, $D^{-1}$ with four divisions, $BD^{-1}C$ with $2\times 8=16$ multiplications, $\det(A-BD^{-1}C)$ with two multiplications, and the final answer with one multiplication. The total number is $2+4+16+2+1=25$ multiplications plus divisions, which is less than the $40$ from cofactor expansion. Using Strassen's algorithm saves two multiplications here, but more asymptotically.

You may notice that this expansion crucially uses division. If you wish to avoid division, then one can do so in $O(n^4)$ operations by working with Clow sequences and dynamic programming. It is also known how to achieve $n^{2+\omega/2+o(1)}$ multiplications and no divisions.