Abstract
| 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 |
Fingerprint
Keywords
- (0
- 1)-matrix
- rank
- graph
Cite this
}
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 paper › Discussion paper › Other 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 -