\problemdata      
        {functions-relations-2} % latex-friendly label for the prob.
        {relation composition proof} % The topic(s) of the problem content.
        {?} % Source (if known)
        {S02 cp3M} % Usage (list ones you are aware of).
        {Radhika Nagpal, S02} % Last revision info (author, date).

\begin{problem}

Recall that the \emph{composition} of relations $R \subseteq A
\times B$ and $S \subseteq B \times C$ is the relation
\[
S \circ R =\{(a,c) \mid \exists b \mbox{ such that } (a,b) \in R \wedge
(b,c) \in S \}.
\]
If we represent relations as matrices, then we can compute the
composition of two relations by a ``boolean'' matrix multiplication of
their matrices. Boolean matrix multiplication is the same as matrix
multiplication except that ``$+$'' is replaced by $\vee$ (Boolean OR)
and ``$\times$'' is replaced by $\wedge$ (Boolean AND).

Prove that the matrix representation of $S o R$ is equal to the
boolean product of $M_R$ and $M_S$, where $M_R$ is the matrix
representing $R$ and $M_S$ is the matrix representing $S$.

\solution{Let $M_P$ be the boolean product of $M_R$ and $M_S$ (notice
that $M_P$, $M_R$ and $M_S$ are all $n\times n$ square matrices). What
we want to prove is that
\[
(i,j) \in S\circ R  \Longleftrightarrow  M_P (i, j)=1
\]

Recall that by the definition of composition, $(i,j) \in S\circ R $
iff there exists a $k$ such that $(i,k) \in R$ and $(k,j) \in
S$. Also, by the definition of boolean matrix multiplication,

\[
M_P (i,j) = \underbrace{\left[M_R(i,k_1) \wedge
M_S(k_1,j)\right]}_{k_1 \text{ is the ``link''}} \vee 
\underbrace{\left[M_R(i,k_2) \wedge
M_S(k_2,j)\right]}_{k_2 \text{ is the ``link''}}\vee 
\ldots \vee\underbrace{\left[M_R(i,k_n) \wedge
M_S(k_n,j)\right]}_{k_n \text { is the ``link''}}
\]

\begin{description}
\item[Case 1:($\Longrightarrow$)] If $(i, j) \in S\circ R$, then for
at least one $k$, say $k'$, $(i,k') \in R$ and $(k',j) \in
S$. Consequently, $M_R(i,k')=1$ and $M_S(k',j)=1$. This turns
$\left[M_R(i,k') \wedge M_S(k',j)\right]$ true, and hence $M_P(i,
j)=1$.

\item[Case 2: ($\Longleftarrow$)] If $M_P(i, j)=1$ then there is at least one
$k$, say $k'$,  for which $\left[M_R(i,k') \wedge
M_S(k',j)\right] =1$. This means that both $M_R(i,k')=1$ and $M_S(k',j)=1$.
Since $M_R$ and $M_S$ are the matrix representations of $R$ and $S$, we
can conclude that $(i,k')\in R$ and $(k',j)\in S$, and so, by the definition
of composition, $(i,j)\in S\circ R$ 
\end{description}
 
}

\end{problem}
