Permanents of Hessenberg (0,1)-matrices revisited

Abstract

This paper considers the maximum value of the permanent over the class H(m,n) of n×n Hessenberg, (0,1)-matrices with m 1’s, and shows that among those matrices that attain the maximum value there exists a matrix with a special form. This special form determines the exact value of the maximum permanent on H(m, n) for certain values of m and n.