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](https://cs.nyu.edu/~gottlieb/tr/back-issues/2018/1-jan-feb-tr.pdf) 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](https://en.wikipedia.org/wiki/Young_tableau#Diagrams) 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.



Unusual matrix product associated with non-transitive dice
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](https://books.google.com/books?id=-2L_CAAAQBAJ&pg=PA61), *Matrix semirings*, of the monograph



> 
> Jonathan Golan, Semirings and Affine Equations over Them: Theory and Applications. Mathematics and Its Applications, vol 556, Springer, 2003
> 
> 
> 


The author cites the following early paper:



> 
> R. Duncan Luce, [A note on Boolean matrix theory](https://doi.org/10.1090/S0002-9939-1952-0050559-1), Proc. Amer. Math.
>  Soc. 3 (1952), 382 - 388 
> 
> 
> 


There is quite a bit of literature on this topic: for example, the MathSciNet search "Title=("boolean matri\*")" returns 321 items, of which Luce's article is the oldest.


