# Looking for a tractable algorithm or formula for the determinant of a tensor

It is possible to define the determinant of a tensor. We think of a tensor as a collection of numbers but this collection easily extends to a proper multilinear map. If $T:\{1,....,n\}^m\to \mathbb C$ then one can define $$\operatorname{Det}T:=\sum_{\sigma_2,...,\sigma_m\in S_n}\left(\left[\prod_{i=2}^m\operatorname{Sign}\sigma_i\right]\left[\prod_{k=1}^n T(k,\sigma_2(k),...,\sigma_m(k))\right]\right).$$

This determinant satisfies some rules that are similar to the normal determinant. For example, if we add a slice to a different slice then the determinant remains the same (for matrices, if we add one column to another one then the determinant does not change). If we view map $T$ as a tensor then the value of the determinant is also invariant under a change of basis (if the transition matrix has determinant one).

For fixed $m$, the naive algorithm to determine the number runs in $O(n!^{m-1})$ (ie not very efficiently). It would be very helpful to have an efficient algorithm to make some small calculations, or even knowing the computational complexity of calculating this number would be very helpful (preferably polynomial, of course). If there is any literature on this determinant (I have not been able to find any on this) then this would also be hugely welcomed.

• By the way, I think your nice properties only hold when the tensor has an even number of indices (i.e. $m$ is even). For example when $m=1$ your formula reduces to saying that $\mathrm{Det} v$ is just the product of the entries of $v$, which is clearly not basis-independent even if we restrict the possible change-of-basis matrices to unitaries with determinant $1$. – Oscar Cunningham Apr 15 '18 at 14:08
• Yes - you are correct, I forgot to mention that. In my application, the $m$ happens to be of the form $k!$, so this is not a problem. Thanks! – Pete L. Apr 16 '18 at 14:57

## 1 Answer

This is the Cayley hyperdeterminant, see [1,2], which is believed to be an NP-hard computation [3].

1. F. Gherardelli, Osservazioni sugli iperdeterminanti, Istit. Lombardo Accad. Sci. Lett. Rend. A 127, 107 (1993).
2. The Cayley Determinant of the Determinant Tensor and the Alon Tarsi Conjecture (1997).
3. On the hardness of the noncommutative determinant (2009).
• This is very helpful. I was wondering how you derive your final statement from [3]. Is the Cayley hyperdeterminant related to the nonsymmetrised Cayley determinant (Cdet) in [3]? – Pete L. Apr 14 '18 at 9:39