The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank

Research output: Working paperDiscussion paperOther research output

Abstract

We look for the maximum order of a square (0, 1)-matrix A with a fixed rank r, provided A has no repeated rows or columns. If A is the adjacency matrix of a graph, Kotlov and Lovász [J. Graph Theory 23, 1996] proved that the maximum order equals Θ(2r/2). In this note we show that this result remains correct if A is symmetric, but becomes false if symmetry is not required.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Volume2011-113
Publication statusPublished - 2011

Publication series

NameCentER Discussion Paper
Volume2011-113

Keywords

  • (0
  • 1)-matrix
  • rank
  • graph

Fingerprint Dive into the research topics of 'The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank'. Together they form a unique fingerprint.

Cite this