2
$\begingroup$

Let's say we have two matrices $M$ and $G$ with $G, M \in \{0, 1\}^{n, n}$, we denote by $m_{i, j}$ the element of $M$ in the $i^\text{th}$ row and $j^\text{th}$ column, same for $G_{i, j}$.

Let's define $K$ the matrix resulting from the matrix operation $G \oplus M$ as follows:

$$\forall i, j \in [1\ldots n] \ \ K_{i,j} = \bigvee_{k \in [1\ldots n]} m_{i,k} \wedge G_{k,j}.$$

I know this operation has a name as it is used in graph theory; however I don't remember what it was. Does someone know the name of this operation?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ This is just matrix multiplication over a Boolean ring. $\endgroup$
    – LSpice
    Commented May 3, 2022 at 17:12
  • 5
    $\begingroup$ Matrix multiplication over the Boolean “semiring” rather than “ring”, I would say. (The Boolean semiring is $\{0,1\}$ with addition being logical OR and multiplication being logical AND. Not to be confused with the field with two elements, whch is also $\{0,1\}$ but this time addition is XOR.) $\endgroup$
    – Gro-Tsen
    Commented May 3, 2022 at 17:56
  • 1
    $\begingroup$ One should use a different symbol to denote the matrix operation in question since the symbol $\oplus$ is used to denote the XOR operation which is just (bitwise) addition modulo $2$. Also, when I hear Boolean ring, I just think of the ring with the XOR for addition and AND for multiplication since this is an actual ring and the category of Boolean rings is isomorphic to the category of Boolean algebras. $\endgroup$
    – Joseph Van Name
    Commented May 3, 2022 at 17:59
  • $\begingroup$ Let $S_n=(2^n,\vee,\mathbf{0})$ denote the algebra where $2^n$ is given the standard Boolean algebra structure and $\vee$ is the join operation. Then the $0,1$-matrices correspond to the join semilattice homomorphisms from $S_n$ to $S_m$ that preserve zero, and the composition of join semilattice homomorphisms corresponds to the matrix multiplication. $\endgroup$
    – Joseph Van Name
    Commented May 3, 2022 at 18:14

1 Answer 1

Reset to default
3
$\begingroup$

Your operation is known as Boolean matrix multiplication. There is a considerable literature on efficient algorithms; see for example An improved combinatorial algorithm for Boolean matrix multiplication by Huacheng Yu.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .