9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Are A, B, C all tensors of the same type? If so, I don't think there's a way to assign a type to all three so that the operation you're looking at makes sense in terms of tensor contraction. $\endgroup$ Jan 25, 2010 at 18:24
  • $\begingroup$ If I understand you correctly, the type is not relevant to me. In the above, I am simply thinking of A, B, and C as just being "three dimensional matrices" with dimensions n by n by n, and each entry is either 0 or 1. You can choose however many contravariant/covariant indices you need for each of A,B,C, if it helps. I just want the resulting n by n by n cube to contain the appropriate quantities (up to a permutation of indices). $\endgroup$ Jan 25, 2010 at 21:52
  • $\begingroup$ @RyanWilliams I need proper definition and some literature on Boolean matrix multiplication in dimension 3 or more. Can you suggest any of your publications where you have used this product? Thanks in advance. $\endgroup$
    – GA316
    May 16, 2020 at 1:57
  • $\begingroup$ I can tell you that my coauthors proved in 2018 that the rank of the above tensor T is essentially n^4. (Unlike matrix multiplication.) This basically means there cannot be a Strassen-like equivalent. The reference is “Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams: Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. SODA 2018: 1236-1252“ $\endgroup$ May 17, 2020 at 2:29

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I am aware of the Bürgisser, Clausen, Shokrollahi book (and in general, of the math community that works on matrix multiplication). But thanks for the other pointers, at the very least they give me some more fodder for the search engines! $\endgroup$ Aug 3, 2010 at 5:12
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for your answer, but I'd really like to know if there's prior work and/or standard terminology for this product. Please let me know if you find any of this. $\endgroup$ Aug 4, 2010 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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