# True Bit Complexity of matrix multiplication is $O(n^{4})$

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?

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