# Elizebeth Friedman and the Holmwood case

Elizebeth Smith Friedman was the top cryptographer for the Coast Guard (then the enforcement arm of the Department of the Treasury) during the Prohibition Era.

According to wrecksite.eu, the SS Holmwood was a steam ship made in 1911. It was a New Zealand passenger/cargo ship with dimensions 50.4 x 8 x 3.9 m and equipped with a triple expansion engine and a 1 singleboiler engine, capable of 78 n.h.p..

The Holmwood case is a prohibition-era legal investigation concerning events up to and including the seizure of the SS Holmwood in October 5, 1933, in the Hudson River, and the subsequent trial of the smugglers. The New York Intelligence Office (of the Coast Guard, as part of the Treasury Department) used Elizebeth Friedman’s cryptanalysis of telegraph messages between the Holmwood and shore-based agents.

The best source of information from the ESF collection at the Marshall library, Box 6, File 24, “Notes on the solution of cipher and code used by the Holmwood” (14 pages), dated October 11, 1934. This document describes the investigation of the liquor smuggling operations of the Holmwood from 1930 to 1934. The first interception was November, 1930, by the New York Intelligence Office of the Treasury Department. The Coast Guard operated radio stations which monitored rum-runner telegraph stations. Usually these were in a telegraph cipher-code but sometimes they were in plain English. For example, it was reported that at 1505 on October 3, 1933, Radioman First Class B. E. Howell, of the New York Intelligence Unit, intercepted the following message

Anchor the boat in good place immediately. Take all men off in one of life boats. Hide the life boat if possible. Come ashore on New York side. Call [undecoded phone number] when you come ashore. PA code.

This message was preceded by a telegraph cipher-code

JDSLE 2221 1612 WJJE …. DEMPY.

which was decoded (by the office of ESF) as

Heave your anchor immediately and get underway. Stand up the river towards Albany.

This led to the seizure of the Holmwood. ESF wrote a strong commendation letter for Radioman Howell for his hard work and dedication to service.

For more on the life of Elizebeth Friedman, see [1], [2], or the book Divine Fire, by Katie Letcher Lyle (and some additional material by myself).

[1] Smith, G. Stuart, A Life in Code: Pioneer Cryptanalyst Elizebeth Smith Friedman, McFarland & Company, Jefferson, NC, 2017.

[2] Fagone, Jason, The Woman Who Smashed Codes: A True Story of Love, Spies, and the Unlikely Heroine Who Outwitted America’s Enemies, Dey Street Books, New York, 2017

# MINIMOGs and Mathematical blackjack

This is an exposition of some ideas of Conway, Curtis, and Ryba on $S(5,6,12)$ and a card game called mathematical blackjack (which has almost no relation with the usual Blackjack).

Many thanks to Alex Ryba and Andrew Buchanan for helpful discussions on this post.

### Definitions

An m￼-(sub)set is a (sub)set with m￼ elements. For integers ￼$k, a Steiner system￼ S(k,m,n) is an ￼n-set X￼ and a set S￼ of ￼m-subsets having the property that any ￼k-subset of X￼ is contained in exactly one ￼m-set in S￼. For example, if ￼$X = \{1,2,\dots,12\}$, a Steiner system S(5,6,12)￼ is a set of ￼6-sets, called hexads, with the property that any set of 5￼ elements of X￼ is contained in (“can be completed to”) exactly one hexad.

Rob Beezer has a nice Sagemath description of S(5,6,12).

If S￼ is a Steiner system of type (5,6,12) in a ￼12-set X￼ then any element the symmetric group $\sigma\in S_X\cong S_{12}$￼ of X￼ sends S￼ to another Steiner system $\sigma(S)$￼ of X￼. It is known that if XS and S’￼ are any two Steiner systems of type (5,6,12)￼ in X￼ then there is a ￼$\sigma\in S_X$ such that $S'=\sigma(S)$￼. In other words, a Steiner system of this type is unique up to relabelings. (This also implies that if one defines $M_{12}$￼ to be the stabilizer of a fixed Steiner system of type (5,6,12)￼ in X￼ then any two such groups, for different Steiner systems in X￼, must be conjugate in ￼$S_X$. In particular, such a definition is well-defined up to isomorphism.)

### Curtis’ kitten

NICOLE SHENTING – Cats Playing Poker Cards

J. Conway and R. Curtis [Cu1] found a relatively simple and elegant way to construct hexads in a particular Steiner system $S(5,6,12)$ using the arithmetical geometry of the projective line over the finite field with 11 elements. This section describes this.

Let $\mathbf{P}^1(\mathbf{F}_{11}) =\{\infty,0,1,2,...,9,10\}$ denote the projective line over the finite field $\mathbf{F}_{11}$ with 11 elements. Let $Q=\{0,1,3,4,5,9\}$ denote the quadratic residues with 0, and let
$L=<\alpha,\beta>\cong PSL(2,\mathbf{F}_{11}),$
where $\alpha(y)=y+1$ and $\beta(y)=-1/y$. Let $S=\{\lambda(Q)\ \vert\ \lambda\in L\}.$

Lemma 1: $S$ is a Steiner system of type $(5,6,12)$.

The elements of S￼ are known as hexads (in the “modulo 11￼ labeling”).

 	 	 	 	 	$\infty$

6

