Permanents of Hessenberg (0,1)-matrices

MaRDI QIDQ2583672zbMATH OpenFDO

Authors D. D. Olesky, Bryan L. Shader, P. van den Driessche

Publication date 17 January 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/125922, http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1r70.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

binary Hessenberg matrixmaximum permanentstaircase

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15) Matrices of integers (15B36)

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.

Recommendations

• Permanents of Hessenberg (0,1)-matrices revisited
• Extremes of permanents of \((0,1)\)-matrices.
• scientific article; zbMATH DE number 3966317
• Maximum permanents of matrices of zeros and ones
• scientific article; zbMATH DE number 1921368

Cited in

(5)

• A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\).
• An identity between the determinant and the permanent of Hessenberg-type matrices
• scientific article; zbMATH DE number 2187090 (Why is no real title available?)
• Permanents of Hessenberg (0,1)-matrices revisited
• scientific article; zbMATH DE number 3998017 (Why is no real title available?)

This page was built for publication: Permanents of Hessenberg (0,1)-matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583672)