Top to random eigenvalues.py

From Werner KRAUTH

Revision as of 19:24, 7 June 2024 Werner (Talk | contribs) ← Previous diff		Revision as of 19:24, 7 June 2024 Werner (Talk | contribs) (→Output) Next diff →
Line 40:		Line 40:
	==Output==		==Output==
-	2 N 2 [1, 0, 1]	+	2 N 2 [1, 0, 1]
		+
	3 N 6 [2, 3, 0, 1]		3 N 6 [2, 3, 0, 1]
		+
	4 N 24 [9, 8, 6, 0, 1]		4 N 24 [9, 8, 6, 0, 1]
		+
	5 N 120 [44, 45, 20, 10, 0, 1]		5 N 120 [44, 45, 20, 10, 0, 1]
		+
	6 N 720 [265, 264, 135, 40, 15, 0, 1]		6 N 720 [265, 264, 135, 40, 15, 0, 1]
	For N=6, the output means that		For N=6, the output means that
		+
	the eigenvalue 1 is 1 times degenerate		the eigenvalue 1 is 1 times degenerate
		+
	the eigenvalue 1 - 1/N is 0 times degenerate		the eigenvalue 1 - 1/N is 0 times degenerate
		+
	the eigenvalue 1 - 2/N is 15 times degenerate		the eigenvalue 1 - 2/N is 15 times degenerate
		+
	the eigenvalue 1 - 3/N is 40 times degenerate, etc		the eigenvalue 1 - 3/N is 40 times degenerate, etc
-	The degeneracy of the second eigenvalue is thus n(n-1)/2.	+	The degeneracy of the second eigenvalue is thus n(n-1)/2.
	==Further information==		==Further information==

---

Revision as of 19:24, 7 June 2024

Contents 1 Context 2 Python program 3 Output 4 Further information 5 References

Context

This page is part of my 2024 Beg Rohu Lectures on "The second Markov chain revolution" at the Summer School "Concepts and Methods of Statistical Physics" (3 - 15 June 2024).

In this example, I consider the transition matrix for the top-to-random shuffle discussed in Lecture 2. This N! x N! matrix has N distinct eigenvalues, and therefore huge degeneracies.

Python program

import numpy as np
import itertools
import scipy.linalg as la

def factorial(n):
    return 1 if n == 0 else (0 if n == 0 else factorial(n - 1) * n)

for N in [2, 3, 4, 5, 6, 7]:
    FacN = factorial(N)
    ConfCopy = [0] * N
    print(N, 'N', FacN)
#
#   Setup of transition matrix
#
    P   = np.zeros((FacN, FacN))
    Conf = [k for k in range(N)]
    ConfList = list(itertools.permutations(Conf))
    for Conf in ConfList:
        i = ConfList.index(tuple(Conf))
        ConfCopy[:] = Conf
        a = ConfCopy.pop(0)
        for k in range(N):
            TargetConf = ConfCopy[0:k] + [a] + ConfCopy[k:N - 1]
            j = ConfList.index(tuple(TargetConf))
            P[i][j] = 1.0 / float(N)
    eigvals, eigvecsl, eigvecsr = la.eig(P, left=True)
    eigvals.sort()
    stats = [0] * (N+1)
    for a in eigvals:
        index =  int(N * a.real + 0.5)
        stats[index] += 1
    print(stats)

Output

2 N 2 [1, 0, 1]

3 N 6 [2, 3, 0, 1]

4 N 24 [9, 8, 6, 0, 1]

5 N 120 [44, 45, 20, 10, 0, 1]

6 N 720 [265, 264, 135, 40, 15, 0, 1]

For N=6, the output means that

the eigenvalue 1 is 1 times degenerate

the eigenvalue 1 - 1/N is 0 times degenerate

the eigenvalue 1 - 2/N is 15 times degenerate

the eigenvalue 1 - 3/N is 40 times degenerate, etc

The degeneracy of the second eigenvalue is thus n(n-1)/2.

Further information

The

References