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 \begin{equation} tr(w(A_G,A_G^t)\cdot J)=tr(w(A_H,A_H^t)\cdot J) \tag{1}\label{eq:one} \end{equation} 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.
