# Sports ranking methods, 1

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 $i$ against team $j$ is $a$, and the total runs allowed by team $i$ against team $j$ is $b$. Here, we order the six teams as above (team $1$ is Army (USMI at Westpoint), team $2$ is Bucknell, and so on). For instance if X played Y and the scores were $10-0$, $0-1$, $0-1$, $0-1$, $0-1$, $0-1$, then the table would read $10-5$ in the position of row X and column Y.

 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 $15\times 6$ matrix:

$M = \left(\begin{array}{cccccc} -1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 0 & 0 & 1 \\ 0 & -1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 & 0 & 0 \\ 0 & 1 & 0 & 0 & -1 & 0 \\ 0 & -1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 & -1 & 0 \\ 0 & 0 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & 1 \end{array}\right).$

We also record their total losses in a column vector:

${\bf b}= \left(\begin{array}{c} 2 \\ 1 \\ 10 \\ 2 \\ 11 \\ 3 \\ 2 \\ 3 \\ 14 \\ 4 \\ 14 \\ 10 \\ 11 \\ 22 \\ 6 \\ \end{array}\right).$

The Massey ranking of these teams is a vector ${\bf r}$ which best fits the equation

$M{\bf r}={\bf b}.$

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

$P_V = B(B^tB)^{-1}B^t,$

valid for matrices $B$ with linearly independent columns. Unfortunately, in this case $B=M$ does not have linearly independent columns, so the formula doesn’t apply.

Massey’s clever idea is to solve

$M^tM{\bf r}=M^t{\bf b}$

by row-reduction and determine the rankings from the parameterized form of the solution. To this end, we compute

$M^tM= \left(\begin{array}{rrrrrr} 5 & -1 & -1 & -1 & -1 & -1 \\ -1 & 5 & -1 & -1 & -1 & -1 \\ -1 & -1 & 5 & -1 & -1 & -1 \\ -1 & -1 & -1 & 5 & -1 & -1 \\ -1 & -1 & -1 & -1 & 5 & -1 \\ -1 & -1 & -1 & -1 & -1 & 5 \end{array}\right)$

and

$M^t{\bf b}= \left(\begin{array}{r} -24 \\ -10 \\ 10 \\ -29 \\ -10 \\ 63 \\ \end{array}\right).$

Then we compute the rref of

$A= (M^tM,M^t{\bf b}) = \left(\begin{array}{rrrrrr|r} 5 & -1 & -1 & -1 & -1 & -1 & -24 \\ -1 & 5 & -1 & -1 & -1 & -1 & -10 \\ -1 & -1 & 5 & -1 & -1 & -1 & 10 \\ -1 & -1 & -1 & 5 & -1 & -1 & -29 \\ -1 & -1 & -1 & -1 & 5 & -1 & -10 \\ -1 & -1 & -1 & -1 & -1 & 5 & 63 \end{array}\right),$

which is

$rref(M^tM,M^t{\bf b})= \left(\begin{array}{rrrrrr|r} 1 & 0 & 0 & 0 & 0 & -1 & -\frac{87}{6} \\ 0 & 1 & 0 & 0 & 0 & -1 & -\frac{73}{6} \\ 0 & 0 & 1 & 0 & 0 & -1 & -\frac{53}{6} \\ 0 & 0 & 0 & 1 & 0 & -1 & -\frac{92}{3} \\ 0 & 0 & 0 & 0 & 1 & -1 & -\frac{73}{6} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right).$

If ${\bf r}=(r_1,r_2,r_3,r_4,r_5,r_6)$ denotes the rankings of Army, Bucknell, Holy Cross, Lafayette, Lehigh, Navy, in that order, then

$r_1=r_6-\frac{87}{6},\ \ r_2=r_6-\frac{73}{6},\ \ r_3=r_6-\frac{53}{6},\ \ r_4=r_6-\frac{92}{6},\ \ r_5=r_6-\frac{73}{6}.$

Therefore

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

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 $20\%$.

# Simple unsolved math problem, 6

If you know a little point-set topology, below is an unsolved math problem whose statement is relatively simple.

Probably everyone has at least seen the Mandelbrot set in some form, as it’s a popular object of mathematical artists. Here’s a picture from Wikipedia:

The formal definition is as follows. Let $f_c (z)=z^2+c$, where $c\in \mathbb{C}$ is a complex number. The Mandelbrot set $X$ is the complex plot of the set of complex numbers $c$ for which the sequence of iterates

$f_c (0), f_c (f_c (0)), f_c (f_c (f_c (0))), \dots,$

