Friday, 3 November 2006

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

The Boolean matrix product of two 0-1 ntimesn matrices A and B is the matrix C defined as
C[i,j]=veek=1n(A[i,k]wedgeB[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]wedgeA[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 e1,e2,e3 from H of the form e1 = {ell,i,j}, e2 = {ell,j,k}, e3 = {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)wedgeA(i,j,k)=1, where A is the "adjacency tensor" of H.



More formally, we can define T(i,j,k)=veeell=1n(A(i,j,ell)wedgeA(j,ell,k)wedgeA(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 ntimesntimesn, define the order-3 tensor T(i,j,k)=sumell=1nA(i,j,ell)cdotB(j,ell,k)cdotC(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