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