# 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”? Commented Jun 24, 2022 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. Commented Jun 24, 2022 at 19:36
• Is there a way on this website to send Bat-signal to lord commander @RyanWilliams? Commented Jun 29, 2022 at 4:16

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

• Thanks! This is definitely food for thought. One thing I'd like to point out - your reasoning for why BMM reduction might be hard to find might not be true. See the abstract and section 1.1 kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf. The same intuition also holds for triangle detection and BMM since detection is 1 bit but BMM is $n^2$ but reductions are there! I strongly feel there should be something from triangle detection here -- perhaps my question is equivalent to asking whether every edge in a graph participates in at least 2 triangles but I am not able to show it (yet). Commented Jul 1, 2022 at 17:42
• Agreed, but I am not claiming that such a reduction does not exist just that if it does, it will likely be a non "trivial" one. I have also seen people use product vector-matrix-vector to optimize matrix-vector product so you can look there. Also note that my last point reduces to the problem "how to deterministically test whether AB=C?" which as far as I know, is open. Commented Jul 1, 2022 at 17:58
• Another question I had, $C$ is the output of $AB$ but in the reduction, it seems $C$ is used as an input just like $A,B$. Is my understanding correct? We don't want to compute $C$ explicitly (otherwise it is BMM amount of work already. Second, $c=1$ should be trivial, right? Each non-zero entry of $AB$ is guaranteed to be at least $1$. Commented Jul 3, 2022 at 4:19