Randomized Algorithm Lemma

Question

Hello I am struggling with proving a lemma, it goes as follows:

Suppose we have a vector r = (r1....rn)^T where rj is either 0 or 1 which is selected uniformly at random with probability 1/2. Suppose now we have a n x n matrix called M (which has at least one non zero element).

I need to prove that the Pr[Mr = 0] <= 1/2(basically prove that the probability of one random position of the matrix M is zero is less than or equal 1/2).

Hint: We can assume that M11 ≠ 0. Based on the hypothesis, argue that the probability of the inner product of the first line of the matrix with the vector r being zero, is at most 1/2.

Also with the help of the above lemma give a randomized algorithm that can check if 3 matrices n x n A,B,C satisfy the relation AB = C in O(n^2).

Answer 1

To prove the claim

$$ P(Mr = 0 ) \leq \frac{1}{2} $$ it is enough to prove it for any row vector $m = (M_{i,1},...,M_{i,n})$ that has at least one non-zero coefficient. Thus, we continue by induction on $n$.

$n= 1 $ base case

The base case is trivial since

$$ P(mr=0) = P(r=0) = \frac{1}{2} $$ in this case.

Induction case $n \implies n+1$.

If $m$ has only one nonzero coefficient then it reduces to the base case; otherwise, there are at least 2 non-zero coefficients say $m_1,m_2$ and we can condition on the two cases $r_1 = 0,1$ to get the result by applying the induction hypothesis.

The second part is given by the following algorithm:

1. Generate a uniform random binary vector $r$
2. Multiply $Br$ to get $r_1$
3. Multiply $Ar_1$ to get $r_2$
4. Multiply $Cr$ to get $r_3$
5. Subtract $r_2-r_3$ to get $r_4$
6. Return $r_4$

This algorithm has $P(r_4 = 0 )>\frac{1}{2} \iff AB = C$ and has complexity $\mathcal{O}(n^2)$.