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

  • $\begingroup$ 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. $\endgroup$ – Sirolf Sep 14 '19 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.