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:


*

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

*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. 
 A: 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. 
A: 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)$.
A: 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.
