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:
(@(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 = 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).