# Characterisation of walk-equivalent digraphs

Setting Let $$G=(V,E)$$ be an undirected graph. A walk $$\pi$$ in $$G$$ of length $$k$$ is a sequence of $$k+1$$ vertices $$v_1,\ldots,v_{k+1}$$ such that for each $$i\in[1,k]$$, $$\{v_i,v_{i+1}\}\in E$$. Let $$H=(W,F)$$ be another undirected graph having the same number of vertices as $$G$$, i.e., $$|V|=|W|=n$$.

If for each $$k$$, $$G$$ and $$H$$ have the same number of walks of length $$k$$, then it is known that there is matrix $$Q$$ such that $$A_G\cdot Q=Q\cdot A_H$$, where $$A_G$$ and $$A_H$$ denote adjacency matrices of $$G$$ and $$H$$, respectively, and such that $$Q\cdot\mathbf{1}=\mathbf{1}$$ and $$\mathbf{1}^t\cdot Q=\mathbf{1}^t$$, where $$\mathbf{1}$$ is the $$n\times 1$$-vector consisting of all ones. (A matrix with this property is sometimes called doubly quasi-stochastic). The converse also holds, i.e., when $$A_G\cdot Q=Q\cdot A_H$$ holds for a doubly quasi-stochastic matrix, then for any $$k$$, $$G$$ and $$H$$ have the same number of walks of length $$k$$.

Question Let us consider the directed graph (digraph) case. Is there an example of two digraphs with the same number of vertices that have same number of walks of length $$k$$, for any $$k$$, yet there is no doubly quasi-stochastic matrix $$Q$$ such that $$A_G\cdot Q=Q\cdot A_H$$?

This should work: $$G$$ is given by $$A_G=\begin{bmatrix}0 & 1 &0 & 0\\0& 0 &1 &1 \\1 &0 &0 &0\\0 &0 &0 &0 \end{bmatrix}$$ and $$H$$ given by $$A_H=\begin{bmatrix}0 & 1 &0 & 0\\0& 0 &1 &0 \\0 &0 &0 &1\\1 &0 &0 &0 \end{bmatrix}$$. Both have $$4$$ walks, of any length. Consider matrix $$Q=\begin{bmatrix}a & b &c & d\\e& f &g &h \\i &j &k &l\\m &n &o &p \end{bmatrix}$$, then $$A_{G}\cdot Q=\begin{bmatrix}e & f &g & h\\i+m& j+n &k+o &l+p \\a &b &c &d\\0 &0 &0 &0 \end{bmatrix}= \begin{bmatrix}d & a &b & d\\h& e &f &g \\ l& i &j &k\\p &m &n &o \end{bmatrix}=Q\cdot A_H,$$ so $$m=p=n=o=0$$ and not all rows of $$Q$$ sum up to $$1$$. A side remark: there is a $$Q\cdot A_G=A_H\cdot Q$$. Just consider $$Q=\begin{bmatrix}1/4 &1/4 &1/4 &1/4 \\1/4 &1/4 &1/4 &1/4 \\ 1/4 &1/4 &1/4 &1/4 \\1/4 &1/4 &1/4 &1/4 \end{bmatrix}$$.
• Nice example. Any idea how to modify this example such that the digraphs have the same number of semi-walks of any type? I.e., such that $tr(w(A_{G},A_G^t).J)=tr(w(A_{H},A_{H}^t).J)$ holds for any word $w(x,y)$ and $J$ the all ones matrix. Sep 14 '19 at 16:20