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.