Friday 3 November 2006

linear algebra - A generalization of Boolean matrix multiplication for order-3 tensors

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

No comments:

Post a Comment