<p>No, the bit complexity of matrix multiplication on $M$-bit entries is $n^{\omega} (\log n)^{O(1)} \cdot M (\log M)^{O(1)}$, where $\omega &lt; 2.4$ is the best known matrix multiplication exponent. Multiplication and addition of $M$-bit numbers can be done in $M (\log M)^2$ time. Multiplying two $M$-bit numbers yields a number which has no more than $2M$ bits. Adding $n$ numbers of $M$ bits each, yields a number which has no more than $M+\log n+O(1)$ bits. (Think about it: the sum is at most $n 2^M$, so the bit representation takes no more than $\log (n 2^M)+O(1)$ bits.)</p>

<p>References to fast integer multiplication algorithms can be found with a web search or wikipedia.</p>

CC BY-SA 2.5
2010-10-21T03:03:53.223Z
I think my argument was flawed. Thank you. I appreciate this.
Turbo
CC BY-SA 2.5
2010-10-21T03:00:47.943Z
2010-10-21T03:00:47.943Z
Ryan Williams
<p>Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry of both matrices being multiplied) of size $m$ bits, the addition operation actually happens on $O(n^{3}nm) = O(n^{4}m)$ bits.</p>

<p>So it seems that the true complexity of matrix multiplication if measured via bit complexity should be $O(n^{4})$. </p>

<p>$(1)$Is this correct?</p>

<p>Supposing if one creates an algorithm which reduces the bit complexity to $O(n^{3+\epsilon})$ rather than total multiplications and additions, this might be a sounder approach than say reducing the total multiplications and additions to $O(n^{2+\epsilon})$ as attempted by researchers such as Coppersmith and Cohn.</p>

<p>$(2)$ Is this a valid argument?</p>

<cc.complexity-theory><algebraic-complexity>
True Bit Complexity of matrix multiplication is $O(n^{4})$
Turbo
# True Bit Complexity of matrix multiplication is $O(n^{4})$

(Asked by: username_0 on 2010-10-21)

Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry of both matrices being multiplied) of size $m$ bits, the addition operation actually happens on $O(n^{3}nm) = O(n^{4}m)$ bits.

So it seems that the true complexity of matrix multiplication if measured via bit complexity should be $O(n^{4})$.

$(1)$Is this correct?

Supposing if one creates an algorithm which reduces the bit complexity to $O(n^{3+\epsilon})$ rather than total multiplications and additions, this might be a sounder approach than say reducing the total multiplications and additions to $O(n^{2+\epsilon})$ as attempted by researchers such as Coppersmith and Cohn.

$(2)$ Is this a valid argument?

**Tags:** cc.complexity-theory, algebraic-complexity


---

## 1 answers

### Answer by username_1 on 2010-10-21. Score: 31 | Accepted answer

No, the bit complexity of matrix multiplication on $M$-bit entries is $n^{\omega} (\log n)^{O(1)} \cdot M (\log M)^{O(1)}$, where $\omega < 2.4$ is the best known matrix multiplication exponent. Multiplication and addition of $M$-bit numbers can be done in $M (\log M)^2$ time. Multiplying two $M$-bit numbers yields a number which has no more than $2M$ bits. Adding $n$ numbers of $M$ bits each, yields a number which has no more than $M+\log n+O(1)$ bits. (Think about it: the sum is at most $n 2^M$, so the bit representation takes no more than $\log (n 2^M)+O(1)$ bits.)

References to fast integer multiplication algorithms can be found with a web search or wikipedia.

> **Comments:**
> **username_0**: I think my argument was flawed. Thank you. I appreciate this.  

---