2	 	10

5	 	7	 	3

6	 	9	 	4	 	6

2	 	10	 	8	 	2	 	10

0	 	 	 	 	 	 	 	 	 	1



Curtis’ Kitten.

In any case, the “views” from each of the three “points at infinity” is given in the following tables.

6	10	3
2	7	4
5	9	8
picture at $\infty$

5	7	3
6	9	4
2	10	8
picture at $0$

5	7	3
9	4	6
8	2	10
picture at $1$


Each of these $3\times 3$ arrays may be regarded as the plane $\mathbf{F}_3^2$. The lines of this plane are described by one of the following patterns.

$\bullet$	$\bullet$	$\bullet$
$\times$	$\times$	$\times$
$\circ$	$\circ$	$\circ$
slope 0

$\bullet$	$\times$	$\circ$
$\bullet$	$\times$	$\circ$
$\bullet$	$\times$	$\circ$
slope infinity

$\bullet$	$\times$	$\circ$
$\circ$	$\bullet$	$\times$
$\times$	$\circ$	$\bullet$
slope -1

$\times$	$\circ$	$\bullet$
$\circ$	$\bullet$	$\times$
$\bullet$	$\times$	$\circ$
slope 1


The union of any two perpendicular lines is called a cross. There are 18 crosses. The complement of a cross in $\mathbf{F}_3^2$ is called a square. Of course there are also 18 squares. The hexads are

1. $\{0,1,\infty\}\cup \{{\rm any\ line}\}$,
2. the union of any two (distinct) parallel lines in the same picture,
3. one “point at infinity” union a cross in the corresponding picture,
4. two “points at infinity” union a square in the picture corresponding to the omitted point at infinity.

Lemma 2 (Curtis [Cu1]) There are 132 such hexads (12 of type 1, 12 of type 2, 54 of type 3, and 54 of type 4). They form a Steiner system of type $(5,6,12)$.

### The MINIMOG description

Following Curtis’ description [Cu2] of a Steiner system $S(5,8,24)$ using a $4\times 6$ array, called the MOG, Conway [Co1] found and analogous description of $S(5,6,12)$ using a $3\times 4$ array, called the MINIMOG. This section is devoted to the MINIMOG. The tetracode words are

0	0	0	0		0	+	+	+		0	-	-	-
+	0	+	-		+	+	-	0		+	-	0	+
-	0	-	+		-	+	0	-		-	-	+	0



With ￼”0″=0, “+”=1, “-“=2, these vectors form a linear code over GF(3)￼. (This notation is Conway’s. One must remember here that “+”+”+”=”-“!) They may also be described as the set of all 4-tuples in ￼ of the form
$(0,a,a,a),(1,a,b,c),(2,c,b,a),$
where abc￼ is any cyclic permutation of 012￼. The MINIMOG in the shuffle numbering is the ￼ array
$\begin{array}{cccc} 6 & 3 & 0 & 9\\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \end{array}$
We label the rows of the MINIMOG array as follows:

1. the first row has label 0,
2. the second row has label +,
3. the third row has label –

A col (or column) is a placement of three + signs in a column of the MINIMOG array. A tet (or tetrad) is a placement of 4 + signs having entries corresponding (as explained below) to a tetracode.

+	+	+	+

0	0	0	0

+
+	+	+

0	+	+	+

+

+	+	+

0	-	-	-


 	+
+	 	+
+

+	0	+	-

 	 	 	+
+	+
+

+	+	-	0

 	 	+
+	 	 	+
+

+	-	0	+

 	+
+
+	 	+

-	0	-	+


 	 	+
+
+	 	 	+

-	+	0	-


 	 	 	+
+
+	+

-	-	+	0



Each line in $\mathbf{F}_3^2$ with finite slope occurs once in the $3\times 3$ part of some tet. The odd man out for a column is the label of the row corresponding to the non-zero digit in that column; if the column has no non-zero digit then the odd man out is a “?”. Thus the tetracode words associated in this way to these patterns are the odd men out for the tets. The signed hexads are the combinations $6$-sets obtained from the MINIMOG from patterns of the form

col-col, col+tet, tet-tet, col+col-tet.Lemma 3 (Conway, [CS1], chapter 11, page 321) If we ignore signs, then from these signed hexads we get the 132 hexads of a Steiner system $S(5,6,12)$. These are all possible $6$-sets in the shuffle labeling for which the odd men out form a part (in the sense that an odd man out “?” is ignored, or regarded as a “wild-card”) of a tetracode word and the column distribution is not $0,1,2,3$ in any order.

Furthermore, it is known [Co1] that the Steiner system $S(5,6,12)$ in the shuffle labeling has the following properties.

1. There are $11$ hexads with total $21$ and none with lower total.
2. The complement of any of these $11$ hexads in $\{0,1,...,11\}$ is another hexad.
3. There are $11$ hexads with total $45$ and none with higher total.

### Mathematical blackjack

Mathematical blackjack is a 2-person combinatorial game whose rules will be described below. What is remarkable about it is that a winning strategy, discovered by Conway and Ryba [CS2] and [KR], depends on knowing how to determine hexads in the Steiner system $S(5,6,12)$ using the shuffle labeling.

