Permanents of Hessenberg (0,1)-matrices (Q2583672)

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.