# Is there an $O(n^2)$ test to determine if an $n \times n$ Boolean matrix $B$ has an inverse?

D.E. Rutherford shows that if a Boolean matrix $B$ has an inverse, then $B^{-1}= B^T$, or $BB^T=B^TB=I$.

I have two related questions:

1. The only invertible Boolean matrices I can find are permutation matrices. Are there others?

2. Is there an $O(n^2)$ test to determine if an $n \times n$ Boolean matrix $B$ has an inverse?

Note: The $O(n^2)$ Matlab function I gave here is wrong.

UPDATE:

I have posted a new $O(n^2)$ Matlab invertibility test here.

-
It is probably still an open problem. cstheory.stackexchange.com might give you the latest best algorithm known. You might also want to read: rjlipton.wordpress.com/2010/03/27/… – Aryabhata Feb 20 '12 at 18:51
This question confused me at first: I suppose you are working over the semiring where addition is logical OR, i.e. 1+1=1, not over the field of order 2 where 1+1=0. – Nate Eldredge Feb 21 '12 at 2:24
Sorry Nate, I should have made it clear that $B$ is a boolean or logical matrix whose elements are True or False with the operations AND, OR, and NOT. – Derek O'Connor Feb 21 '12 at 2:42
Related question on MathOverflow: mathoverflow.net/questions/62125/… – Yuval Filmus Feb 21 '12 at 4:09
@Aryabhata and Yuval Thank you for the links. – Derek O'Connor Feb 21 '12 at 10:12

At http://www.mathnet.or.kr/mathnet/thesis_file/15_B07-0905.pdf there's a paper, Song, Kang, and Shin, Linear operators that preserve perimeters of boolean matrices, Bull. Korean Math. Soc. 45 (2008) 355-363. At the top of page 356, it says, "It is well known that the permutation matrices are the only invertible Boolean matrices (see [1])." The reference is to Beasley and Pullman, Boolean-rank-preserving operators and Boolean rank-1 spaces, Linear Algebra Appl. 59 (1984) 55-77. I haven't attempted to track down the Beasley-Pullman paper.

-
The review of Beasley-Pullman in Math Reviews doesn't mention the invertible Boolean matrices result, and I found some other papers that make use of invertible Boolean matrices without noting that they must be permutations, so I'm not vouching for the Song-Kang-Shin citation, just noting it. – Gerry Myerson Feb 21 '12 at 1:00
The Beasley and Pullman paper actually quotes two other papers for this result (in addition to proving it in their own Corollary 2.5.1(d) on page 61). The papers are: D. de Caen and D. A. Gregory, Primes in the semigroup of Boolean matrices, Linear Algebra Appl. 37:119-134 (1981) and D. J. Richman and H. Schneider, Primes in the semigroup of nonnegative matrices‌​, Linear and Multilinear Algebra 2:135-140 (1974). – cardinal Feb 21 '12 at 1:51
It's rather obvious. Suppose $AB = BA = I$ where $A$ and $B$ are Boolean matrices. $A$ and $B$ must have at least one $1$ in each row and column. If $A_{ij} = 1$, then we must have $B_{jk} = 0$ for all $k \ne i$ and $B_{ki} = 0$ for all $k \ne j$. So $B$ has only one $1$ in each row and column, and is a permutation matrix. – Robert Israel Feb 21 '12 at 2:24
@Derek: It answers both questions since a verification algorithm requires inspecting each entry of the matrix at most once. – cardinal Feb 21 '12 at 2:56
If it's that easy, why didn't Rutherford see it? – Gerry Myerson Feb 21 '12 at 3:13

For question 2, I am not aware of a result, but my intuition is that the answer is no. This is too long for a comment so I will post it as answer. Checking that $BB^T = I$ can be done in randomized $O(n^2)$ time (using random sampling as in Lipton's blogpost). But deterministically over any field, it needs $O(n^\omega)$ time using matrix matrix product [see these notes by A. Gupta]. If you present me with an algorithm for checking $B B^T = I$ in $O(n^2)$ then I can solve the problem in the course notes by A. Gupta, as follows. If $$B = \begin{pmatrix} A && -D \\ C && I \end{pmatrix}$$ then $$B B^T = \begin{pmatrix} \ldots && AC-D \\ \ldots && \ldots \end{pmatrix}.$$ I run your algorithm on $BB^T = I$. This is equivalent to deciding $AC -D = 0$, or $AC = D$ which we do not know how to solve in less than $O(n^\omega)$.
Hmm. But, if Gerry's answer is correct, there is a trivial $O(n^2)$ algorithm. Right? :) – cardinal Feb 21 '12 at 0:49
@cardinal No. I can't see how. Gerry's answer is concerning question 1. So if permutation matrices are the only permutation matrices, then we need to check if the input $B$ is a permutation matrix. I can't see how you solve this in $O(n^2)$. – user2468 Feb 21 '12 at 1:05
If the only invertible Boolean matrices are permutation matrices then my second question becomes 'Is there an $O(n^2)$ test for a permutation matrix?'. I think the answer is yes. Just do as cardinal says. Or convert the permutation matrix into a permutation vector in $O(n^2)$ time and test the permutation vector in $O(n)$ time. – Derek O'Connor Feb 21 '12 at 6:34
If addition is defined modulo two, it becomes xor, while multiplication becomes the 'and' operation. Using these with Gauss Jordan elimination yields that an inverse to $\begin{bmatrix}0 & 1 & 0\\0 & 1 & 1\\1 & 0 & 1\end{bmatrix}$ is $\begin{bmatrix}1 & 1 & 1\\1 & 0 & 0\\1 & 1 & 0\end{bmatrix}$, and multiplying out confirms that you do get the identity matrix, so that is at least one counter example.