remains bounded in absolute value.
We say $X$ is locally connected if every point $x\in X$ admits a neighborhood basis consisting entirely of open, connected sets.

Conjecture: The Mandelbrot set $X$ is locally connected.

# A tribute to TS Michael

I’ve known TS for over 20 years as a principled colleague and a great teacher.

TS at the USNA in Dec 2015.

However, we really never spoke much except for the past five-to-ten years or so. For a period, I wrote a lot about error-correcting codes and we’d talk occasionally about our common interests (for example, I found his paper “The rigidity theorems of Hamada and Ohmori, revisited” fascinating). However, once I became interested in graph theory, we spoke as often as I could corner him. He taught me a lot and only know I realize how lucky I was to have him as a colleague.

I remember many times, late on a Friday, when we’d talk for an hour or two about chess, mathematics, “office politics” (he always knew more than me), and allergies. Here’s one of his favorite chess problems:

Mate in 549 moves. This problem was discovered by a team of chess engame experts at Lomonosov University, Moscow, August 2012.

Maybe this says more about me than him, but when it was just the two of us, we rarely talked about families or relationships. None-the-less, he always treated me like a good friend. One of my favorite memories was when my wife and I were shopping at the plaza where his condo building was located (it’s a big plaza). Elva and I were walking store-to-store when we spotted TS. He was walking to distract himself from his discomfort. At the time, doctors didn’t know what his problems were and he suspected allergies. I have a number of food sensitivities and he was a welcomed fountain of medical knowledge about these issues. (In fact, his hints have really helped me a lot, health-wise.) In any case, TS and Elva and I spoke for 30 minutes or so about health and family. I remember how gracious and thoughtful he was, skillfully steering the conversation into non-technical matters for Elva’s benefit. I ran into him another time while waiting for Elva, who was in a nearby doctor’s office (I told you this was a big shopping plaza). TS generously waited with me until Elva was ready to be picked up. What we chatted about is lost in the cobwebs of my memory but I remember vividly where we sat and the kind of day it was. TS had such a kind heart.

As I said, TS taught me a lot about graph theory. Whether in-between classes or when I was lucky enough to spot him late in the day, he’d kindly entertain my naive (usually false) conjectures and speculations about strongly regular graphs. I never heard him speak in anything but the kindest terms. He’d never say “that’s just plain wrong” or “idiotic” (even if it was) but instead teach me the correct way to think about it in a matter in which I could see myself how my speculations were wrong-headed. My upcoming book with Caroline Melles is indebted to his insight and suggestions.

Even after he left Maryland to spend his remaining days with his family in California, TS emailed encouragement and suggestions about an expository paper I was writing to help connect my matrix theory students with the methods of ranking sports teams. While he was very helpful and provided me with his excellent insights as usual, in truth, I used the work on the paper as an excuse to keep up with his health status. I’m relatively ignorant of medical issues and tried to stay optimistic until it’s totally unrealistic. As sad as it was, we was always frank and honest with me about his prognosis.

He’s gone now, but as a teacher, researcher, and as a kind soul, TS is unforgettable.

A list of TS’s publications:

