exercise01.17.tex

\paragraph{Exercise 1.17} Let's analyse the matrix multiplication algorithm of
section 1.3 under the assumption that we are working over the integers modulo $k$
for $k > 2$. \\
Our modified algorithm chooses a random vector $\bar{r} = (r_1, r_2, ..., r_n)
\in \{ 0, 1, ..., k-1 \} ^n$. It then computes $\textbf{AB}\bar{r}$ by first
computing $\textbf{B}\bar{r}$ and then $\textbf{A}(\textbf{B} \bar{r})$, and it
also computes $\textbf{C} \bar{r}$. If $\textbf{A}(\textbf{B}\bar{r}) \not=
\textbf{C}\bar{r}$, then $\textbf{AB} \not= \textbf{C}$. Otherwise, it returns
that $\textbf{AB} = \textbf{C}$. \\
The probability that the algorithm returns that $\textbf{AB} = \textbf{C}$ when
they are actually not equal is bounded by the following theorem. \\
\textbf{Theorem}: If $\textbf{AB} \not= \textbf{C}$ and if $\bar{r}$ is chosen
uniformly at random from $\{ 0, 1, ..., k-1 \} ^n$, then
\[ \pr(\textbf{AB}\bar{r}) = \textbf{C}\bar{r}) \leq \frac{1}{k}. \]
\textit{Proof}. Let $\textbf{D} = \textbf{AB} - \textbf{C} \not= 0$. Then
$\textbf{AB}\bar{r} = \textbf{C}\bar{r}$ implies that $\textbf{D}\bar{r} = 0$.
Since $\textbf{D} \not= 0$ it must have some nonzero entry; without loss of
generality, let that entry be $d_{11}$. \\
For $\textbf{D}\bar{r} = 0$, it must be the case that
\[ \sum_{j=1}^n d_{1j}r_j = 0 \]
or, equivalently,
\begin{align} r_1 = \frac{\sum_{j=2}^n d_{1j}r_j}{d_{11}}. \end{align}
Suppose that we choose the $r_j$ independently and uniformly at random from
$\{ 0, 1, ..., k-1 \}$ in order, from $r_n$ down to $r_1$. Choosing the $r_j$ in
this way is equivalent to choosing a vector $\bar{r}$ uniformly at random. Now
consider the situation just before $r_1$ is chosen. At this point, the right-hand
side of Eqn. (1.1) is determined, and there is at most one choice for $r_1$ that
will make the equality hold. Since there are $k$ choices for $r_1$, the equality
holds with probability at most $\frac{1}{k}$, and hence the probability that
$\textbf{AB}\bar{r} = \textbf{C}\bar{r}$ is at most $\frac{1}{k}$.