{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Random Matrix Theory

\n",
"\n",
"(Sethna, \"Entropy, Order Parameters, and Complexity\", ex. 1.6, developed with Piet Brouwer)\n",
"\n",
"© 2016, James Sethna, all rights reserved."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is an ipython notebook. This hints file is unusually detailed, but only covers the computational parts (a & f) of the exercise: don't neglect the analytical portions! If you are familiar with Mathematica, feel free to skip parts you don't need, or start your own notebooks.\n",
"\n",
"Lectures about Python, useful both for beginners and experts, can be found at http://scipy-lectures.github.io. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I recommend installing the [Anaconda](https://store.continuum.io/cshop/academicanaconda) distribution. \n",
"\n",
"Go to https://www.continuum.io/downloads\n",
"\n",
"Pick your operating system (Windows, Mac OS X, Linux)\n",
"\n",
"Follow instructions for Python 3.5.\n",
"\n",
"To make it run much faster (probably necessary for some assignments):\n",
"\n",
"Be sure not to pay for it! Get an academic subscription, using your Cornell (.edu) e-mail,\n",
"from https://www.continuum.io/anaconda-academic-subscriptions-available\n",
" * Set up an account, using your Cornell e-mail\n",
" * Go to My Settings under your name in the upper right hand side\n",
" of the Anaconda Cloud window, and\n",
" * Go to Add Ons, the lowest menu entry in the left-hand column\n",
" * Download the licenses, and follow the installation instructions link\n",
" just above the MKL licence button (or go to\n",
" http://docs.continuum.io/advanced-installation)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Open the notebook by (1) copying this file into a directory, (2) in that directory typing:\n",
"\n",
" ipython notebook\n",
"\n",
"and (3) selecting the notebook. In later exercises, if you do animations, you may choose to not have the plots inline.\n",
"\n",
"Like Mathematica, you type in commands and then hit 'Shift Return' to execute them."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"a = 3.\n",
"print(a)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Python is not a complete scientific environment. Functions like log, sin, and exp are provided by external packages. The plotting package pylab supports many of these; '%pylab inline' puts the graphs into the notebook. We usually want more functionality than that, so we import a package called 'scipy' (an extension of 'numpy'). We'll also be using some of their linear algebra routines, which are in a sub-package 'scipy.linalg'. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%pylab inline \n",
"from scipy import *"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One of the most active and unusual applications of ensembles is *random matrix theory*, used to describe phenomena in nuclear physics, mesoscopic quantum mechanics, and wave phenomena. Random matrix theory was invented in a bold attempt to describe the statistics of energy level spectra in nuclei. In many cases, the statistical behavior of\n",
"systems exhibiting complex wave phenomena -- almost any correlations involving eigenvalues and eigenstates -- can be quantitatively modeled using ensembles of matrices with completely random, uncorrelated entries!\n",
"\n",
"The most commonly explored ensemble of matrices is the Gauusian orthogonal ensemble (GOE). Generating a member takes two steps:\n",
" * Generate an NxN matrix whose elements are independent Gaussian distributions of zero mean and standard deviation $\\sigma = 1$.\n",
" * Add the matrix to its transpose to symmetrize it."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. \n",
"\n",
"Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is the distribution Gaussian, uniform, or exponential? The flag 'normed' tells us to not just count the number of occurences in each bin, but to divide by the width of the bin and the number of counts (to approximate a normalized probability distribution). "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"?random\n",
"print(random.random())\n",
"print(random.random(6))\n",
"hist(random.random(1000), normed=True);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Use random.standard_normal to generate a Gaussian distribution of one thousand random numbers. Check that it is a standard Gaussian \n",
"$$\\rho(x) = \\frac{1}{\\sqrt{2\\pi}\\sigma} e^{-x^2/2\\sigma^2}$$\n",
"by using 'hist'."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"print(random.standard_normal(...))\n",
"hist(random.standard_normal(...), normed=...);\n",
"x = arange(-3,3,0.01)\n",
"plot(x,(1./sqrt(2*pi))*exp(-x**2/2),'r')\n",
"show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One final matrix operation. To generate a symmetric matrix of the GOE form, we'll want to add a matrix to its transpose. Generate a 2x3 matrix of normally distributed random numbers, and print it and its transpose."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"m = random.standard_normal((2,3));\n",
"print(m)\n",
"print(transpose(m))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now define a function GOE(N) (using 'def') which generates a GOE NxN matrix."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def GOE(N):\n",
" \"\"\"\n",
" Creates an NxN element of the Gaussian Orthogonal Ensemble,\n",
" by creating an NxN matrix of Gaussian random variables\n",
" using the random array function random.standard_normal([shape]) \n",
" with [shape] = (N,N).\n",
" and adding it to its transpose (applying transpose to the matrix)\n",
" #\n",
" Typing GOE(4) a few times, check it's symmetric and random\n",
" \"\"\"\n",
" m = random. ...((...,...))\n",
" m = m + transpose(m)\n",
" return m"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Test it by generating a 4x4 matrix. Is it symmetric?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"GOE(4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now write a function GOE_Ensemble(num, N) generating an ensemble (a long list with 'num' elements) of GOE NxN matrices. Call GOE(N) to fill the list."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def GOE_Ensemble(num, N):\n",
" \"\"\"\n",
" Creates a list \"ensemble\" of length num of NxN GOE matrices.\n",
" # \n",
" You can start with an empty list, and fill it with 'append'\n",
" ensemble = []\n",
" for n in range(num):\n",
" ensemble.append(GOE(N))\n",
" return ensemble\n",
" or you can use the convenient 'list comprehension'\n",
" ensemble = [GOE(N) for n in range(num)]\n",
" #\n",
" Check GOE_Ensemble(3,2) gives 3 2x2 symmetric matrices\n",
" \"\"\"\n",
" ensemble = ...\n",
" return ensemble"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here you may want to generate an ensemble, and check if the diagonal elements and the off-diagonal elements have different standard deviations, as you calculated in part (c). (This difference is part of the definition of the GOE ensemble, and is needed to make the ensemble rotation invariant.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One of the most striking properties that large random matrices share is the distribution of level splittings.\n",
"\n",
"To look at eigenvalues of our symmetric matrices, we use 'eigvalsh'. We'll want them sorted. And we'll want to find the difference between the two middle-most eigenvalues.\n",
"\n",
"Notice, in python, arrays are indexed lambda = [lambda[0], ..., lambda[N-1]], so the middle two are N/2 and N/2-1. Note that in the new version of python dividing integers 4/2 = 2.0 gives a floating point number, so we need to use N//2 to get an integer. (This is a good thing: having 2/10 = 0 causes lots of problems when you write routines that don't know whether their inputs are floats or ints.)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"N=4\n",
"midpoint = int(N/2)\n",
"mat = GOE(N)\n",
"print(mat)\n",
"eig = sort(eigvalsh(mat))\n",
"print(eig)\n",
"print(eig[N//2]-eig[N//2-1])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def CenterEigenvalueDifferences(ensemble):\n",
" \"\"\"\n",
" For each symmetric matrix in the ensemble, calculates the difference \n",
" between the two center eigenvalues of the ensemble, and returns the\n",
" differences as an array.\n",
" #\n",
" Given an ensemble of symmetric matrices, \n",
" finds their size N, using the first member ensemble[0]\n",
" len(m) gives the number of rows in m\n",
" starts with an empty list of differences\n",
" for each m in ensemble\n",
" finds the eigenvalues\n",
" eigvals(m) gives the eigenvalues of m\n",
" sorts them\n",
" sort(e) sorts a list from smallest to largest\n",
" appends eigenvalue[N/2] - eigenvalue[N/2-1] to the list\n",
" (Note: python lists go from 0 ... N-1, so for N=2 this \n",
" gives the difference between the only two eigenvalues)\n",
" #\n",
" Check \n",
" ensemble = GOE_Ensemble(3,2)\n",
" CenterEigenvalueDifferences(ensemble) \n",
" gives three positive numbers, that look like eigenvalues of the 2x2 matrices\n",
" \"\"\"\n",
" # Size of matrix\n",
" N = len(...)\n",
" diffs = []\n",
" # Note that you can 'iterate' not only over integers, but over elements of a list (for mat in ensemble: ...)\n",
" for mat in ensemble:\n",
" eigenvalues = sort(...)\n",
" diffs.append(...)\n",
" return diffs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Check that\n",
"\n",
" ensemble = GOE_Ensemble(3,2)\n",
" CenterEigenvalueDifferences(ensemble) \n",
" \n",
"gives three positive numbers, that look like eigenvalue differences of 2x2 matrices, Check that\n",
"\n",
" hist(CenterEigenvalueDifferences(ensemble), bins=30, normed=True);\n",
"\n",
"gives three spikes at the three eigenvalue differences. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"ensemble = GOE_Ensemble(...)\n",
"print(CenterEigenvalueDifferences(...))\n",
"hist(CenterEigenvalueDifferences(...), bins=50, normed=True);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now try it with 10000 or more. Notice the smooth distribution, with a linear tail near zero."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"M = 10000\n",
"N = 2\n",
"ensemble = GOE_Ensemble(M, N);\n",
"diffs = CenterEigenvalueDifferences(ensemble)\n",
"hist(diffs, bins=50, normed=True);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What is this dip in the eigenvalue splitting probability near zero? It is called *level repulsion*."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wigner's surmise (meaning 'guess') was that this distribution was **universal**, that is, independent of the ensemble of matrices. Clearly another ensemble, with all our matrix elements multiplied by two, will have eigenvalue differences twice as big. Wigner surmised that the eigenvalue differences, *divided by the mean of the differences* would be universal. Plot these normalized centered differences against your analytical prediction for 2x2 matrices (see text), which should be $\\rho_{Wigner}(s) = (\\pi s/2) \\exp(-\\pi s^2 / 4)$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"hist(diffs/mean(diffs), bins=50, normed=True);\n",
"s = arange(0.,3.,0.01)\n",
"rhoWigner = ...\n",
"plot(s, rhoWigner, 'r');\n",
"title('2x2 matrix eig diffs')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Try N=4 and N=10; do they look similar?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"M = 10000\n",
"N = 4\n",
"ensemble = ...\n",
"diffs = ...\n",
"hist(...);\n",
"plot(...);\n",
"title(...)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"M = 10000\n",
"N = 10\n",
"ensemble = ...\n",
"diffs = ...\n",
"hist(...);\n",
"plot(...);\n",
"title(...)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that we're typing the same commands several times. This is a bad programming practice (a 'bad smell') -- whenever writing the same code more than a couple of lines long, write it as a subroutine. That way, when you fix an error, it'll get fixed everywhere you use it."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def CompareEnsembleWigner(ensemble):\n",
" diffs = ...\n",
" hist(...);\n",
" plot(...)\n",
"\n",
"CompareEnsembleWigner(ensemble)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Your 2x2 formula is pretty good, but turns out to be up to 2% off for larger matrices; Wigner was wrong about that. But he was correct that the eigenvalue splitting is universal, if you consider large matrices. \n",
"\n",
"We can test this by trying a different ensemble. For example, let's try random symmetric matrices filled with +-1. In the past, we've created these matrices the hard way. But let's just take the signs of the matrix elements generated by the GOE ensemble!"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"sign(GOE_Ensemble(4,3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Define a PM1 ensemble (Plus or Minus 1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def PM1_Ensemble(num, N):\n",
" \"\"\"\n",
" Generates a +-1 ensemble, as for GOE_Ensemble above.\n",
" Use with CompareEnsembleWigner to test that N=2 looks different\n",
" from the Wigner ensemble, but larger N looks close to the GOE ensemble.\n",
" #\n",
" This is a powerful truth: the eigenvalue differences of very general classes\n",
" of symmetric NxN matrices all have the same probability distribution\n",
" as N goes to infinity. This is what we call universality. \n",
" \"\"\"\n",
" return sign(...)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Try comparing the splittings for 2x2 matrices with the prediction."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"CompareEnsembleWigner(PM1_Ensemble(10000,2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Is it well approximated by the Wigner surmise? Why not? (Hint: how many different symmetric 2x2 matrices of $\\pm 1$ are there?)\n",
"\n",
"Try it with 4x4 and 10x10 matrices."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"CompareEnsembleWigner(...)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"10x10 should work better, except for a funny bump at zero."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"CompareEnsembleWigner(...)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The GOE ensemble has some nice statistical properties (see text)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is our first example of an *emergent symmetry*. Many different\n",
"ensembles of symmetric matrices, as the size $N$ goes to infinity,\n",
"have eigenvalue and eigenvector distributions that are invariant under\n",
"orthogonal transformations *even though the original matrix ensemble\n",
"did not have this symmetry*. Similarly, rotational symmetry emerges\n",
"in random walks on the square lattice as the number of steps $N$ goes\n",
"to infinity, and also emerges on long length scales for Ising models at\n",
"their critical temperatures."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}