# Deciding if all matrix multiplication entries have at least two witnesses

Consider two square matrices $$A(x,y)$$ and $$B(y,z)$$ of dimensions $$N×N$$ containing boolean entries. Consider the output product matrix $$C(x,z)$$ where $$C=AB$$ (not boolean matrix multiplication but the entries store the count of how many $$y$$ generate a given output entry). Consider the decision problem of whether all non-zero entries of C are $$\geq 2$$. Is this problem known to be as hard as combinatorial BMM or triangle detection/k-clique detection using combinatorial algorithms? I am mainly interested in using "combinatorial" algorithms but any hardness result related to FMM would also instructive.

• Why 2? As in, is it already known/easy for “at least 1”? Jun 24 at 5:02
• All non-zero entries of C will always be at least 1 since $A$ and $B$ contain 0/1 entries. So the answer to that question is always yes. Jun 24 at 19:36
• Is there a way on this website to send Bat-signal to lord commander @RyanWilliams? 2 days ago

This is not a proper answer but it might help you. I think a reduction to BMM might exist, but if it does, it will be hard to find: on the problem you ask for one bit (whether all ones are double-witnessed) while in BMM you ask for $$n^2$$ bits.
Now let us generalize this "witnessed 2 times" to witnessed $$c$$ times for any fixed $$c\geq 1$$.
• If you were to ask for the positions in $$C$$ where the product is witnessed $$c$$ times then there would be an easy BMM reduction (see below).
• In converse, if you were to ask whether there is at least one element that has $$c$$ witnesses then there would be an easy $$O(n^2)$$ algorithm (just compute the product and stop as soon as one element is witnessed $$c$$ times).
• Your problem asks for all non zero element in $$C$$ to be witnessed $$c$$ times (at least), with $$c=2$$ and I don't know whether we can't do it but note that the case $$c=1$$ it is also unknown, as far as I know, how do it faster than BMM in deterministic time (see Freivalds' algorithm for a randomized efficient algorithm). Solving the case $$c=2$$ would also solve the case $$c=1$$ (see below). I don't know if we can adapt Freivalds' randomized algorithm for $$c=2$$.
Reduction : computing $$\begin{bmatrix} A & A \\ 0 & 0 \end{bmatrix}\times \begin{bmatrix} B & 0 \\ B & 0 \end{bmatrix} = \begin{bmatrix} 2AB & 0 \\ 0 & 0 \end{bmatrix}$$, hence finding the doubly witnessed elements in $$\begin{bmatrix} 2AB & 0 \\ 0 & 0 \end{bmatrix}$$ gives $$AB$$ and testing whether the doubly witnessed elements correspond to all non-zero position of $$\begin{bmatrix} C & 0 \\ 0 & 0 \end{bmatrix}$$ gives the the multiplication check of $$AB=C$$.