Vol. 44, No. 2, 1973

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Author Index
To Appear
Other MSP Journals
Counterexamples to conjectures of Ryser and de Oliveira

Roy Bruce Levow

Vol. 44 (1973), No. 2, 603–606

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.

Mathematical Subject Classification 2000
Primary: 15A36
Secondary: 15A51
Received: 18 October 1971
Revised: 19 January 1972
Published: 1 February 1973
Roy Bruce Levow