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

W.H. Haemers; M.J.P. Peeters

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

Research output: Working paper › Discussion paper › Other 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 language	English
Place of Publication	Tilburg
Publisher	Operations research
Volume	2011-113
Publication status	Published - 2011

Publication series

Name	CentER Discussion Paper
Volume	2011-113

Keywords

(0
1)-matrix
rank
graph

Access to Document

2011-113

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

@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",

}

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 -