<p>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 <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra">this table</a> 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.</p>

<p>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:</p>

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

<p>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.</p>

<p>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.</p>

<p>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 <a href="http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf">Clow sequences and dynamic programming</a>.  It is also <a href="http://www4.ncsu.edu/~kaltofen/bibliography/92/Ka92_issac.pdf">known</a> how to achieve $n^{2+\omega/2+o(1)}$ multiplications and no divisions.</p>

CC BY-SA 3.0
2016-11-30T10:52:15.417Z
Do you know any lower bound on just the number of multiplications?  Even for n = 3?
Jeffrey Shallit
CC BY-SA 3.0
2016-11-30T11:00:38.703Z
Your phrasing "the number of arithmetic operations necessary to compute the determinant of an $n \times n$ matrix is $n^{\omega +o(1)}$" suggests that a lower bound is known.  But I did not see this in any of the cited works.  Am I missing something?
Jeffrey Shallit
CC BY-SA 3.0
2016-11-30T12:38:29.867Z
The lower bound is in the paper by W.Baur and V.Strassen "The complexity of partial derivatives" (http://dx.doi.org/10.1016/0304-3975(83)90110-X)
Vladimir Lysikov
CC BY-SA 3.0
2016-11-30T06:51:52.197Z
2016-11-30T18:04:31.327Z
2016-11-30T18:04:31.327Z
A. Rex
<p>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$.</p>

CC BY-SA 3.0
2016-11-21T17:23:14.313Z
I've asked experts about this, and apparently it is not even currently known whether or not 9 multiplications are needed to compute the determinant of a 3x3 matrix.
Jeffrey Shallit
CC BY-SA 3.0
2016-11-21T19:36:30.640Z
@JeffreyShallit If $9$ is possible that is already interesting (as it is less than $n^3$ for example). How about $n=4$?
Simd
CC BY-SA 3.0
2016-11-21T22:41:18.937Z
No, not interesting at all.  9 multiplications for n=3 follows by expansion by minors.  For n = 4 again, expansion by minors gives 40.  I don't know how to do it in less than 40 multiplications.
Jeffrey Shallit
CC BY-SA 3.0
2016-11-22T08:41:59.103Z
@JeffreyShallit Oh I see, good point. It's amazing (at least to me) if nothing better than naive is known for any fixed $n$.
Simd
CC BY-SA 3.0
2016-11-22T15:32:24.683Z
If someone knows, perhaps they can tell us.
Jeffrey Shallit
CC BY-SA 3.0
2016-11-23T23:27:18.173Z
No, I know of no decent lower bound.  Dan Roche is working on it, though.
Jeffrey Shallit
<cc.complexity-theory><linear-algebra><determinant>
The minimum number of arithmetic operations to compute the determinant
Simd
# The minimum number of arithmetic operations to compute the determinant

(Asked by: username_0 on 2016-11-21)

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

**Tags:** cc.complexity-theory, linear-algebra, determinant
> **Comments:**
> **username_1**: I've asked experts about this, and apparently it is not even currently known whether or not 9 multiplications are needed to compute the determinant of a 3x3 matrix.  
> **username_0**: @JeffreyShallit If $9$ is possible that is already interesting (as it is less than $n^3$ for example). How about $n=4$?  
> **username_1**: No, not interesting at all.  9 multiplications for n=3 follows by expansion by minors.  For n = 4 again, expansion by minors gives 40.  I don't know how to do it in less than 40 multiplications.  
> **username_0**: @JeffreyShallit Oh I see, good point. It's amazing (at least to me) if nothing better than naive is known for any fixed $n$.  
> **username_1**: If someone knows, perhaps they can tell us.  
> **username_1**: No, I know of no decent lower bound.  Dan Roche is working on it, though.  

---

## 1 answers

### Answer by username_2 on 2016-11-30. Score: 11 | Accepted answer

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](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra) 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](http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf). It is also [known](http://www4.ncsu.edu/~kaltofen/bibliography/92/Ka92_issac.pdf) how to achieve $n^{2+\omega/2+o(1)}$ multiplications and no divisions.

> **Comments:**
> **username_1**: Do you know any lower bound on just the number of multiplications?  Even for n = 3?  
> **username_1**: Your phrasing "the number of arithmetic operations necessary to compute the determinant of an $n \times n$ matrix is $n^{\omega +o(1)}$" suggests that a lower bound is known.  But I did not see this in any of the cited works.  Am I missing something?  
> **username_3**: The lower bound is in the paper by W.Baur and V.Strassen "The complexity of partial derivatives" (http://dx.doi.org/10.1016/0304-3975(83)90110-X)  

---

