        \problemdata       % Takes 5 *mandatory* arguments
        {parity-comp}             % latex-friendly label for the prob.
        {relations}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut3-3} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
\newcommand{\paritycomp}{\diamond} 
Suppose that $A$, $B$ and~$C$ are finite sets and that $R$~is
a relation from $A$ to $B$ and $S$~is a relation from $B$ to $C$. 

The \emph{parity composition} of the relations $R$ and~$S$, denoted 
$S\paritycomp R$, is defined as follows:
\begin{align*}
  (a,c) \in S \paritycomp R & \iff \card{\set{b \in B \suchthat (a,b) \in
      R \land (b,c) \in S}} \text{is an odd number}.
\end{align*}
Let $M_R = [r_{ab}]$ be the matrix representing $R$.  \emph{Reminder}: this means
\begin{align*}
    r_{ab} & = \begin{cases}
      1 & \mbox{if $(a,b) \in R$,} \\
      0 & \mbox{otherwise,}
    \end{cases}
\end{align*}
for $a \in A, b \in B$.
Similarly, let $M_S = [s_{bc}]$ be the matrix representing $S$ and $M_{S
\paritycomp R} = [t_{ac}]$ be the matrix representing $M_{S \paritycomp
R}$.

Find a formula for $t_{ac}$ in terms of the $r$'s and $s$'s, and explain
why your formula is correct.

\solution{
\[
t_{ac} = \bigoplus_{b \in B} r_{ab} \cdot s_{bc},
\]
where $\bigoplus$ denotes mod 2 sum.

\begin{proof}
By the definition of parity composition,
\begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there are 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 are an odd number of~$b \in B$ such that
          $r_{ab} \cdot 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} \cdot s_{bc},    
\end{displaymath}
by the definition of~$\bigoplus$.
\end{proof}
}

%% Describes how to do count, eaiser than parity so should be before

% \problempart
% Consider the matrix $U_{R,S}=(u_{ac})$, whose $(a,c)$th entry is 
% \[
% u_{ac} \eqdef \card{\set{b\in B \suchthat (a,b)\in R \land (b,c)\in S$.
% \]
% Extending the ideas you have used for
% the first part of this problem, can you find a formula for~$u_{ac}$? 

% \solnospace{
% To calculate $u_{ac}$, we need to count the number of $b$'s in $B$ for
% which $(a,b)\in R$ and $(b,c)\in S$. Thinking as in the first part of
% the problem, we see that this is exactly the number of $b$'s in $B$
% for which $r_{ab}\wedge s_{bc}=1$. So, if we just sum up all
% $(r_{ab}\wedge s_{bc})$'s, we will get exactly this number (because,
% whenever a $(r_{ab}\wedge s_{bc})$ is not~1, it is~0). Hence, we can
% derive the formula of $u_{ac}$ from that of $t_{ac}$, by simply
% replacing the XOR operator with the summation operator:
% $$
% u_{ac} = \sum_{b\in B}  r_{ab}\wedge s_{bc} .
% $$
% Notice that this formula is identical to the one that we would get for
% $u_{ac}$ if $U_{R,S}$ were the ordinary matrix product of $M_R$ and
% $M_S$. Therefore, a more compact way to define $U_{R,S}$ is actually, 
% $$
% U_{R,S} = M_R \times M_S.
% $$
% }
\end{problem}
