<p>Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: &quot;set A[i,j] = 1&quot;, &quot;set B[i,j] = 1&quot;. The result of each operation is a set of updated cells (not just affected, it is important that value is changed from 0 to 1) in matrix C. Is there any research on this problem? Can we do the update (theoretically) faster than in a naive way? For example, are there estimations on possible speedup by a logarithmic factor? The problem looks slightly similar to incremental transitive closure or dynamic matrix inverse, but quite specific.</p>

CC BY-SA 4.0
2020-07-25T07:37:19.980Z
Could you specify what kind of result you expect ? The matrix product is bilinear, so $(A_1+A_2)\times B=A_1\times B+ A_2\times B$, and doing each update is therefore pretty easy (linear in one of the dimensions).
xavierm02
CC BY-SA 4.0
2020-07-28T10:03:38.027Z
@xavierm02 Thank you! I try to find a theoretically optimal solution. Can we do the update better than in a naive way? The original question is extended.
gsv
CC BY-SA 4.0
2020-07-28T22:42:42.857Z
If you start with $A=0$, and $B$ with each cell equal to $1$, then adding a $1$ to $A$ induces $n$ writes in $C$. So unless you take a non-standard representation for $C$, you can't get anything sublinear in the dimension in the worst case.
xavierm02
<matrices><matrix-product><dynamic-algorithms><boolean-matrix>
Dynamic matrix-matrix multiplication
gsv
# Dynamic matrix-matrix multiplication

(Asked by: username_0 on 2020-07-22)

Suppose A and B are initial Boolean matrices. Let C = A\*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1". The result of each operation is a set of updated cells (not just affected, it is important that value is changed from 0 to 1) in matrix C. Is there any research on this problem? Can we do the update (theoretically) faster than in a naive way? For example, are there estimations on possible speedup by a logarithmic factor? The problem looks slightly similar to incremental transitive closure or dynamic matrix inverse, but quite specific.

**Tags:** matrices, matrix-product, dynamic-algorithms, boolean-matrix
> **Comments:**
> **username_1**: Could you specify what kind of result you expect ? The matrix product is bilinear, so $(A_1+A_2)\times B=A_1\times B+ A_2\times B$, and doing each update is therefore pretty easy (linear in one of the dimensions).  
> **username_0**: @xavierm02 Thank you! I try to find a theoretically optimal solution. Can we do the update better than in a naive way? The original question is extended.  
> **username_1**: If you start with $A=0$, and $B$ with each cell equal to $1$, then adding a $1$ to $A$ induces $n$ writes in $C$. So unless you take a non-standard representation for $C$, you can't get anything sublinear in the dimension in the worst case.  

---

## 0 answers

