Multi-dimensional permanent

Question

Is there a particularly natural / "correct" way of generalizing permanents to tensors? (I mean of course, 'square' tensors.) There seem to be very few resources on the matter. There needs to be a replacement for considering the permutations from one index. For a rank $k$ tensor, some sources seem to take $k-1$ permutations $\sigma_i$ and then multiply over the indices $A_{i,\sigma_1(i),\sigma_2(i)\dots \sigma_{k-1}(i)}$. For instance, Multi-dimensional permanent of structured tensor uses them this way.

Alternately, we can think of the permanent's permutations as providing a "map" from one index to another -- this is particularly relevant in graph theory where it describes a path from one vertex to another -- so there it seems more reasonable to sum over arrays $M$. Each array $M$ has $k-1$ indices, and contains values in the range $1\dots d$ (where $d$ is the number of rows etc in the tensor). I think require that all rows columns etc. in this array are orthogonal: if I change one index in $M$ then I change the value. There is at least one source, http://www.sciencedirect.com/science/article/pii/0024379587903119 that considers these and calls them "$s$-permanents", although I admit I'm not clear why this name. The source https://arxiv.org/pdf/1101.3629.pdf also refers to them as the permanent, without any particular name.

Can anyone explain what the salient differences of these two are? I'm trying to interpret permanents on hypergraphs, and to me, these $s$-permanents seem to be the more natural construction. Is there an immediate rational for the former definition? Maybe in terms of their relation to determinants?

Answer 1

Indeed, there is no generally accepted definition of the permanent of multidimensional tensor (or matrix) yet. I suppose that the basic definition of the permanent of a $d$-dimensional matrix $A$ of order $n$ is the sum over all permutations $\sigma_1, \ldots, \sigma_{d-1} \in S_n$ of products $\prod\limits_{i=1}^n a_{i, \sigma_1(i), \ldots, \sigma_{d-1}(i)}$. I also mention that the paper https://arxiv.org/pdf/1101.3629.pdf uses the same definition of the permanent.

Concerning hypergraphs, the permanent of a $d$-dimensional $(0,1)$-matrix could be interpreted as the number of perfect matchings in a $d$-uniform $d$-partite hypergraph and it is connected with the number of perfect matchings in a general $d$-uniform hypergraph. It is also related to the number of some combinatorial structures, for example, to the number of transversals in latin squares and hypercubes.

I know no relation between multidimensional permanent and determinant (possibly, because I know no satisfactory definition of the multidimensional determinant too).

$s$-permanent from http://www.sciencedirect.com/science/article/pii/0024379587903119 for $s=1$ coincides with the previous definition. For $s=d-1$ the $s$-permanent of a $d$-dimensional matrix $A$ of order $n$ is the sum over all sets $D$ of $n^{d-1}$ entries such that each line ($1$-dimensional plane) of $A$ contains exactly one element from $D$ of products $\prod\limits_{a_{i_1, \ldots, i_d \in D}} a_{i_1, \ldots, i_{d}}$. For $1 < s < d-1$ the $s$-permanent of a $d$-dimensional matrix may not exist. It will be interesting what does the $s$-permanent mean for hypergraphs.

Some additional information about multidimensional permanents you can find in https://link.springer.com/article/10.1134/S1990478916040141