Calculate boolean matrix multiplication (BMM) using transitive closure

Question

Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$.
How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two matrices $X$ and $Y$?

I know that in order to calculate the transitive closure of a matrix $I$ need to compute $I^{(V-1)}$. But what else?

Answer 1

Let us build the tripartite graph $G = (S := U\dot\cup V \dot\cup W, E)$, where $U := \{u_1, \dots u_n\}$ and similarly $V := \{v_1, \dots v_n\}$ and $W := \{w_1, \dots w_n\}$. Define $E$ as follows: For $i, j \in [n]$, we add $(u_i, v_j)$ to $E$ for $u_i \in U$ and $v_j \in V$, if and only if $X_{ij} = 1$. Similarly we add $(v_i, w_j)$ to $E$ for $v_i \in V$ and $w_j \in W$ if and only if $Y_{ij} = 1$.

Let $G^T := (S, E')$ be the transitive closure of $G$. This means $(x, y) \in E'$ if and only if there is a path from $x$ to $y$ in $G$.

Claim. Let $Z := X \cdot Y$ be the matrix resulting from the multiplication. We claim that $Z_{ij} = 1$ if and only if $(u_i, w_j) \in E'$.

Proof. $Z_{ij} = 1$ if and only if $\bigvee\limits_{k=1}^nX_{ik}\land Y_{kj}$ if and only if there is a $k\in [n]$ such that $X_{ik} = 1$ and $Y_{kj} = 1$ which is the case if and only if there is a $k\in [n]$ such that $(u_i, v_k) \in E$ and $(v_k, w_j) \in E$ which is the case if and only if$^{(*)}$ there is a path in $G$ from $u_i$ to $w_j$ and hence $(u_i, w_j) \in E'$.

Try to prove $(*)$ as an exercise. Hint: for the harder direction use the fact that the graph is directed.