# Correspondence between matrix multiplication and a graph operation of Lovasz

In his book "Large networks and graph limits" (available online here: http://web.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf), Lovasz describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $$(m,n)$$ bi-labeled graph is a graph in which some vertices are labeled with the left labels $$1, \ldots, m$$, and some are labeled with the right labels $$1, \ldots, n$$. The left and right label $$i$$ are distinguished. A vertex is allowed to have more than one left and/or right labels assigned to it.

The concatenation operation of Lovasz (definition begins on page 85 of the above link), is as follows. If $$G$$ is a $$(m,n)$$ bi-labeled graph and $$H$$ is a $$(n,k)$$ bi-labeled graph, then the concatenation $$G \circ H$$ is the $$(m,k)$$ bi-labeled graph obtained from the disjoint union of $$G$$ and $$H$$ by identifying the vertex of $$G$$ with right label $$i$$ with the vertex of $$H$$ with left label $$i$$ for all $$i = 1, \ldots n$$, and then forgetting these labels, but retaining the left labels of $$G$$ and the right labels of $$H$$.

If it is not clear how this corresponds to matrix multiplication, consider the following. Fix a graph $$K$$. For any $$(m,n)$$ bi-labeled graph $$G$$, define the $$K$$-homomorphism matrix of $$G$$ as the matrix $$M^{G \to K}$$ whose rows/columns are indexed by $$m$$-tuples/$$n$$-tuples of vertices of $$K$$ such that its $$(u_1, \ldots, u_m),(v_1, \ldots, v_n)$$-entry is equal to the number of homomorphisms from $$G$$ to $$K$$ that map the vertex with left label $$i$$ to $$u_i$$ and the vertex with right label $$j$$ to $$v_j$$ for all $$i,j$$. One can check that $$M^{G \circ H \to K} = M^{G \to K}M^{H \to K}$$.

It is unlikely, to say the least, that Lovasz was not aware of this correspondence between concatenation and matrix multiplication, but I could not find any explicit mention of this in the book or elsewhere. Admittedly I have not read the entire book in detail yet, but I have looked through it for mention of this.

Does anyone know if this correspondence is explicitly spelled out anywhere? Either in the book or an article somewhere?