Mathematical blackjack is played with 12 cards, labeled $0,\dots ,11$ (for example: king, ace, $2$, $3$, …, $10$, jack, where the king is $0$ and the jack is $11$). Divide the 12 cards into two piles of $6$ (to be fair, this should be done randomly). Each of the $6$ cards of one of these piles are to be placed face up on the table. The remaining cards are in a stack which is shared and visible to both players. If the sum of the cards face up on the table is less than 21 then no legal move is possible so you must shuffle the cards and deal a new game. (Conway [Co2] calls such a game *={0|0}, where 0={|}; in this game the first player automatically wins.)

1. Players alternate moves.
2. A move consists of exchanging a card on the table with a lower card from the other pile.
3. The player whose move makes the sum of the cards on the table under 21 loses.

The winning strategy (given below) for this game is due to Conway and Ryba [CS2], [KR]. There is a Steiner system $S(5,6,12)$ of hexads in the set $\{0,1,...,11\}$. This Steiner system is associated to the MINIMOG of in the “shuffle numbering” rather than the “modulo $11$ labeling”.

Proposition 6Lemma 7 The probability that the first player has a win in mathematical blackjack (with a random initial deal) is $6/7$.

An example is given in this expository hexads_sage. This paper was inspired by the research done in Ann Luers’ thesis.

### Bibliography

[Cu1] R. Curtis, “The Steiner system $S(5,6,12)$, the Mathieu group $M_{12}$, and the kitten,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Cu2] —, “A new combinatorial approach to $M_{24}$,” Math Proc Camb Phil Soc 79(1976)25-42
[Co1] J. Conway, “Hexacode and tetracode – MINIMOG and MOG,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Co2] —, On numbers and games (ONAG), Academic Press, 1976.
[CS1] J. Conway and N. Sloane, Sphere packings, Lattices and groups, 3rd ed., Springer-Verlag, 1999.
[CS2] —, “Lexicographic codes: error-correcting codes from game theory,” IEEE Trans. Infor. Theory32(1986)337-348.
[KR] J. Kahane and A. Ryba, “The hexad game,” Electronic Journal of Combinatorics, 8 (2001)

# Simple unsolved math problem, 8

Sylver coinage is a game for 2 players invented by John H. Conway.

The two players take turns naming positive integers that are not the sum of non-negative multiples of any previously named integers. The player who is forced to name 1 loses.

James Joseph Sylvester proved the following fact.

Lemma: If a and b are relatively prime positive integers, then (a – 1)(b – 1) – 1 is the largest number that is not a sum of nonnegative multiples of a and b.

Therefore, if a and b have no common prime factors and are the first two moves, this formula gives an upper bound on the next number that can still be played.

R. L. Hutchings proved the following fact.

Theorem: If the first player selects any prime number $p>3$ as a first move then he/she has a winning strategy.

Very little is known about the subsequent winning moves. That is, a winning strategy exists but it’s not know what it is!

Unsolved problem:Are there any non-prime winning opening moves in Sylver coinage?

For further info, Sicherman maintains a Sylver coinage game webpage.

# 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)


# How do I construct … in GAP?

“How do I construct … in GAP?” You may view the html source code
for the GAP commands without the output or GAP prompt.

David Joyner.

Questions

 How do I construct a … group? permutation dihedral  cyclicconjugacy classes of a finitely presented How do I … a polynomial? factor find roots of evaluate Groebner basis of ideal of Brauer characters How do I find the … of a group representation? How do I compute an mod m, where A is …? Given a group G, how do I compute … ?

• permutation:
To construct a permutation group, write down generators in disjoint cycle notation,
put them in a list (i.e., surround them by square brackets), andThe permutation group G generated by the cycles
(1,2)(3,4) and (1,2,3):
gap> G:=Group((1,2)(3,4),(1,2,3));

Group([ (1,2)(3,4), (1,2,3) ])


This is of course a subgroup of the symmetric group S4 on 4
letters.
Indeed, this G is in fact the alternating group
on four letters, A4.

By virtue of the fact that the permutations generating G employ
integers less than or equal to 4, this group G
is a subgroup of the symmetric group S4 on 4
letters. Some permutation groups have special constructions:

gap> S4:=SymmetricGroup(4);
Sym( [ 1 .. 4 ] )
gap> A4:=AlternatingGroup(4);
Alt( [ 1 .. 4 ] )
gap> IsSubgroup(S4,G);
true
gap> IsSubgroup(A4,G);
true
gap> S3:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> IsSubgroup(S3,G);
false



• dihedral
To construct a dihedral group, use the special “DihedralGroup” command:
gap> G:=DihedralGroup(6);

gap> Size(G);
6
gap> f:=GeneratorsOfGroup( G );
[ f1, f2 ]
gap> f[1]^2; f[2]^3;
identity of ...
identity of ...
gap> f[1]^2= f[2]^3;
true



• cyclic group
To construct a cyclic group, you may
construct integers mod n:

gap> R:=ZmodnZ( 12);
(Integers mod 12)
gap> a:=Random(R);
ZmodnZObj( 11, 12 )
gap> 4*a;
ZmodnZObj( 8, 12 )
gap> b:=Random(R);
ZmodnZObj( 9, 12 )
gap> a+b;
ZmodnZObj( 8, 12 )


or use the special “CyclicGroup” command

