Deciding if all matrix multiplication entries have at least two witnesses

Question

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.

Answer 1

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