\problemdata                                                             
        {Matrix Composition} % latex-friendly label for the prob.
        {Induction, Relations} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 3, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
\newcommand{\paritycomp}{\diamond}                                                                  
\begin{problem}           
Suppose that $A$, $B$ and~$C$ are finite sets and that $R$~is
a relation on $A \times B$ and $S$~is a relation in $B \times C$. The
\emph{parity composition} of the relations $R$ and~$S$, denoted 
$S \paritycomp R$, is defined as follows:
\begin{displaymath}
  S \paritycomp R = \bigl\{
  (a,c) \in A \times C \suchthat
  \mbox{there is an odd number of~$b \in B$ such that
    $(a,b) \in R$ and $(b,c) \in S$}
  \bigr\}.
\end{displaymath}
Let $M_R$ and $M_S$ be the matrices representing $R$ and~$S$,
respectively. Find a formula for the entries in $M_{S \paritycomp R}$
and prove that this formula is correct.

\solution{%
  \textbf{Solution:} Suppose that $M_R = (r_{ab})$, $M_S = (s_{bc})$
  and $M_{S \paritycomp R} = (t_{ac})$. By the definition of matrix
  representation of relations,
  \begin{gather}
    r_{ab} = \begin{cases}
      1 & \mbox{if $(a,b) \in R$,} \\
      0 & \mbox{otherwise.}
    \end{cases} \\
    s_{bc} = \begin{cases}
      1 & \mbox{if $(b,c) \in R$,} \\
      0 & \mbox{otherwise.}
    \end{cases} \\
    t_{ac} = \begin{cases}
      1 & \mbox{if $(a,c) \in S \circ R$,} \\
      0 & \mbox{otherwise.}
    \end{cases}
  \end{gather}
  Now consider ``products'' of the form $r_{ab} \land s_{bc}$. Such a
  product is one iff $r_{ab} = 1$ and $s_{bc} = 1$, i.e., if $(a,b)
  \in R$ and $(b,c) \in S$. So, we want to set $t_{ac}$~to one iff
  there is an odd number of~$b$'s such that $r_{ab} \land s_{bc} = 1$.
  
  A good way to express this mathematically is to use the
  XOR operation, denoted by~$\bigoplus$.
  \begin{definition*}
    Let $S$~be a non-empty set of binary variables and let $s$~be a
    member of~$S$. Then
    \begin{displaymath}
      \bigoplus_{x \in S} x =
      s \oplus \biggl(\bigoplus_{x \in S-\{s\}} x\biggr).
    \end{displaymath}
    Furthermore,
    \begin{displaymath}
      \bigoplus_{x \in \emptyset} x = 0.
    \end{displaymath}
  \end{definition*}
  \begin{lemma*}
    Let $S$~be a set of binary variables. Then
    \begin{displaymath}
      \bigoplus_{x \in S} x = \begin{cases}
        1 & \mbox{if there is an odd number of ones in~$S$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
  \end{lemma*}
  \begin{proof}
    The proof is by induction on~$|S|$. The base case is clear---when
    $S = \emptyset$, it contains no ones.
    
    Suppose that the claim is true for all sets~$S'$ of
    cardinality~$n$. We now prove that this implies that the claim is
    true for any~$S$ of cardinality $n+1$. We pick any $s \in S$ and
    let $S' = S-\{s\}$. By the definition of~$\bigoplus$,
    \begin{displaymath}
      \bigoplus_{x \in S} x =
      s \oplus \biggl(\bigoplus_{x \in S'} x\biggr).
    \end{displaymath}
    Since $|S'| = |S|-1 = n$, we can use the inductive hypothesis, 
    \begin{displaymath}
      \bigoplus_{x \in S'} x = \begin{cases}
        1 & \mbox{if there is an odd number of ones in~$S'$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
    Let $t = \bigoplus_{x \in S'} x$. We get four cases
    \begin{displaymath}
      \begin{array}{cc|c}
        s & t & s \oplus t \\
        \hline
        0 & 0 & 0 \\
        0 & 1 & 1 \\
        1 & 0 & 1 \\
        1 & 1 & 0
      \end{array}
    \end{displaymath}
    Thus, the claim is true for any set of cardinality $n+1$.
  \end{proof}
  Using the symbol~$\bigoplus$ as defined above, we can put everything
  together and obtain the following theorem:
  \begin{theorem*}
    Suppose that $A$, $B$ and~$C$ are finite sets and that $R$~is a
    relation on $A \times B$ and $S$~is a relation in $B \times C$.
    Suppose that the matrix representations of $R$ and~$S$ are $M_R =
    (r_{ab})$ and $M_S = (s_{bc})$, respectively. Then $S \paritycomp
    R$ have the matrix representation $M_{S \paritycomp R} =
    (t_{ac})$, where
    \begin{displaymath}
      t_{ac} = \bigoplus_{b \in B} r_{ab} \land s_{bc}.
    \end{displaymath}
  \end{theorem*}
  \begin{proof}
    By the definition of parity composition,
    \begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there is an odd number of~$b \in B$ such that
          $(a,b) \in R$ and $(b,c) \in S$} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
    Using the matrix representation of $R$ and~$S$, respectively, we
    can rewrite this as
    \begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there is an odd number of~$b \in B$ such that
          $r_{ab} \land s_{bc} = 1$} \\
        0 & \mbox{otherwise.}
      \end{cases}
    \end{displaymath}
    Now, this is exactly the same thing as saying that
    \begin{displaymath}
      t_{ac} = \bigoplus_{b \in B} r_{ab} \land s_{bc},    
    \end{displaymath}
    by the definition of~$\bigoplus$.
\end{proof}
}
\end{problem}
                                 