# Sports ranking methods, 4

This is the fourth of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the Elo rating.

This system was originally developed by Arpad Elo (Elo (1903-1992) was a physics professor at Marquette University in Milwaukee and a chess master, eight-time winner of the Wisconsin State Chess Championships.) Originally, it was developed for rating chess players in the 1950s and 1960s. Now it is used for table tennis, basketball, and other sports.

We use the following version of his rating system.

As above, assume all the $n$ teams play each other (ties allowed)
and let $r_i$ denote the rating of Team $i$, $i=1,2,\dots,n$.

Let $A=(A_{ij})$ denote an $n\times n$ matrix of score results:

$A_{ij}= \left\{ \begin{array}{rr} -1,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ +1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.$

Let $S_{ij}=(A_{ij}+1)/2$.

As in the previous post, the matrix $A$ associated to the example of the Patriot league is the adjacency matrix of a diagraph.

1. Initialize all the ratings to be $100$: ${\bf r}=(r_1,\dots,r_n) = (100,\dots,100)$.
2. After Team $i$ plays Team $j$, update their rating using the formula

$r_i = r_i+K(S_{ij}-mu_{ij}),$

where $K=10$ and

$\mu_{ij} = (1+e^{-(r_i-r_j)/400})^{-1}.$

In the example of the Patriot league, the ratings vector is

${\bf r}=(85.124, 104.79, 104.88, 85.032, 94.876, 124.53).$

This gives the ranking

Lafayette $<$ Army $<$ Lehigh $<$ Bucknell $<$ Holy Cross $<$ Navy.

This gives a prediction failure rate of $13.3\%$.

Some SageMath code for this:

def elo_rating(A):
"""
A is a signed adjacency matrix for a directed graph.

Returns elo ratings of the vertices of Gamma = Graph(A)

EXAMPLES:
sage: A = matrix(QQ,[
[0 , -1 , 1  , -1 , -1 , -1 ],
[1,   0 ,  -1,  1,  1,   -1  ],
[-1 , 1 ,  0 ,  1 , 1  , -1  ],
[1 , -1 , -1,  0 ,  -1 , -1  ],
[1 , - 1 , - 1 , 1 , 0 , - 1  ],
[1 ,  1  ,  1  , 1  , 1  , 0 ]
])
sage: elo_rating(A)
(85.124, 104.79, 104.88, 85.032, 94.876, 124.53)

"""
n = len(A.rows())
RR = RealField(prec=20)
V = RR^n
K = 10
r0 = 100 # initial rating
r = n*[r0]
for i in range(n):
for j in range(n):
if ij and A[i][j]==1:
S = 1
elif ij and A[i][j]==-1:
S = 0
else:
S = 1/2
mu = 1/(1+e^(-(r[i]-r[j])/400))
r[i] = r[i]+K*(S-mu)
return V(r)


# Chess problem 1 by Karl Fabel

I found the following problem in the book C. Bandelow, Inside Rubik’s cube and beyond, Birkhauser, 1982

White to play and mate in 182 moves.

Here are the pieces and their locations:

Black pieces:

• pawns at b3, b6, c7, g4, g6, g7, h7
• knights at a8, f1, h3
• bishops at a7, g2
• rook at h2
• king at h1

White pieces:

• pawns at b2, b5, c6, g3
• knights at d1, e2
• rook at e1
• king at d8

solution below

.

.

.

.

.

.

.

.

This is a Dec 5, 1999 email from Dror Efraty, with some minor edits:
hi David,

I send you my analyzis of the solution.

this is my analisis of the position:

in the given position few black pieces can move.
if Nh3 moves white mates in 1 move: Nf2#
if Bg2 moves, white mates in 2 – 1. R:f1 Kg2, 2. Ne3#
so black can only move with his king side pawns, and with Ba7.
note that after black captures g3 with his pawn (and later, when he moves
other pawns to g3) he can move Nf4 next move, and no mate is possible.
thus immidiately after black has a pawn on g3, white must move:
1. N:g3+ Kg1, 2. Ne2+ Kh1 to remove black’s pawn from g3.

this means, that if white kills black’s Ba7 and queen side pawns, black
must move with either Nh3 or Bg2, which result in mate in 2. but this is
not so easy for white to kill Ba7. the obvious way will be to move Kb7,
but then black move: B:c6+ and kg2 to release the position. then, black
has enough to win the game. also, if white’s king moves to almost every
other white square on the board, black can check him with either Bg2 or
Nh3, and release the position.there are 2 exceptions: c8 (current
position) and a4.
now, white can only kill black’s Ba7 on b8 and not on a7. but this can’t
happen if all white’s moves are king moves on black squares, because then
it takes white an even number of moves to return with his king to c8, and
during that time black moves Ba7-b8-a7-b8-a7, so that when white moves
Kd8-c8 black moves Bb8-a7. also, white can’t move either of his knights
because this will let black move Nh3 and release the position, so white
can only move his king.
so, as explained, white can kill Ba7 only if he can move an odd number of
moves with his king, and return to c8. this can be done in 19 moves:
Kd8-e7-f8:g7-f6-e5-d4-c3-b4-a4-a3-b4-c3-d4-e5-f6-e7-d8-c8.
and after black’s pawn g7 is gone, white can do it in 17 moves:
Kd8-e7-f6-e5-d4-c3-b4-a4-a3-b4-c3-d4-e5-f6-e7-d8-c8.
after each such sequence, black’s bishop is on a7, and can’t move to b8,
so black spare a pawn move.
black has 8 pawn moves to spare: h7-h6, h6-h5, h5-h4, h4:g3, g4-g3, g6-g5,
g5-g4, and g4-g3 again. as noted above, after the moves: h4:g3 and g4-g3
white must make the moves N:g3+ Kg1, Ne2+ kh1 so that black won’t release
the position.
so the sequence for the mate is:
white’s king 19 moves trip (including killing g7, meanwhile black moves
with his Ba7)
19. … h7-h6
20.-36. white king’s 17 moves trip
36. … h6-h5
37.-53. white king’s 17 moves trip
53. … h5-h4
54.-70. white king’s 17 moves trip
70. … h4:g3
71. N:g3+ Kg1, 72. Ne2+ Kh1
73.-89. white king’s 17 moves trip
89. … g4-g3
90. N:g3+ Kg1, 91. Ne2+ Kh1
92.-108. white king’s 17 moves trip
108. … g6-g5
109.-125. white king’s 17 moves trip
125. … g5-g4
126.-142. white king’s 17 moves trip
142. … g4-g3
143. N:g3+ Kg1, 144. Ne2+ Kh1
145.-161. white king’s 17 moves trip
162. … Ba7-b8
163. K:b8 Bg7 – somewhere,
164. R:f1+ Kg2, and finally 165. Nf3#

black can save his g7 pawn by moving g6-g5, and g7-g6, but
this means that black has pawns on g6 and g7, and white can make shorter
odd moves trips to h7. he can do it only after black moves h7-h6 ohterwise
black moves Nf4+ or Nf2+. now, white has an eleven moves trip:
Kd8-e7-f8-g7-h8-h7-g7-f8-e7-d8-c8.

so, the count is:

1.-19. white king trip, meanwhile black moves g6-g5 and g7-g6
19. … h7-h6
20.-30. 11 moves trip, … h6-h5
31.-41. 11 moves trip, … h5-h4
42.-52. 11 moves trip, … h4:g3
53. N:g3+ Kg1, 54. Ne2+ Kh1
55.-71. 17 moves trip, … g4-g3
72. N:g3+ Kg1, 73. Ne2+ Kh1
74.-90. 17 moves trip, … g5-g4
91.-107. 17 moves trip, … g4-g3
108. N:g3+ Kg1, 109. Ne2+ Kh1
110.-126. 17 moves trip, … g6-g5
127.-143. 17 moves trip, … g5-g4
144.-160. 17 moves trip, … g4-g3
161. N:g3+ Kg1, 162. Ne2+ Kh1
163.-179. 17 moves trip
179. … Bb8, 180. K:b8 Bg2-somewhere, 181 R:f1+ Kg2, 182. Ne3#

so, these are the whole 182 moves. another fabel’s masterpiece.

Dror.

# Chess problem 3 by Christoph Bandelow

I thank Christoph Bandelow for allowing this chess problem, with a mathematical flavor, to be posted here.

Position:

• In algebraic:White: King c7, Rooks c3 and d3, Knights b1 and e1,
Pawn e3 (6 pieces).Black: King b5, Knight a4 and c4, Knights
a4 and c4, Pawns a7, b6, and a5 (7 pieces).
• In Forsyth notation:
8
p1K5
rp6
pk6
n1n5
2RRP3
8
1N2N3


From the chess problem collection “Problem-Juwelen” by Herbert Grasemann. Publisher: Siegfried Engelhardt Verlag, Berlin 1964.

White to mate in 6 (Christoph Bandelow, 1959)

Solution: 1. Rb3+ … 2. Rb5+ … 3. Rb3+ … 4. Rb5+ … 5. Nd3

This problem was originally posted at http://www.permutationpuzzles.org/chess/bandelow3.html.

# Chess problem 2 by Christoph Bandelow

I thank Christoph Bandelow for allowing this chess problem, with a mathematical flavor, to be posted here.

Position:

• In algebraic:White: King b4, Rooks b2 and e1, Bishop a1, Knight d4, Pawns c5, g3, g4
(8 pieces).Black: King c1, Rook h1, Bishop d1, Knights d2 and g1, Pawns c6, d5,
e2, g5, h2 (10 pieces).
• In Forsyth notation:
8
8
2p5
2Pp2p1
1K1N2P1
6P1
1R1np2p
B1kbR1nr


From the chess problem collection “Problem-Juwelen” by Herbert Grasemann. Publisher: Siegfried Engelhardt Verlag, Berlin 1964.

White to mate in 8 (Christoph Bandelow, 1958)

Solution: 1. Kc3 Ne4+ 2. Kd3 Nf2+ 3. Ke3 Nxg4+ 4. Kd3 Nf2+ 5. Kc3 Ne4+ 6. Kb4 Nd2 7. g4

This problem was originally posted at http://www.permutationpuzzles.org/chess/bandelow2.html.

# Chess problem 1 by Christoph Bandelow

I thank Christoph Bandelow for allowing this chess problem, with a mathematical flavor, to be posted here.

Position:

• In algebraic:White: King g8, Queen e2, Bishops a1 and g4, Pawn e6 (5 pieces),Black: King f6, Bishop a2, Knight b1 (3 pieces).
• In Forsyth notation:
6K1
8
4Pk2
8
6B1
8
b3Q3
Bn6

What were the last 6 single moves? (retrochess problem by Christoph Bandelow)

Solution: -1. d5xe6 e.p.+ -2. ….. d7-d5 -3. d4-d5+ -4. ….. Ke6xPf6+ -5. e6xf6 e.p.++ -6. ….. f7-f5

# Complements in the symmetric group

About 20 years ago I was asked a question of Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in $S_E$ and $S_V$ (the groups of all permutations of the edges $E$ and vertices $V$, respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of $S_m$ in $S_n$. Specifically, he asked if $S_8$ has a complement in $S_{12}$ (this terminology is defined below). The answer is,
as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a “$k$-tuple of complementary subgroups” (defined below) for which the answer to the analogous question is ”yes.”

This post is a very short summary of a paper I wrote (still unpublished) which can be downloaded here.

# Splitting fields of representations of generalized symmetric groups, 1

The main result of this series of blog posts (originally written 1998), which is expository, is to determine (in a sense made precise later) the splitting field of any irreducible character of a generalized symmetric group. This was basically solved by M. Benard in a 1976 J. of Algebra paper. We use one of his results to make the splitting field explicit.

Notation and definitions

Let $C_\ell$ denote the cyclic group of order $\ell\geq 1$, let $S_n$ denote the symmetric group of degree $n\geq 1$, and let $G$ denote the semi-direct product $G=C_\ell^n\, >\!\!\lhd \, S_n$. We think of this as the set of pairs $(v,p)$, with

• $v=(v_1,...,v_n)$, where each $v_i\in C_\ell=\{0,1,...,\ell-1\}$,
• $p\in S_n$,
• $S_n$ acts on $C_\ell^n$ by $p(v)=(v_{p(1)},v_{p(2)},...,v_{p(n)})$,
• multiplication given by $(v,p)*(v',p')=(v+p(v'),pp'),\ \ \ \ \ (v,p),(v',p')\in G.$

A group of the form $C_\ell^n\, >\!\!\lhd \, S_n$, also written $S_n \ {\rm wr}\ C_\ell$ (here wr denotes the wreath product), will be called a generalized symmetric group.

We may identify each element of $C_\ell^n\, >\!\!\lhd \, S_n$ with an $n\times n$ monomial matrix (a matrix with exactly one non-zero entry in each row and column) with entries in $C_\ell$.

Our main goal will be to investigate the following question: What is the smallest extension of ${\mathbb{Q}}$ required to realize (using matrices) a given irreducible character of a generalized symmetric group?