Permanents of Hessenberg (0,1)-matrices

Abstract

Let $P\left( m,n\right) $ denote the maximum permanent of an $n$-by-$n$ lower Hessenberg $(0,1) $-matrix with $m$ entries equal to 1. A "staircased" structure for some matrices achieving this maximum is obtained, and recursive formulas for computing $P\left( m,n\right) $ are given. This structure and results about permanents are used to determine the exact values of $P\left( m,n\right) $ for $n \leq m \leq 8n/3$ and for all $\hbox{nnz}(H_n)-\hbox{nnz}(H_{\lfloor n/2 \rfloor}) \leq m \leq \hbox{nnz}(H_n)$, where $\hbox{nnz}(H_n)=(n^2+3n-2)/2$ is the maximum number of ones in an $n$-by-$n$ Hessenberg $(0,1)$-matrix.