Digraph vertices: classification by counting outgoing walks I'm reproducing a question I posted on MSE (yet with no answer both there and by myself).

Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W_v(n)$ be the number of walks in $G$ of length exactly $n$ originating at $v$. That is,
$$W_v(0) = 1 \quad\text{and}\quad W_v(n + 1) = \sum_{\substack{u \in V \\ (v, u) \in E}} W_u(n).$$
Now, for $u, v \in V$, let $u \sim v$ iff $W_u(n) = W_v(n)$ for all $n$. This equivalence of vertices induces a partitioning of $V$. What is known on the complexity of computing this partition?

(By "computing", it may have meant an algorithm that assigns each vertex $v\in V$ a number of its class, so that two vertices are equivalent iff they get assigned the same number. I do see some resemblance to the Hopcroft's DFA minimization algorithm, but still the problem being solved is different... and I see this to be a corner case of some harder problems.)
Let $A$ be the adjacency matrix of the graph, let $\mathbf 1$ be the all-ones vector, and let $\delta_v$ be the indicator of vertex $v$. Then
$$
W_v(t) = \delta_v A^t \mathbf 1.
$$
It follows that $v \sim u$ iff for all $t$,
$$
(\delta_u - \delta_v) A^t \mathbf 1 = 0.
$$
Let $n = |V|$. The Cayley–Hamilton theorem shows $A^t$ is always a linear combination of $A^0,\ldots,A^{n-1}$. Therefore
$$
v \sim u \Longleftrightarrow (\delta_u - \delta_v) A^0 \mathbf{1} = \cdots = (\delta_u - \delta_v) A^{n-1} \mathbf{1} = 0.
$$
The latter property can be checked in polynomial time, so the partition can be computed in polynomial time. This procedure can be optimized by computing the kernel of the matrix
$$
\begin{bmatrix}
A^0 \mathbf{1} \\
\cdots \\
A^{n-1} \mathbf{1}
\end{bmatrix}
$$
and then finding all $\delta_u-\delta_v$ that belong to it.