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

(0, 1)-matrices
Adjacency Matrix
Graph in graph theory
Graph theory
Symmetry
False

Cite this

@article{4d0f6b7a344e4a62b221daa605ea8fa7,
title = "The maximum order of reduced square (0,1)-matrices with a given rank",
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{\'a}sz [A. Kotlov and L. Lov{\'a}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.",
author = "W.H. Haemers and M.J.P. Peeters",
note = "Appeared earlier as CentER Discussion Paper 2011-113",
year = "2012",
language = "English",
volume = "24",
pages = "3--6",
journal = "Electronic Journal of Linear Algebra",
issn = "1081-3810",
publisher = "International Linear Algebra Society",

}

The maximum order of reduced square (0,1)-matrices with a given rank. / Haemers, W.H.; Peeters, M.J.P.

In: Electronic Journal of Linear Algebra, Vol. 24, 2012, p. 3-6.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - Haemers, W.H.

AU - Peeters, M.J.P.

N1 - Appeared earlier as CentER Discussion Paper 2011-113

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Article

VL - 24

SP - 3

EP - 6

JO - Electronic Journal of Linear Algebra

JF - Electronic Journal of Linear Algebra

SN - 1081-3810

ER -