gap> G:=CyclicGroup(12);
pc group of size 12 with 3 generators
gap> a:=Random(G);
f3^2
gap> f:=GeneratorsOfGroup( G );
[ f1, f2, f3 ]
gap> f[1]^4;
f3
gap> f[1]^12;
identity of ...



• conjugacy:
The conjugacy classes of a group G are computed using
the “ConjugacyClasses” command. This is a list
of classes{x^-1*g*x | x in G}.

gap> G:=SL(2,7);
SL(2,7)
gap> CG:=ConjugacyClasses(G);
[ [ [ Z(7)^0, 0*Z(7) ], [ 0*Z(7), Z(7)^0 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^5 ] ]^G,
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]^G,
[ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]^G,
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, 0*Z(7) ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^4 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7) ] ]^G,
[ [ Z(7)^4, 0*Z(7) ], [ 0*Z(7), Z(7)^2 ] ]^G,
[ [ Z(7)^5, 0*Z(7) ], [ 0*Z(7), Z(7) ] ]^G ]
gap> g:=Representative(CG[3]); Order(g);
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]
14
gap> g:=Representative(CG[4]); Order(g);
[ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]
2
gap> g:=Representative(CG[5]); Order(g);
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]
7
gap> g:=Representative(CG[6]); Order(g);
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]
7
gap>


• presented
To construct a finitely presented group in GAP, use the
“FreeGroup” and “” commands. Here is one example.

gap> M12 := MathieuGroup( 12 );
Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6), (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])
gap> F := FreeGroup( "a", "b", "c" );
free group on the generators [ a, b, c ]
gap> words := [ F.1, F.2 ];
[ a, b ]
gap> P := PresentationViaCosetTable( M12, F, words );
presentation with 3 gens and 10 rels of total length 97
gap> TzPrintRelators( P );
#I  1. c^2
#I  2. b^4
#I  3. a*c*a*c*a*c
#I  4. a*b^2*a*b^-2*a*b^-2
#I  5. a^11
#I  6. a^2*b*a^-2*b^2*a*b^-1*a^2*b^-1
#I  7. a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1
#I  8. a^2*b*a^2*b^2*a^-1*b*a^-1*b^-1*a^-1*b^-1
#I  9. a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c
#I  10. a^4*b*a^2*b*a^-2*c*a*b*a^-1*c
gap> G := FpGroupPresentation( P );
fp group on the generators [ a, b, c ]
gap> RelatorsOfFpGroup( G );
[ c^2, b^4, a*c*a*c*a*c, a*b^-2*a*b^-2*a*b^-2, a^11, a^2*b*a^-2*b^-2*a*b^-1*a^2*b^-1, a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1,
a^2*b*a^2*b^-2*a^-1*b*a^-1*b^-1*a^-1*b^-1, a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c, a^4*b*a^2*b*a^-2*c*a*b*a^-1*c ]
gap> Size(M12);
95040
gap> Size(G);
95040
gap> IsomorphismGroups(G,M12);
????????


The last command is computationally intensive and requires more
than the default memory allocation of 256M of RAM.

Here is another example.

gap> F := FreeGroup( "a", "b");
free group on the generators [ a, b ]
gap> G:=F/[F.1^2,F.2^3,F.1*F.2*F.1^(-1)*F.2^(-1)];
fp group on the generators [ a, b ]
gap> Size(G);
6



• rref
The key command for row reduction is “TriangulizeMat”.
The following example illustrates the syntax.

