**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$?



Characterisation of walk-equivalent digraphs
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}$.


