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

Research output: Working paperDiscussion paperOther research output

235 Downloads (Pure)

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

Fingerprint

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

Keywords

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

Cite this

Haemers, W. H., & Peeters, M. J. P. (2011). The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank. (CentER Discussion Paper; Vol. 2011-113). Tilburg: Operations research.
Haemers, W.H. ; Peeters, M.J.P. / The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank. Tilburg : Operations research, 2011. (CentER Discussion Paper).
@techreport{cd086add9be744aea1cd7df4db73aab5,
title = "The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank",
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{\'a}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.",
keywords = "(0, 1)-matrix, rank, graph",
author = "W.H. Haemers and M.J.P. Peeters",
note = "Subsequently published in the Electronic Journal of Linear Algebra (2012)",
year = "2011",
language = "English",
volume = "2011-113",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Haemers, WH & Peeters, MJP 2011 'The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank' CentER Discussion Paper, vol. 2011-113, Operations research, Tilburg.

The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank. / Haemers, W.H.; Peeters, M.J.P.

Tilburg : Operations research, 2011. (CentER Discussion Paper; Vol. 2011-113).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

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

AU - Haemers, W.H.

AU - Peeters, M.J.P.

N1 - Subsequently published in the Electronic Journal of Linear Algebra (2012)

PY - 2011

Y1 - 2011

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

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

KW - (0

KW - 1)-matrix

KW - rank

KW - graph

M3 - Discussion paper

VL - 2011-113

T3 - CentER Discussion Paper

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

PB - Operations research

CY - Tilburg

ER -

Haemers WH, Peeters MJP. The Maximum Order of Reduced Square(0, 1)-Matrices with a Given Rank. Tilburg: Operations research. 2011. (CentER Discussion Paper).