Permanents and determinants of (0,1) matrices

[Edwin Clark]

On Fri, 31 Oct 2003, Meeussen Wouter (bkarnd) wrote:

> Determinants: n=1..4
> {2, 3, 5, 7}
> 
> {
> {{0, 1}, {1, 1}}, 
> {{-1, 3}, {0, 10}, {1, 3}}, 
> {{-2, 3}, {-1, 84}, {0, 338}, {1, 84}, {2, 3}}, 
> {{-3, 60}, {-2, 1200}, {-1, 10020}, {0, 
>       42976}, {1, 10020}, {2, 1200}, {3, 60}}
> }
> read this as:
> Determinants, n=2; reads as:
> {{Det=-1, 3 times}, {Det=0, 10 times}, {Det=1, 3 times}}
> 3+10+3= 16 cases in all= 2^(2^2)
> 


It is tempting to conjecture that the values of the determinant on nxn
(0,1) matrices are the intergral interval [-(n-1),(n-1)]. However the
following paper asserts otherwise:

Craigen, R.(3-WTRL)
The range of the determinant function on the set of $n\times n$
$(0,1)$-matrices.
J. Combin. Math. Combin. Comput. 8 (1990), 161--171.
--------------------------------------------------------------------------------
It has been conjectured that the determinant function maps the set of
$n\times n$ $(0,1)$-matrices onto a set of consecutive integers for any
given $n$. The author shows this to be false (it does not hold in
particular for $n=7$) and then further discusses the range of the
determinant function. Several open questions are given.

Another paper shows that there are nxn (0,1) matrices with determinant =
the n-th Fibonacci number:

Li, Ching 
The maximum determinant of an $n\times n$ lower Hessenberg $(0,1)$
matrix. (English. English summary) 
Linear Algebra Appl. 183 (1993), 147--153.
------------------------------------------------------------------------
For a positive integer $n>2$, an $n\times n$ $(0,1)$ matrix $A=(a_{ij})$
is said to be lower Hessenberg if $a_{ij}=0$ for $j>i+1$. There are at
most $2^{n-1}$ nonzero terms in the determinant of an $n\times n$ lower
Hessenberg $(0,1)$ matrix, so this is a trivial upper bound for the
determinant. The author defines an $n\times n$ lower Hessenberg $(0,1)$
matrix $D_n$ with determinant equal to the $n$th Fibonacci number and
proves that $|\det A|\leq \det D_n$ for any $n\times n$ lower Hessenberg
$(0,1)$ matrix $A$. This result answers a question due to W. W. Barrett
\ref[Linear Algebra Appl. 107 (1988), 315--316].

--Edwin