# Calculate boolean matrix multiplication (BMM) using transitive closure

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?

• How is the graph $G$ given as input? Feb 18, 2020 at 16:52
• G={V,E},directed graph Feb 18, 2020 at 16:52

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.