## 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- 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.

Proof. Let be a matrix and be the column vectors of . Then . This means that multiplying a vector with a matrix is linear combination of the columns, the coefficient is the component of . Since is a boolean and acts as an indicator variable on the selection of column . So if is chosen from a uniform distribution .

Now let and be the column vectors of , similarly let be the column vectors of . Let , clearly since . Then since . Intuitively this means we select our random vector such that for all , such a selection will always ensure even though .

Proof. Continuing with the proof of Theorem- 1 , .