Relationship between free probability and deterministic graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:02:32Z http://mathoverflow.net/feeds/question/76350 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76350/relationship-between-free-probability-and-deterministic-graphs Relationship between free probability and deterministic graphs? Jiahao Chen 2011-09-25T17:45:43Z 2011-10-23T15:40:07Z <p>Consider the $N\times N$ matrix <code>$$M = \left(\begin{array} \\ 0 &amp; 1 &amp; &amp; 0 \\ 1 &amp; \ddots &amp; \ddots &amp; \\ &amp; \ddots &amp; \ddots &amp; 1 \\ 0 &amp; &amp; 1 &amp; 0 \\ \end{array}\right)$$</code></p> <p>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$$</p> <p>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 &lt; 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.</p> <blockquote> <p>Is this mere coincidence, or evidence of something deeper? I feel like this must be some example of a known result out there.</p> </blockquote> <p>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$$ <code>$$A = \left(\begin{array}{cccccc} 0 &amp; 1\\ 1 &amp; 0\\ &amp; &amp; 0 &amp; 1\\ &amp; &amp; 1 &amp; 0\\ &amp; &amp; &amp; &amp; \ddots\\ &amp; &amp; &amp; &amp; &amp; \ddots \end{array}\right) = \sigma_x \oplus \sigma_x \oplus \cdots$$</code> <code>$$B = \left(\begin{array}{cccccc} 0\\ &amp; 0 &amp; 1\\ &amp; 1 &amp; 0\\ &amp; &amp; &amp; 0 &amp; 1\\ &amp; &amp; &amp; 1 &amp; 0\\ &amp; &amp; &amp; &amp; &amp; \ddots \end{array}\right) = [0] \oplus \sigma_x \oplus \sigma_x \oplus \cdots$$</code></p> <p>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.</p> <p>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. </p> http://mathoverflow.net/questions/76350/relationship-between-free-probability-and-deterministic-graphs/76354#76354 Answer by Chris Godsil for Relationship between free probability and deterministic graphs? Chris Godsil 2011-09-25T18:32:37Z 2011-09-25T18:32:37Z <p>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.</p> http://mathoverflow.net/questions/76350/relationship-between-free-probability-and-deterministic-graphs/76360#76360 Answer by suVRit for Relationship between free probability and deterministic graphs? suVRit 2011-09-25T19:50:58Z 2011-09-25T19:50:58Z <p>I'd like to add that in general, your matrix is a special case of symmetric tridiagonal matrices of the form</p> <p>$$\begin{bmatrix} a &amp; b &amp; \cdots &amp; \cdots &amp; 0\\ b &amp; a &amp; b &amp; \cdots &amp; 0\\ &amp; \ddots &amp; \ddots &amp; \ddots\\ 0 &amp; \cdots &amp; &amp;a &amp; b\\ 0 &amp; \cdots &amp; &amp;b &amp; a \end{bmatrix}$$</p> <p>The eigenvalues of this matrix are $$\lambda_k = a + 2b\cos(k\pi/(n+1)),\qquad 1 \le k \le n.$$</p> <p>The eigenvectors have a similar nice closed form.</p> <p>$$v_{ik} = \sin\left(\frac{ik\pi}{n+1}\right),\qquad 1\le i,k \le n.$$</p> <p>These facts can probably be quickly derived by looking at the characteristic polynomial.</p> http://mathoverflow.net/questions/76350/relationship-between-free-probability-and-deterministic-graphs/78883#78883 Answer by Adrien Hardy for Relationship between free probability and deterministic graphs? Adrien Hardy 2011-10-23T11:08:03Z 2011-10-23T15:40:07Z <p>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. </p> <p>Let me try to develop : We first need some computations.</p> <p>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 &lt; 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 &lt; 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$. </p> <p>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.</p> <p>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).</p> <p>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})$.</p>