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.

  • 0
    @Aryabhata and Yuval Thank you for the links.2012-02-21

3 Answers 3

1

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.

  • 0
    @cardinal - Using Robert Israel's result and your advice I have written an $O(n^2)$ Matlab function to test if the Boolean matrix $B$ is a permutation matrix. See the link in my Update above.2012-02-23
0

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

  • 0
    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.2012-02-21
0

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.