1. T. S. Michael, Tournaments, book chapter in Handbook of Linear Algebra, 2nd ed, CRC Press, Boca Raton, 2013.
2. T. S. Michael, Cycles of length 5 in triangle-free graphs: a sporadic counterexample to a characterization of equality, Bulletin of the Institute of Combinatorics and Its Applications, 67 (2013) 6–8.
3. T. S. Michael and Val Pinciu, Guarding orthogonal prison yards: an upper bound,
Congressus Numerantium, 211 (2012) 57–64.
4. Ilhan Hacioglu and T. S. Michael, The p-ranks of residual and derived skew Hadamard designs,
Discrete Mathematics, 311 (2011) 2216-2219.
5. T. S. Michael, Guards, galleries, fortresses, and the octoplex, College Math Journal, 42 (2011) 191-200. (This paper won a Polya Award)
6. Elizabeth Doering, T. S. Michael, and Bryan Shader, Even and odd tournament matrices with minimum rank over finite fields, Electronic Journal of Linear Algebra, 22 (2011) 363-377.
7. Brenda Johnson, Mark E. Kidwell, and T. S. Michael, Intrinsically knotted graphs have at least 21 edges, Journal of Knot Theory and Its Ramifications, 19 (2010) 1423-1429.
8. T. S. Michael, How to Guard an Art Gallery and Other Discrete Mathematical Adventures. Johns Hopkins University Press, Baltimore, 2009.
9. T. S. Michael and Val Pinciu, Art gallery theorems and triangulations, DIMACS Educational Module Series, 2007, 18 pp (electronic 07-1)
10. T. S. Michael and Thomas Quint, Sphericity, cubicity, and edge clique covers of graphs, Discrete Applied Mathematics, 154 (2006) 1309-1313.
11. T. S. Michael and Val Pinciu, Guarding the guards in art galleries, Math Horizons, 14 (2006), 22-23, 25.
12. Richard J. Bower and T. S. Michael, Packing boxes with bricks, Mathematics Magazine, 79 (2006), 14-30.
13. T. S. Michael and Thomas Quint, Optimal strategies for node selection games: skew matrices and symmetric games, Linear Algebra and Its Applications 412 (2006) 77-92.
14. T. S. Michael, Ryser’s embedding problem for Hadamard matrices, Journal of Combinatorial Designs 14 (2006) 41-51.
15. Richard J. Bower and T. S. Michael, When can you tile a box with translates of two given rectangular bricks?, Electronic Journal of Combinatorics 11 (2004) Note 7, 9 pages.
16. T. S. Michael and Val Pinciu, Art gallery theorems for guarded guards, Computational Geometry 26 (2003) 247-258.
17. T. S. Michael, Impossible decompositions of complete graphs into three Petersen subgraphs, Bulletin of the Institute of Combinatorics and Its Applications 39 (2003) 64-66.
18. T. S. Michael and William N. Traves, Independence sequences of well-covered graphs: non-unimodality and the roller-coaster conjecture, Graphs and Combinatorics 19 (2003) 403-411.
19. T. S. Michael and Thomas Quint, Sphere of influence graphs and the L-Infinity metric, Discrete Applied Mathematics 127 (2003) 447-460.
20. T. S. Michael, Signed degree sequences and multigraphs, Journal of Graph Theory 41 (2002) 101-105.
21. T. S. Michael and Val Pinciu, Multiply guarded guards in orthogonal art galleries, Lecture Notes in Computer Science 2073, pp 753-762, in: Proceedings of the International Conference on Computer Science, San Francisco, Springer, 2001.
22. T. S. Michael, The rigidity theorems of Hamada and Ohmori, revisited, in Coding Theory and Cryptography: From the Geheimschreiber and Enigma to Quantum Theory. (Annapolis, MD, 1998), 175-179, Springer, Berlin, 2000.
23. T. S. Michael and Thomas Quint, Sphere of influence graphs in general metric spaces, Mathematical and Computer Modelling, 29 (1999) 45-53.
24. Suk-Geun Hwang, Arnold R. Kraeuter, and T. S. Michael, An upper bound for the permanent of a nonnegative matrix, Linear Algebra and Its Applications 281 (1998), 259-263.
* First Corrections: Linear Algebra and Its Applications 300 (1999), no. 1-3, 1-2
25. T. S. Michael and W. D. Wallis, Skew-Hadamard matrices and the Smith normal form, Designs, Codes, and Cryptography, 13 (1998) 173-176.
26. T. S. Michael, The p-ranks of skew Hadamard designs, Journal of Combinatorial Theory, Series A, 73 (1996) 170-171.
27. T. S. Michael, The ranks of tournament matrices, American Mathematical Monthly, 102 (1995) 637-639.
28. T. S. Michael, Lower bounds for graph domination by degrees, pp 789-800 in Graph Theory, Combinatorics, and Algorithms: Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Y. Alavi and A. Schwenk (eds.), Wiley, New York, 1995.
29. T. S. Michael and Thomas Quint, Sphere of influence graphs: a survey, Congressus Numerantium, 105 (1994) 153-160.
30. T. S. Michael and Thomas Quint, Sphere of influence graphs: edge density and clique size, Mathematical and Computer Modelling, 20 (1994) 19-24.
31. T. S. Michael and Aaron Stucker, Mathematical pitfalls with equivalence classes, PRIMUS, 3 (1993) 331-335.
32. T. S. Michael, The structure matrix of the class of r-multigraphs with a prescribed degree sequence, Linear Algebra and Its Applications, 183 (1993) 155-177.
33. T. S. Michael, The decomposition of the complete graph into three isomorphic strongly regular graphs, Congressus Numerantium, 85 (1991) 177-183.
34. T. S. Michael, The structure matrix and a generalization of Ryser’s maximum term rank formula, Linear Algebra and Its Applications, 145 (1991) 21-31.
35. Richard A. Brualdi and T. S. Michael, The class of matrices of zeros, ones and twos with prescribed row and column sums, Linear Algebra and Its Applications, 114(115) (1989) 181-198.
36. Richard A. Brualdi and T. S. Michael, The class of 2-multigraphs with a prescribed degree sequence, Linear and Multilinear Algebra, 24 (1989) 81-102.
37. Richard A. Brualdi, John L. Goldwasser, and T. S. Michael, Maximum permanents of matrices of zeros and ones, Journal of Combinatorial Theory, Series A, 47 (1988) 207-245.

