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) \]
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 \]
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:
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.
Let’s let last be the last expression. Now, we reshape it to an \[ n \times n \] matrix.
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.
Finally, we parameterize the whole thing by the matrix size \[ n \] using another anonymous function.
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:
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 = 6At 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).