Short Factorization of Invertible Binary Matrices based on Optimizing Pivoting in Gaussian Elimination

Inhalt:
Gaussian elimination is a classical algorithm in linear algebraic programming, there are many situations for using Gaussian elimination. For a binary matrix, i.e., a matrix whose elements are only 0 or 1, we can factor it into the product of a permutation matrix and a series of row-addition transformation matrices via Gaussian elimination. The problem of finding such a factorization with as few row-addition transformation matrices as possible is of great importance in engineering applications. In this paper we propose a greedy algorithm to tackle the problem. The main idea lies in eliminating most of 1s in every row operation in the process of Gaussian elimination. We implement our algorithm by C++ code and test I t with a number of real-world data sets. It turns out that our algorithm and implementation behave well for most of the tested data.