26
$\begingroup$

In a comment on this question in 2016, 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.

$\endgroup$
1
  • 8
    $\begingroup$ 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 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). $\endgroup$
    – holf
    Jun 26 at 6:30

1 Answer 1

5
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.