Consider two $N \times N$ adjacency matrices $A$ and $B$ belonging to different graphs(unweighted and undirected). What does their product $AB$ represent? I know that the powers of the adjacency matrix gives the number of paths between any two vertices of length equal to the power. But I am having trouble extendeding this logic to the above problem
$\endgroup$ 01 Answer
$\begingroup$Cell $(i,j)$ in $AB$ contains the number of walks from $i$ to $j$ where the first step is in $A$, but the second step is in $B$. (As if someone changed the maze from $A$ to $B$ after the first step.)
In terms of matrix multiplication $$(AB)_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{in}b_{nj}$$ where e.g. the term $a_{i1}b_{1j}$ is equal to $1$ if and only if we can walk from vertex $i$ to vertex $1$ in $A$, then from vertex $1$ to vertex $j$ in $B$.
$\endgroup$
