¿Hay una prueba de $O(n^2)$ para determinar si una matriz booleana de $n \times n$ $B$ tiene una inversa?

Question

D. E. Rutherford muestra que si una matriz Booleana $B$ tiene una inversa, a continuación, $B^{-1}= B^T$ o $BB^T=B^TB=I$.

Tengo dos preguntas:

1. La única invertible Booleano matrices de lo que puede encontrar son permutación las matrices. ¿Hay otros?

2. Hay un $O(n^2)$ prueba para determinar si una $n \times n$ Booleano matriz $B$ tiene una inversa?

Nota: El $O(n^2)$ la función de Matlab que me dieron aquí está mal.

ACTUALIZACIÓN:

He publicado una nueva $O(n^2)$ Matlab invertibility de prueba aquí.

Answer 1

En http://www.mathnet.or.kr/mathnet/thesis_file/15_B07-0905.pdf hay un papel, Canción, Kang, y Shin, Lineal operadores que preservan los perímetros de matrices booleanas, Bull. Coreano De Matemáticas. Soc. 45 (2008) 355-363. En la parte superior de la página 356, dice, "es bien sabido que la permutación de matrices son sólo invertible Booleano matrices (ver [1])." La referencia es a Beasley y Pullman, Boolean-rango-la preservación de los operadores Booleanos rango-1 espacios, Álgebra Lineal Appl. 59 (1984) 55-77. No he intentado seguir la pista de las Beasley-Pullman de papel.