This is the first of a series of expository posts on matrix-theoretic sports ranking methods. This post, which owes much to discussions with TS Michael, discusses Massey’s method.
Massey’s method, currently in use by the NCAA (for football, where teams typically play each other once), was developed by Kenneth P. Massey
while an undergraduate math major in the late 1990s. We present a possible variation of Massey’s method adapted to baseball, where teams typically play each other multiple times.
There are exactly 15 pairing between these teams. These pairs are sorted lexicographically, as follows:
(1,2),(1,3),(1,4), …, (5,6).
In other words, sorted as
Army vs Bucknell, Army vs Holy Cross, Army vs Lafayette, …, Lehigh vs Navy.
The cumulative results of the 2016 regular season are given in the table below. We count only the games played in the Patriot league, but not including the Patriot league post-season tournament (see eg, the Patriot League site for details). In the table, the total score (since the teams play multiple games against each other) of the team in the vertical column on the left is listed first. In other words, ”a – b” in row $i$ and column $j$ means the total runs scored by team 
| 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
In this ordering, we record their (sum total) win-loss record (a 1 for a win, -1 for a loss) in a 
We also record their total losses in a column vector:
The Massey ranking of these teams is a vector 
While the corresponding linear system is over-determined, we can look for a best (in the least squares sense) approximate solution using the orthogonal projection formula
valid for matrices 
Massey’s clever idea is to solve
by row-reduction and determine the rankings from the parameterized form of the solution. To this end, we compute
and
Then we compute the rref of
which is
If 
Therefore
Lafayette 
If we use this ranking to predict win/losses over the season, it would fail to correctly predict Army vs Holy Cross (Army won), Bucknell vs Lehigh, and Lafayette vs Army. This gives a prediction failure rate of 
Team 
Team 
denote some fixed ranking (where 
is some permutation of 
). An upset occurs when a lower ranked team beats an upper ranked team. For each ranking, 
denote the total number of upsets. The minimum upset problem is to find an “efficient” construction of a ranking for which 
denote the number of times Team i beat team $j$ minus the number of times Team j beat Team i. We regard this matrix as the signed adjacency matrix of a digraph 
. Our goal is to find a Hamiltonian (undirected) path through the vertices of 
, with rows and columns indexed by the teams in some fixed order. The entry in the i-th row and the j-th column is defined by
, and those that lost the most at the bottom.
board may be represented graph theoretically as a Hamiltonian cycle on a particular graph with 
vertices, of which 
of them have degree 
, 
have degree 
and the remaining 
vertices have degree 
. The problem of finding an algorithm to find a hamiltonian circuit in a general graph is known to be NP complete. The problem of finding an efficient algorithm to search for such a tour therefore appears to be very hard problem. In [BK], C. Bailey and M. Kidwell proved that complete even king tours do not exist. They left the question of the existence of complete odd tours open but showed that if they did exist then it would have to end at the edge of the board.
and 
,
, 
and 
or 
(or both) is odd,
, 
and the tour is “rapidly filling”.
array of neighboring squares on the board. A foursome is called completed if all four squares have been visited by the the king at some point in a tour, including the case where the king is still on one of the four squares.
denote the change in the number of completed foursomes and let 
denote the change in the number of completed neighbor pairs. Note that 
then 
. If 
then 
. If 
then 
. If 
then 
. 
. If 
. If 
. If 
. 
and 
.
denote the total number of completed neighbor pairs after a given point of a given odd king tour. We may represent the values of 
. Here 
is the total number of completed neighbor pairs after the first move, 
. In particular, the parity of 
, which is obviously even. This is a contradiction. QED
is odd. This follows from a computer computation, an argument from Sands [Sa], and the sequence of lemmas that follow. The proofs are in the original paper, and omitted.
denote the number of completed foursomes in a given odd king tour. Let $M$ denote the number of moves in a given odd king tour. Let 
, where 
are defined as above. Then 
equals 
, 
only occurs when 
.
denote the largest number of non-overlapping ![[m/2][n/2]](https://s0.wp.com/latex.php?latex=%5Bm%2F2%5D%5Bn%2F2%5D&bg=ffffff&fg=323232&s=0&c=20201002)
0’s.
on an 
then all 
boards have nearly complete odd king tours.
, ![{\mathbb{Z}}[V]](https://s0.wp.com/latex.php?latex=%7B%5Cmathbb%7BZ%7D%7D%5BV%5D&bg=ffffff&fg=323232&s=0&c=20201002)
.
and 
are linearly equivalent and write 
if 
is a principal divisor, i.e., if 
for some function 
. Note that if ![[D]](https://s0.wp.com/latex.php?latex=%5BD%5D&bg=ffffff&fg=323232&s=0&c=20201002)
the element of the Jacobian determined by 
for all vertices 
. We write 
to mean that 
is the set of all effective divisors linearly equivalent to 
, then 
. We note also that if 
, then 
between graphs 
and 
can be uniquely defined by specifying where the vertices of 
go. If 
and 
then this is a list of length 
consisting of elements taken from the 
vertices in 
.
and let 
denote the “cube graph” (actually the unit square) in 
.
by
to be a subgraph of 
is called harmonic if for all vertices 
, the quantity
in 
.
. In this post, I’d like to give some more examples, based on a 
. The Cayley graph of 
and the set of edges is defined by 
has weight 
. However, if 
as an edge-weighted (undirected) graph. 
, define
to be the set of all neighbors of 
in 
to be the set of all neighbors 
),
to be the set of all non-neighbors 
),
, 
, 
, denoted 
, if it consists of 
, 
, 
are as above. Here, 
is the set of weights, including 
listed in the table below
![GF(9) = GF(3)[x]/(x^2+1) = \{0,1,2,x,x+1,x+2,2x,2x+1,2x+2\}.](https://s0.wp.com/latex.php?latex=GF%289%29+%3D+GF%283%29%5Bx%5D%2F%28x%5E2%2B1%29+%3D+%5C%7B0%2C1%2C2%2Cx%2Cx%2B1%2Cx%2B2%2C2x%2C2x%2B1%2C2x%2B2%5C%7D.++&bg=ffffff&fg=323232&s=0&c=20201002)
and whose edges 
are those pairs for which 
.
.
be a finite set and let 
denote binary relations on 
). The dual of a relation 
is the set
. We say 
is an 
-class association scheme on 
for all $i\not= j$.
(and if 
for all 
and all 
, define
, the integer 
is a constant, denoted 
.
and 
of the association scheme 
, where 
, 
.
is 
is the identity matrix. In the above computation, Sage has also verified that they commute and satisfy
. If the level curves of 
be a prime power such that 
. Note that this implies that the unique finite field of order 
, has a square root of 
and
if and only if 
. By definition 
is the 
(with multiplicity 
(both with multiplicity 
, where 
is prime, then 
has order 
.
” above; I was having trouble rendering it in html.) Below is an example.
, it has only three distinct eigenvalues, and its automorphism group is order 
.
:
:
, let 
denote the set of complements 
, for 
, and let 
denote the complementary Boolean function. Note that
denotes the complement of 
. Let
is even (resp., odd). We may identify a vector in 
Let
).
denote the $2^n\times 2^n$ Hadamard matrix defined by 
, for each 
. Inductively, these can be defined by
whose 
as the column vector where the 
.
. It is even because
be the Cayley graph of 
so 
has no loops. In this case, 
-regular graph having 
connected components, where
, the set of neighbors 
of 
be the 
adjacency matrix of 
of the adjacency matrix 
) to the Walsh-Hadamard transform 
. Note that 
where 
. She discovered the relationship
Yet Another Mathblog 
You must be logged in to post a comment.