Boolean matrix

Remarks

Equivalently, the entries are computed in the Boolean semiring $\set{0, 1}$ with $1 + 1 = 1$. For finite sets $X = \set{x_1, \ldots, x_m}$ and $Y = \set{y_1, \ldots, y_n}$, a relation $R \subseteq X \times Y$ has the Boolean matrix with $a_{ij} = 1$ exactly when $(x_i, y_j) \in R$. If $S \subseteq Y \times Z$ has matrix $B$, then the composite relation "first $R$, then $S$" has matrix $A \odot B$. Example: for $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$, $A \odot A = A$, since the entry $(1,2)$ is $\max(\min(1,1), \min(1,1)) = 1$ and the entry $(2,1)$ is $\max(\min(0,1), \min(1,0)) = 0$; the ordinary product would give the entry $2$ at $(1,2)$. Non-example: $\begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$ is not a Boolean matrix, because the entry $2$ is not in $\set{0, 1}$.