<p>I have a partial answer to this now.</p>
<p>I still don’t know whether anyone had ever explicitly written down a method for computing the 3×3 determinant using 8 multiplications, but anyone with sufficient knowledge of linear algebra <em>could have done</em>, if it had occurred to them.</p>
<p>The tensor rank of the cross product is known to be at most 5. This follows from a general theorem of Kruskal (1989, but a proof was apparently only published years later by Murray and Hu (2013)), and an explicit formula is given by Krishna and Makam (2018) at the bottom of page 5.</p>
<p>Concretely this implies that the cross product may be computed using 5 multiplications, from which of course it follows immediately that the determinant may be computed using 8.</p>
<hr />
<p>Bremner, Murray R.; Hu, Jiaxiong,
<em>On Kruskal's theorem that every <span class="math-container">$3\times3\times3$</span> array has rank at most 5</em>.
Linear Algebra Appl. 439,
2013,
no. 2,
pages 401–421.
<a href="https://arxiv.org/abs/1209.1553" rel="nofollow noreferrer">arXiv:1209.1553</a></p>
<p>Kruskal, Joseph B.
<em>Rank, decomposition, and uniqueness for 3-way and N-way arrays.</em>
Multiway data analysis,
1989,
pages 7-18</p>
<p>Siddharth Krishna and Visu Makam,
<em>On the tensor rank of 3×3 permanent and determinant</em>,
2018,
<a href="https://arxiv.org/abs/1801.00496" rel="nofollow noreferrer">arXiv:1801.00496</a></p>

CC BY-SA 4.0
2022-06-29T13:56:47.123Z
2022-06-29T14:52:35.003Z
2022-06-29T14:52:35.003Z
Robin Houston
<p>In a comment on <a href="https://cstheory.stackexchange.com/questions/37017/the-minimum-number-of-arithmetic-operations-to-compute-the-determinant">this question</a> in 2016, <a href="https://cstheory.stackexchange.com/users/3227/jeffrey-shallit">Jeffrey Shallit</a> remarked:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p><strong>I’m curious as to whether the state of knowledge has improved since this was written.</strong></p>
<hr />
<p>The reason I’m curious is that I can do it in 8 multiplications, like so:</p>
<p><span class="math-container">$$\left|\begin{array}{ccc}a&amp;b&amp;c\\d&amp;e&amp;f\\g&amp;h&amp;i\end{array}\right|=a(E+F+G)+b(D+F+H)-c(F+G+H)$$</span></p>
<p>where <span class="math-container">$$\begin{eqnarray}D&amp;=&amp;d(h-i)\\E&amp;=&amp;e(i-g)\\F&amp;=&amp;f(g-h)\\G&amp;=&amp;g(e-f)\\H&amp;=&amp;h(f-d)\end{eqnarray}$$</span></p>
<p>and I’m interested in whether this was already known.</p>

CC BY-SA 4.0
2022-06-26T06:30:28.863Z
Related: it is not known how many multiplications you need to multiply two $3 \times 3$ matrices. The best upper bound is 23. Heule, Kauers and Seidl have tried to use SAT-solvers based techniques for this https://arxiv.org/abs/1903.11391. They found new schemes with 23 multiplications but could not get further down. I wonder whether such techniques could be used for your question (an UNSAT result with the right formula will give you a certified lower bound since SAT solvers output certificate of unsatisfiability).
holf
<cc.complexity-theory><linear-algebra><determinant>
How many multiplications are needed to compute the determinant of a 3×3 matrix?
Robin Houston
# How many multiplications are needed to compute the determinant of a 3×3 matrix?

(Asked by: username_0 on 2022-06-25)

In a comment on [this question](https://cstheory.stackexchange.com/questions/37017/the-minimum-number-of-arithmetic-operations-to-compute-the-determinant) in 2016, [Jeffrey Shallit](https://cstheory.stackexchange.com/users/3227/jeffrey-shallit) remarked:

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

**I’m curious as to whether the state of knowledge has improved since this was written.**

---

The reason I’m curious is that I can do it in 8 multiplications, like so:

$$\left|\begin{array}{ccc}a&b&c\\d&e&f\\g&h&i\end{array}\right|=a(E+F+G)+b(D+F+H)-c(F+G+H)$$

where $$\begin{eqnarray}D&=&d(h-i)\\E&=&e(i-g)\\F&=&f(g-h)\\G&=&g(e-f)\\H&=&h(f-d)\end{eqnarray}$$

and I’m interested in whether this was already known.

**Tags:** cc.complexity-theory, linear-algebra, determinant
> **Comments:**
> **username_1**: Related: it is not known how many multiplications you need to multiply two $3 \times 3$ matrices. The best upper bound is 23. Heule, Kauers and Seidl have tried to use SAT-solvers based techniques for this https://arxiv.org/abs/1903.11391. They found new schemes with 23 multiplications but could not get further down. I wonder whether such techniques could be used for your question (an UNSAT result with the right formula will give you a certified lower bound since SAT solvers output certificate of unsatisfiability).  

---

## 1 answers

### Answer by username_0 on 2022-06-29. Score: 6

I have a partial answer to this now.

I still don’t know whether anyone had ever explicitly written down a method for computing the 3×3 determinant using 8 multiplications, but anyone with sufficient knowledge of linear algebra *could have done*, if it had occurred to them.

The tensor rank of the cross product is known to be at most 5. This follows from a general theorem of Kruskal (1989, but a proof was apparently only published years later by Murray and Hu (2013)), and an explicit formula is given by Krishna and Makam (2018) at the bottom of page 5.

Concretely this implies that the cross product may be computed using 5 multiplications, from which of course it follows immediately that the determinant may be computed using 8.

---

Bremner, Murray R.; Hu, Jiaxiong,
*On Kruskal's theorem that every $3\times3\times3$ array has rank at most 5*.
Linear Algebra Appl. 439,
2013,
no. 2,
pages 401–421.
[arXiv:1209.1553](https://arxiv.org/abs/1209.1553)

Kruskal, Joseph B.
*Rank, decomposition, and uniqueness for 3-way and N-way arrays.*
Multiway data analysis,
1989,
pages 7-18

Siddharth Krishna and Visu Makam,
*On the tensor rank of 3×3 permanent and determinant*,
2018,
[arXiv:1801.00496](https://arxiv.org/abs/1801.00496)


---

