Freivalds' Algorithm - Example

Example

Suppose one wished to determine whether:

AB = \begin{bmatrix} 2 & 3 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 2 \end{bmatrix} \stackrel{?}{=} \begin{bmatrix} 6 & 5 \\ 8 & 7 \end{bmatrix} = C.

A random two-element vector with entries equal to 0 or 1 is selected — say — and used to compute:

\begin{align} A \times (B \vec{r}) - C\vec{r} & = \begin{bmatrix} 2 & 3 \\ 3 & 4 \end{bmatrix} \left( \begin{bmatrix} 1 & 0 \\ 1 & 2 \end{bmatrix} \begin{bmatrix}1 \\ 1\end{bmatrix} \right) - \begin{bmatrix} 6 & 5 \\ 8 & 7 \end{bmatrix} \begin{bmatrix}1 \\ 1\end{bmatrix} \\ & = \begin{bmatrix} 2 & 3 \\ 3 & 4 \end{bmatrix} \begin{bmatrix}1 \\ 3\end{bmatrix} - \begin{bmatrix}11 \\ 15\end{bmatrix} \\ & = \begin{bmatrix}11 \\ 15\end{bmatrix} - \begin{bmatrix}11 \\ 15\end{bmatrix} \\ & = \begin{bmatrix}0 \\ 0\end{bmatrix}. \end{align}

This yields the zero vector, suggesting the possibility that AB = C. However, if in a second trial the vector is selected, the result becomes:

A \times (B \vec{r}) - C\vec{r} = \begin{bmatrix} 2 & 3 \\ 3 & 4 \end{bmatrix} \left( \begin{bmatrix} 1 & 0 \\ 1 & 2 \end{bmatrix} \begin{bmatrix}1 \\ 0\end{bmatrix} \right) - \begin{bmatrix} 6 & 5 \\ 8 & 7 \end{bmatrix} \begin{bmatrix}1 \\ 0\end{bmatrix} = \begin{bmatrix}-1 \\ -1\end{bmatrix}.

The result is nonzero, proving that in fact AB ≠ C.

There are four two-element 0/1 vectors, and half of them give the zero vector in this case ( and ), so the chance of randomly selecting these in two trials (and falsely concluding that AB=C) is 1/22 or 1/4. In the general case, the proportion of r yielding the zero vector may be less than 1/2, and a larger number of trials (such as 20) would be used, rendering the probability of error very small.

Read more about this topic:  Freivalds' Algorithm

Famous quotes containing the word example:

    “Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
    —Marcel Proust (1871–1922)