Uniform and minimal {0,1} – cp matrices

Abstract

Let A be an n × n real matrix. A is called {0,1}-cp if it can be factorized as A = BB ^T with b_ij =0 or 1. The smallest possible number of columns of B in such a factorization is called the {0,1}-rank of A. A {0,1}-cp matrix A is called minimal if for every nonzero nonnegative n × n diagonal matrix D, A-D is not {0,1}-cp, and r-uniform if it can be factorized as A=BB ^T, where B is a (0, 1) matrix with r 1s in each column. In this article, we first present a necessary condition for a nonsingular matrix to be {0,1}-cp. Then we characterize r-uniform {0,1}-cp matrices. We also obtain some necessary conditions and sufficient conditions for a matrix to be minimal {0,1}-cp, and present some bounds for {0,1}-ranks.

Keywords:

• {0, 1} – Cp
• Uniform {0, 1} – cp
• Minimal {0, 1} – cp
• AMS Subject Classifications:
• 15A23
• 15A48

Acknowledgement

A. Berman was supported by the New York Metropolitan Research Fund at the Technion. C. Xu was supported by a postdoctoral scholarship from the Israel Council for Higher education. We are grateful to the referee for his/her helpful comments.