Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
The discrete Laplacian on a chain approximates the Laplacian on $[0, 1]$, so its eigenvalues approximate frequencies of standing waves with vanishing (?) boundary conditions. In fact using this idea one can explicitly write down eigenfunctions and eigenvalues. –  Qiaochu Yuan Sep 25 '11 at 18:21
Why do you call o-o-...-o a cartoon of a graph? Isn't it a legitimate presentation of a graph? –  Hans Stricker Sep 25 '11 at 22:46

3 Answers 3

up vote 4 down vote accepted

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 Chebychev (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})$.

share|improve this answer
I would agree that there is something special about the matrix structure that allows this correspondence. I was not aware of Heine's formula, thanks. This deserves to be accepted as an answer, although I wonder if there is something more interesting that points toward possible generalizations. –  Jiahao Chen May 11 '12 at 18:01

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.

share|improve this answer
Thanks for crossing one item off my to-do list. –  Jiahao Chen Sep 26 '11 at 17:52
In short: tridiagonal Toeplitz matrices and Chebyshev polynomials are intimately related. –  J. M. Nov 21 '11 at 16:22

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.