An upper bound for the permanent of a nonnegative matrix

✍ Scribed by Suk-Geun Hwang; Arnold R. Kräuter; T.S. Michael

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 311 KB
• Volume: 281
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(98)10040-x

✦ Synopsis

Let A be a fully indecomposable, nonnegative matrix of order n with row sums rt,..., ~;,, and let s~ equal the smallest positive element in row i of A. We prove the permanental inequality 11 II per(A) ~< 1-I s, + IX('"-s;) i::1 i::1 and characterize the case of equality. In 1984 Donald, Elwin, Hager, and Salamon gave a graph-theoretic proof of the special case in which A is a nonnegative integer matrix.