### Abstract

Let P_{n}^{k} be the maximum value achieved by the permanent over Λ_{n}^{k}, the set of (0,1)-matrices of order n with exactly k ones in each row and column. Brègman proved that P_{n}^{k}≤k!^{n/k}. It is shown here that P _{n}^{k}≥k!^{t}r! where n=tk+r and 0≤r<k. From this simple bound we derive that (P_{n}^{k}) ^{1/n}∼k!^{1/k} whenever k=o(n) and deduce a number of structural results about matrices which achieve P_{n}^{k}. These include restrictions for large n and k on the number of components which may be drawn from Λ_{k+c}^{k} for a constant c≥1.Our results can be directly applied to maximisation problems dealing with the number of extensions to Latin rectangles or the number of perfect matchings in regular bipartite graphs.

Original language | English |
---|---|

Pages (from-to) | 153-167 |

Number of pages | 15 |

Journal | Linear Algebra and Its Applications |

Volume | 373 |

Issue number | SUPPL. |

DOIs | |

Publication status | Published - 1 Nov 2003 |

Externally published | Yes |

Event | Combinatorial Matrix Theory Conference (POSTECH) - Pohang, Korea, Republic of (South) Duration: 14 Jan 2002 → 17 Jan 2002 |

### Keywords

- (0,1) matrix
- Bregman bound
- Latin rectangle
- Merriell's conjecture
- Permanent
- Regular bipartite graph