Exercise on number of walks in a graph The following is an exercise (Exercise #2 (a), Chapter 3, page 28) from Richard Stanley's Algebraic Combinatorics.  

Let $G$ be a finite graph (allowing loops and multiple edges). Suppose that
  there is some integer $l > 0$ such that the number of walks of length $l$ 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).

My approach:
Let $A$ be the adjacency matrix of the graph $G$. The given condition implies that $\exists \ \ l > 0$ such that $A^l = cJ$, where $c$ is a non-negative integer and $J$ is the all one matrix. In order to prove this exercise, it is equivalent to show that $A = d J$, for some non-negative integer $d$. The only way I am able to think of in order to prove this is via induction but that too I am not able to implement. Removing a vertex from a graph will still give some condition like $A^l = cJ$ is not clear to me.
Thanks in advance!!
 A: Hint: Consider the formula for the number of triangles in a graph, $tr(A^3)/6$. The reason this holds is that, more generally, the entry $i,j$ in $A^k$ is  constant (dependent only on $k$) multiple of the number of paths from $i$ to $j$.
When you think about the problem in these terms, you realize it's asking you to assume that every entry of $A^\ell$ is the same, for some $\ell$.
Can you take it from here?
A: Since this exercise is in the chapter on random walks, I suspect the expected solution should also be in terms of those. It also follows some discussion on eigenvalues.
So I shall provide a solution that uses some elementary facts about the eigenvalues of adjacency matrices.
If $\lambda_1, \ldots, \lambda_n$ are the $n$ eigenvalues of $A$ (of order $n$, the order of the graph), then the eigenvalues of $A^l$ are exactly $\lambda_1^l, \ldots, \lambda_n^l$. Since $A^l = cJ$, whose eigenvalues are $cn, 0, \ldots, 0$, we get
$\lambda_1^l = cn$, $\lambda_2^l = \cdots = \lambda_n^l = 0$.
This shows that $A$ is a matrix of rank $1$, and being symmetric, it can be written as $aa^T$, where $a$ is a (column) vector of length $n$.
Then $A^l = a(a^Ta)^{l-1}a = (a^Ta)^{l-1}A$ (since $a^Ta$ is scalar).
Thus, $A^l = cJ \implies (a^Ta)^{l-1}A = cJ$, which shows that $A$ is a scalar multiple of $J$, as required.
(In fact, $a^Ta$ is nothing but the number of walks of length $1$ from the first vertex to itself, which is the number of loops on the first vertex)
