Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
2  
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

2 Answers 2

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.

share|improve this answer
1  
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
1  
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
2  
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
1  
@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
1  
If it's that easy, why didn't Rutherford see it? –  Gerry Myerson Feb 21 '12 at 3:13

Edit: Wrong answer. See comments below.

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

share|improve this answer
1  
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
    
Oops. Typo. I meant: "So if permutation matrices are the only invertible Boolean matrices,..." –  user2468 Feb 21 '12 at 1:13
1  
Do a single pass scan of each column noting the location of the entry that is one in each column and look for duplicates along the way? –  cardinal Feb 21 '12 at 1:21
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.