14
$\begingroup$

I was wondering if there was any meaningful interpertation of the product of two $n\times n$ adjacency matrices of two distinct graphs.

2 Answers 2

9

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.

  • 1
    D$i$d you buy or download a pirate copy? ;)2012-02-28
24

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

  • 6
    These sorts of results seem too good to be true.2012-02-28