# Memories of TS Michael, by Bryan Shader

TS Michael passed away on November 22, 2016, from cancer. I will miss him as a colleague and a kind, wise soul.

TS Michael in December 2015 at the USNA

Bryan Shader has kindly allowed me to post these reminiscences that he wrote up.

Memories of TS Michael, by Bryan Shader

Indirect influence
TS indirectly influenced my choice of U. Wisconsin-Madison for graduate school. My senior year as an undergraduate, Herb Ryser gave a talk at my school. After the talk I was able to meet Ryser and asked for advice on graduate schools. Herb indicated that one of his very good undergraduate students had chosen UW-Madison and really liked the program. I later found out that the person was TS.

Back in the dark ages, universities still did registration by hand. This meant that for a couple of days before each semester the masses of students would wind their way through a maze of stations in a large gymnasium. For TS’s first 4 years, he would invariably encounter a road block because someone had permuted the words in his name (Todd Scott Michael) on one of the forms. After concretely verifying the hatcheck probabilities and fearing that this would cause some difficulties in graduating, he legally changed his name to TS Michael.

Polyominoes & Permanents
I recall many stories about how TS’s undergraduate work on polyominoes affected
his life. In particular, he recalled how once he started working on tilings on
polyominoes, he could no longer shower, or swim without visualizing polynomino
tilings on the wall’s or floor’s tiling. We shared an interest and passion for permanents (the permanent is a function of a matrix much like the determinant and plays a critical role in combinatorics). When working together we frequently would find that we both couldn’t calculate the determinant of a 3 by 3 matrix correctly, because we were calculating the permanent rather than the determinant.

Presentations and pipe-dreams
TS and I often talked about how best to give a mathematical lecture, or
presentation at a conference. Perhaps this is not at all surprising, as our common advisor (Richard Brualdi) is an incredible expositor, as was TS’s undergraduate advisor (Herb Ryser, our mathematical grandfather). TS often mentioned how Herb Ryser scripted every moment of a lecture; he knew each word he would write on the board and exactly where it would be written. TS wasn’t quite so prescriptive–but before any presentation he gave he would go to the actual room of the presentation a couple of times and run through the talk. This would include answering questions from the “pretend” audience. After being inspired by TS’s talks, I adopted this preparation method.
TS and I also fantasized about our talks ending with the audience lifting us up on their shoulders and carrying us out of the room in triumph! That is never happened to either of us (that I know of), but to have it, as a dream has always been a good motivation.

Mathematical heritage
TS was very interested in his mathematical heritage, and his mathematics brothers and sisters. TS was the 12th of Brandi’s 37 PhD students; I was the 15th. In 2005, TS and I organized a conference (called the Brualidfest) in honor of Richard Brualdi. Below I attach some photos of the design for the T-shirt.

t-shirt design for Brualdi-Fest, 1

The first image shows a biclique partition of K_5; for each color the edges of the given color form a complete bipartite graph; and each each of the completed graph on 5 vertices is in exactly one of these complete bipartite graph. This is related to one of TS’s favorite theorem: the Graham-Pollak Theorem.

t-shirt design for Bruldi-Fest, 2

The second image (when the symbols are replaced by 1s) is the incidence matrix of the projective plane of order 2; one of TS’s favorite matrices.

Here’s a photo of the Brualdi and his students at the conference:

From L to R they are: John Mason (?), Thomas Forreger, John Goldwasser, Dan Pritikin, Suk-geun Hwang, Han Cho, T.S. Michael, B. Shader, Keith Chavey, Jennifer Quinn, Mark Lawrence, Susan Hollingsworth, Nancy Neudauer, Adam Berliner, and Louis Deaett.

Here’s a picture for a 2012 conference:

From bottom to top: T.S. Michael (1988), US Naval Academy, MD; Bryan Shader (1990), University of Wyoming, WY; Jennifer Quinn (1993), University of Washington, Tacoma, WA; Nancy Neudauer (1998), Pacific University, OR; Susan Hollingsworth (2006), Edgewood College, WI; Adam Berliner (2009), St. Olaf College, MN; Louis Deaett (2009), Quinnipiac University, CT; Michael Schroeder (2011), Marshall University, WV; Seth Meyer (2012), Kathleen Kiernan (2012).

Here’s a caricature of TS made by Kathy Wilson (spouse of mathematician
Richard Wilson) at the Brualdifest:

TS Michael, by Kathy Wilson

Long Mathematical Discussions
During graduate school, TS and I would regularly bump into each other as we
were coming and going from the office. Often this happened as we were crossing University Avenue, one of the busiest streets in Madison. The typical conversation started with a “Hi, how are you doing? Have you considered X?” We would then spend the next 60-90 minutes on the street corner (whether it was a sweltering 90 degrees+, or a cold, windy day) considering X. In more recent years, these conversations have moved to hotel lobbies at conferences that we attend together. These discussions have been some of the best moments of my life, and through them I have become a better mathematician.

Here’s a photo of T.S. Michael with Kevin van der Meulen at the Brualdi-fest.

I’m guessing they are in the midst of one of those “Have you considered X?” moments that TS is famous for.

Mathematical insight
TS has taught me a lot about mathematics, including:

•  How trying to generalize a result can lead to better understanding of the original result.
•  How phrasing a question appropriately is often the key to a mathematical breakthrough
• Results that are surprising (e.g. go against ones intuition), use an elegant proof (e.g. bring in matrices in an unexpected way), and are aesthetically pleasing are worth pursing (as Piet Hein said “Problems worthy of attack, prove their worth by fighting back.”)
•  The struggle to present the proof of a result in the simplest, most self-contained way is important because often it produces a better understanding. If you can’t say something in a clean way, then perhaps you really don’t understand it fully.

TS’ mathematics fathers are:
Richard Brualdi ← Herb Ryser ← Cyrus MacDuffee ← Leonard Dickson ← E.H. Moore ← H. A. Newton ← Michel Chasles ← Simeon Poisoon ← Joseph Lagrange ← Leonhard Euler ← Johann Bernoulli.

# Simple unsolved math problem, 5

It seems everyone’s heard of Pascal’s triangle. However, if you haven’t then it is an infinite triangle of integers with 1‘s down each side and the inside numbers determined by adding the two numbers above it:

First 6 rows of Pascal’s triangle

The first 6 rows are depicted above. It turns out, these entries are the binomial coefficients that appear when you expand $(x+y)^n$ and group the terms into like powers $x^{n-k}y^k$:

First 6 rows of Pascal’s triangle, as binomial coefficients.

The history of Pascal’s triangle pre-dates Pascal, a French mathematician from the 1600s, and was known to scholars in ancient Persia, China, and India.

Starting in the mid-to-late 1970s, British mathematician David Singmaster was known for his research on the mathematics of the Rubik’s cube. However, in the early 1970’s, Singmaster made the following conjecture [1].

Conjecture: If $N(a)$ denotes the number of times the number $a > 1$ appears in Pascal’s triangle then $N(a) \leq 12$ for all $a>1$.

In fact, there are no known numbers $a>1$ with $N(a)>8$ and the only number greater than one with $N(a)=8$ is a=3003.

References:

[1] Singmaster, D. “Research Problems: How often does an integer occur as a binomial coefficient?”, American Mathematical Monthly, 78(1971) 385–386.

# Simple unsolved math problem, 3

A perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself. For example,  1 + 2 + 3 = 6 implies 6 is a perfect number.

Unsolved Problem: Are there any odd perfect numbers?

The belief, by some, that there are none goes back over 500 years (wikipedia).

If you want to check out some recent research into this problem, see oddperfect.org.

(Another unsolved problem: Are there an infinite number of even perfect numbers?)

# Simple unsolved math problem, 2

In 1911, Otto Toeplitz asked the following question.

Inscribed Square Problem: Does every plane simple closed curve contain all four vertices of some square?

This question, also known as the square peg problem or the Toeplitz’ conjecture, is still unsolved in general. (It is known in lots of special cases.)

Inscribed square, by Claudio Rocchini

Thanks to Mark Meyerson (“Equilateral triangles and continuous curves”,Fundamenta Mathematicae, 1980) and others, the analog for triangles is true. For any triangle T and Jordan curve C, there is a triangle similar to T and inscribed in C. (In particular, the triangle can be equilateral.) The survey page by Mark J. Nielsen has more information on this problem.