# Digraphs with same number of semiwalks

This is a follow-up question to Characterisation of walk-equivalent digraphs.

Question: Do there exists two directed graphs $$G$$ and $$H$$ consisting of the same number ($$n$$) of vertices, such that $$$$tr(w(A_G,A_G^t)\cdot J)=tr(w(A_H,A_H^t)\cdot J) \tag{1}\label{eq:one}$$$$ holds for every word $$w(x,y)$$? Intuitively, this condition states that $$G$$ and $$H$$ have the same number of semi-walks of a certain type (as described by $$w(x,y)$$), and this for any such type (i.e., any word $$w(x,y)$$).

Here, $$A_G$$ and $$A_H$$ are the adjacency matrices of $$G$$ and $$H$$, respectively, $$J$$ is the $$n\times n$$-matrix consisting of all ones. For a word $$w(x,y)$$, for example $$w(x,y)=x.y.x$$, $$w(A_G,A_G^t)$$ is interpreted as $$A_G\cdot A_G^t\cdot A_G$$.

Important restriction: There should not exist a doubly quasi-stochastic matrix $$S$$ (a matrix $$S$$ such that $$S.\mathbf{1}=\mathbf{1}$$ and $$\mathbf{1}^t\cdot S=\mathbf{1}$$ with $$\mathbf{1}$$ the $$n\times 1$$-vector consisting of all ones.) such that $$A_G\cdot S=S\cdot A_H$$.

In the answer https://mathoverflow.net/q/341573 to Characterisation of walk-equivalent digraphs a counter example was given such that $$tr(A^k\cdot J)=tr(B^k\cdot J)$$ holds for every $$k\geq 0$$. However, the example does not satisfy the more general condition (\ref{eq:one}).

Update: Note that since $$A_G\cdot A_G^t$$ and $$A_H\cdot A_H^t$$ are symmetric matrices, and (\ref{eq:one}) implies that $$tr((A_G\cdot A_G^t)^k\cdot J)=tr((A_H\cdot A_H^t)^k\cdot J)$$ for any $$k\geq 0$$, these matrices must be related by a doubly quasi-stochastic matrix $$O$$, i.e., $$A_G\cdot A_G^t\cdot O=O\cdot A_H\cdot A_H^t$$. Similarly for the symmetric matrices $$A_G^t\cdot A_G$$ and $$A_H^t\cdot A_H$$, possibly with another doubly quasi-stochastic matrix $$O'$$. This severely restricts candidate graphs. Perhaps this helps.