Permanents of Hessenberg (0,1)-matrices
type: Item
instance of: scholarly article
title: Permanents of Hessenberg (0,1)-matrices
zbMATH Open document ID: 1086.15007
author: D. D. Olesky
author: Bryan L. Shader
author: P. van den Driessche
published in: The Electronic Journal of Combinatorics
publication date: 2006-01-17T00:00:00Z
full work available at URL: https://eudml.org/doc/125922
full work available at URL: v12i1r70.html
review text: This paper concerns the function \(P(m,n)\) defined to be the maximum permanent over all \(n\times n\) binary Hessenberg matrices with \(m\) entries equal to \(1\) (and hence \(n^2-m\) entries equal to \(0\)). The first theorem shows that \(P(m,n)\) is always achieved (perhaps not uniquely) by a Hessenberg matrix with a certain ``staircase'' structure. This characterisation is then used to derive several formulae which enable \(P(m,n)\) to be calculated in many instances (though by no means all). Problems of finding the maximum permanent over classes of binary matrices are important but tend to be very difficult. In that context, the authors' choice of problem is sensible and their results commendable.
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 2248142
zbMATH Keywords: maximum permanent
zbMATH Keywords: binary Hessenberg matrix
zbMATH Keywords: staircase
reviewed by: Ian M. Wanless
MaRDI profile type: Publication
description: scientific article