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