On Invertibility of Large Binary Matrices

Many data processing applications involve binary matrices for storing digital information. At present, there are limited results in the literature about algorithms for inverting large binary matrices. This paper contributes the following three results. First, the divide-and-conquer methods for efficiently inverting large matrices over finite fields such as Strassen’s matrix inversion often fail on singular sub-blocks, even if the original matrix is non-singular. It is proposed to combine Strassen’s method with the PLU factorization at each recursive step in order to obtain robust pivoting, which correctly inverts all non-singular matrices over any finite field. The resulting algorithm is shown to maintain the sub-cubic time complexity. Second, although there are theoretical studies on how to systematically enumerate all invertible matrices over finite fields without redundancy, no practical algorithm has been reported in the literature that is easy to understand and also suitable for enumerating large matrices. The use of Bruhat decomposition has been proposed to enumerate all invertible matrices. It leverages the linear group-theoretic structure and defines an ordered sequence of invertible matrices, so that each matrix is generated exactly once. Third, large binary matrices have about 29% probability to be invertible. In some applications, it may be desirable to repair the singular matrices by performing a small number of bit-flips. It is shown that the minimum number of bit-flips is equal to the matrix rank deficiency, i.e., the minimum Hamming distance from the general linear group. The required bit-flips are identified by pivoting during the matrix inversion, so the matrix rank can be restored. The correctness and the time complexity of the proposed algorithms were verified both theoretically and empirically. The reference implementation of these algorithms in C++ is available on Github.