12_01_quantum_spin_chain.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum Spins\n",
    "\n",
    "We are going consider a magnetic insulator, \n",
    "a Mott insulator. In this problem we have a valence electron per\n",
    "atom, with very localized wave-functions. The Coulomb repulsion between\n",
    "electrons on the same orbital is so strong, that electrons are bound to\n",
    "their host atom, and cannot move. For this reason, charge disappears\n",
    "from the equation, and the only remaining degree of freedom is the spin\n",
    "of the electrons. The corresponding local state can therefore be either\n",
    "$|\\uparrow\\rangle$ or $|\\downarrow\\rangle$. The only interaction taking\n",
    "place is a process that “flips” two anti-aligned neighboring spins\n",
    "$|\\uparrow\\rangle|\\downarrow\\rangle \\rightarrow |\\downarrow\\rangle|\\uparrow\\rangle$.\n",
    "\n",
    "Let us now consider a collection of spins residing on site of a\n",
    "–one-dimensional for simplicity– lattice. An arbitrary state of\n",
    "$N$-spins can be described by using the $S^z$ projection\n",
    "($\\uparrow,\\downarrow$) of each spin as: $|s_1,s_2,..., s_N\\rangle$. As\n",
    "we can easily see, there are $2^N$ of such configurations.\n",
    "\n",
    "Let us now consider a collection of spins residing on site of a\n",
    "–one-dimensional for simplicity– lattice. An arbitrary state of\n",
    "$N$-spins can be described by using the $S^z$ projection\n",
    "($\\uparrow,\\downarrow$) of each spin as: $|s_1,s_2,..., s_N\\rangle$. As\n",
    "we can easily see, there are $2^N$ of such configurations.\n",
    "\n",
    "We shall describe the interactions between neighboring spins using the\n",
    "so-called Heisenberg Hamiltonian:\n",
    "\n",
    "$$\\hat{H}=\\sum_{i=1}^{N-1} \\hat{\\mathbf{S}}_i \\cdot \\hat{\\mathbf{S}}_{i+1}\n",
    "$$\n",
    "\n",
    "where $\\hat{\\mathbf{S}}_i = (\\hat{S}^x,\\hat{S}^y,\\hat{S}^z)$ is the spin\n",
    "operator acting on the spin on site $i$.\n",
    "\n",
    "Since we are concerned about spins one-half, $S=1/2$, all these\n",
    "operators have a $2\\times2$ matrix representation, related to the\n",
    "well-known Pauli matrices:\n",
    "\n",
    "$$S^z = \\left(\n",
    "\\begin{array}{cc}\n",
    "1/2 & 0 \\\\\n",
    "0 & -1/2\n",
    "\\end{array}\n",
    "\\right),\n",
    "S^x = \\left(\n",
    "\\begin{array}{cc}\n",
    "0 & 1/2 \\\\\n",
    "1/2 & 0\n",
    "\\end{array}\n",
    "\\right),\n",
    "S^y = \\left(\n",
    "\\begin{array}{cc}\n",
    "0 & -i/2 \\\\\n",
    "i/2 & 0\n",
    "\\end{array}\n",
    "\\right),\n",
    "$$\n",
    "\n",
    "These matrices act on two-dimensional vectors defined by the basis\n",
    "states $|\\uparrow\\rangle$ and $|\\downarrow\\rangle$. It is useful to\n",
    "introduce the identities:\n",
    "$$\\hat{S}^\\pm = \\left(\\hat{S}^x \\pm i \\hat{S}^y\\right),$$ where $S^+$\n",
    "and $S^-$ are the spin raising and lowering operators. It is intuitively\n",
    "easy to see why by looking at how they act on the basis states:\n",
    "$\\hat{S}^+|\\downarrow\\rangle = |\\uparrow\\rangle$ and\n",
    "$\\hat{S}^-|\\uparrow\\rangle = |\\downarrow\\rangle$. Their corresponding\n",
    "$2\\times2$ matrix representations are: $$S^+ = \\left(\n",
    "\\begin{array}{cc}\n",
    "0 & 1 \\\\\n",
    "0 & 0\n",
    "\\end{array}\n",
    "\\right),\n",
    "S^- = \\left(\n",
    "\\begin{array}{cc}\n",
    "0 & 0 \\\\\n",
    "1 & 0\n",
    "\\end{array}\n",
    "\\right),\n",
    "$$\n",
    "\n",
    "We can now re-write the Hamiltonian (\\[heisenberg\\]) as:\n",
    "$$\\hat{H}=\\sum_{i=1}^{N-1}\n",
    "\\hat{S}^z_i \\hat{S}^z_{i+1} +\n",
    "\\frac{1}{2}\\left[\n",
    "\\hat{S}^+_i \\hat{S}^-_{i+1} +\n",
    "\\hat{S}^-_i \\hat{S}^+_{i+1}\n",
    "\\right]\n",
    "$$ The first term in this expression is diagonal and\n",
    "does not flip spins. This is the so-called Ising term. The second term\n",
    "is off-diagonal, and involves lowering and raising operators on\n",
    "neighboring spins, and is responsible for flipping anti-aligned spins.\n",
    "This is the “$XY$” part of the Hamiltonian.\n",
    "\n",
    "The Heisenberg spin chain is a paradigmatic model in condensed matter.\n",
    "Not only it is attractive due to its relative simplicity, but can also\n",
    "describe real materials that can be studied experimentally. The\n",
    "Heisenberg chain is also a prototypical integrable system, that can be\n",
    "solved exactly by the Bethe Ansatz, and can be studied using\n",
    "bosonization techniques and conformal field theory.\n",
    "\n",
    "The Heisenberg spin chain is a paradigmatic model in condensed matter.\n",
    "Not only it is attractive due to its relative simplicity, but can also\n",
    "describe real materials that can be studied experimentally. The\n",
    "Heisenberg chain is also a prototypical integrable system, that can be\n",
    "solved exactly by the Bethe Ansatz, and can be studied using\n",
    "bosonization techniques and conformal field theory.\n",
    "\n",
    "In these lectures, we will be interested in obtaining its ground state\n",
    "properties of this model by numerically solving the time-independent\n",
    "Schrödinger equation: $$\\hat{H}|\\Psi\\rangle = E|\\Psi\\rangle,$$ where $H$\n",
    "is the Hamiltonian of the problem, $|\\Psi\\rangle$ its eigenstates, with\n",
    "the corresponding eigenvalues, or energies $E$.\n",
    "\n",
    "Exact diagonalization\n",
    "=====================\n",
    "\n",
    "![blocks](figures/fig_blocks.png)\n",
    "#### Pictorial representation of the Hamiltonian building recursion explained in the text. At each step, the block size is increased by adding a spin at a time.\n",
    "\n",
    "In this section we introduce a technique that will allow us to calculate\n",
    "the ground state, and even excited states of small Heisenberg chains.\n",
    "Exact Diagonalization (ED) is a conceptually simple technique which\n",
    "basically consists of diagonalizing the Hamiltonian matrix by brute\n",
    "force. Same as for the spin operators, the Hamiltonian also has a\n",
    "corresponding matrix representation. In principle, if we are able to\n",
    "compute all the matrix elements, we can use a linear algebra package to\n",
    "diagonalize it and obtain all the eigenvalues and eigenvectors @lapack.\n",
    "\n",
    "In these lectures we are going to follow a quite unconventional\n",
    "procedure to describe how this technique works. It is important to point out that this\n",
    "is a quite inefficient and impractical way to diagonalize the\n",
    "Hamiltonian, and more sophisticated techniques are generally used in\n",
    "practice.\n",
    "\n",
    "Two-spin problem\n",
    "----------------\n",
    "\n",
    "The Hilbert space for the two-spin problem consists of four possible\n",
    "configurations of two spins\n",
    "$$\\left\\{ |\\uparrow\\uparrow\\rangle,|\\uparrow\\downarrow\\rangle,|\\downarrow\\uparrow\\rangle,|\\downarrow\\downarrow\\rangle \\right\\}$$\n",
    "\n",
    "The problem is described by the Hamiltonian: $$\\hat{H}=\n",
    "\\hat{S}^z_1 \\hat{S}^z_2 +\n",
    "\\frac{1}{2}\\left[\n",
    "\\hat{S}^+_1 \\hat{S}^-_2 +\n",
    "\\hat{S}^-_1 \\hat{S}^+_2\n",
    "\\right]$$\n",
    "\n",
    "The corresponding matrix will have dimensions $4 \\times 4$. In order to\n",
    "compute this matrix we shall use some simple matrix algebra to first\n",
    "obtain the single-site operators in the expanded Hilbert space. This is\n",
    "done by following the following simple scheme: And operator $O_1$ acting\n",
    "on the left spin, will have the following $4 \\times 4$ matrix form:\n",
    "$$\\tilde{O}_1 = O_1 \\otimes {1}_2\n",
    "$$ Similarly, for an operator $O_2$ acting on the right\n",
    "spin: $$\\tilde{O}_2 = {1}_2 \\otimes O_2\n",
    "$$ where we introduced the $n \\times n$ identity matrix\n",
    "${1}_n$. The product of two operators acting on different sites\n",
    "can be obtained as: $$\\tilde{O}_{12} = O_1 \\otimes O_2$$ It is easy to\n",
    "see that the Hamiltonian matrix will be given by: $$H_{12}=\n",
    "S^z \\otimes S^z +\n",
    "\\frac{1}{2}\\left[\n",
    "S^+ \\otimes S^- +\n",
    "S^- \\otimes S^+\n",
    "\\right]$$ where we used the single spin ($2 \\times 2$) matrices $S^z$\n",
    "and $S^\\pm$. We leave as an exercise for the reader to show that the\n",
    "final form of the matrix is:\n",
    "\n",
    "$$H_{12} = \\left(\n",
    "\\begin{array}{cccc}\n",
    "1/4 & 0 & 0 & 0 \\\\\n",
    "0 & -1/4 & 1/2 & 0 \\\\\n",
    "0 & 1/2 & -1/4 & 0 \\\\\n",
    "0 & 0 & 0 & 1/4 \\\\\n",
    "\\end{array}\n",
    "\\right),\n",
    "$$\n",
    "\n",
    "Obtaining the eigenvalues and eigenvectors is also a straightforward\n",
    "exercise: two of them are already given, and the entire problem now\n",
    "reduces to diagonalizing a two by two matrix. We therefore obtain the\n",
    "well known result: The ground state\n",
    "$|s\\rangle = 1/\\sqrt{2}\\left[ |\\uparrow\\downarrow\\rangle - |\\downarrow\\uparrow\\rangle \\right]$,\n",
    "has energy $E_s=-3/4$, and the other three eigenstates\n",
    "$\\left\\{|\\uparrow\\uparrow\\rangle,|\\downarrow\\downarrow\\rangle,1/\\sqrt{2}\\left[ |\\uparrow\\downarrow\\rangle + |\\downarrow\\uparrow\\rangle \\right] \\right\\}$\n",
    "form a multiplet with energy $E_t=1/4$.\n",
    "\n",
    "Many spins\n",
    "----------\n",
    "\n",
    "Imagine now that we add a third spin to the right of our two spins. We\n",
    "can use the previous result to obtain the new $8 \\times 8$ Hamiltonian\n",
    "matrix as: $$H_{3}=\n",
    "H_{2} \\otimes {1}_2 +\n",
    "\\tilde{S}^z_2 \\otimes S^z +\n",
    "\\frac{1}{2}\\left[\n",
    "\\tilde{S}^+_2 \\otimes S^- +\n",
    "\\tilde{S}^-_2 \\otimes S^+\n",
    "\\right]$$ Here we used the single spin $S^z_1$, $S^\\pm_1$, and the\n",
    "\\`tilde\\` matrices defined in Eqs.(\\[tildeL\\]) and (\\[tildeR\\]):\n",
    "$$\\tilde{S}^z_2 = {1}_2 \\otimes S^z,$$ and\n",
    "$$\\tilde{S}^\\pm_2 = {1}_2 \\otimes S^\\pm,$$\n",
    "\n",
    "It is easy to see that this leads to a recursion scheme to construct the\n",
    "$2^i \\times 2^i$ Hamiltonian matrix the $i^\\mathrm{th}$ step as:\n",
    "\n",
    "$$H_{i}=\n",
    "H_{i-1} \\otimes {1}_2 +\n",
    "\\tilde{S}^z_{i-1} \\otimes S^z +\n",
    "\\frac{1}{2}\\left[\n",
    "\\tilde{S}^+_{i-1} \\otimes S^- +\n",
    "\\tilde{S}^-_{i-1} \\otimes S^+\n",
    "\\right]$$\n",
    "\n",
    "with $$\\tilde{S}^z_{i-1} = {1}_{2^{i-2}} \\otimes S^z,$$ and\n",
    "$$\\tilde{S}^\\pm_{i-1} = {1}_{2^{i-2}} \\otimes S^\\pm,$$\n",
    "\n",
    "This recursion algorithm can be visualized as a left ‘block’, to which\n",
    "we add new ‘sites’ or spins to the right, one at a time, as shown in\n",
    "Fig.\\[fig:block\\].The block has a ‘block Hamiltonian’, $H_L$, that is\n",
    "iteratively built by connecting to the new spins through the\n",
    "corresponding interaction terms.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ADDING SITE  1  DIML=  1\n",
      "ADDING SITE  2  DIML=  2\n",
      "ADDING SITE  3  DIML=  4\n",
      "[-1.6160254  -0.95710678 -0.95710678 -0.95710678 -0.25       -0.25\n",
      " -0.25        0.1160254   0.45710678  0.45710678  0.45710678  0.75\n",
      "  0.75        0.75        0.75        0.75      ]\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "from matplotlib import pyplot\n",
    "\n",
    "# PARAMETERS\n",
    "nsites = 4\n",
    "\n",
    "#Single site operators\n",
    "sz0 = np.zeros(shape=(2,2)) # single site Sz\n",
    "splus0 = np.zeros(shape=(2,2)) # single site S+\n",
    "sz0[0,0]         = -0.5\n",
    "sz0[1,1]         =  0.5\n",
    "splus0[1,0]      =  1.0\n",
    "\n",
    "term_szsz = np.zeros(shape=(4,4)) #auxiliary matrix to store Sz.Sz\n",
    "term_szsz = np.kron(sz0,sz0)\n",
    "\n",
    "term_spsm = np.zeros(shape=(4,4)) #auxiliary matrix to store 1/2 S+.S-\n",
    "term_spsm = np.kron(splus0,np.transpose(splus0))*0.5\n",
    "term_spsm += np.transpose(term_spsm)\n",
    "\n",
    "h12 = term_szsz+term_spsm\n",
    "\n",
    "H = np.zeros(shape=(2,2))\n",
    "for i in range(1,nsites):\n",
    "\n",
    "    diml = 2**(i-1)        # 2^i\n",
    "    dim = diml*2\n",
    "    \n",
    "    print (\"ADDING SITE \",i,\" DIML= \",diml)\n",
    "\n",
    "    Ileft = np.eye(diml)\n",
    "    Iright = np.eye(2)\n",
    "\n",
    "    # We add the term for the interaction S_i.S_{i+1}\n",
    "\n",
    "    aux = np.zeros(shape=(dim,dim))\n",
    "    aux = np.kron(H,Iright)\n",
    "    H = aux\n",
    "\n",
    "    H = H + np.kron(Ileft,h12)\n",
    "\n",
    "w, v = np.linalg.eigh(H) #Diagonalize the matrix\n",
    "print(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.1 -0.05760987249510802\n",
      "0.2 -0.11772708133199768\n",
      "0.30000000000000004 -0.1799749161303902\n",
      "0.4 -0.24390632110272253\n",
      "0.5 -0.30901701565428624\n",
      "0.6 -0.37476304806595323\n",
      "0.7000000000000001 -0.4405815376403906\n",
      "0.8 -0.5059129169711236\n",
      "0.9 -0.5702227720500874\n",
      "1.0 -0.6330214400416623\n",
      "1.1 -0.6938798489847898\n",
      "1.2000000000000002 -0.7524406008645199\n",
      "1.3000000000000003 -0.8084239045835981\n",
      "1.4000000000000001 -0.8616285472956369\n",
      "1.5000000000000002 -0.9119285611250054\n",
      "1.6 -0.9592665450743981\n",
      "1.7000000000000002 -1.0036447279137457\n",
      "1.8000000000000003 -1.0451148298845272\n",
      "1.9000000000000001 -1.0837676421128473\n",
      "2.0 -1.1197230415459163\n",
      "2.1 -1.1531209397429492\n",
      "2.2 -1.1841134584514705\n",
      "2.3000000000000003 -1.2128584531880562\n",
      "2.4000000000000004 -1.2395143762135286\n",
      "2.5000000000000004 -1.2642363821382747\n",
      "2.6 -1.2871735275792655\n",
      "2.7 -1.3084668931419337\n",
      "2.8000000000000003 -1.328248453489718\n",
      "2.9000000000000004 -1.3466405322009147\n",
      "3.0000000000000004 -1.363755696693066\n",
      "3.1 -1.3796969704179296\n",
      "3.2 -1.3945582618585033\n",
      "3.3000000000000003 -1.4084249307704304\n",
      "3.4000000000000004 -1.4213744306172185\n",
      "3.5000000000000004 -1.4334769818512214\n",
      "3.6 -1.4447962435689152\n",
      "3.7 -1.4553899613221313\n",
      "3.8000000000000003 -1.4653105768129209\n",
      "3.9000000000000004 -1.4746057911956585\n",
      "4.0 -1.4833190781084635\n",
      "4.1 -1.4914901456799556\n",
      "4.2 -1.4991553488883003\n",
      "4.3 -1.5063480550238921\n",
      "4.3999999999999995 -1.5130989658181841\n",
      "4.5 -1.5194364002033278\n",
      "4.6 -1.525386541780906\n",
      "4.7 -1.5309736549956194\n",
      "4.8 -1.5362202738007493\n",
      "4.9 -1.5411473663178232\n",
      "5.0 -1.545774478670119\n",
      "5.1 -1.5501198608343107\n",
      "5.2 -1.5542005770242835\n",
      "5.3 -1.5580326028072495\n",
      "5.4 -1.5616309108616067\n",
      "5.5 -1.5650095470219236\n",
      "5.6 -1.5681816980203966\n",
      "5.7 -1.5711597521256073\n",
      "5.8 -1.5739553536973145\n",
      "5.9 -1.5765794525182384\n",
      "6.0 -1.5790423486282907\n",
      "6.1 -1.5813537332709984\n",
      "6.2 -1.5835227264637413\n",
      "6.3 -1.585557911620593\n",
      "6.4 -1.587467367587014\n",
      "6.5 -1.5892586983874784\n",
      "6.6 -1.5909390609386986\n",
      "6.7 -1.59251519094089\n",
      "6.8 -1.5939934271262712\n",
      "6.9 -1.5953797340165645\n",
      "7.0 -1.5966797233186383\n",
      "7.1 -1.5978986740689103\n",
      "7.2 -1.599041551621867\n",
      "7.3 -1.6001130255655813\n",
      "7.4 -1.6011174866368567\n",
      "7.5 -1.6020590627002125\n",
      "7.6 -1.6029416338480085\n",
      "7.7 -1.6037688466733007\n",
      "7.8 -1.604544127762277\n",
      "7.9 -1.6052706964491754\n",
      "8.0 -1.605951576873285\n",
      "8.1 -1.6065896093747862\n",
      "8.2 -1.607187461263813\n",
      "8.3 -1.6077476369949997\n",
      "8.4 -1.6082724877779597\n",
      "8.5 -1.6087642206525095\n",
      "8.6 -1.6092249070559606\n",
      "8.7 -1.609656490908509\n",
      "8.8 -1.6100607962414513\n",
      "8.9 -1.6104395343918765\n",
      "9.0 -1.6107943107863336\n",
      "9.1 -1.6111266313349915\n",
      "9.2 -1.6114379084568324\n",
      "9.3 -1.6117294667554514\n",
      "9.4 -1.612002548364183\n",
      "9.5 -1.612258317978388\n",
      "9.6 -1.612497867591895\n",
      "9.700000000000001 -1.6127222209538343\n",
      "9.8 -1.6129323377612643\n",
      "9.9 -1.613129117602311\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAD8CAYAAAB+UHOxAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAHm9JREFUeJzt3XmUHGd97vHvb1ZJM9o1Gq229tUBy5KNFwwGy8g2BGOCiQlOZF+4CgQI5EDAYM7NTXJyrsOSQAKXHCEWGzhgjnewg2TJGMEFjCUs2xqN9nWkmdGM9pmRZuvf/aNrRu3RbFJ1d/V0PZ9zdLqr++1+37al96l637eqzN0REZH4KYi6ASIiEg0FgIhITCkARERiSgEgIhJTCgARkZhSAIiIxJQCQEQkphQAIiIxVZSOLzGzW4GvA4XAGnd/sMf7pcDDwFLgGPDn7r5/gO/UGWoiIpfA3W0w5UIfAZhZIfBN4DZgEfABM1vUo9iHgBPuPgf4d+Bfw9YrIiLhpOMI4Bpgt7vvBTCznwB3ANtSytwB/O/g+aPAN8zMfBDXodClKkREBsdsUDv+3dIxBzAVOJSyXRO81msZd+8ATgHj01C3iIhcopybBDazVWa2Kep2iIjku3QEwGFgesr2tOC1XsuYWREwmuRk8AXcfbW7L0tDu0REpB/pCICXgLlmNtPMSoC7gad7lHkaWBk8fx/w/GDG/0VEJHNCTwK7e4eZfRxYS3IZ6HfdvcrM/gnY5O5PA98BfmBmu4HjJENCREQiZLm6I951HkCutk9EJNd0rQLK2nkAIiIyNKXlTGARETnP3WntSNDc2kFzaydNrR20tHXQFGw3t3UE73XQ1NqZ8l4HLW3J8v91z1IqRw3LaDsVACISe+7OufbEhR11a0d3Z93UYzv1/a73WlqDz7Z10pkIN3x9sqVdASAi0pO709LWtSfdGXTQXZ13Z/feddfedlN35xx01L108iH76wuUFBZQVlpIWWkR5aVFjChJfV5EefBeWWkRZanvlSbfmz5ueHob1AsFgIhkXCLhtLSndNTBsMj5Pep+OvG2nnvjyU493etDSosKgg64kLKSZGec7KCT293Pg446+VpqJ57c7urgS4pyf4pVASAiF+hM+IVDHd0ddGrn3fd7PZ+n27DigvOd9AWdcUpHnbKdujee+tkRpYUUF+Z+h51uCgCRPNDRmXjd5OIFHXVKZ929B54yEfn6iclOzranv8PuGgLpvzPu572UPfCykiIKCy7uwmdyIQWASATaOxPdnfFAq0J6Tjaen2g8P5TS2pFIa/vMSO4Zp3TAF3TGrxu3LkwZFukxVFJaxIjiQgrUYeccBYDIIHV0Jqg7fa67Y35dZ3zBcEgvnXjKHnZbZ3o77IKgwy4bqDMe5FDJcHXYsaAAEOnhVEs7exqb2NvQzJ6GJvY2NLGnoZkDx5pp70zPzGNhgb1uuOPCzjh14jG5KmREysRk6t54eWkRw4oLLvpa8CIKAImlzoRTc6Il6OCTHf2ehmb2NjTR2NTW5+cqR5UyenhxSmfcf0edOmadOlRSWqQOW6KnAJC8dvpce7KDP9rE3sYm9hxtZm9jE/sbW/ochhleXMjMCWXMnljOrJTHWRVljCjRPxnJH/rbLENeZ8I5cvIsuxuago6+ufux4Uxrn5+bPHoYsyrKmF2R0tFXlDN51DCNf0ssKABkyGhq7QjG41PH55vZ29hMWx+rYEqLCphVUd7d0c8OHmdOKKOsVH/9Jd70L0BySiLhHD55NmUv/vywTf3pvvfmK0eVJvfku/bog85+yujh2psX6YMCQCLR3NoR7L0nh232BB3+/mPNnGvvfW++pKigeyw+tbOfOaGMkcOKs/wLRIY+BYBk1KmWdl6pOdm9lLJrj77u9Lk+P1MxspTZFWXBXnyyo59TUc6UMcN19qdIGoUKADMbBzwCzAD2A+939xM9ylwJfAsYBXQC/+Luj4SpV3Jb/elzrNtWz7qqOn635xgdvVxmsaSwgBkTRlwwbDOrooxR2psXyYpQt4Q0sy8Bx939QTO7Hxjr7p/rUWYe4O6+y8ymAJuBhe5+coDv1i0hh5B9jc2srapjbVUdLx88/7+2sMC4cvoY5lWWB5OwyU5+2tgR2psXSbOLvSVk2ADYAdzk7rVmNhl4wd3nD/CZV4D3ufuuAcopAHKYu1N15DTrqupYW1XPjvoz3e+VFhVw49wKbr1iEjcvmMjYspIIWyoSHxcbAGHnACrdvTZ4XgdU9lfYzK4BSoA9/ZRZBawK2S7JgM6Es/nACX6xtY512+qoOXG2+72Rw4q4ecFEViyexFvnV+iEKZEhYMAjADNbD0zq5a0HgIfcfUxK2RPuPraP75kMvACsdPffD9gwHQHkhNaOTn67+xhrq+p4bls9x5rPXyahYmQptyyqZMXiSVw3a/yQuAGGSD5L+xGAuy/vp7J6M5ucMgR0tI9yo4BngAcG0/lLtJpaO3hhx1HWVtXzy+1HaWrt6H7v8vEjWLF4EisWV7Jk+litsRcZwsIepz8NrAQeDB6f6lnAzEqAJ4CH3f3RkPVJhhxramV9dT1rq+r5ze7G151Zu3DyKFYsTu7pL5g0UhcxE8kTYSeBxwM/BS4DDpBcBnrczJYBH3H3D5vZPcD3gKqUj97r7lsG+G4NAWXY4ZNnWbs1uXLnpf3Hu2+KbQZLLxvLrVdM4h2LJnHZ+BHRNlREBiWrq4AySQGQOQeONfOVdTv52StHul8rLjSunz2BFYsnsXzRRCaOHBZhC0XkUmR7FZAMIY1Nrfznhl386MWDdCSckqICli9Mrtx524KJOgFLJGYUADHQ1NrBtzfuZc2v99Lc1kmBwV1Lp/GpW+YxdczwqJsnIhFRAOSxto4EP/7DQf5jw67u5ZvLF07k71csYP6kkRG3TkSipgDIQ4mE87NXj/DVdTs5eLwFgKsuG8P9ty3kmpnjIm6diOQKBUCe+fWuBh787+1UHTkNwJyJ5Xx2xXxuWVSp5Zsi8joKgDzxWs0p/vUX2/nN7kYAJo0axt/dMpc/u2oaRYU6Q1dELqQAGOL2NzbzlXU7+PmryUsyjRpWxEdvmsO9189geElhxK0TkVymABiiOhPOV9ftYPXGvd1LOu+7fgYfvWk2Y0bo6psiMjAFwBB0qqWdT/zkZTbubKDA4P3LpvGp5fOYoiWdInIRFABDzO6jTfzPhzexr7GZcWUlfOuDV/GmWeOjbpaIDEEKgCHk+e31fPLHWzjT2sHCyaP49l8tZdpYXadHRC6NAmAIcHe+9as9fHntDtzhnX8ymS/f9QbddEVEQlEPkuPOtnXy2cde7b5w22feMY+PvW2O1vSLSGgKgBx2+ORZVj28iaojpykrKeRrdy/hlkX93nVTRGTQFAA56qX9x/noDzfT2NTG5eNH8O2/Wsa8Sl2/R0TSRwGQgx556SBffHIr7Z3Om+dM4Bt/sURr+0Uk7UJfI8DMxpnZc2a2K3js9abwQdlRZlZjZt8IW2++emxzDZ977DXaO53/ccNMvn/f1er8RSQj0nGRmPuBDe4+F9gQbPfln4GNaagzL/2/3Y187rFXAfjiOxfyv/50ka7jIyIZk47e5Q7goeD5Q8B7eitkZkuBSmBdGurMOzvqzvCRH2ymI+F8+M0z+fCNs6JukojkuXQEQKW71wbP60h28q9jZgXAV4HPpKG+vFN36hz3fu8PnGnt4LYrJvGF2xdG3SQRiYFBTQKb2XpgUi9vPZC64e7edTP3Hv4GeNbdawZav25mq4BVg2lXPmhq7eC+779E7alzLL18LP/+51dSUKA1/iKSeebeW399EV9gtgO4yd1rzWwy8IK7z+9R5kfAjUACKAdKgP/r7n3OF3QFSdj25bL2zgQfemgTG3c2MHNCGY999HrGlWnCV0QuTdcOtrsPai8yHctAnwZWAg8Gj0/1LODuH0xp4L3Asv46/zhwd774xFY27mxgfFkJ37/vanX+IpJV6ZgDeBC4xcx2AcuDbcxsmZmtScP356VvPL+bRzYdYlhxAWtWLuPy8WVRN0lEYib0EFCm5PMQ0NqqOv76B5sxg/+6ZykrFvc2vSIicnEudghIi8yz7ERzGw888RoAn79tgTp/EYmMAiDL/vFnVTQ2tXHNzHF8+M1a6y8i0VEAZNFz2+p5cssRhhUX8KU/e4OWe4pIpBQAWXKypY0vBEM/f79iATMmaNJXRKKlAMiSf/r5NhrOtLL08rHce/2MqJsjIqIAyIbnt9fz+B8PU1pUwJfe9wYKNfQjIjlAAZBhp86284XHtwLw6XfMY3ZFecQtEhFJUgBk2P95tpq60+e4cvoYPqRVPyKSQxQAGbSj7gyPbDpEcaHxZQ39iEiOUQBk0FfX7cAdPnDNZczV/XxFJMcoADJky6GTrNtWz7DiAj7+tjlRN0dE5AIKgAz56rodANx7/UwmjhoWcWtERC6kAMiA3+5p5Ne7GhlZWsRH3qqJXxHJTQqANHN3vrI2ufe/6i2zGDNC1/gXkdykAEiz57cf5Y8HTzKurIT73jwz6uaIiPRJAZBGiYTzlXU7Afibm2ZTXpqOG66JiGSGAiCNfrWzgera00waNYx7rr086uaIiPQrVACY2Tgze87MdgWPY/sod5mZrTOzajPbZmYzwtSbq7732/0A3HvDDIYVF0bbGBGRAYQ9Argf2ODuc4ENwXZvHga+7O4LgWuAoyHrzTl7GprYuLOBYcUF3H319KibIyIyoLABcAfwUPD8IeA9PQuY2SKgyN2fA3D3JndvCVlvznk42Pt/z5VTtfJHRIaEsAFQ6e61wfM6oLKXMvOAk2b2uJm9bGZfNrM+x0fMbJWZbQrZrqw6c66dRzfXALBS1/oXkSFiwGUqZrYe6O3O5Q+kbri7m5n3UceNwBLgIPAIcC/wnd7qc/fVwOo+visnPbq5hua2Tq6dNY6Fk0dF3RwRkUEZMADcfXlf75lZvZlNdvdaM5tM72P7NcAWd98bfOZJ4Fr6CIChJpFwHv7dAQDd6UtEhpSwQ0BPAyuD5yuBp3op8xIwxswqgu23A9tC1pszfrWrgX2NzUwdM5zlC3sbARMRyU1hA+BB4BYz2wUsD7Yxs2VmtgbA3TuBzwAbzOw1wIBvh6w3Z/zkDwcB+OC1l1FUqNMqRGToMPfcHGrvmgPI1fYBnGxp4+p/WU9nwvn952/WVT9FJFJmyZtOufug7j6lXdYQnnmtlvZO54Y5E9T5i8iQowAI4Yk/HgbgziVTI26JiMjFUwBcooPHWth04ATDiwtZsbi3VbIiIrlNAXCJntyS3PtfsbiSMl31U0SGIAXAJXB3nnw5GP65alrErRERuTQKgEvwas0p9jY2M6G8lBtmj4+6OSIil0QBcAme3Zq8/NG73jBZa/9FZMhS73WR3J11VfUA3HqFJn9FZOhSAFykPQ1N7GtsZuyIYpZd3uv9b0REhgQFwEVaG+z937ywUsM/IjKkqQe7SOuq6gB4xyJd+E1EhjYFwEWoPXWWV2pOMay4gBvnVgz8ARGRHKYAuAjrtyWHf94yt4LhJbrpu4gMbQqAi/BcdfJ+N+/QpR9EJA8oAAbpXHsnL+49BsBN8zX8IyJDnwJgkP6w7zitHQkWTxnFhPLSqJsjIhJa6AAws3Fm9pyZ7Qoee10cb2ZfMrMqM6s2s/+wrjsXDBEbdzYA8JZ52vsXkfyQjiOA+4EN7j4X2BBsv46ZXQ/cALwBuAK4GnhrGurOmo27ggDQ6h8RyRPpCIA7gIeC5w8B7+mljAPDgBKgFCgG6tNQd1bUnjrLzvomykoKWaqzf0UkT6QjACrdvTZ4XgdccIaUu/8O+CVQG/xZ6+7Vaag7K369sxGA62aPp6RI0yYikh8GdScTM1sP9Lb28YHUDXf3rpu59/j8HGAh0HXx/OfM7EZ3/3UvZVcBqwbTrmzpHv7R+L+I5JFBBYC7L+/rPTOrN7PJ7l5rZpOBo70UuxP4vbs3BZ/5b+A64IIAcPfVwOregiQK7s7v9x4H4PrZEyJujYhI+qRjPONpYGXwfCXwVC9lDgJvNbMiMysmOQE8JIaA9jQ009jUyoTyUmZXlEXdHBGRtElHADwI3GJmu4DlwTZmtszM1gRlHgX2AK8BrwCvuPvP0lB3xv0+OPnr2lnjGGIrV0VE+hX6bubufgy4uZfXNwEfDp53An8dtq4onA8A3fpRRPKLlrT0I3X8XwEgIvlGAdAPjf+LSD5TAPTjD/uSe/9v0vi/iOQhBUA/Nh1IBsDVOvtXRPKQAqAfmw+cAGDZjHERt0REJP0UAH1oONPKgWMtjCgpZMGkkVE3R0Qk7RQAfeja+79y+hiKCvWfSUTyj3q2PmwOxv+XafxfRPKUAqAPXUcAVykARCRPKQB60daRYOuR0wAsma4AEJH8pADoxY66M7R1JJhVUcboEcVRN0dEJCMUAL3YciiYAJ42JuKWiIhkjgKgF1sOnQLgyssUACKSvxQAveg6AnijjgBEJI8pAHo4fa6dPQ3NlBQWsHDyqKibIyKSMQqAHrYeTg7/LJw8UjeAF5G8FqqHM7O7zKzKzBJmtqyfcrea2Q4z221m94epM9O6AuBPpo2OuCUiIpkVdhd3K/BeYGNfBcysEPgmcBuwCPiAmS0KWW/GvFoTBMBUBYCI5LdQt4R092pgoGvlXwPsdve9QdmfAHcA28LUnSldRwBXKABEJM9lY5B7KnAoZbsmeC3nnD7Xzv5jLZQUFTCvUlcAFZH8NuARgJmtByb18tYD7v5UuhtkZquAVen+3sE4PwE8imJdAVRE8tyAAeDuy0PWcRiYnrI9LXitr/pWA6vNzEPWe9G2Bdf/WTxFyz9FJP9lYzf3JWCumc00sxLgbuDpLNR70aoUACISI2GXgd5pZjXAdcAzZrY2eH2KmT0L4O4dwMeBtUA18FN3rwrX7MyoOpIcAlo8RRPAIpL/zD3rIy2D0jUElK32nWvvZPE/rMXdqfrHWxleUpiVekVE0qVrRaa797s0s4tmOgM76s7QmXBmVZSr8xeRWFAABKprk+P/i3T9HxGJCQVAoCsAdAE4EYkLBUCguvYMkLwInIhIHCgASE40V9dpCEhE4kUBABw+eZYz5zoYX1ZCxcjSqJsjIpIVCgBgezD8s2DyyIEubCcikjcUAMCO+mQAzK/U8I+IxIcCgPMrgBZoAlhEYkQBQPIkMIAFkxQAIhIfsQ+A1o5O9jY2YwZzJyoARCQ+Yh8Aexua6Uw4M8aX6RIQIhIrsQ+AncEE8LzK8ohbIiKSXbEPgK7x//m6BaSIxEzsA6DrCGCuAkBEYkYBUN8EwHytABKRmIl1ALS0dXDweAvFhcaM8WVRN0dEJKvC3hLyLjOrMrOEmS3ro8x0M/ulmW0Lyn4yTJ3ptPtocu9/5oQySopinYUiEkNhe72twHuBjf2U6QA+7e6LgGuBj5nZopD1pkXX8I/G/0UkjorCfNjdq4F+L6Dm7rVAbfD8jJlVA1OBbWHqToddR4MloDoBTERiKKvjHmY2A1gCvNhPmVVmtikb7dkVHAHoHAARiaMBjwDMbD0wqZe3HnD3pwZbkZmVA48Bn3L3032Vc/fVwGoz88F+96XqOgKYqwAQkRgaMADcfXnYSsysmGTn/yN3fzzs96VDS1sHNSfOUlxoXK4VQCISQxkfArLkBMF3gGp3/7dM1zdYe442455cAVRcqBVAIhI/YZeB3mlmNcB1wDNmtjZ4fYqZPRsUuwH4S+DtZrYl+HN7qFanQffwjyaARSSmwq4CegJ4opfXjwC3B89/A+TcfRZ3BecAzJ6o8X8RiafYjn1oBZCIxF1sA2BPQ3ASmIaARCSmYhkA59o7OXCsmQKDGRNGRN0cEZFIxDIA9jU2k3CYMb6M0iLdBUxE4imWAbBbE8AiIvEMgK4VQHMUACISY7EMgD1HuyaAFQAiEl+xDIDdR7UCSEQkdgHQ0ZlgX2MzALMqdA0gEYmv2AXAgeMttHUmmDpmOGWloU6EFhEZ0mIXAFoBJCKSFNsA0ASwiMRd7AJgV33XVUAVACISb7ELgN0NOgdARARiFgCJhLPnaHIFkJaAikjcxSoADp88y9n2TiaUlzJ6RHHUzRERiVTYO4LdZWZVZpYws2UDlC00s5fN7Odh6gxDE8AiIueFPQLYCrwX2DiIsp8EqkPWF0rXbSA1/i8iEjIA3L3a3XcMVM7MpgHvBNaEqS8s3QVMROS8bM0BfA34LJDIUn29Or8CSBPAIiIDBoCZrTezrb38uWMwFZjZu4Cj7r55kOVXmdmmwZS9GO7Obh0BiIh0G/BiOO6+PGQdNwDvNrPbgWHAKDP7obvf00d9q4HVZuYh632dutPnONPawdgRxYwvL03nV4uIDEkZHwJy98+7+zR3nwHcDTzfV+efSTuDvf+5lRr+ERGB8MtA7zSzGuA64BkzWxu8PsXMnk1HA9Ol6xIQGv4REUkKdT1kd38CeKKX148At/fy+gvAC2HqvFQ76roCQEcAIiIQozOBdx7tmgBWAIiIQEwCIJHwlCEgBYCICMQkAA6fPEtLW/IaQOPKSqJujohITohFAGwPxv8XTNLev4hIl1gEwI660wDMVwCIiHSLRQBU6whAROQCsQiA7bXJI4CFk0dF3BIRkdyR9wFwtq2TfY3NFBaYLgMtIpIi7wNgR/0ZEg6zK8oYVlwYdXNERHJG3gdA1ZFTACyeMjriloiI5Ja8D4Cth5Pj/4unaPxfRCRVDAIgeQRwxVQdAYiIpMrrADjX3sn2utOYKQBERHrK6wCoOnKa9k5n7sRyyktDXfhURCTv5HUAvHzwBABLpo+NuCUiIrknrwPgpf3HAVg6QwEgItJT3gZAZ8J5cV8yAN40c1zErRERyT1hbwl5l5lVmVnCzJb1U26MmT1qZtvNrNrMrgtT72BsPXyKky3tTB0znMvGjch0dSIiQ07YI4CtwHuBjQOU+zrwC3dfALwRqA5Z74DWV9cD8LYFFZhZpqsTERlywt4TuBrot4M1s9HAW4B7g8+0AW1h6h1IIuE8ueUwALddMTmTVYmIDFnZmAOYCTQA3zOzl81sjZmV9VXYzFaZ2aYwFf7s1SMcOn6WqWOGc+2s8WG+SkQkbw0YAGa23sy29vLnjkHWUQRcBXzL3ZcAzcD9fRV299Xu3ud8wkB+tbOB+x97DYBPvH0OhQUa/hER6c2AQ0DuvjxkHTVAjbu/GGw/Sj8BENa8ynJGlBTy7jdO4f3LpmeqGhGRIS/jp8e6e52ZHTKz+e6+A7gZ2Jap+iaPHs4zf3sjlaNKNfkrItIPc/dL/7DZncB/AhXASWCLu68wsynAGne/PSh3JbAGKAH2Ave5+4kBvtsBwrRPRCROunZ63X1Qe7+hAiCTFAAiIhfnYgMgb88EFhGR/ikARERiSgEgIhJTCgARkZhSAIiIxFTO3yZLa/lFRDJDRwAiIjGVs+cBXAoz2xTmOkJDURx/M8Tzd8fxN0M8f3e2frOOAEREYkoBICISU/kWAKujbkAE4vibIZ6/O46/GeL5u7Pym/NqDkBERAYv344ARERkkPIiAMzsVjPbYWa7zSxjN5vJJWY23cx+aWbbzKzKzD4ZdZuyxcwKg9uL/jzqtmSLmY0xs0fNbLuZVZvZdVG3KdPM7O+Cv9tbzezHZjYs6jZlgpl918yOmtnWlNfGmdlzZrYreBybibqHfACYWSHwTeA2YBHwATNbFG2rsqID+LS7LwKuBT4Wk98N8EmgOupGZNnXgV+4+wLgjeT57zezqcDfAsvc/QqgELg72lZlzPeBW3u8dj+wwd3nAhvI0F0Uh3wAANcAu919r7u3AT8BBnu/4iHL3Wvd/Y/B8zMkO4Sp0bYq88xsGvBOkjcYigUzGw28BfgOgLu3ufvJaFuVFUXAcDMrAkYARyJuT0a4+0bgeI+X7wAeCp4/BLwnE3XnQwBMBQ6lbNcQg44wlZnNAJYAL/ZfMi98DfgskIi6IVk0E2gAvhcMfa0xs7KoG5VJ7n4Y+ApwEKgFTrn7umhblVWV7l4bPK8DKjNRST4EQKyZWTnwGPApdz8ddXsyyczeBRx1981RtyXLioCrgG+5+xKgmQwNCeSKYMz7DpLhNwUoM7N7om1VNDy5VDMjyzXzIQAOA9NTtqcFr+U9Mysm2fn/yN0fj7o9WXAD8G4z209yqO/tZvbDaJuUFTVAjbt3HeE9SjIQ8tlyYJ+7N7h7O/A4cH3EbcqmejObDBA8Hs1EJfkQAC8Bc81sppmVkJwoejriNmWcJS+T+h2g2t3/Ler2ZIO7f97dp7n7DJL/n59397zfK3T3OuCQmc0PXroZ2BZhk7LhIHCtmY0I/q7fTJ5PfPfwNLAyeL4SeCoTleT85aAH4u4dZvZxYC3JlQLfdfeqiJuVDTcAfwm8ZmZbgte+4O7PRtgmyZxPAD8KdnL2AvdF3J6McvcXzexR4I8kV7y9TJ6eEWxmPwZuAiaYWQ3wD8CDwE/N7EPAAeD9GalbZwKLiMRTPgwBiYjIJVAAiIjElAJARCSmFAAiIjGlABARiSkFgIhITCkARERiSgEgIhJT/x8DAurxnHYr6wAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from matplotlib import pyplot\n",
    "pyplot.rcParams['axes.linewidth'] = 2 #set the value globally\n",
    "%matplotlib inline\n",
    "\n",
    "Beta = np.arange(0.1,10,0.1)\n",
    "et = np.copy(Beta)\n",
    "n = 0\n",
    "for x in Beta:\n",
    "    p = np.exp(-w*x)\n",
    "    z = np.sum(p)\n",
    "    et[n] = np.dot(w,p)/z\n",
    "    print (x,et[n])    \n",
    "    n+=1\n",
    "\n",
    "pyplot.plot(1/Beta,et,lw=2);\n",
    "     \n",
    "    \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Challenge 12.1:\n",
    "\n",
    "Compute the energy and specific heat of the spin chain with $L=12$ as a function of temperature, for $T < 4$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A practical exact diagonalization algorithm\n",
    "\n",
    "1. Initialization: Topology of the lattice, neighbors, and signs. \n",
    "2. Contruction of a basis suitable for the problem. \n",
    "3. Constuction of the matrix element of the Hamiltonian. \n",
    "4. Diagonalization of the matrix. \n",
    "5. Calculation of observables or expectation values.\n",
    "\n",
    "As we shall see below, we are going to need the concept of “binary\n",
    "word”. A binary word is the binary representation of an integer (in\n",
    "powers of ‘two’, i.e. $n=\\sum_{i}b_{i}.2^{i}$), and consist of a\n",
    "sequence of ‘bits’. A bit $b_{i}$ in the binary basis correspond to our\n",
    "digits in the decimal system, and can assumme the values ‘zero’ or\n",
    "‘one’. At this stage we consider appropriate to introduce the logical\n",
    "operators `AND, OR, XOR`. The binary operators act between bits and\n",
    "their multiplication tables are listed below\n",
    "\n",
    "**AND** | 0 | 1\n",
    ":---:|:---:|:---:\n",
    "**0** | 0 | 0\n",
    "**1** | 0 | 1\n",
    "\n",
    "**OR** | 0 | 1\n",
    ":---:|:---:|:---:\n",
    "**0** | 0 | 1\n",
    "**1** | 1 | 1\n",
    "\n",
    "**XOR** | 0 | 1\n",
    ":---:|:---:|:---:\n",
    "**0** | 0 | 1\n",
    "**1** | 1 | 0\n",
    "\n",
    "\n",
    "The bit manipulation is a very useful tool, and most of the programming\n",
    "languages provide the needed commands.\n",
    "\n",
    "## Initilalization and definitions\n",
    "\n",
    "In the program, it is convenient to store in arrays all those quantities\n",
    "that will be used more frequently. In particular, we must determine the\n",
    "topology of the cluster, labeling the sites, and storing the components\n",
    "of the lattice vectors. We must also generate arrays with the nearest\n",
    "neighbors, and the next-nearest neighbors, according to our needs.\n",
    "\n",
    "## Construction of the basis\n",
    "\n",
    "Memory limitations impose severe restrictions on the size of the\n",
    "clusters that can be studied with this method. To understand this point,\n",
    "note that although the lowest energy state can be written in the\n",
    "$\\{|\\phi\n",
    "_{n}\\rangle \\}$ basis as\n",
    "$|\\psi _{0}\\rangle =\\sum_{m}c_{m}|\\phi _{m}\\rangle $, this expression is\n",
    "of no practical use unless $|\\phi _{m}\\rangle $ itself is expressed in a\n",
    "convenient basis to which the Hamiltonian can be easily applied. A\n",
    "natural orthonormal basis for fermion systems is the occupation number\n",
    "representation, describing all the possible distributions of $N_{e}$\n",
    "electrons over $N$ sites, while for spin systems it is covenient to work\n",
    "in a basis where the $S_{z}$ is defined at every site, schematically\n",
    "represented as $|n\\rangle =|\\uparrow \\downarrow \\uparrow ...\\rangle $.\n",
    "The size of this type of basis set\n",
    "grows exponentially with the system size. In practice this problem can be\n",
    "considerably alleviated by the use of symmetries of the Hamiltonian that\n",
    "reduces the matrix to a block-form. The most obvious symmetry is the\n",
    "number of particles in the problem which is usually conserved at least\n",
    "for fermionic problems. The total projection of the spin\n",
    "$S_{total}^{z}$, is also a good quantum number. For translationally\n",
    "invariant problems, the total momentum $\\mathbf{k%\n",
    "}$ of the system is also conserved introducing a reduction of $1/N$ in\n",
    "the number of states (this does not hold for models with open boundary\n",
    "conditions or explicit disorder). In addition, several Hamiltonians have\n",
    "additional symmetries. On a square lattice, rotations in $\\pi /2$ about\n",
    "a given site, spin inversion, and reflections with respect to the\n",
    "lattice axis are good quantum numbers (although care must be taken in\n",
    "their implementation since some of these operations are combinations of\n",
    "others and thus not independent). \n",
    "\n",
    "In the following we shall consider a spin-1/2 Heisenberg chain as a\n",
    "practical example. In this model it is useful to represent the spins\n",
    "pointing in the ‘up’ direction by a digit ‘1’, and the down-spins by a\n",
    "‘0’. Following this rule, a state in the $S^{z}$ basis can be\n",
    "represented by a sequence of ones and zeroes, i.e., a “binary word”.\n",
    "Thus, two Néel configurations in the 4-site chain can be seen as\n",
    "$$\\begin{aligned}\n",
    "\\mid \\uparrow \\downarrow \\uparrow \\downarrow \\rangle \\equiv |1010\\rangle , \\\\\n",
    "\\mid \\downarrow \\uparrow \\downarrow \\uparrow \\rangle \\equiv |0101\\rangle .\\end{aligned}$$\n",
    "Once the up-spins have been placed the whole configuration has been\n",
    "uniquely determined since the remaining sites can only be occupied by\n",
    "down-spins. The resulting binary number can be easily converted into\n",
    "integers $i\\equiv\n",
    "\\sum_{l}b_{l}.2^{l}$, where the summation is over all the sites of the\n",
    "lattice, and $b_{l}$ can be $1$ or $0$. For example:\n",
    "$$\\begin{array}{lllll}\n",
    "2^{3} & 2^{2} & 2^{1} & 2^{0} &  \\\\\n",
    "1 & 0 & 1 & 0 & \\rightarrow 2^{1}+2^{3}=10, \\\\\n",
    "0 & 1 & 0 & 1 & \\rightarrow 2^{0}+2^{2}=5.\n",
    "\\end{array}$$\n",
    "\n",
    "Using the above convention, we can construct the whole basis for the\n",
    "given problem. However, we must consider the memory limitations of our\n",
    "computer, introducing some symetries to make the problem more tractable.\n",
    "The symetries are operations that commute with the Hamiltonian, allowing\n",
    "us to divide the basis in subspaces with well defined quantum numbers.\n",
    "By means of similarity transformations we can generate a sequence of\n",
    "smaller matrices along the diagonal (i.e. the Hamiltonian matrix is\n",
    "“block diagonal”), and each of them can be diagonalized independently.\n",
    "For fermionic systems, the simplest symmetries are associated to the\n",
    "conservation of the number of particles and the projection\n",
    "$S_{total}^{z}$ of the total spin in the $z$ direction. In the spin-1/2\n",
    "Heisenberg model, a matrix with $2^{N}\\times 2^{N}$ elements can be\n",
    "reduced to $2S+1$ smaller matrices, corresponding to the projections $%\n",
    "m=(N_{\\uparrow }-N_{\\downarrow })/2=-S,-S+1,...,S-1,S$, with $S=N/2$.\n",
    "\n",
    "The dimension of each of these subspaces is obtained from the\n",
    "combinatory number $\\left(\n",
    "\\begin{array}{c}\n",
    "N \\\\\n",
    "N_{\\uparrow }\n",
    "\\end{array}\n",
    "\\right) = \\frac{N!}{N_{\\uparrow }!N_{\\downarrow }!}$.\n",
    "\n",
    "#### Example: 4-site Heisenberg chain\n",
    "\n",
    "The total basis has\n",
    "$2^{4}=16$ states that can be grouped in\n",
    "$4+1=5$ subspaces with well defined values of the quantum\n",
    "number $m=S^z$. The dimensions of these subspaces are:\n",
    "\n",
    " m | dimension \n",
    ":--:|:--:\n",
    "-2 | 1 \n",
    "-1 | 4 \n",
    "0 | 6 \n",
    "2 | 4 \n",
    "1 | 1 \n",
    " \n",
    "Since we know that the ground state of the Hilbert\n",
    "chain is a singlet, we are only interested in the subspace with\n",
    "</span>$S_{total}^{z}=m=0$<span>. For our example, this subspace is\n",
    "given by (in increasing order): </span> \n",
    "$$\\begin{eqnarray}\n",
    "\\mid \\downarrow \\downarrow \\uparrow \\uparrow \\rangle & \\equiv &|0011\\rangle\n",
    "\\equiv |3\\rangle , \\\\\n",
    "\\mid \\downarrow \\uparrow \\downarrow \\uparrow \\rangle &\\equiv &|0101\\rangle\n",
    "\\equiv |5\\rangle , \\\\\n",
    "\\mid \\downarrow \\uparrow \\uparrow \\downarrow \\rangle &\\equiv &|0110\\rangle\n",
    "\\equiv |6\\rangle , \\\\\n",
    "\\mid \\uparrow \\downarrow \\downarrow \\uparrow \\rangle &\\equiv &|1001\\rangle\n",
    "\\equiv |9\\rangle , \\\\\n",
    "\\mid \\uparrow \\downarrow \\uparrow \\downarrow \\rangle &\\equiv &|1010\\rangle\n",
    "\\equiv |10\\rangle , \\\\\n",
    "\\mid \\uparrow \\uparrow \\downarrow \\downarrow \\rangle &\\equiv &|1010\\rangle\n",
    "\\equiv |12\\rangle .\n",
    "\\end{eqnarray}\n",
    "$$\n",
    "\n",
    "Generating the possible configurations of $N$ up-spins (or\n",
    "spinless fermions) in $L$ sites is equivalent to the problem of\n",
    "generating the corresponding combinations of zeroes and ones in\n",
    "lexicographic order.\n",
    "\n",
    "## Construction of the Hamiltonian matrix elements\n",
    "\n",
    "We now have to address the problem of generating all the Hamiltonian matrix elements\n",
    ". These are obtained by the application of the\n",
    "Hamiltonian on each state of the basis $|\\phi \\rangle $, generating all\n",
    "the values\n",
    "$H_{\\phi ,\\phi ^{\\prime }}=\\langle \\phi ^{\\prime }|{{\\hat{H}}}%\n",
    "|\\phi \\rangle $. We illustrate this procedure in the following\n",
    "pseudocode:\n",
    "\n",
    "&ensp;&ensp;&ensp;&ensp;**for** each term ${\\hat{H}_i}$ of the Hamiltonian ${\\hat{H}}$\n",
    "\n",
    "&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;**for** all the states $|\\phi\\rangle $ in the basis\n",
    "\n",
    "&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;$\\hat{H}_i|\\phi\\rangle = \\langle \\phi^{\\prime }|{\\hat{H}_i}|\\phi\\rangle |\\phi^{\\prime }\\rangle  $ \n",
    "\n",
    "&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;\n",
    "$H_{\\phi,\\phi^{\\prime }}=H_{\\phi,\\phi^{\\prime }} + \\langle \\phi^{\\prime }|{\\hat{H}_i}|\\phi\\rangle $\n",
    "\n",
    "&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;**end for**\n",
    "\n",
    "&ensp;&ensp;&ensp;&ensp;**end for**\n",
    "\n",
    "As the states are representated by binary words, the spin operators (as\n",
    "well as the creation and destructions operators) can be be easily\n",
    "implemented using the logical operators `AND, OR, XOR`.\n",
    "\n",
    "As a practical example let us consider the spin-1/2 Heisenberg\n",
    "Hamiltonian on the 4-sites chain:\n",
    "$${{\\hat{H}}}=J\\sum_{i=0}^{3}\\mathbf{S}_{i}.\\mathbf{S}_{i+1}=J%\n",
    "\\sum_{i=0}^{3}S_{i}^{z}.S_{i+1}^{z}+\\frac{J}{2}%\n",
    "\\sum_{i=0}^{3}(S_{i}^{+}S_{i+1}^{-}+S_{i}^{-}S_{i+1}^{+}), $$\n",
    "\n",
    "with $\\mathbf{S}_{4}=\\mathbf{S}_{0}$, due to the periodic boundary\n",
    "conditions. To evaluate the matrix elements in the basis (\\[basis0\\]) we\n",
    "must apply each term of ${{\\hat{H}}}$ on such states. The first term is\n",
    "called Ising term, and is diagonal in this basis (also called Ising\n",
    "basis). The last terms, or fluctuation terms, give strictly off-diagonal\n",
    "contributions to the matrix in this representation (when symmetries are\n",
    "considered, they can also have diagonal contributions). These\n",
    "fluctuations cause an exchange in the spin orientation between neighbors\n",
    "with opposite spins, e.g. $\\uparrow \\downarrow \\rightarrow $\n",
    "$\\downarrow \\uparrow $. The way to implement spin-flip operations of\n",
    "this kind on the computer is defining new ‘masks’. A mask for this\n",
    "operation is a binary number with ‘zeroes’ everywhere, except in the\n",
    "positions of the spins to be flipped, e.g 00..0110...00. Then, the\n",
    "logical operator `XOR` is used between the initial state and the mask to\n",
    "invert the bits (spins) at the positions indicated by the mask. For\n",
    "example, (0101)$\\mathtt{.}$`XOR.`(1100)=(1001), i.e., 5`.XOR.`12=9. It\n",
    "is useful to store all the masks for a given geometry in memory,\n",
    "generating them immediately after the tables for the sites and neighbors.\n",
    "\n",
    "<span>In the Heisenberg model the spin flips can be implemented using\n",
    "masks, with ‘zeroes’ everywhere, except in the positions of the spins to\n",
    "be flipped. To illustrate this let us show the effect of the\n",
    "off-diagonal terms on one of the Néel configurations:</span>\n",
    "$$\\begin{eqnarray}\n",
    "S_{0}^{+}S_{1}^{-}\\,+S_{0}^{-}S_{1}^{+}\\,|0101\\rangle &\\equiv &(0011)\\mathtt{%\n",
    ".XOR.}(0101)=3\\mathtt{.XOR.}5=(0110)=6\\equiv \\,|0110\\rangle , \\\\\n",
    "S_{1}^{+}S_{2}^{-}+S_{1}^{-}S_{2}^{+}\\,\\,|0101\\rangle &\\equiv &(0110)\\mathtt{%\n",
    ".XOR.}(0101)=6\\mathtt{.XOR.}5=(0011)=3\\equiv \\,|0011\\rangle , \\\\\n",
    "S_{2}^{+}S_{3}^{-}+S_{2}^{-}S_{3}^{+}\\,\\,|0101\\rangle &\\equiv &(1100)\\mathtt{%\n",
    ".XOR.}(0101)=12\\mathtt{.XOR.}5=(1001)=9\\equiv \\,|1001\\rangle , \\\\\n",
    "S_{3}^{+}S_{0}^{-}\\,+S_{3}^{-}S_{0}^{+}|0101\\rangle &\\equiv &(1001)\\mathtt{%\n",
    ".XOR.}(0101)=9\\mathtt{.XOR.}5=(1100)=12\\equiv \\,|1100\\rangle .%\n",
    "\\end{eqnarray}$$\n",
    "\n",
    "<span>After applying the Hamiltonian (\\[h4\\]) on our basis states, the\n",
    "reader can verify as an exercise that we obtain </span>\n",
    "$$\\begin{eqnarray}\n",
    "{{\\hat{H}}}\\,|0101\\rangle &=&-J\\,|0101\\rangle +\\frac{J}{2}\\left[\n",
    "\\,|1100\\rangle +\\,|1001\\rangle +\\,|0011\\rangle +\\,|0110\\rangle \\right] , \\\\\n",
    "{{\\hat{H}}}\\,|1010\\rangle &=&-J\\,|1010\\rangle +\\frac{J}{2}\\left[\n",
    "\\,|1100\\rangle +\\,|1001\\rangle +\\,|0011\\rangle +\\,|0110\\rangle \\right] , \\\\\n",
    "{{\\hat{H}}}\\,|0011\\rangle &=&\\frac{J}{2}\\left[ \\,\\,|0101\\rangle\n",
    "+\\,|1010\\rangle \\right] , \\\\\n",
    "{{\\hat{H}}}\\,|0110\\rangle &=&\\frac{J}{2}\\left[ \\,\\,|0101\\rangle\n",
    "+\\,|1010\\rangle \\right] , \\\\\n",
    "{{\\hat{H}}}\\,|1001\\rangle &=&\\frac{J}{2}\\left[ \\,|0101\\rangle +\\,|1010\\rangle\n",
    "\\right] , \\\\\n",
    "{{\\hat{H}}}\\,|1100\\rangle &=&\\frac{J}{2}\\left[ \\,|0101\\rangle +\\,|1010\\rangle\n",
    "\\right] .%\n",
    "\\end{eqnarray}$$\n",
    "\n",
    "<span>The resulting matrix for the operator </span>$\\hat{H}$<span>in the\n",
    "</span>$S^{z}$<span> representation is: </span> $$H=J\\left(\n",
    "\\begin{array}{llllll}\n",
    "0 & 1/2 & 0 & 0 & 1/2 & 0 \\\\\n",
    "1/2 & -1 & 1/2 & 1/2 & 0 & 1/2 \\\\\n",
    "0 & 1/2 & 0 & 0 & 1/2 & 0 \\\\\n",
    "0 & 1/2 & 0 & 0 & 1/2 & 0 \\\\\n",
    "1/2 & 0 & 1/2 & 1/2 & -1 & 1/2 \\\\\n",
    "0 & 1/2 & 0 & 0 & 1/2 & 0\n",
    "\\end{array}\n",
    "\\right) .  $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Basis:\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]\n",
      "[[ 1.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.5  0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.5  0.   0.   0.5  0.   0.   0.   0.   0.   0.   0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.5  0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.5  0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.5  0.  -1.   0.5  0.   0.   0.5  0.   0.   0.5  0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.5  0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.5  0.   0.\n",
      "   0.5  0. ]\n",
      " [ 0.   0.5  0.   0.   0.5  0.   0.   0.   0.   0.   0.   0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.5  0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.5  0.   0.   0.5  0.   0.   0.5 -1.   0.   0.5  0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.   0.5\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.5  0.   0.   0.\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.5  0.   0.\n",
      "   0.5  0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.   0.   0.5  0.   0.   0.   0.   0.   0.5\n",
      "   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.   0.\n",
      "   0.   1. ]]\n",
      "===================================================================================================================\n",
      "[-2.00000000e+00 -1.00000000e+00 -1.00000000e+00 -1.00000000e+00\n",
      " -2.25514052e-17 -1.78638187e-17 -7.68015095e-32  0.00000000e+00\n",
      "  2.42866341e-47  6.17036833e-34  1.31651255e-31  1.00000000e+00\n",
      "  1.00000000e+00  1.00000000e+00  1.00000000e+00  1.00000000e+00]\n",
      "[ 0.          0.          0.         -0.28867513  0.          0.57735027\n",
      " -0.28867513  0.          0.         -0.28867513  0.57735027  0.\n",
      " -0.28867513  0.          0.          0.        ]\n"
     ]
    }
   ],
   "source": [
    "class BoundaryCondition:\n",
    "    RBC, PBC = range(2)\n",
    "\n",
    "class Direction:\n",
    "    RIGHT, TOP, LEFT, BOTTOM = range(4)\n",
    "    \n",
    "L = 4\n",
    "Nup = 2\n",
    "maxdim = 2**L\n",
    "bc = BoundaryCondition.PBC\n",
    "\n",
    "#  Tables for energy\n",
    "\n",
    "hdiag = np.zeros(4) # Diagonal energies\n",
    "hflip = np.zeros(4) # off-diagonal terms\n",
    "\n",
    "hdiag[0] = +0.25\n",
    "hdiag[1] = -0.25\n",
    "hdiag[2] = -0.25\n",
    "hdiag[3] = +0.25\n",
    "\n",
    "hflip[0] = 0.\n",
    "hflip[1] = 0.5\n",
    "hflip[2] = 0.5\n",
    "hflip[3] = 0.\n",
    "\n",
    "#hflip *= 2\n",
    "#hdiag *= 0.\n",
    "\n",
    "# Lattice geometry  (1D chain)\n",
    "\n",
    "nn = np.zeros(shape=(L,4), dtype=np.int16)\n",
    "for i in range(L):\n",
    "    nn[i, Direction.RIGHT] = i-1\n",
    "    nn[i, Direction.LEFT] = i+1\n",
    "\n",
    "if(bc == BoundaryCondition.RBC):   # Open Boundary Conditions\n",
    "    nn[0, Direction.RIGHT] = -1    # This means error\n",
    "    nn[L-1, Direction.LEFT] = -1\n",
    "else:                              # Periodic Boundary Conditions\n",
    "    nn[0, Direction.RIGHT] = L-1   # We close the ring\n",
    "    nn[L-1, Direction.LEFT] = 0\n",
    "  \n",
    "# We build basis\n",
    "\n",
    "basis = []\n",
    "\n",
    "dim = 0\n",
    "for state in range(maxdim):\n",
    "    basis.append(state)\n",
    "    dim += 1\n",
    "\n",
    "print (\"Basis:\")\n",
    "print (basis)\n",
    "\n",
    "# We build Hamiltonian matrix\n",
    "\n",
    "H = np.zeros(shape=(dim,dim))\n",
    "\n",
    "def IBITS(n,i):\n",
    "    return ((n >> i) & 1)\n",
    "\n",
    "for i in range(dim):\n",
    "    state = basis[i]\n",
    "\n",
    "    # Diagonal term\n",
    "    for site_i in range(L):\n",
    "        site_j = nn[site_i, Direction.RIGHT]\n",
    "        if(site_j != -1):   # This would happen for open boundary conditions\n",
    "            two_sites  = IBITS(state,site_i) | (IBITS(state,site_j) << 1)\n",
    "            value = hdiag[two_sites]\n",
    "            H[i,i] += value\n",
    "\n",
    "        \n",
    "for i in range(dim):\n",
    "    state = basis[i]\n",
    "\n",
    "    # Off-diagonal term\n",
    "    for site_i in range(L):\n",
    "        site_j = nn[site_i, Direction.RIGHT]\n",
    "\n",
    "        if(site_j != -1):\n",
    "            mask = (1 << site_i) | (1 << site_j)\n",
    "            two_sites  = IBITS(state,site_i) | (IBITS(state,site_j) << 1)\n",
    "            value = hflip[two_sites]\n",
    "            if(value != 0.):\n",
    "                new_state = (state ^ mask)\n",
    "                j = new_state\n",
    "                H[i,j] += value\n",
    "\n",
    "print(H)\n",
    "d, v = np.linalg.eigh(H) #Diagonalize the matrix \n",
    "print(\"===================================================================================================================\")\n",
    "print(d)\n",
    "print(v[:,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dim= 70\n",
      "Basis:\n",
      "[15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240]\n",
      "[[1.  0.5 0.  ... 0.  0.  0. ]\n",
      " [0.5 0.  0.5 ... 0.  0.  0. ]\n",
      " [0.  0.5 0.  ... 0.  0.  0. ]\n",
      " ...\n",
      " [0.  0.  0.  ... 0.  0.5 0. ]\n",
      " [0.  0.  0.  ... 0.5 0.  0.5]\n",
      " [0.  0.  0.  ... 0.  0.5 1. ]]\n",
      "[-3.65109341e+00 -3.12841906e+00 -2.69962815e+00 -2.45873851e+00\n",
      " -2.45873851e+00 -2.14514837e+00 -2.14514837e+00 -1.85463768e+00\n",
      " -1.85463768e+00 -1.80193774e+00 -1.70710678e+00 -1.70710678e+00\n",
      " -1.61803399e+00 -1.61803399e+00 -1.26703510e+00 -1.26703510e+00\n",
      " -1.20163968e+00 -1.14412281e+00 -1.14412281e+00 -1.00000000e+00\n",
      " -8.58923550e-01 -8.58923550e-01 -7.60876722e-01 -7.26109445e-01\n",
      " -6.28378427e-01 -6.28378427e-01 -5.96968283e-01 -5.96968283e-01\n",
      " -5.12683203e-01 -5.12683203e-01 -4.45041868e-01 -4.37016024e-01\n",
      " -4.37016024e-01 -2.92893219e-01 -2.92893219e-01 -2.58652023e-01\n",
      " -2.58652023e-01 -2.60477563e-16 -6.54585555e-17 -4.45385084e-17\n",
      "  3.08216485e-16  3.47303424e-16  2.65452712e-01  2.65452712e-01\n",
      "  2.92893219e-01  2.92893219e-01  3.77202854e-01  4.37016024e-01\n",
      "  4.37016024e-01  4.51605963e-01  4.51605963e-01  6.18033989e-01\n",
      "  6.18033989e-01  8.92693358e-01  8.92693358e-01  1.00000000e+00\n",
      "  1.00000000e+00  1.00000000e+00  1.14412281e+00  1.14412281e+00\n",
      "  1.24697960e+00  1.33005874e+00  1.44572599e+00  1.44572599e+00\n",
      "  1.46050487e+00  1.52568712e+00  1.52568712e+00  1.70710678e+00\n",
      "  1.70710678e+00  2.00000000e+00] -3.651093408937174\n",
      "[ 0.00746966 -0.03474209  0.05454486 -0.03474209  0.00746966  0.05454486\n",
      " -0.16440628  0.13713385 -0.03474209  0.09005865 -0.16440628  0.05454486\n",
      "  0.05454486 -0.03474209  0.00746966 -0.03474209  0.13713385 -0.16440628\n",
      "  0.05454486 -0.16440628  0.39829674 -0.16440628 -0.16440628  0.13713385\n",
      " -0.03474209  0.05454486 -0.16440628  0.09005865  0.13713385 -0.16440628\n",
      "  0.05454486 -0.03474209  0.05454486 -0.03474209  0.00746966  0.00746966\n",
      " -0.03474209  0.05454486 -0.03474209  0.05454486 -0.16440628  0.13713385\n",
      "  0.09005865 -0.16440628  0.05454486 -0.03474209  0.13713385 -0.16440628\n",
      " -0.16440628  0.39829674 -0.16440628  0.05454486 -0.16440628  0.13713385\n",
      " -0.03474209  0.00746966 -0.03474209  0.05454486  0.05454486 -0.16440628\n",
      "  0.09005865 -0.03474209  0.13713385 -0.16440628  0.05454486  0.00746966\n",
      " -0.03474209  0.05454486 -0.03474209  0.00746966]\n"
     ]
    }
   ],
   "source": [
    "# Using quantum number conservation : Sz\n",
    "L=8\n",
    "Nup=4\n",
    "maxdim = 2**L\n",
    "\n",
    "\n",
    "# Lattice geometry  (1D chain)\n",
    "\n",
    "nn = np.zeros(shape=(L,4), dtype=np.int16)\n",
    "for i in range(L):\n",
    "    nn[i, Direction.RIGHT] = i-1\n",
    "    nn[i, Direction.LEFT] = i+1\n",
    "\n",
    "if(bc == BoundaryCondition.RBC):   # Open Boundary Conditions\n",
    "    nn[0, Direction.RIGHT] = -1    # This means error\n",
    "    nn[L-1, Direction.LEFT] = -1\n",
    "else:                              # Periodic Boundary Conditions\n",
    "    nn[0, Direction.RIGHT] = L-1   # We close the ring\n",
    "    nn[L-1, Direction.LEFT] = 0\n",
    "  \n",
    "\n",
    "basis = []\n",
    "\n",
    "dim = 0\n",
    "for state in range(maxdim):\n",
    "    n_ones = 0\n",
    "    for bit in range(L):\n",
    "        n_ones += IBITS(state,bit)\n",
    "    if(n_ones == Nup):\n",
    "        basis.append(state)\n",
    "        dim += 1\n",
    "\n",
    "print (\"Dim=\",dim)\n",
    "print (\"Basis:\")\n",
    "print (basis)\n",
    "\n",
    "#hflip[:] *= 2\n",
    "# We build Hamiltonian matrix\n",
    "\n",
    "H = np.zeros(shape=(dim,dim))\n",
    "\n",
    "def IBITS(n,i):\n",
    "    return ((n >> i) & 1)\n",
    "\n",
    "for i in range(dim):\n",
    "    state = basis[i]\n",
    "\n",
    "    # Diagonal term\n",
    "    for site_i in range(L):\n",
    "        site_j = nn[site_i, Direction.RIGHT]\n",
    "        if(site_j != -1):   # This would happen for open boundary conditions\n",
    "            two_sites  = IBITS(state,site_i) | (IBITS(state,site_j) << 1)\n",
    "            value = hdiag[two_sites]\n",
    "            H[i,i] += value\n",
    "\n",
    "\n",
    "def bisect(state, basis):  \n",
    "    # Binary search, only works in a sorted list of integers\n",
    "    # state : integer we seek\n",
    "    # basis : list of sorted integers in increasing order\n",
    "    # ret_val : return value, position on the list, -1 if not found\n",
    "    \n",
    "    ret_val = -1\n",
    "    dim = len(basis)\n",
    "    \n",
    "#    for i in range(dim):\n",
    "#        if(state == basis[i]):\n",
    "#            return i\n",
    "\n",
    "    origin = 0\n",
    "    end = dim-1\n",
    "    middle = (origin+end)/2\n",
    "\n",
    "    while(1):\n",
    "        index_old = middle\n",
    "\n",
    "        middle = (origin+end)//2\n",
    "        if(state < basis[middle]):\n",
    "            end = middle\n",
    "        else:\n",
    "            origin = middle\n",
    "\n",
    "        if(basis[middle] == state):\n",
    "            break\n",
    "\n",
    "        if(middle == index_old):\n",
    "            if(middle == end):\n",
    "                end = end - 1\n",
    "            else:\n",
    "                origin = origin + 1\n",
    "\n",
    "    ret_val = middle\n",
    "    return ret_val           \n",
    "\n",
    "            \n",
    "for i in range(dim):\n",
    "    state = basis[i]\n",
    "\n",
    "    # Off-diagonal term\n",
    "    for site_i in range(L):\n",
    "        site_j = nn[site_i, Direction.RIGHT]\n",
    "\n",
    "        if(site_j != -1):\n",
    "            mask = (1 << site_i) | (1 << site_j)\n",
    "            two_sites  = IBITS(state,site_i) | (IBITS(state,site_j) << 1)\n",
    "            value = hflip[two_sites]\n",
    "            if(value != 0.):\n",
    "                new_state = (state ^ mask)\n",
    "                j = bisect(new_state, basis)\n",
    "                H[i,j] += value\n",
    "\n",
    "print(H)\n",
    "d, v = np.linalg.eigh(H) #Diagonalize the matrix \n",
    "print(d,np.min(d))\n",
    "print(v[:,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obtaining the ground-state: Lanczos diagonalization\n",
    "---------------------------------------------------\n",
    "\n",
    "Once we have a superblock matrix, we can apply a library routine to\n",
    "obtain the ground state of the superblock $|\\Psi\\rangle$. The two\n",
    "algorithms widely used for this purpose are the Lanczos and Davidson\n",
    "diagonalization. Both are explained to great extent in Ref.@noack, so we\n",
    "refer the reader to this material for further information. In these\n",
    "notes we will briefly explain the Lanczos procedure.\n",
    "\n",
    "The basic idea of the Lanczos method is that a special basis can be constructed\n",
    "where the Hamiltonian has a tridiagonal representation. This is carried\n",
    "out iteratively as shown below. First, it is necessary to select an\n",
    "arbitrary seed vector $|\\phi _{0}\\rangle $ in the Hilbert space of the\n",
    "model being studied. If we are seeking the ground-state of the model,\n",
    "then it is necessary that the overlap between the actual ground-state\n",
    "$|\\psi\n",
    "_{0}\\rangle $, and the initial state $|\\phi _{0}\\rangle $ be nonzero. If\n",
    "no “a priori” information about the ground state is known, this\n",
    "requirement is usually easily satisfied by selecting an initial state\n",
    "with *randomly* chosen coefficients in the working basis that is being\n",
    "used. If some other information of the ground state is known, like its\n",
    "total momentum and spin, then it is convenient to initiate the\n",
    "iterations with a state already belonging to the subspace having those\n",
    "quantum numbers (and still with random coefficients within this\n",
    "subspace).\n",
    "\n",
    "After $|\\phi _{0}\\rangle $ is selected, define a new vector by applying\n",
    "the Hamiltonian ${{\\hat{H}}}$, over the initial state. Subtracting the\n",
    "projection over $|\\phi _{0}\\rangle $, we obtain\n",
    "$$|\\phi _{1}\\rangle ={{\\hat{H}}}|\\phi _{0}\\rangle -\\frac{{\\langle }\\phi _{0}|{{%\n",
    "\\hat{H}}}|{\\phi }_{0}{\\rangle }}{\\langle \\phi _{0}|\\phi _{0}\\rangle }|\\phi\n",
    "_{0}\\rangle ,$$ that satisfies $\\langle \\phi _{0}|\\phi _{1}\\rangle =0$.\n",
    "Now, we can construct a new state that is orthogonal to the previous two\n",
    "as,\n",
    "$$|\\phi _{2}\\rangle ={{\\hat{H}}}|\\phi _{1}\\rangle -{\\frac{{\\langle \\phi _{1}|{%\n",
    "\\hat{H}}|\\phi _{1}\\rangle }}{{\\langle \\phi _{1}|\\phi _{1}\\rangle }}}|\\phi\n",
    "_{1}\\rangle -{\\frac{{\\langle \\phi _{1}|\\phi _{1}\\rangle }}{{\\langle \\phi\n",
    "_{0}|\\phi _{0}\\rangle }}}|\\phi _{0}\\rangle .$$ It can be easily checked\n",
    "that $\\langle \\phi _{0}|\\phi _{2}\\rangle\n",
    "=\\langle \\phi _{1}|\\phi _{2}\\rangle =0$. The procedure can be\n",
    "generalized by defining an orthogonal basis recursively as,\n",
    "$$|\\phi _{n+1}\\rangle ={{\\hat{H}}}|\\phi _{n}\\rangle -a_{n}|\\phi _{n}\\rangle\n",
    "-b_{n}^{2}|\\phi _{n-1}\\rangle ,$$ where $n=0,1,2,...$, and the\n",
    "coefficients are given by\n",
    "$$a_{n}={\\frac{{\\langle \\phi _{n}|{\\hat{H}}|\\phi _{n}\\rangle }}{{\\langle \\phi\n",
    "_{n}|\\phi _{n}\\rangle }}},\\qquad b_{n}^{2}={\\frac{{\\langle \\phi _{n}|\\phi\n",
    "_{n}\\rangle }}{{\\langle \\phi _{n-1}|\\phi _{n-1}\\rangle }}},$$\n",
    "supplemented by $b_{0}=0$, $|\\phi _{-1}\\rangle =0$. In this basis, it\n",
    "can be shown that the Hamiltonian matrix becomes, $$H=\\left(\n",
    "\\begin{array}{lllll}\n",
    "a_{0} & b_{1} & 0 & 0 & ... \\\\\n",
    "b_{1} & a_{1} & b_{2} & 0 & ... \\\\\n",
    "0 & b_{2} & a_{2} & b_{3} & ... \\\\\n",
    "0 & 0 & b_{3} & a_{3} & ... \\\\\n",
    "\\vdots\n",
    "{} &\n",
    "\\vdots\n",
    "&\n",
    "\\vdots\n",
    "&\n",
    "\\vdots\n",
    "&\n",
    "\\end{array}\n",
    "\\right)$$ i.e. it is tridiagonal as expected. Once in this form the\n",
    "matrix can be diagonalized easily using standard library subroutines.\n",
    "However, note that to diagonalize completely a Hamiltonian on a finite\n",
    "cluster, a number of iterations equal to the size of the Hilbert space\n",
    "(or the subspace under consideration) are needed. In practice this would\n",
    "demand a considerable amount of CPU time. However, one of the advantages\n",
    "of this technique is that accurate enough information about the ground\n",
    "state of the problem can be obtained after a small number of iterations\n",
    "(typically of the order of $\\sim 100$ or less).\n",
    "\n",
    "Another way to formulate the problem is by obtaining the tridiagonal\n",
    "form of the Hamiltonian starting from a Krylov basis, which is spanned\n",
    "by the vectors\n",
    "$$\\left\\{|\\phi_0\\rangle,\\hat{H}|\\phi_0\\rangle,\\hat{H}^2|\\phi_0\\rangle,...,\\hat{H}^n|\\phi_0\\rangle\\right\\}$$\n",
    "and asking that each vector be orthogonal to the previous two. Notice\n",
    "that each new iteration of the process requires one application of the\n",
    "Hamiltonian. Most of the time this simple procedure works for practical\n",
    "purposes, but care must be payed to the possibility of losing\n",
    "orthogonality between the basis vectors. This may happen due to the\n",
    "finite machine precision. In that case, a re-orthogonalization procedure\n",
    "may be required.\n",
    "\n",
    "Notice that the new super-Hamiltonian matrix has dimensions\n",
    "$D_L D_R d^2 \\times D_L D_R d^2$. This could be a large matrix. In\n",
    "state-of-the-art simulations with a large number of states, one does not\n",
    "build this matrix in memory explicitly, but applies the operators to the\n",
    "state directly in the diagonalization routine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lanczos(m, seed, maxiter, tol, use_seed, calc_gs, force_maxiter = False):\n",
    "    x1 = seed\n",
    "    x2 = seed\n",
    "    gs = seed\n",
    "    a = np.zeros(100)\n",
    "    b = np.zeros(100)\n",
    "    z = np.zeros((100,100))\n",
    "    lvectors = []\n",
    "    control_max = maxiter;\n",
    "\n",
    "    if(maxiter == -1):\n",
    "        force_maxiter = False\n",
    "\n",
    "    if(control_max == 0):\n",
    "        gs = 1\n",
    "        maxiter = 1\n",
    "        return(e0,gs)\n",
    "    \n",
    "    x1[:] = 0\n",
    "    x2[:] = 0\n",
    "    gs[:] = 0\n",
    "    maxiter = 0\n",
    "    a[:] = 0.0\n",
    "    b[:] = 0.0\n",
    "    if(use_seed):\n",
    "        x1 = seed\n",
    "    else :\n",
    "        x1 = np.random.random(x1.shape[0])*2-1.\n",
    "\n",
    "    b[0] = np.sqrt(np.dot(x1,x1))\n",
    "    x1 = x1 / b[0]\n",
    "    x2[:] = 0\n",
    "    b[0] = 1.\n",
    "\n",
    "    e0 = 9999\n",
    "    nmax = min(99, gs.shape[0])\n",
    "    for iter in range(1,nmax+1):\n",
    "        eini = e0\n",
    "        if(b[iter - 1] != 0.):\n",
    "            aux = x1\n",
    "            x1 = -b[iter-1] * x2\n",
    "            x2 = aux / b[iter-1]\n",
    "\n",
    "        aux = np.dot(m,x2)\n",
    "        x1 = x1 + aux\n",
    "        a[iter] = np.dot(x1, x2)\n",
    "        x1 = x1 - x2*a[iter]\n",
    "        b[iter] = np.sqrt(np.dot(x1, x1))\n",
    "        lvectors.append(x2)                                          \n",
    "\n",
    "        z.resize((iter+1,iter+1))\n",
    "        z[:,:] = 0\n",
    "        for i in range(0,iter-1):\n",
    "            z[i,i+1] = b[i+1]\n",
    "            z[i+1,i] = b[i+1]\n",
    "            z[i,i] = a[i+1]\n",
    "        z[iter-1,iter-1]=a[iter]\n",
    "        d, v = np.linalg.eig(z)\n",
    "        col = 0\n",
    "        n = 0\n",
    "        e0 = 9999\n",
    "        for e in d:\n",
    "            if(e < e0):\n",
    "                e0 = e\n",
    "                col = n\n",
    "            n+=1\n",
    "        e0 = d[col]\n",
    "        print (\"Iter = \",iter,\" Ener = \",e0)\n",
    "        if((force_maxiter and iter >= control_max) or (iter >= gs.shape[0] or iter == 99 or abs(b[iter]) < tol) or \\\n",
    "            ((not force_maxiter) and abs(eini-e0) <= tol)):\n",
    "            # converged\n",
    "            gs = 0.\n",
    "            for i in range(0,iter):\n",
    "                gs += v[i,col]*lvectors[i]\n",
    "            print (\"E0 = \", e0, np.sqrt(np.dot(gs,gs)))\n",
    "            maxiter = iter\n",
    "            return(e0,gs) # We return with ground states energy\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "seed = np.zeros(H.shape[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iter =  1  Ener =  -0.32059440314178866\n",
      "Iter =  2  Ener =  -1.207943534608849\n",
      "Iter =  3  Ener =  -1.7312786649917817\n",
      "Iter =  4  Ener =  -2.463042387743914\n",
      "Iter =  5  Ener =  -2.758240572039436\n",
      "Iter =  6  Ener =  -2.7935078581431574\n",
      "Iter =  7  Ener =  -2.8001936054168652\n",
      "Iter =  8  Ener =  -2.802412181520129\n",
      "Iter =  9  Ener =  -2.8027617389669075\n",
      "Iter =  10  Ener =  -2.802773890249349\n",
      "Iter =  11  Ener =  -2.8027756307225253\n",
      "E0 =  -2.8027756307225253 1.0000000000000004\n"
     ]
    }
   ],
   "source": [
    "e0, gs = lanczos(H,seed,6,1.e-5,False,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.06293272 -0.20780802  0.20781428 -0.06290635  0.20781929 -0.4785539\n",
      "  0.20780196  0.20781618 -0.20781206  0.06293183 -0.06290584  0.20780202\n",
      " -0.20783061 -0.20782075  0.47853525 -0.20781988  0.06293281 -0.20782154\n",
      "  0.20779574 -0.06290309]\n"
     ]
    }
   ],
   "source": [
    "print(gs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9999999999999994\n"
     ]
    }
   ],
   "source": [
    "print(np.dot(gs,gs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}