A generalization of Boolean matrix multiplication for order-3 tensors

Question

The Boolean matrix product of two 0-1 $n \times n$ matrices $A$ and $B$ is the matrix $C$ defined as $$C[i,j] = \vee_{k=1}^n (A[i,k] \wedge B[k,j]).$$ If $A = B$ and the matrix is an adjacency matrix of a graph $G$, then $C$ determines for all pairs of vertices in $G$ whether or not there is a path of length two from one vertex to the other. This operation can be used to detect if a graph has a 3-clique: we check for an $(i,j)$ such that $C[i,j] \wedge A[i,j] = 1$.

I am interested in a natural generalization of this to 4-cliques in 3-uniform hypergraphs. Let $i,j,k$ be vertices of such a hypergraph $H$. We say that a triangle on $i,j,k$ in $H$ is a set of three edges $e_1,e_2,e_3$ from $H$ of the form $e_1$ = {$\ell, i,j$}, $e_2$ = {$\ell, j,k$}, $e_3$ = {$\ell, k,i$} for some vertex $\ell$.

Let $T(i,j,k) = 1$ iff there is a triangle on $i,j,k$ in $H$. We can detect if there is a 4-clique in $H$ by checking for $(i,j,k)$ such that $T(i,j,k) \wedge A(i,j,k) = 1$, where $A$ is the "adjacency tensor" of $H$.

More formally, we can define $$T(i,j,k) = \vee_{\ell=1}^n (A(i,j,\ell)\wedge A(j,\ell,k) \wedge A(\ell,k,i)).$$

Is there a name for this type of operation in the literature? I would expect the following to have a name: Given three order-3 tensors $A,B,C$ of dimensions $n \times n \times n$, define the order-3 tensor $$T(i,j,k) = \sum_{\ell = 1}^n A(i,j,\ell) \cdot B(j,\ell,k) \cdot C(\ell,k,i).$$ However I can't seem to find anything related. (Pardon me for the lack of subscripts, but I find the above notation easier to read.)

Answer 1

I've been studying tensors (but mostly concerning lower bounds for their rank) for some months now, and can't say I've come across this and wouldn't be surprised if its new. Loosely, there are two groups of people I've seen studying tensors: mathematicians/theory-comp-sci-people interested in matrix multiplication algorithms, and numerical analysts interested in approximating 3D data with low-rank tensors (that is, a way of compressing 3D data by taking the "most important" aspects).

For the first group, a good reference is "Algebraic Complexity Theory" by Bürgisser, Clausen, Shokrollahi. I wouldn't expect your operation to be known in this community as it is a triary-operation, as opposed to binary. Mathematics of triary-operations doesn't seem common.

The other community does seem to be exploring operations on tensors, in particular interest with generalizing things such as SVD to tensors. Their literature is harder to navigate for me, but a good start is this page, and to know that tensor decomposition is sometimes called "PARAFAC" analysis (parallel factorization).

Answer 2

This is an incomplete answer but the hope is that it might give an alternative point of view.

First a quick review of the relationship between rank (1,1) tensors and linear maps:

A linear map $f : V \to W$ is the same as an element of $V^\star \otimes W$. This says that $f$ is a $W$-valued linear form on V. When the base field is $K$ (e.g. $F_2$ in your case), a $K$-valued linear form on $V$ is by definition an element of $V^\star$. Tensoring with $W$ extends the values from $K$ to $W$.

Let $A \in U^\star \otimes V$ and $B \in V^\star \otimes W$. Their tensor product $A \otimes B$ is an element of

$$(U^\star \otimes V) \otimes (V^\star \otimes W) = U^\star \otimes (V \otimes V^\star) \otimes W$$

There is only one way to turn this into an element of $U^\star \otimes W$. You have to contract the bracketed $V$ and $V^\star$ terms. This corresponds to composition of linear maps.

In terms of coordinates, this means first taking the outer product of $A$'s and $B$'s matrices, which gives a matrix-valued matrix, and taking the trace to get back a scalar-valued matrix.

If you think of your three tensors as respectively living in $V \otimes V \otimes V^\star$, $V \otimes V^\star \otimes V$ and $V^\star \otimes V \otimes V$ then the product you wrote down seems to be the tensor product followed by contraction on pairable indices in cyclic order: (3, 6), (5, 8) and (7, 1). A reasonable name would be 'cyclic triple product'.