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 P_{1},P_{2},⋯,P_{k} ∈ U(n;1) such that A = P_{1} + P_{2} + ⋯ + P_{k} and
P_{i}P_{j} = P_{j}P_{i}(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
P_{i}P_{j} = P_{j}P_{i}(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.