gap> M:=[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
[ [ 1, 2, 3, 4, 5 ], [ 1, 2, 1, 2, 1 ], [ 1, 1, 0, 0, 0 ] ]
gap> TriangulizeMat(M);
gap> M;
[ [ 1, 0, 0, -1, 1 ], [ 0, 1, 0, 1, -1 ], [ 0, 0, 1, 1, 2 ] ]
gap> Display(M);
[ [   1,   0,   0,  -1,   1 ],
[   0,   1,   0,   1,  -1 ],
[   0,   0,   1,   1,   2 ] ]
gap> M:=Z(3)^0*[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
[ [ Z(3)^0, Z(3), 0*Z(3), Z(3)^0, Z(3) ],
[ Z(3)^0, Z(3), Z(3)^0, Z(3), Z(3)^0 ],
[ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ] ]
gap> TriangulizeMat(M);
gap> Display(M);
1 . . 2 1
. 1 . 1 2
. . 1 1 2
gap>


• kernel:
There are different methods for matrices over the integers and
matrices over a field.For integer entries, related commands include
“NullspaceIntMat” and “SolutionNullspaceIntMat”
in section

25.1 “Linear equations over the integers and Integral Matrices”

of the reference manual.

gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
gap> NullspaceIntMat(M);
[ [ 1, -2, 1 ] ]
gap> SolutionNullspaceIntMat(M,[0,0,1]);
[ fail, [ [ 1, -2, 1 ] ] ]
gap> SolutionNullspaceIntMat(M,[0,0,0]);
[ [ 0, 0, 0 ], [ [ 1, -2, 1 ] ] ]
gap> SolutionNullspaceIntMat(M,[1,2,3]);
[ [ 1, 0, 0 ], [ [ 1, -2, 1 ] ] ]



Here (0,0,1) is not in the image of M
(under v-> v*M) but (0,0,0) and (1,2,3) are.

For field entries, related commands include
“NullspaceMat” and “TriangulizedNullspaceMat”
in section

24.6 “Matrices Representing Linear Equations and the Gaussian Algorithm”

of the reference manual.

gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
gap> NullspaceMat(M);
[ [ 1, -2, 1 ] ]
gap> TriangulizedNullspaceMat(M);
[ [ 1, -2, 1 ] ]
gap> M:=[[1,2,3,1,1],[4,5,6,1,1],[7,8,9,1,1],[1,2,3,1,1]];
[ [ 1, 2, 3, 1, 1 ], [ 4, 5, 6, 1, 1 ], [ 7, 8, 9, 1, 1 ],
[ 1, 2, 3, 1, 1 ] ]
gap> NullspaceMat(M);
[ [ 1, -2, 1, 0 ], [ -1, 0, 0, 1 ] ]
gap> TriangulizedNullspaceMat(M);
[ [ 1, 0, 0, -1 ], [ 0, 1, -1/2, -1/2 ] ]



• characteristic polynomial:
24.12.1 of the GAP reference manual
for examples of characteristic polynomial of a
square matrix (“CharacteristicPolynomial”) and
section

56.3
for examples of the “characteristic polynomial”
(called a “TracePolynomial”) of an
element of a field extension.

• character:
GAP contains very extensive character theoretic functions
and data libraries (including an interface the character table in the
Atlas).
Here is just one simple example.

gap> G:=Group((1,2)(3,4),(1,2,3));
Group([ (1,2)(3,4), (1,2,3) ])
gap> T:=CharacterTable(G);
CharacterTable( Alt( [ 1 .. 4 ] ) )
gap> Display(T);
CT1

2  2  2  .  .
3  1  .  1  1

1a 2a 3a 3b
2P 1a 1a 3b 3a
3P 1a 2a 1a 1a

X.1     1  1  1  1
X.2     1  1  A /A
X.3     1  1 /A  A
X.4     3 -1  .  .

A = E(3)^2
= (-1-ER(-3))/2 = -1-b3
gap> irr:=Irr(G);
[ Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, 1, 1 ] ),
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] ),
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3), E(3)^2 ] ),
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 3, -1, 0, 0 ] ) ]
gap> Display(irr);
[ [       1,       1,       1,       1 ],
[       1,       1,  E(3)^2,    E(3) ],
[       1,       1,    E(3),  E(3)^2 ],
[       3,      -1,       0,       0 ] ]
gap> chi:=irr[2]; gamma:=CG[3]; g:=Representative(gamma); g^chi;
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] )
(1,2,3)^G
(1,2,3)
E(3)^2



For further details and examples, see chapters
69
72 of the
GAP reference manual.

• brauer:
Just a simple example of what GAP can do here.
To construct a Brauer character table:

gap> G:=Group((1,2)(3,4),(1,2,3));
Group([ (1,2)(3,4), (1,2,3) ])
gap> irr:=IrreducibleRepresentations(G,GF(7));
[ [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^0 ] ] ],

[ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^4 ] ] ],

[ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^2 ] ] ],

[ (1,2)(3,4), (1,2,3) ] -> [

[ [ 0*Z(7), Z(7)^3, Z(7)^0 ], [ 0*Z(7), Z(7)^3, 0*Z(7) ],
[ Z(7)^0, Z(7)^3, 0*Z(7) ] ],
[ [ 0*Z(7), Z(7)^0, 0*Z(7) ],
[ 0*Z(7), 0*Z(7), Z(7)^0 ], [ Z(7)^0, 0*Z(7), 0*Z(7) ] ]

] ]
gap> brvals := List(irr,chi-> List(ConjugacyClasses(G),c->
BrauerCharacterValue(Image(chi, Representative(c)))));
[ [ 1, 1, 1, 1 ], [ 1, 1, E(3)^2, E(3) ], [ 1, 1, E(3), E(3)^2 ],
[ 3, -1, 0, 0 ] ]
gap> Display(brvals);
[ [       1,       1,       1,       1 ],

[       1,       1,  E(3)^2,    E(3) ],

[       1,       1,    E(3),  E(3)^2 ],

[       3,      -1,       0,       0 ] ]
gap>


List(ConjugacyClasses(G),c->BrauerCharacterValue(Image(chi, Representative(c)))));
#Display(brvals);
T:=CharacterTable(G);
Display(T);
–>

• polynomial
There are various ways to construct a polynomial in GAP.

gap> Pts:=Z(7)^0*[1,2,3];
[ Z(7)^0, Z(7)^2, Z(7) ]
gap> Vals:=Z(7)^0*[1,2,6];
[ Z(7)^0, Z(7)^2, Z(7)^3 ]
gap> g:=InterpolatedPolynomial(GF(7),Pts,Vals);
Z(7)^5*x_1^2+Z(7)


Or:

