Vol. 44, No. 2, 1973

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1  2
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
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
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
Abstract

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
Milestones
Received: 18 October 1971
Revised: 19 January 1972
Published: 1 February 1973
Authors
Roy Bruce Levow