= Boolean matrix multiplication
{c}
{title2=$C_{ij}=\bigvee_k(A_{ik}\land B_{kj})$}
For <Boolean> <matrices>, replace numerical <addition> by logical disjunction and <multiplication> by logical conjunction. Applied to <adjacency matrices>, the product records a <walk> formed by following one segment represented by the first <matrix> and one represented by the second. For an <adjacency matrix> $A$ on $n\geq1$ <vertices>, start from $I\lor A$. Repeated squaring then computes <reflexive transitive closure> once the exponent reaches $n-1$: the identity entries pad shorter <walks>, and every reachable pair has a <simple path> of length at most $n-1$.
Back to article page