gap> p:=3;; F:=GF(p);;
gap> R:=PolynomialRing(F,["x1","x2"]);
PolynomialRing(..., [ x1, x2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R);;
gap> x1:=vars[1]; x2:=vars[2];
x1
x2
gap> p:=x1^5-x2^5;
x1^5-x2^5
gap> DivisorsMultivariatePolynomial(p,R);
[ x1^4+x1^3*x2+x1^2*x2^2+x1*x2^3+x2^4, x1-x2 ]


Or:

gap> x:=X(Rationals);
x_1
gap> f:=x+x^2+1;
x_1^2+x_1+1
gap> Value(f,[x],[1]);
3


• factor
To factor a polynomial in GAP, there is one command for
univariate polynomials (“Factors”) and another command for
multivariate polynomials (“DivisorsMultivariatePolynomial”).For a factoring a univariate polynomial,
GAP provides only methods over finite fields
and over subfields of cyclotomic fields.
examples given in section

64.10 “Polynomial Factorization”
for more details.For multivariate polynomials,
a very slow algorithm has been implemented in GAP
and an interface to a very fast algorithm in
Singular
has been implemented for those who have both Singular and
the GAP Singular package
installed. The former of these was
illustrated above in
“polynomial” above.
(Again, the ground field must be a finite field
or a subfields of cyclotomic fields.)
For the latter, please see the example
in the (GAP-)Singular manual
FactorsUsingSingularNC.

• roots
There are some situtations where GAP does find the roots
of a polynomial but GAP does not do this generally.
(The roots must generate either a finite field
or a subfield of a cyclotomic field.) However, there is a package called

which must be installed which does help to do this
for polynomials with rational coefficients
(radiroot itself requires other packages to be installed;
please see the webpage for more details).The “Factors” command actually has an option which allows you to
increase the groundfield so that a factorization actually
returns the roots. Please see the
examples given in section

64.10 “Polynomial Factorization”
for more details.Here is a second appoach.

gap> p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2;
3
4
GF(3^4)
Z(3^4)^79
2
gap>  x:=X(F,1); f:=x^r-c*x+c-1;
x_1
x_1^2+Z(3^4)^39*x_1+Z(3^4)^36
gap>  F_f:=FieldExtension( F, f );
AsField( GF(3^4), GF(3^8) )
gap>  alpha:=RootOfDefiningPolynomial(F_f);
Z(3^4)^36
gap> Value(f,[x],[alpha]);
0*Z(3)



Here is a third. First, enter the following program:

RootOfPolynomial:=function(f,R)
local F0,Ff,a;
F0:=CoefficientsRing(R);
Ff:=FieldExtension(F0,f);
a:=RootOfDefiningPolynomial(Ff);
return a;
end;


Here’s how this can be used to find a root:

gap> F:=Rationals;
Rationals
gap> x:=X(F,1); f:=x^2+x+1;
x_1
x_1^2+x_1+1
gap> R:=PolynomialRing( F, [ x ]);
PolynomialRing(..., [ x_1 ])
gap> a:=RootOfPolynomial(f,R);
E(3)
gap> # check:
gap> Value(f,[x],[a]);
0


1. In the GAP Forum:

Hensel lifting discussion
.
2. In the manual,

Galois groups
.

• evaluate:
The relevant command is “Value”. There are several examples already on
64.7 Multivariate polynomials of the manual.
For sparse uivariate polynomials, there is also the command
“ValuePol” in section
23.6 of the manual.

• integer power
This is easy and intuitive:

gap> a:=1000; n:=100000; m:=123;
1000
100000
123
gap> a^n mod m;
1



• matrix power:
This too is easy and intuitive:

gap> A:=[[1,2],[3,4]]; n:=100000; m:=123;
[ [ 1, 2 ], [ 3, 4 ] ]
100000
123
gap> A^n mod m;
[ [ 1, 41 ], [ 0, 1 ] ]


• polynomial power
GAP allows you to do arithmetic over the polynomial
ring R[x], where R = Z/nZ (where n is a positive integer).
Here’s an example.

gap> Z4:=ZmodnZ(4);
(Integers mod 4)
gap> R:=UnivariatePolynomialRing(Z4,1);
PolynomialRing(..., [ x ])
gap> x:=IndeterminatesOfPolynomialRing(R)[1];
x
gap> I:=TwoSidedIdealByGenerators( R,[x^8-x^0]);
two-sided ideal in PolynomialRing(..., [ x ]), (1 generators)
gap> gen:=x^8-x^0;
x8-ZmodnZObj(1,4)
gap> QuotientRemainder(R,x^8,gen);
[ ZmodnZObj(1,4), ZmodnZObj(1,4) ]
gap> QuotientRemainder(R,x^15,gen);
[ x^7, x^7 ]
gap> QuotientRemainder(R,x^15+x^8,gen);
[ x^7+ZmodnZObj(1,4), x^7+ZmodnZObj(1,4) ]
gap> PowerMod( R, x+x^0, 15, gen );
ZmodnZObj(0,4)
gap> PowerMod( R, x, 15, gen );
x^7



• Groebner basis
GAP’s Groebner bases algorithms are relatively slow
and are included mostly for simple examples and for
teaching purposes. However, a GAP interface to a very
fast algorithm in Singular
has been implemented for those who have both Singular and
the
GAP Singular package
installed. The former of these is
illustrated in section
64.17 Groebner bases of the GAP manual.
For the latter, please see the example
in the (GAP-)Singular manual
GroebnerBasis.

• normal subgroup:
Here is an example:

gap> G := AlternatingGroup( 5 );
Group( (1,2,5), (2,3,5), (3,4,5) )
gap> normal := NormalSubgroups( G );
[ Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ),
Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (1,2)(3,4), (1,3)(4,5), (1,4)(2,3) ] ) ]


GAP Forum response to a related question.
2. The

