The maximum order of reduced square (0,1)-matrices with a given rank

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The maximum order of a square (0, 1)-matrix A with a fixed rank r is considered, provided A has no repeated rows or columns. When A is the adjacency matrix of a graph, Kotlov and Lovász [A. Kotlov and L. Lovász. The rank and size of graphs. J. Graph Theory, 23:185–189,
1996.] proved that the maximum order equals Θ(2r/2). In this note, it is showed that this result remains correct if A is symmetric, but becomes false if symmetry is not required.
Original languageEnglish
Pages (from-to)3-6
JournalElectronic Journal of Linear Algebra
Volume24
Publication statusPublished - 2012

    Fingerprint

Cite this