Relationship between free probability and deterministic graphs?

Question

Consider the $N\times N$ matrix $$ M = \left(\begin{array} \\ 0 & 1 & & 0 \\ 1 & \ddots & \ddots & \\ & \ddots & \ddots & 1 \\ 0 & & 1 & 0 \\ \end{array}\right) $$

which comes from the adjacency matrix of a graph corresponding to a one-dimensional chain of $N$ nodes with dangling ends. A cartoon of this graph is $$\circ -\circ -\circ -\circ -\cdots-\circ -\circ$$

It turns out that if you plot a histogram of its eigenvalues, it appears to fit exactly with an arcsine distribution $$f(x) = \frac{1} {\pi \sqrt{4-x^2}}, \vert x \vert < 2 $$ which is exactly what one would expect from the free convolution of the binomial distribution $$ p(x) = \frac 1 2 \left( \delta\left(x-1\right) + \delta \left(x+1\right)\right)$$ with itself.

Is this mere coincidence, or evidence of something deeper? I feel like this must be some example of a known result out there.

I've gotten as far as figuring out how $\pm 1$ shows up; you can write $M$ as the sum of two pieces $$ M = A + B $$ $$ A = \left(\begin{array}{cccccc} 0 & 1\\ 1 & 0\\ & & 0 & 1\\ & & 1 & 0\\ & & & & \ddots\\ & & & & & \ddots \end{array}\right) = \sigma_x \oplus \sigma_x \oplus \cdots $$ $$ B = \left(\begin{array}{cccccc} 0\\ & 0 & 1\\ & 1 & 0\\ & & & 0 & 1\\ & & & 1 & 0\\ & & & & & \ddots \end{array}\right) = [0] \oplus \sigma_x \oplus \sigma_x \oplus \cdots $$

where $\sigma_x$ is the Pauli sigma matrix which of course has eigenvalues $\pm 1$. It must be that these two matrices are freely independent in the $N\rightarrow \infty$ limit, and possibly even for finite $N$ also, so that this reduces to the free convolution described above.

I may be reading too much into this, but it's interesting to me that this is a completely deterministic matrix problem with free probabilistic characteristics. I'm not at all familiar with the algebraic aspects of free probability theory, let alone what the graph theoretic relationships would be.

Answer 1

I believe the relation between deterministic graphs and free probability you mentioned is not something generic. In fact, the main property of your matrix $M$ which makes connection with free probability (at the best of my knowledge) is not to be the adjacency matrix of some graph, but a Jacobi matrix related to some orthogonal polynomials, which themselves come from random matrix models.

Let me try to develop : We first need some computations.

We have to assume $N$ even to make things properly. The Chebyshev (monic) polynomials $(T_k)_{k\geq0}$ of the first kind satisfy $T_k(x)=x^k+\ldots$ and are orthogonal for the weight $$ w(x)=\frac{1}{\sqrt{1-x^2}}, $$ defined on $[-1,1]$, namey for any $k\neq l$ $$ \int_{-1}^1T_k(x)T_{l}(x)w(x)=0. $$ Their Jacobi matrix (associated with its recurrent coefficients) is actually $M/2$. For our purpose its enough to know that the zeros of $T_N$ are actually the eigenvalues of $M/2$. Moreover, a formula due to Heine yields $$ T_N(x)=\int_{-1}^1\ldots\int_{-1}^1\prod_{i=1}^N(x-x_i)\prod_{1\leq i < j \leq N}|x_i-x_j|^2\prod_{i=1}^Nw(x_i)dx_i. $$ The change of variables $x_i=\cos\theta_i$ gives $$ T_N(x)=\int_{0}^{2\pi}\ldots \int_0^{2\pi}\prod_{i=1}^N(x-\cos\theta_i)\prod_{1\leq i < j \leq N}|\cos\theta_i - \cos\theta_j|^2\prod_{i=1}^Nd\theta_i $$ and by Weyl formula $$ T_N(x)=\int_{\mathcal{U}_N}\det(xI_N-\frac{U+U^*}{2}) dU = \mathbb{E}_{Haar}\Big(\det(xI_N-\frac{U+U^*}{2})\Big) $$ where $dU$ stands for the Haar measure of the unitary group $\mathcal{U}_N$.

Conclusion : The random matrix $U+U^*$, with $U$ distributed according to Haar, has for mean eigenvalues the zeros of $T_N(x/2)$, and equivalently the eigenvalues of $M$. Thus they should have the same limiting distribution as $N\rightarrow\infty$ as soon as that the limiting distribution of $U+U^*$ is deterministic.

One one hand, the limiting distribution of $M$ is indeed known to be the arcsine distribution (note it is also the limiting distribution of the zeros of $T_N$ as $N\rightarrow\infty$, which is known to minimize the logarithmic energy $$ \iint \log\frac{1}{|x-y|}d\mu(x)d\mu(y) $$ over all probability measure $\mu$ on $[-1,1]$, a classical statement in potential theory).

On an other hand, by the invariance property of the Haar measure, the distribution of $U+U^* $ is the same than $A+VAV^*$, with $V$ also distributed according to Haar, which is known to converge by Voiculescu Theorem towards $\mu_A\boxplus\mu_A$, where $\mu_A$ is the limiting distribution of your matrix $A$, namely $\mu_A=\frac{1}{2}(\delta_1+\delta_{-1})$.

Answer 2

I'd like to add that in general, your matrix is a special case of symmetric tridiagonal matrices of the form

$$ \begin{bmatrix} a & b & \cdots & \cdots & 0\\\\ b & a & b & \cdots & 0\\\\ & \ddots & \ddots & \ddots\\\\ 0 & \cdots & &a & b\\\\ 0 & \cdots & &b & a \end{bmatrix} $$

The eigenvalues of this matrix are $$ \lambda_k = a + 2b\cos(k\pi/(n+1)),\qquad 1 \le k \le n. $$

The eigenvectors have a similar nice closed form.

$$ v_{ik} = \sin\left(\frac{ik\pi}{n+1}\right),\qquad 1\le i,k \le n. $$

These facts can probably be quickly derived by looking at the characteristic polynomial.

Answer 3

The relation between free probability and graphs you are looking for comes from the free product of (rooted) graphs, see for example the paper of Accardi, Lenczewski and Salapata https://arxiv.org/abs/math/0609329, where a decompostion of this prodcut as a sum of free operators is given in terms of the individual adjacency operators of the factors.

Now, there are actually two small differences between the free product of K2 (corresponding to $1/2\delta_{-1}+1/2\delta_1$) with itself and the graphs you are considering: First, the free product is actually infinite: $$⋯∘-∘-∘-∘-∘-∘-⋯$$ and second, one needs to consider the vector state $<A~\delta(e),\delta(e)>$, where $e$ is root of the graph, instead of the normalized trace $tr$. However, both differences "vanish" in the limit since almost all the vertexes look locally as belonging to the actual free product.

Answer 4

If $\phi_n$ denotes the characteristic polynomial of the path on $n$ vertices then $$ \phi_{n+1}(t) = t\phi_n(t) - \phi_{n-1}(t), $$ from which you can show that $$ \phi_n(2\cos(\zeta)) = \frac{\sin(n+1)\zeta}{\sin(\zeta)}. $$ So your observation is not a surprise from a graph theoretical viewpoint. I have nothing useful to say about free probability.