Product of adjacency matrices

Suppose $A$ is the adjacency matrix of graph $G_1$ and $B$ the adjacency matrix of graph $G_2$, where we consider both $G_1$ and $G_2$ to have the same vertices $1,\ldots,n$. Then $(AB)_{ij}$ is the number of ways to get from $i$ to $j$ by going first along an edge of $G_1$ and then along an edge of $G_2$.

The story extends to non-square matrices. Consider a collection $A$ of $a$ vertices, another collection $B$ of $b$ vertices, and a collection of directed edges from the first collection to the second (in other words, a bipartite graph, but where we choose explicitly a $2$-coloring of the vertices). We can organize this data into a $b \times a$ matrix whose entries describe the number of edges from a vertex in the first collection to a vertex in the second.

Now consider a third collection $C$ of $c$ vertices and some directed edges from vertices in $B$ to vertices in $C$. We can organize this data into a $c \times b$ matrix as above.

Then the product of the two matrices above is a $c \times a$ matrix describing how to get from vertices in $A$ to vertices in $C$ by following edges that go through $B$.

This idea is the basis of a combinatorial approach to linear algebra which is described, for example, in Brualdi and Cvetkovic's A combinatorial approach to matrix theory and its applications.

---

For the initiated, the above admits the following nice interpretation: we have described composition of morphisms of a particularly nice category. In fact, if I'm not mistaken, it's the free category with finite biproducts on one object.