# Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In other words, return the result of expression (A x B) mod 10 == C.

For example:

$\qquad A = \begin{bmatrix} 0 & 5 & 8 \\ 1 & 4 & 9 \\ 2 & 3 & 3 \end{bmatrix}\qquad B = \begin{bmatrix} 3 & 5 & 0 \\ 1 & 2 & 6 \\ 3 & 7 & 0 \end{bmatrix}\qquad C = \begin{bmatrix} 9 & 6 & 0 \\ 4 & 6 & 4 \\ 8 & 7 & 8 \end{bmatrix}$

return: TRUE

If

$\qquad C = \begin{bmatrix} 1 & 6 & 0 \\ 4 & 6 & 4 \\ 8 & 7 & 8 \end{bmatrix}$

return: FALSE, since the element C(1, 1) must be 9.

Time limit is 1s, pretty strict. Please gives me some idea how to solve the problem efficiently; is it possible time $O(N^2)$?

• Note that a time limit in seconds and $O(\dots)$ are incomparable measures, with the answers probably wildly different. What is your priority? (For example, a time limit for any fixed $N$ can be realised by employing recursive matrix multiplication algorithms and storing all (preprocessed) products up to a certain size.) – Raphael Aug 12 '14 at 6:06
• Have you considered Freivalds' algorithm? It's probabilistic but will give the right answer with probability at least $1-2^{-k}$ in time $O(kn^2)$. I'm not sure how good it is, in practice. – David Richerby Aug 12 '14 at 11:51
• @Raphael $k=10$ gives an error rate of about one in a thousand. That's a lot higher than the probability of the CPU randomly flipping a bit. But, yes, you don't need a very big $k$ to get reliability that's indistinguishable from perfect. – David Richerby Aug 12 '14 at 13:48
• @Raphael I don't know so I asked a question about it! – David Richerby Aug 12 '14 at 15:20
• (I should add that the bound mentioned by @DavidRicherby holds if and only if you have a proper source of (pseudo) random numbers. If not, arbitrarily bad stuff can happen.) – Raphael Aug 12 '14 at 19:10

## 1 Answer

I got Accepted by using Freivald's algorithm as suggested by @David Richerby. Thank you very much !

I have not tested the brute-force solution using Coppersmith-Winograd algorithm yet. Will report in a couple of days, by the way I think it might not get Accepted but possibly will gain a fairly amount of points.

For those who want to check your implementation, submit your code on http://vn.spoj.com/problems/VMATRIX/. The problem statement is in Vietnamese, so here is the short description of input format:

• First line is number of testcase (the example gives 2 testcases)
• For each testcase:
• the first line is size of 3 matrices, N. In 20% testcase N <= 100.
• next N * N lines: matrix A
• next N * N lines: matrix B
• next N * N lines: matrix C

Output: YES or NO for the result.

• As I commented below mohaned's answer, Coppersmith–Winograd isn't competitive for the sorts of matrices you're dealing with. For the sizes of matrices you're dealing with, the naive $O(n^3)$ algorithm with a few optimizations tends to be faster than any of the fancy, asymptotically faster algorithms. – David Richerby Aug 12 '14 at 15:31