# Matrix multiplication randomised verification - error probability

Let s say we have an algorithm that takes as input 3 matrix A,B and C

$$\text{Input} :A,B,C \in Mat(n\times n)$$ $$\text{Question} :\text{is } A\cdot B=C$$

the algorith works as follow ;

$$\text{if }(A\cdot B)_{ij}=C_{ij} \Rightarrow A\cdot B=C$$ $$\text{if }(A\cdot B)_{ij} \neq C_{ij} \Rightarrow A\cdot B \neq C$$

with random chosen $$i$$ and $$j$$ .

I have to find in this case the error probrabilty. Can someone please give me some hints.

This problem looks a bit like the freivalds algorithm, somehow i think i have to drive a trick with it so solve mine but i am not sure .

• Well, $C$ could be wrong on a single entry, so the error probability could be quite large. – Yuval Filmus Oct 31 '18 at 16:19
• yeah but how much , i am guessing by 0.5 – Mohbenay Oct 31 '18 at 16:21
• Don’t guess, calculate. – Yuval Filmus Oct 31 '18 at 16:22
• Use the definition of probability. Count the number of elements to choose and the size of the space. Distinguish the cases where the answer is yes and the answer is no and output the smaller probability among both. – narek Bojikian Dec 26 '19 at 2:27