Volume: 468 • Pages: 63-79

In this paper, we consider the problem of factorizing the n×n matrix Jn of all ones into the n×n binary matrices. We show that under some conditions on the factors, these are isomorphic to a row permutation of a De Bruijn matrix. Moreover, we consider in particular the binary roots of Jn, i.e. the binary solutions to Am=Jn. On the one hand, we prove that any binary root with minimum rank is isomorphic to a row permutation of a De Bruijn matrix whose row permutation is represented by a block diagonal matrix. On the other hand, we partially solve Hoffman's open problem of characterizing the binary solutions to A2=Jn by providing a characterization of the binary solutions to A2=Jn with minimum rank. Finally, we provide a class of roots which are isomorphic to a De Bruijn matrix.