2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ How is the graph $G$ given as input? $\endgroup$ – vonbrand Feb 18 '20 at 16:52
  • $\begingroup$ G={V,E},directed graph $\endgroup$ – ga as Feb 18 '20 at 16:52
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.