|
Let U(n;k) be the set of all
n×n binary matrices with k ones in each row and column. Considering the relation
between the permanent and the determinant for matrices in U(n;k), Tinsley
established the following result:
Theorem: Let C ∈ U(7;3) be the cyclic matrix defined by the differences 0,1,3(
mod 7). Let A ∈ U(n;k) with k ≧ 3. Suppose that there are permutation
matrices P1,P2,⋯,Pk ∈ U(n;1) such that A = P1 + P2 + ⋯ + Pk and
PiPj = PjPi(i,j = 1,⋯,k). Then per A = |detA| if and only if k = 3, 7 |n, and the
rows and columns of A can be permuted in euch a way that the resulting matrix is
the direct sum of C taken n∕7 times. Ryser posed
Conjecture I. Tinsley’s Theorem remains valid when the condition
PiPj = PjPi(i,j = 1,⋯,k) is dropped.
Discovery of counterexamples to Conjecture I leads directly to counterexamples to
the following conjecture of de Oliveira:
Conjecture II. Let A be an n×n doubly stochastic irreducible matrix. If n is even,
then f(z) = per (zI −A) has no real roots; if n is odd, then f(z) = per(zI −A) has
one and only real root.
|