xgap
package displays subgroup lattices graphically.

• abelian subgroup
One idea to compute all the abelian subgroups is to compute all the
subgroups then “filter” out the abelian ones.
Here is an illustration, taked from a
GAP Forum response Volkmar Felsch.

gap> G := AlternatingGroup( 5 );
Group( (1,2,5), (2,3,5), (3,4,5) )
gap> classes := ConjugacyClassesSubgroups( G );
[ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (1,2,3,4,5) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (3,4,5), (1,2)(4,5) ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (1,2,3,4,5), (2,5)(3,4) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (2,3)(4,5), (2,4)(3,5), (3,4,5) ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), (3,4,5) ), Group(
(1,2,5), (2,3,5), (3,4,5) ) ) ]
gap> cl := classes[4];
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] ) )
gap> length := Size( cl );
5
gap> rep := Representative( cl );
Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] )
gap> order := Size( rep );
4
gap> IsAbelian( rep );
true
gap> abel := Filtered( classes, cl -> IsAbelian( Representative( cl ) ) );
[ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (1,2,3,4,5) ] ) ) ]


• homology
This depends on how the group is given. For example, suppose that
G is a permutation group with generators genG and
H is a permutation group with generators genH. To find a
homomorphism from G to H, one may use the
“GroupHomomorphismByImages” or “GroupHomomorphismByImagesNC”
commands. For examples of the syntax, please see
section
38.1 Creating Group Homomorphisms.Here’s an illustration of how to convert a finitely presented
group into a permutation group.

gap> p:=7;
7
gap> G:=PSL(2,p);
Group([ (3,7,5)(4,8,6), (1,2,6)(3,4,8) ])
gap> H:=SchurCover(G);
fp group of size 336 on the generators [ f1, f2, f3 ]
gap> iso:=IsomorphismPermGroup(H);
[ f1, f2, f3 ] -> [ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
(2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
15)(14,16) ]
gap> H0:=Image(iso);                       # 2-cover of PSL2
Group([ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
(2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
15)(14,16) ])
gap> IdGroup(H0);
[ 336, 114 ]
gap> IdGroup(SL(2,7));
[ 336, 114 ]
gap>


• semi-direct product(Contributed by Nilo de Roock):
As you can easily verify, D8 is isomorphic to C2:C4. Or in GAP…

N:=CyclicGroup(IsPermGroup,4);
G:=CyclicGroup(IsPermGroup,2);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,GeneratorsOfGroup(G),[Elements(AutN)[2]]);
NG:=SemidirectProduct(G,f,N);


Verify with

StructureDescription(NG);


• semi-direct products(Contributed by Nilo de Roock):
The following shows how to construct all non-abelian groups
of order 12 as semi-direct products. These products are not
trivial yet small enough to verify by hand.

#D12 = (C2 x C2) : C3
G1:=CyclicGroup(IsPermGroup,2);
G2:=CyclicGroup(IsPermGroup,2);
G:=DirectProduct(G1,G2);
N:=CyclicGroup(IsPermGroup,3);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
NG:=SemidirectProduct(G,f,N);
Print(str(NG));
Print("\n");

#T = C4 : C3
G:=CyclicGroup(IsPermGroup,4);
N:=CyclicGroup(IsPermGroup,3);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
NG:=SemidirectProduct(G,f,N);
Print(str(NG));
Print("\n");

#A4 = C3 : (C2 x C2)
G:=CyclicGroup(IsPermGroup,3);
N1:=CyclicGroup(IsPermGroup,2);
N2:=CyclicGroup(IsPermGroup,2);
N:=DirectProduct(G1,G2);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3]],[Elements(AutN)[1],Elements(AutN)[4],Elements(AutN)[5]]);
NG:=SemidirectProduct(G,f,N);
Print(str(NG));
Print("\n");


• cohomology
GAP will compute the Schur multiplier
H2(G,C) using the
“AbelianInvariantsMultiplier” command.
Here is an example showing how to find H2(A5,C),
where A5 is the alternating group on 5 letters.

gap> A5:=AlternatingGroup(5);
Alt( [ 1 .. 5 ] )
gap> AbelianInvariantsMultiplier(A5);
[ 2 ]


So, H2(A5,C) is Z/2Z.

1. See section

37.23
and
section

37.24
of the GAP manual.
2. See D. Holt’s GAP package
cohomolo.

# Sports ranking methods, 3

This is the third of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the random walker ranking.

We follow the presentation in the paper by Govan and Meyer (Ranking National Football League teams using Google’s PageRank). The table of “score differentials” based on the table in a previous post is:

$\begin{tabular}{c|cccccc} \verb+x\y+ & Army & Bucknell & Holy Cross & Lafayette & Lehigh & Navy \\ \hline Army & 0 & 0 & 1 & 0 & 0 & 0 \\ Bucknell & 2 & 0 & 0 & 2 & 3 & 0 \\ Holy Cross & 0 & 3 & 0 & 4 & 14 & 0 \\ Lafayette & 10 & 0 & 0 & 0 & 0 & 0 \\ Lehigh & 2 & 0 & 0 & 11 & 0 & 0 \\ Navy & 11 & 14 & 8 & 22 & 6 & 0 \\ \end{tabular}$
This leads to the following matrix:

