This problem originates from an exercise in Richard Stanley's Algebraic Combinatorics. The exercise in the text (Chapter 3, Exercise 2(a)) asks
Let $G$ be a finite graph (allowing loops and multiple edges). Suppose that there is some $\ell> 0$ such that the number of walks of length $\ell$ from any fixed vertex $u$ to any fixed vertex $v$ is independent of $u$ and $v$. Show that $G$ has the same number $k$ of edges between any two vertices (including $k$ loops at each vertex.
The hypothesis of the problem (that the number of walks of length $\ell$ between any two vertices is the same) tells us that the adjacency matrix $A(G)$ of $G$ raised to the $\ell$ power is a constant matrix $$ (A(G))^{\ell} = \begin{pmatrix} c & c & \cdots & c \\ c & c & \cdots & c \\ \vdots & \vdots & \ddots & \vdots \\ c & c & \cdots & c \end{pmatrix} $$ for some constant $C$. We would like to conclude that this means the adjacency matrix itself is a constant matrix (hence, the number of walks of length 1 between any two vertices is the same, i.e., the number of edges between any two vertices is the same). Update in response to comments below: In this case we also have that $A(G)$ is a symmetric matrix which would eliminate some trivial counter examples.
Does this result follow from something in linear algebra? What is the proof? If not, is there some other approach that might be more fruitful?
Since $A(G)$ is symmetric, it is diagonalizable. In particular, this implies that $\ker(A(G)^\ell)=\ker(A(G))$ for all $\ell>0$. If $A(G)^\ell$ is a constant matrix, then for any $i$ and $j$, $e_i-e_j$ is in its kernel (where $\{e_i\}$ is the standard basis). Thus $e_i-e_j\in \ker(A(G))$ for every $i$ and $j$, which says that the columns of $A(G)$ are all the same. Since $A(G)$ is symmetric, this actually implies all the entries of $A(G)$ are the same.