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


❮ Magic Square Generation
Generating magic squares with backtracking, in Rust
Currying and Macros ❯
Partially applied higher-order functions can replace some macros