# Complexity of matrix multiplication over $\mathbb F_2$

I've been reading about theoretical bounds on the computational complexity of $$n\times n$$ matrix-matrix multiplication in floating-point arithmetic, about how the complexity is known to fall between $$\mathcal O(n^2)$$ and $$\mathcal O(n^3)$$, and how the exponent has been slowly whittled down over time by various researchers. It's currently unknown whether a $$\mathcal O(n^2)$$ algorithm is possible.

I was wondering about what the complexity of multiplying two bit-matrices over the finite field $$\mathbb F_2$$ (or other finite fields - my intuition tells me the complexity will be the same), but I haven't found any references online. Are there any known "tricks" for multiplying matrices in $$\mathbb F_2^{n\times n}$$ that makes it less expensive than multiplication in larger fields or in floating point? What current bounds are known? Is there a known $$\mathcal O(n^2)$$ algorithm? Can anyone provide any relevant references for these sort of questions?

• This is a good and interesting question. In case it doesn't get answered here, you could also always try computer science stackexchange cs.stackexchange.com or if no answer there then maybe even cstheory.stackexchange.com Apparently even for reals, you can do slightly better than otherwise possible if you have sparse matrices: quantamagazine.org/… So I think it is quite reasonable to expect that, given even more special structure, e.g. like $\mathbb{F}_2$, faster algorithms could be possible. Commented Feb 15, 2022 at 17:22

In general, it is no more efficient to multiply over $$\mathbb{F}_2$$ compared to over $$\mathbb{R}$$ unless you have sparse matrices or special structure.

Even though there are efficient algorithms for certain arithmetic and polynomial operations over finite fields (and in particular $$\mathbb{F}_2$$ this efficiency does not seem to extend to make an asymptotic difference in the complexity of matrix multiplication.

See the answers in mathoverflow to a similar question for more details, I will quote a small part from there below:

For $$\mathbb{F}_2$$ (and other finite fields of characteristic $$2$$) there is a specialized library for computing with matrices over that structure.

It is called M4RI. In particular, a paper by developpers of the library: Martin Albrecht, Gregory Bard, William Hart. Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2). ACM Transactions on Mathematical Software 2010.

Preprint at http://arxiv.org/abs/0811.1714.

Edit:

Thanks to @pcpthm for pointing this out, the claim below for the average complexity would not hold over $$\mathbb{F}_2$$ in such generality. Since the result over boolean algebras may still be of interest I will let the paragraph below stand.

However, due to the special structure of $$\mathbb{F}_2,$$ one can actually prove that on average matrix multiplication can be performed with complexity $$O(n^{2+\varepsilon})$$ elementary operations by a randomized algorithm, see this paper.

• It looks like the algorithm presented in the linked paper assumes Boolean semiring $\mathbb{B}$ (AND, OR), not $\mathbb{F}_2$ (XOR, AND). Commented Feb 17, 2022 at 13:14