Possible numbers of ones in the squares of 0–1 matrices with a given rank

Abstract

For a symmetric 0–1 matrix A, we give the number of ones in A ² when rank(A) = 1, 2, and give the maximal number of ones in A ² when rank(A) = k (3 ≤ k ≤ n). The sufficient and necessary condition under which the maximal number is achieved is also obtained. For generic 0–1 matrices, we only study the cases of rank 1 and rank 2.

Keywords:

• 0–1 matrix
• square of a 0–1 matrix
• symmetric matrix
• rank
• number of ones

AMS subject classifications::

• 15A03
• 15A36
• 05B20

Acknowledgements

The author is grateful to Professor Xingzhi Zhan for suggesting that she study this problem and the referees for their careful reading of the manuscript and helpful comments. Supported by NSFC (No. 10571060).