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.

cartoonof a graph? Isn't it a legitimate presentation of a graph? $\endgroup$ – Hans-Peter Stricker Sep 25 '11 at 22:46