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.

1more comment