### 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*. (CentER Discussion Paper; Vol. 2011-113). Tilburg: Operations research.

}

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

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 -