Some Binary Operations on Boolean Matrices

Definition 12.3. A Boolean matrix is a real matrix whose every entry is either $0$ or $1$. Boolean entries $0/1$ naturally model "off/on" in electrical switching circuits, or the adjacency matrix of a graph.

Given two Boolean matrices $A=[a_{ij}]$ and $B=[b_{ij}]$ of the same order, two new binary operations combine them entrywise:

Definition 12.4 (Join). $A\vee B=[a_{ij}\vee b_{ij}]=[c_{ij}]$, where $c_{ij}=1$ if either $a_{ij}=1$ or $b_{ij}=1$, and $c_{ij}=0$ if both $a_{ij}=0$ and $b_{ij}=0$. Equivalently $a_{ij}\vee b_{ij}=\max(a_{ij},b_{ij})$.

Definition 12.5 (Meet). $A\wedge B=[a_{ij}\wedge b_{ij}]=[c_{ij}]$, where $c_{ij}=1$ only if both $a_{ij}=1$ and $b_{ij}=1$, and $c_{ij}=0$ if either entry is $0$. Equivalently $a_{ij}\wedge b_{ij}=\min(a_{ij},b_{ij})$.

Worked pattern. For $A=\begin{pmatrix}0&1\\1&1\end{pmatrix}$, $B=\begin{pmatrix}1&1\\0&1\end{pmatrix}$: $A\vee B=\begin{pmatrix}\max(0,1)&\max(1,1)\\\max(1,0)&\max(1,1)\end{pmatrix}=\begin{pmatrix}1&1\\1&1\end{pmatrix}$, and $A\wedge B=\begin{pmatrix}\min(0,1)&\min(1,1)\\\min(1,0)&\min(1,1)\end{pmatrix}=\begin{pmatrix}0&1\\0&1\end{pmatrix}$.

Which of the five properties do join and meet satisfy? Let $\mathbb B$ be the set of all Boolean matrices of a fixed order.

• Closure: since $a_{ij}\vee b_{ij}$ and $a_{ij}\wedge b_{ij}$ are always $0$ or $1$, both operations are binary on $\mathbb B$.
• Commutative: both hold, since $\max$ and $\min$ do not depend on the order of their two arguments.
• Associative: both hold, entrywise.
• Existence of identity: for $\vee$, the identity is the null matrix $O$ (every entry $0$) -- $A\vee O=O\vee A=A$. For $\wedge$, the identity is the matrix $U$ of all $1$s -- $A\wedge U=U\wedge A=A$. …