6
$\begingroup$

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.

  • 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: http://rjlipton.wordpress.com/2010/03/27/fast-matrix-products-and-other-amazing-results/2012-02-20
  • 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.2012-02-21
  • 1
    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.2012-02-21
  • 0
    Related question on MathOverflow: http://mathoverflow.net/questions/62125/invertible-matrices-of-natural-numbers-are-permutations-why2012-02-21
  • 0
    @Aryabhata and Yuval Thank you for the links.2012-02-21

3 Answers 3