2
$\begingroup$

Suppose $G$ is a $k-$regular graph and $A$ is its adjacency matrix, and let $[ \ 1 \ ]$ denote "all ones" square matrix of size $|V(G)|$. After some computations, I believe the following holds:

$$\lim_{n\to\infty} A^n/k^n=\frac{1}{|V(G)|}[ \ 1 \ ]$$

I sort of understand why, in terms of walks, but this intuition is not aiding me in the proof that this limit would require. Could someone point me in the right direction on how to prove this statement? Thanks.

enter image description here

$\endgroup$
2
  • $\begingroup$ This is quite interesting, +1! (I tried a less symmetric $3$-regular graph, because I thought the symmetry of the Peterson might be deceptive; it still seems true) Although, your example seems to show that every entry is tending toward $1/V$, rather than just those on the main diagonal. $\endgroup$
    – pjs36
    Mar 12, 2018 at 0:23
  • $\begingroup$ Right, I made a mistake in my presentation of my problem. Let me make an edit. I have tried this for several $k-$regular graphs. Note that this doesn't work for bipartite graphs for a silly reason - there are no odd walks between vertices in the same partition. $\endgroup$
    – J. Moeller
    Mar 12, 2018 at 0:28

1 Answer 1

2
$\begingroup$

Assume the graph is connected. First of all, it's easy to check that the constant vector $v_{const}=\textbf{1}/\sqrt{\mid V(G)\mid}$ is an eigenvector of A/k with eigenvalue 1 (by regularity). By the Perron-Frobenius theorem, this is the largest eigenvalue, and it has multiplicity 1 (this is where I use the connectivity, see the section on Non-Negative matrices in the wikipedia page).

Thus, $A/k=v_{const}v_{const}^T+\sum_i \lambda_i v_iv_i^T$ where $\lambda_i$ have magnitude strictly less than 1, and the $v_i$ are orthogonal to each other and to $v_{ones}$ (because A is symmetric).

In particular, $(A/k)^n=v_{const}v_{const}^T+\sum_i \lambda_i^n v_iv_i^T$, and in the limit, we get $v_{const}v_{const}^T=\textbf{1}\textbf{1}^T/\mid V(G)\mid$. Finally, note that $\textbf{1}\textbf{1}^T$ coincides with your matrix $[1]$

$\endgroup$
1
  • $\begingroup$ That is very slick. Thanks. $\endgroup$
    – J. Moeller
    Mar 12, 2018 at 0:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .