# Unusual matrix product associated with non-transitive dice

Not long ago, the Puzzle Corner of the magazine MIT Technology Review asked for a set of $N$ dice that are non-transitive in the sense that there is a cyclic ordering on them, in which each die beats the next die in the cyclic order. I had not seen this particular question about non-transitive dice before, but it is not a terribly difficult puzzle; you can view one solution here if you are curious. My question here is not about the puzzle per se but about a curious kind of matrix product that arose while I was trying to solve the puzzle.

For simplicity, assume that all numbers on all dice are distinct. Suppose we have two dice $A$ and $B$ with respective numbers $A_1, A_2, A_3, \ldots$ and $B_1, B_2, B_3, \ldots$ and assume without loss of generality that $A_1 > A_2 > A_3 > \cdots$ and $B_1 > B_2 > B_3 > \cdots$. Then we may record the relationship between the dice by a 0-1 matrix $M$ whose $(i,j)$ entry $M_{ij}$ is given by $$M_{ij} = \cases{1, &if A_i>B_j;\cr 0, &if A_i<B_j.}$$ Note that if $A_i>B_j$ then $A_i>B_{j+1}$ and $A_{i-1}>B_j$. This means that the "1" entries in $M$ form a Young diagram in the upper right-hand corner of $M$ (except that the rows are right-justified rather than left-justified).

Now let us consider a third die $C$, and let $M'$ denote the 0-1 matrix that records the relationship between $B$ and $C$. It is natural to ask:

What relationships necessarily hold between $A$ and $C$?

This question is readily answered. If $A_i>B_j$ and $B_j>C_k$ then necessarily $A_i>C_k$. Conversely, if there is no $B_j$ such that both $A_i>B_j$ and $B_j>C_k$ then there is no necessary relationship between $A_i$ and $C_k$. Therefore we can compute the necessary relationships between $A$ and $C$ by computing $M\boxtimes M'$, where by $\boxtimes$ I mean the matrix product defined by $$(M\boxtimes M')_{ik} = \max_j M_{ij}M'_{jk}.$$ Equivalently, $\boxtimes$ is matrix multiplication on Boolean matrices, with scalar multiplication replaced by AND and scalar addition replaced by (inclusive) OR.

In this language, the existence of non-transitive dice is equivalent to the existence of $M$ and $M'$, each with more 1's than 0's, such that $M\boxtimes M'$ has more 0's than 1's.

My question is:

Does $\boxtimes$ have any interesting properties? Does it show up elsewhere in mathematics?

One can think of $\boxtimes$ as an operation on Young diagrams or on lattice paths, but I do not recall encountering this operation before.

• just a comment; if they did not mention it, Martin Gardner gave a set of four nontransitve dice, six sides each, in a column in the 1960's or 1970's – Will Jagy Dec 31 '17 at 20:31
• There is a lot of literature on matrices over semirings, and in particular, the Boolean semiring. But I don't understand the reduction of the non-transitive dice problem to "necessary telationships" framework: if die $B$ has the extreme property that each of its entries is either larger than the maximum of all $A_i$ and $C_k$ or smaller than the minimum of the same then the Boolean matrix product $M\boxtimes M'$ is zero, yet it carries no information on the relative sizes of the entries of $A$ and $C$. What am I missing? – Victor Protsak Dec 31 '17 at 21:35
• A better formalization is to use the hyperring where $0+1=\{0,1\}$, indicating that if there is no $B_j$ witnessing that $A_i>C_k$ then the relationship can go either way. – Victor Protsak Dec 31 '17 at 21:43
• @VictorProtsak : Yes, to be more precise, I should have said that in $M\boxtimes M'$, a 1 indicates that $A_i < C_k$ is impossible whereas a 0 indicates that $A_i < C_k$ is possible. For the purposes of determining whether you can "loop back" from $C$ to $A$, this is all the information you really need; the distinction between $0$ and $\{0,1\}$ is immaterial. – Timothy Chow Dec 31 '17 at 22:11
• @VictorProtsak : If you expand your comment about matrices over Boolean semirings into an answer with some references, I will accept it. – Timothy Chow Dec 31 '17 at 22:21

As Timothy mentioned in the question itself, $\boxtimes$ is the matrix multiplication of Boolean matrices, i.e. square matrices over the Boolean semiring $\Bbb{B}=\{0,1\}$. More generally, for any semiring $R$, one can define multiplication of matrices over $R$ by the usual formula. This construction yields the semiring $M_n(R)$ of $n\times n$ matrices over $R$. It is discussed in Chapter 5, Matrix semirings, of the monograph