Randomized Algorithm Lemma

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

• Please ask only one question per post. I see two questions here. We're not particularly looking for posts that are just the statement of an exercise-style task and a request for us to solve it for you. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Please credit the source of all copied material: cs.stackexchange.com/help/referencing
– D.W.
6 hours ago

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)$$.

• Hey thanks for the answer just a quick question. My lemma has the claim P(Mr = 0) <= 1/2 and not P(Mr= 0 ) >= 1/2 is that a typo of yours or not? May 8 at 13:49
• @kostger I think I fixed it. May 9 at 16:01