TAOCP 7.1.4 Exercise 90

Section 7.1.4: Binary Decision Diagrams

Exercise 90. [M20] [M20] When l = m = n = 3, Eq. (64) corresponds to the MOR operation of MMIX. Is there an analogous formula that corresponds to MXOR (matrix multiplication mod 2)?

Verified: no
Solve time: 6m29s

Solution

Let Eq. (64) denote the MOR formulation of matrix composition for Boolean matrices, where the entry of the product is formed using the Boolean semiring operations, specifically

$c_{ij} = \bigvee_{k=1}^{3} (a_{ik} \wedge b_{kj}).$

When $l=m=n=3$, this corresponds exactly to the MMIX MOR operation because MOR implements componentwise OR over words, while bitwise AND supplies the pairwise conjunctions of bits across corresponding positions.

For MXOR the underlying algebra changes from the Boolean semiring to the field $\mathbb{F}_2$, where addition is exclusive-or and multiplication is conjunction. The matrix product is therefore defined entrywise by

$c_{ij} = \bigoplus_{k=1}^{3} (a_{ik} \wedge b_{kj}),$

where $\oplus$ denotes bitwise XOR.

This expression is obtained from the MOR formula by replacing the idempotent addition $\vee$ with addition modulo $2$, while leaving the multiplicative structure unchanged. The distributive law still holds because $\mathbb{F}_2$ is a commutative ring, so the standard matrix multiplication identity remains valid under the substitution $\vee \mapsto \oplus$.

Thus the analogous formula to Eq. (64) for MXOR is the same matrix product structure with OR replaced by XOR, yielding the Boolean matrix product over $\mathbb{F}_2$:

$C = A \cdot B \quad \text{over } ({0,1}, \oplus, \wedge).$

This completes the solution. ∎