Saturday, December 12, 2009

[TECH] Simplified Proof For The Application Of Freivalds' Technique to Verify Matrix Multiplication

We first give a simple and alternative proof for Theorem-$ 7.2$ in [Randomized Algorithms, Motwani R. and Raghavan P., pp 162--163]. Later in Theorem 2 we show that the assumption on the uniformness is not necessary.
\begin{theorem} Let $A$,$B$\ and $C$\ be three $n\times n$\ matrices such that $... ...tribution. Then $P[AB\vec{r} = C\vec{r} \vert AB \neq C] \leq 1/2$ \end{theorem}

Proof. Let $ X$ be a $ n\times n$ matrix and $ \vec{x_1}, \vec{x_2}\ldots \vec{x_n}$ be the column vectors of $ X$. Then $ X\vec{r} = \sum_{i=1}^{n}r_i\vec{x_1}$. This means that multiplying a vector with a matrix is linear combination of the columns, the coefficient $ r_i$ is the $ i^{th}$ component of $ \vec{r}$. Since $ \vec{r}$ is a boolean and $ r_i$ acts as an indicator variable on the selection of column $ \vec{x_i}$. So if $ \vec{r}$ is chosen from a uniform distribution $ P[r_i=0] = P[r_i=1] = 1/2$.

Now let $ D=AB$ and $ \vec{d_1},\vec{d_2}\ldots \vec{d_n}$ be the column vectors of $ D$, similarly let $ \vec{c_1},\vec{c_2}\ldots \vec{c_n}$ be the column vectors of $ C$. Let $ Y =\{\vec{d_j} \vert \vec{d_j}\neq \vec{c_j}$, clearly $ \vert Y\vert \geq 1$ since $ C\neq D$. Then $ P[AB\vec{r} = C\vec{r} \vert AB \neq C] = \displaystyle\Pi_{\vec{d_i}\notin Y}P[r_i] = (1/2)^{n-\vert Y\vert} \leq 1/2$ since $ 1 \leq \vert Y\vert\leq n-1$. Intuitively this means we select our random vector $ \vec{r}$ such that $ r_i=0$ for all $ d_i \in Y$, such a selection will always ensure $ AB\vec{r} = C\vec{r}$ even though $ AB\neq C$. $ \qedsymbol$


\begin{theorem} Let $A$,$B$\ and $C$\ be three $n \times n$\ matrices. Let $\vec... ...$f(r)$\ is an arbitrary probability density/distribution function. \end{theorem}

Proof. Continuing with the proof of Theorem- 1 , $ P[AB\vec{r} = C\vec{r}\vert AB\neq C] = \displaystyle\Pi_{\vec{d_i}\notin Y} P[r=r_i] \leq f(r)$. $ \qedsymbol$


\begin{corollary} There always exists an $\Theta(n^2)$\ time Monte Carlo algorit... ...creasing error probability, for the problem to check if $AB=C$. \end{corollary}

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)