<p>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 <span class="math-container">$n^2$</span> bits.</p>
<p>Now let us generalize this &quot;witnessed 2 times&quot; to witnessed <span class="math-container">$c$</span> times for any fixed <span class="math-container">$c\geq 1$</span>.</p>
<ul>
<li>If you were to ask for the positions in <span class="math-container">$C$</span> where the product is witnessed <span class="math-container">$c$</span> times then there would be an easy BMM reduction (see below).</li>
<li>In converse, if you were to ask whether there is <strong>at least one</strong> element that has <span class="math-container">$c$</span> witnesses then there would be an easy <span class="math-container">$O(n^2)$</span> algorithm (just compute the product and stop as soon as one element is witnessed <span class="math-container">$c$</span> times).</li>
<li>Your problem asks for all non zero element in <span class="math-container">$C$</span> to be  witnessed <span class="math-container">$c$</span> times (at least), with <span class="math-container">$c=2$</span> and I don't know whether we can't do it but note that the case <span class="math-container">$c=1$</span> 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 <span class="math-container">$c=2$</span> would also solve the case <span class="math-container">$c=1$</span> (see below). I don't know if we can adapt Freivalds' randomized algorithm for <span class="math-container">$c=2$</span>.</li>
</ul>
<p><strong>Reduction</strong> : computing <span class="math-container">$\begin{bmatrix} A &amp; A \\ 0 &amp; 0 \end{bmatrix}\times \begin{bmatrix} B &amp; 0 \\ B &amp; 0 \end{bmatrix} = \begin{bmatrix} 2AB &amp; 0 \\ 0 &amp; 0 \end{bmatrix}$</span>, hence finding the doubly witnessed elements in <span class="math-container">$ \begin{bmatrix} 2AB &amp; 0 \\ 0 &amp; 0 \end{bmatrix}$</span> gives <span class="math-container">$AB$</span> and testing whether the doubly witnessed elements correspond to all non-zero position of <span class="math-container">$ \begin{bmatrix} C &amp; 0 \\ 0 &amp; 0 \end{bmatrix}$</span> gives the the multiplication check of <span class="math-container">$AB=C$</span>.</p>

CC BY-SA 4.0
2022-07-01T17:42:06.167Z
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 https://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).
karmanaut
CC BY-SA 4.0
2022-07-01T17:58:47.520Z
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.
Louis
CC BY-SA 4.0
2022-07-03T04:19:58.220Z
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$.
karmanaut
CC BY-SA 4.0
2022-07-01T13:25:13.060Z
2022-07-01T13:25:13.060Z
Louis
<p>Consider two square matrices <span class="math-container">$A(x,y)$</span> and <span class="math-container">$B(y,z)$</span> of dimensions <span class="math-container">$N×N$</span> containing boolean entries. Consider the output product matrix <span class="math-container">$C(x,z)$</span> where <span class="math-container">$C=AB$</span> (not boolean matrix multiplication but the entries store the count of how many <span class="math-container">$y$</span> generate a given output entry). Consider the decision problem of whether all non-zero entries of C are <span class="math-container">$\geq 2$</span>. 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 &quot;combinatorial&quot; algorithms but any hardness result related to FMM would also instructive.</p>

CC BY-SA 4.0
2022-06-24T05:02:29.330Z
Why 2? As in, is it already known/easy for “at least 1”?
daniello
CC BY-SA 4.0
2022-06-24T19:36:36.440Z
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.
karmanaut
CC BY-SA 4.0
2022-06-29T04:16:33.217Z
Is there a way on this website to send Bat-signal to lord commander @RyanWilliams?
karmanaut
<ds.algorithms><lower-bounds><matrices>
Deciding if all matrix multiplication entries have at least two witnesses
karmanaut
# Deciding if all matrix multiplication entries have at least two witnesses

(Asked by: username_0 on 2022-06-20)

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.

**Tags:** ds.algorithms, lower-bounds, matrices

> **Comments:**
> **username_1**: Why 2? As in, is it already known/easy for “at least 1”?  
> **username_0**: 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.  
> **username_0**: Is there a way on this website to send Bat-signal to lord commander @RyanWilliams?  

---

## 1 answers

### Answer by username_2 on 2022-07-01. Score: 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$.

> **Comments:**
> **username_0**: 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 https://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).  
> **username_2**: 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.  
> **username_0**: 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$.  

---