$M_0=\left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 2 & 3 & 0 \\ 0 & 3 & 0 & 4 & 14 & 0 \\ 10 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 11 & 0 & 0 \\ 11 & 14 & 8 & 22 & 6 & 0 \\ \end{array}\right) .$

The edge-weighted score-differential graph associated to $M_0$ (regarded as a weighted adjacency matrix) is in the figure below.

This matrix $M_0$ must be normalized to create a (row) stochastic matrix:

$M = \left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ {2}/{7} & 0 & 0 /{7} /{7} & 0 \\ 0 /{7} & 0 /{21} /{3} & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ {2}/{13} & 0 & 0 /{13} & 0 & 0 \\ {11}/{61} /{61} /{61} /{61} /{61} & 0 \\ \end{array}\right) .$

Next, to insure it is irreducible, we replace $M$ by $A=(M+J)/2$, where $J$ is the $6\times 6$ doubly stochastic matrix with every entry equal to $1/6$:

$A=\left(\begin{array}{cccccc} {1}/{12} & 1/{12} & 7/{12} & 1/{12} & 1/{12} & 1/{12} \\ {19}/{84} & 1/{12} & 1/{12} & 19/{84} & 25/{84} & 1/{12} \\ {1}/{12} & 13/{84} & 1/{12} & 5/{28} & 5/{12} & 1/{12} \\ {7}/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} \\ {25}/{156} & 1/{12} & 1/{12} & 79/{156} & 1/{12} & 1/{12} \\ {127}/{732} & 145/{732} & 109/{732} & 193/{732} & 97/{732} & 1/{12} \end{array}\right).$

Let

${\bf v}_0 = \left( \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6}\right).$

The ranking determined by the random walker method is the reverse of the left eigenvector of $A$ associated to the largest eigenvalue $\lambda_{max}=1$ (by reverse, I mean that the vector ranks the teams from worst-to-best, not from best-to-worst, as we have seen in previous ranking methods).
In other words, the vector

${\bf r}^*=\lim_{n\to \infty}{\bf v}_0A^n.$

This is approximately

${\bf r}^* \cong \left(0.2237\dots ,\,0.1072\dots ,\,0.2006\dots ,\,0.2077\dots ,\,0.1772\dots ,\,0.0833\dots \right).$

Its reverse gives the ranking:

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

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

# Sports ranking methods, 2

This is the second of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses Keener’s method (see J.P. Keener, The Perron-Frobenius theorem and the ranking of football, SIAM Review 35 (1993)80-93 for details).

See the first post in the series for a discussion of the data we’re using to explain this method. We recall the table of results:

 X\Y Army Bucknell Holy Cross Lafayette Lehigh Navy Army x 14-16 14-13 14-24 10-12 8-19 Bucknell 16-14 x 27-30 18-16 23-20 10-22 Holy Cross 13-14 30-27 x 19-15 17-13 9-16 Lafayette 24-14 16-18 15-19 x 12-23 17-39 Lehigh 12-10 20-23 13-17 23-12 x 12-18 Navy 19-8 22-10 16-9 39-17 18-12 x

Win-loss digraph of the Patriot league mens baseball from 2015

Suppose T teams play each other. Let $A=(a_{ij})_{1\leq i,j\leq T}$ be a non-negative square matrix determined by the results of their games, called the preference matrix. In his 1993 paper, Keener defined the score of the $i$th team to be given by

$s_i = \frac{1}{n_i}\sum_{j=1}^T a_{ij}r_j,$

where $n_i$ denotes the total number of games played by team $i$ and ${\bf r}=(r_1,r_2,\dots ,r_T)$ is the rating vector (where $r_i\geq 0$ denotes the rating of team $i$).

One possible preference matrix the matrix $A$ of total scores obtained from the pre-tournament table below:

$A = \left(\begin{array}{rrrrrr} 0 & 14 & 14 & 14 & 10 & 8 \\ 16 & 0 & 27 & 18 & 23 & 28 \\ 13 & 30 & 0 & 19 & 27 & 43 \\ 24 & 16 & 15 & 0 & 12 & 17 \\ 12 & 20 & 43 & 23 & 0 & 12 \\ 19 & 42 & 30 & 39 & 18 & 0 \end{array}\right),$

(In this case, $n_i=4$ so we ignore the $1/n_i$ factor.)

In his paper, Keener proposed a ranking method where the ranking vector ${\bf r}$ is proportional to its score. The score is expressed as a matrix product $A{\bf r}$, where $A$ is a square preference matrix. In other words, there is a constant $\rho>0$ such that $s_i=\rho r_i$, for each $i$. This is the same as saying $A {\bf r} = \rho {\bf r}$.

The Frobenius-Perron theorem implies that $S$ has an eigenvector ${\bf r}=(r_1,r_2,r_3,r_4,r_5,r_6)$ having positive entries associated to the largest eigenvalue $\lambda_{max}$ of $A$, which has (geometric) multiplicity $1$. Indeed, $A$ has maximum eigenvalue $\lambda_{max}= 110.0385...$, of multiplicity $1$, with eigenvector

${\bf r}=(1, 1.8313\dots , 2.1548\dots , 1.3177\dots , 1.8015\dots , 2.2208\dots ).$

Therefore the teams, according to Kenner’s method, are ranked,

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

This gives a prediction failure rate of just $6.7\%$.