Motivated by the prospect of finding interesting or relevant hypermatrix algebras of higher arity, this project aims to explore and classify finite directed uniform hypergraphs by utilizing the computational power of Wolfram Language. Associated hypermatrix products may then be extracted from these hypergraphs and analyzed. The analysis of such hypermatrix operations is reserved for future work on the project.
The Necessary Code
The Necessary Code
Hypergraphs and Hypermatrix Products
Hypergraphs and Hypermatrix Products
The motivation of this project is to identify possible hypermatrix operations of abstract `arity. This may be done by analyzing the possible contractions of directed hypergraphs with respect to the indices of the elements of the hypermatrix.
For a standard 2 x 2 matrix multiplication, we have:
AB =
=
a 1,1 | a 1,2 |
a 1,2 | a 2,2 |
b 1,1 | b 1,2 |
b 1,2 | b 2,2 |
a 1,1 b 1,1 a 1,2 b 1,2 | a 1,1 b 1,2 a 1,2 b 2,2 |
a 1,2 b 1,1 a 2,2 b 1,2 | a 1,2 b 1,2 a 2,2 b 2,2 |
In summation form, we have . This notion can be generalized to matrices of arbitrary dimension, summing over all indices, = ·. Now, this summation may be represented as a directed hypergraph, whose edges contain a number of vertices equal to the arity of the (hyper)matrix, and whose edge set has cardinality equal to the number of indices summed over. In the case of this example, A and B are ordinary binary matrices, so this matrix product may be represented by the graph:
A·B==·
(ab)
ij
2
∑
k=1
a
ik
b
kj
(ab)
ij
∑
k=1
a
ik
b
kj
In[]:=
PlexDiagram[{{i,k},{k,j}},{k},"Symmetry""Ordered"]
Out[]=
Notice that the indices of the matrix product are representative of the vertices of the graph, the number of edges in the graph is equal to the number of matrices being summed, and the number of contracted vertex, colored gray, are equal to the number of indices summed over. This turns out to be true in the general case of hypermatrices and hypergraphs as well. For example, the following hypermatrix may be thought of as a hypermatrix product
ABC= ··
∑
j,k
A
ijk
B
jkl
C
klm
In[]:=
PlexDiagram[{{i,j,k},{j,k,l},{k,l,m}},{j,k}]
Out[]=
For hypergraph plex diagrams like the ones seen above, the following code may be run to determine the hypermatrix product of a given diagram:
In[]:=
PlexToProduct[plex_]:=Module[{edgeLabels,indexLabels,numEdges,hyperedges,contractIndices},edgeLabels=GetEdgeLabels[plex];indexLabels=GetVertexLabels[plex];numEdges=Length[EdgeList[plex]];hyperedges=EdgeList[plex]/.indexLabels;contractIndices=ContractIndices[plex]/.indexLabels;TraditionalForm[Inactive[Sum][Row[Table[Subscript[Symbol[edgeLabels[[z]]],Sequence@@hyperedges[[z]]],{z,1,numEdges}],"·"],Sequence@@Table[{v,""},{v,contractIndices}]]]]
Using the same example as above, we get:
In[]:=
PlexToProduct
Out[]//TraditionalForm=
∑
j
∑
k
A
i,j,k
B
j,k,l
C
k,l,m
As can be seen, the PlexToProduct function yields the same product as we formulated by hand, albeit, notated differently. For a visual representation of how these hypergraphs and hypermatrices relate, the ShowHyperMatrix function can be used to generate the adjacency hypermatrices of the hypergraphs.
In[]:=
FlattenShowHyperMatrix/@
,
Out[]=
,
0 | 1 | 0 |
0 | 0 | 1 |
0 | 0 | 0 |
Classification of Hypergraphs
Classification of Hypergraphs
In order to determine the behavior of all possible hypermatrix products, it would help to know the behavior of all hypergraphs. To do this, we use the following code:
In[]:=
GetHypergraphClassTemp[arity_Integer,EdgeOrder_Integer,indexList_List]:=Select[EnumeratePlexProducts[arity,EdgeOrder],FreeAndContractIndices[#]==indexList&](*Donotusethisversion*)GetHypergraphClass[indexList_List,maxArity_Integer]:=Flatten[Table[GetHypergraphClassTemp[i,j,indexList],{i,Range[maxArity]},{j,Range[Binomial[Total[indexList],i]]}],2]
An example of the use of this function can be seen below:
In[]:=
class1=GetHypergraphClass[{2,1},2]
Out[]=
,
,
,
,
,
As can be observed, this function takes a pair ({,},) and returns all directed connected -uniform hypergraphs having free indices and contracted indices. Now, we may apply the PlexToProduct function to generate the hypermatrix operations that correspond to each of these plex diagrams:
In[]:=
sums1=PlexToProduct/@GetHypergraphClass[{2,1},2]
Out[]=
·,·,·,··,··,··
∑
i
A
i,j
B
i,k
∑
j
A
i,j
B
i,k
∑
k
A
i,j
B
i,k
∑
i
A
i,j
B
i,k
C
j,k
∑
j
A
i,j
B
i,k
C
j,k
∑
k
A
i,j
B
i,k
C
j,k
These results look like what we might expect, as for all hypermatrix products in this list, there is only one index summed over, two free indices, and two indices per term. Now we may pair the plex diagrams with their corresponding matrix products:
In[]:=
Grid@Transpose[{class1,sums1}]
Out[]=
∑ i A i,j B i,k | |
∑ j A i,j B i,k | |
∑ k A i,j B i,k | |
∑ i A i,j B i,k C j,k | |
∑ j A i,j B i,k C j,k | |
∑ k A i,j B i,k C j,k |
Future Work
Future Work
Future work includes extending the plex diagram enumeration to non-uniform hypergraphs. Similarly, extending the GetHypergraphClass function to accommodate for these non-uniform diagrams is another step to take. A more nuanced task to be done in the future is to delete the “duplicates” of hypergraphs. That is, to remove the all but one of the hypergraphs whose associated hypermatrix products are the same up to renaming of the indices.
Outside of this, the scope of this project is very broad. The main intention is to analyze some of these hypermatrix products more rigorously to see if there exists any hypermatrix products that yield relevant or interesting algebraic results.
Outside of this, the scope of this project is very broad. The main intention is to analyze some of these hypermatrix products more rigorously to see if there exists any hypermatrix products that yield relevant or interesting algebraic results.
Concluding Remarks
Concluding Remarks
While the short-term motivation of this project was to generate and identify hypermatrix products through hypergraph enumeration, the long-term goal is to both improve the constraints on this taxonomy of hypergraphs as well as to find some sort of patterns within the algebras induced by the corresponding hypermatrix products of these hypergraphs.
Acknowledgments
Acknowledgments
A huge thanks to Carlos Zapata-Carratalá and Nik Murzin for being excellent mentors, writing much of the essential code in the Hypergraph paclet, and having patience with me and my questions. Another massive thank you to Xerxes Arsiwalla for helping organize the program, contacting me about the winter school, discussing higher arity mathematics with me long before the winter school began, and working with me despite my scheduling confusions and conflicts. Thank you to all of the staff who made the winter school possible!
References
References
1
.C. Zapata-Carratalá, Unpublished Mathematica Notebooks - “HypergraphMinicouse,” “Hypergraph Calculus & Hypermatrices,” and “ArrayAlgebra”
2
.C. Zapata-Carratalá and N. Murzin Hypergraph Paclet https://resources.wolframcloud.com/PacletRepository/resources/WolframInstitute/Hypergraph
3
.C. Zapata-Carratalá, X. D. Arsiwalla, T. Beynon (2022), “Heaps of Fish: arrays, generalized associativity and heapoids,” https://arxiv.org/abs/2205.05456.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Finding hypermatrix products via hypergraph classification
by Tate Allen
Wolfram Community, STAFF PICKS, January 16, 2025
https://community.wolfram.com/groups/-/m/t/3357835
by Tate Allen
Wolfram Community, STAFF PICKS, January 16, 2025
https://community.wolfram.com/groups/-/m/t/3357835