# Invertible Bitmatrices

## Exposition

How many $$\{ 0, 1 \}$$ valued $$n \times n$$ matrices are invertible over $$\mathbb{R}$$?

Even at first glance, this question seems like it lends itself well to inductive reasoning. That means we just need to find a base case and a convenient inductive step.

For each matrix size $$n$$ there are $$2^{n^2}$$ possible bitmatrices. This is because each cell of the matrix can be either $$0$$ or $$1$$. This means there are $$2^1 = 2$$ possible bitmatrices of size $$1 \times 1$$ and they are $$\left( \begin{matrix} 1 \end{matrix} \right)$$ and $$\left( \begin{matrix} 0 \end{matrix} \right)$$.

A matrix $$A$$ is invertible iff $$A A^{-1} = I = A^{-1}A$$. We check multiplication in both orders since matrix multiplication is not commutative. A matrix $$A$$ is also only invertible iff its determinant is nonzero.

So far, we know there is $$1$$ invertible $$1 \times 1$$ bitmatrix: $$\left( \begin{matrix} 1 \end{matrix} \right)$$

## Listing initial cases by hand

Let’s move on to $$2 \times 2$$ matrices. There are $$2^{2^2} = 16$$ of them. We could write them all out by hand and find their determinants:

$\left| \begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix} \right| = 0, \: \left| \begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix} \right| = 0, \: \left| \begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix} \right| = 0, \: \left| \begin{matrix} 0 & 0 \\ 1 & 1 \end{matrix} \right| = 0, \\[1em] \left| \begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix} \right| = 0, \: \left| \begin{matrix} 0 & 1 \\ 0 & 1 \end{matrix} \right| = 0, \: \left| \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right| = -1, \: \left| \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right| = -1, \\[1em] \left| \begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix} \right| = 0, \: \left| \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right| = 1, \: \left| \begin{matrix} 1 & 0 \\ 1 & 0 \end{matrix} \right| = 0, \: \left| \begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix} \right| = 1, \\[1em] \left| \begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix} \right| = 0, \: \left| \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right| = 1, \: \left| \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right| = -1, \: \left| \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right| = 0$

## Solving the first few cases by computer

There are six invertible $$2 \times 2$$ bitmatrices (since their determinants are nonzero). However, it’d be nice to be able to generate all bitmatrices of size $$n$$ automatically so we can more easily examine and play with them. Luckily, we can do that with this Octave one-liner:

(@(n) arrayfun(@(x) reshape(bitget(x, n^2:-1:1), n, n), 0:2^(n^2)-1, 'UniformOutput', false))(3)

This is a bit dense so let’s explain it from the inside out. bitget returns a number as a vector of bits. We pass it the number x, and the range counting from $$n^2$$ down to $$1$$ as an index for which bits we want. For example, when passed 15 for $$x$$ and 3 for $$n$$, we get 0 0 0 0 0 1 1 1 1.

bitget(x, n^2:-1:1)

Let’s let last be the last expression. Now, we reshape it to an $$n \times n$$ matrix.

reshape(last, n, n)

After that we use arrayfun to apply an anonymous function of $$x$$ to every element of the $$n \times n$$ matrix. The anonymous function does bitget and reshape. We map this over the range $$\left[ 0, 2^{n^2}-1 \right]$$ because those are the possible bit values for an $$n \times n$$ matrix. We also set UniformOutput to false because Octave wants that.

arrayfun(@(x) last, 0:2^(n^2)-1, 'UniformOutput', false)

Finally, we parameterize the whole thing by the matrix size $$n$$ using another anonymous function.

(@(n) last)(3)

Let’s make sure that we can get the same number of invertible $$2 \times 2$$ bitmatrices from our code as we got by hand. All we have to do is count up the nonzero determinants. Our final one-liner, though a bit unwieldy, looks like this:

(@(n) length(nonzeros(arrayfun(@(x) det(reshape(bitget(x, n^2:-1:1), n, n)), 0:2^(n^2)-1))))(3)

And, it gives us the same answer for the $$2 \times 2$$ case!

octave:1> (@(n) length(nonzeros(arrayfun(@(x) det(reshape(bitget(x, n^2:-1:1), n, n)), 0:2^(n^2)-1))))(2)
ans =  6

## Getting Stuck

At this point I got really stuck. I was able to generate answers for small $$n$$, but didn’t see any reasonable formula for finding the number.

As a bonus double-check, if we look up $$1, 6, 174, 22560...$$ in OEIS we get the sequence we’re looking for. There’s even a formula! But the formula is presented in terms of another sequence. And that sequence’s formula is presented in terms of…this sequence. So a circular formula won’t help us much.

I also looked into the Leibniz formula, trying to see if I could find some pattern at play that might give insight into the special case of $$\{ 0, 1 \}$$ matrices.

$\mathrm{det}(A) = \sum_{\sigma \in S_n} \left( \mathrm{sgn}(\sigma) \prod_{i=1}^n a_{i, \sigma_i} \right)$

I still didn’t find anything, but really wanted to. After a few hours of banging my head against the problem and asking friends for help, I caved and looked for an answer directly. At least if I had the answer, maybe I could work backwards and determine some way to come up with that formula based on the pieces I already had. Maybe the two tracks of thinking could meet in the middle. It still felt like the kind of problem that I should be able to solve.

So what’s the actual answer? Turns out nobody knows (yet).