Matrix of paths from graph $G_1$ to graph $G_2$ to graph $G_3$

adjacency matrixcombinatoricsdiscrete mathematicsgraph theorymatrices

If $A$ is the adjacency matrix of graph $G$, then it is a well know property that $A^n$ is a matrix where the element $(i, j)$ gives the number of walks of length $n$ from vertex $i$ to vertex $j$.

The matrix of paths is different and there are closed forms for paths of length 2 and 3 (https://mathworld.wolfram.com/GraphPath.html). For example, the matrix of paths of length 3 is given by:

$$
P_3 = A^3 – \text{diag}(A^2) \cdot A – A \cdot \text{diag}(A^2) + A \times A^T – \text{diag}(A^3)
$$

("$\cdot$" is normal matrix multiplication, "$\times$" is element-wise multiplication and "diag$(A)$" has the same principal diagonal as A with the remaining elements set to zero)

I am interested in the matrix of paths of length 3, for 3 (potentially different) graphs. The interpretation of the product of two different adjacency matrices $A \cdot B$ is (from this post):

"Cell $(i,j)$ in $A \cdot B$ contains the number of walks from $i$ to $j$ where the
first step is in $A$, but the second step is in $B$"

Given three undirected graphs $G_1$, $G_2$ and $G_3$ with (symmetric since undirected) adjacency matrices $A$, $B$ and $C$, what I need is an expression for the matrix of 3-paths from $G_1$ to $G_2$ to $G_3$.

My attempt at this is:

$$
A \cdot B \cdot C + (A \cdot B \cdot C)^T – C \cdot \text{diag}(A \cdot B) – \text{diag}(A \cdot B) \cdot C – \text{diag}(A \cdot B \cdot C)
$$

However, this is just based on observations and tweaking. It works on a non-trivial example, but I do not know if it is correct. What I'd like is:

  1. To confirm this is correct, or if it is not, find the correct expression.
  2. Have a sketch/intuition of a proof

Best Answer

I would proceed the same way as in the $A=B=C$ case (assuming no self-loops):

  • start from all walks of length 3 (given by $A^3$)
  • subtract all walks of the form $u\to v\to w\to u$ (1) (given by $\text{diag}(ABC)$)
  • subtract all walks of the form $u\to v\to u\to w$ (2) (given by $\text{diag}(AB) \cdot C$)
  • subtract all walks of the form $u\to v\to w\to v$ (3) (given by $A \cdot\text{diag}(BC)$)

Now what we have subtracted twice? Note that there is no intersection between (1) and (2) as well as between (1) and (3). The only walks we have subtracted twice are the intersection of (2) and (3), ie. walks of the form $u\to v\to u\to v$.

In other words, what we need to add is the number of pairs of vertices $(u,v)$ such that there is an edge from $u$ to $v$ in $G_1$, from $v$ to $u$ in $G_2$ and from $u$ to $v$ in $G_3$. In the $A=B=C$ case, we get $A\times A^T\times A=A\times A^T$ (keeping your notation for elementwise multiplication). In the general case, this can be expressed as $A\times B^T\times C$ instead.

So the number of paths of length 3 in counted by:

$$A^3-\text{diag}(ABC)-\text{diag}(AB)\cdot C-A\cdot\text{diag}(BC)+A\times B^T\times C$$

Note that when $A=B=C$, we recover the original formula.

Related Question