4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Will Jagy
    Dec 31, 2017 at 20:31
  • 1
    $\begingroup$ 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? $\endgroup$
    – Victor Protsak
    Dec 31, 2017 at 21:35
  • $\begingroup$ 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. $\endgroup$
    – Victor Protsak
    Dec 31, 2017 at 21:43
  • $\begingroup$ @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. $\endgroup$
    – Timothy Chow
    Dec 31, 2017 at 22:11
  • $\begingroup$ @VictorProtsak : If you expand your comment about matrices over Boolean semirings into an answer with some references, I will accept it. $\endgroup$
    – Timothy Chow
    Dec 31, 2017 at 22:21

1 Answer 1

Reset to default
4
$\begingroup$

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

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, 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.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.