THE MAXIMUM DETERMINANT OF AN N X N LOWER HESSENBERG (0, 1) MATRIX

Let A = (a(ij)) be an n X n (0, 1) matrix which is lower Hessenberg, i.e., a(ij) = 0 for j > i + 1. There are 2n-1 (possibly nonzero) terms in the determinant of an n X n lower Hessenberg (0, 1) matrix so this is a trivial upper bound for the determinant. We define an n X n (0, 1) matrix D(n) and show that this upper bound is det D(n) = 1/square-root 5[(1 + square-root 5/2)n - (1 - square-root 5/3)n] Here det D(n) is the nth Fibonacci number, i.e., det D(n) = det D(n-1) + det D(n-2) and det D1 = det D2 = 1 One has det D(n) --> infinity as n --> infinity. This answers positively a question due to W. W. Barrett.