Permanental bounds for nonnegative matrices via decomposition

✍ Scribed by George W. Soules

• Book ID: 104036097
• Publisher: Elsevier Science
• Year: 2005
• Tongue: English
• Weight: 288 KB
• Volume: 394
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2004.06.022

✦ Synopsis

We investigate an old suggestion of A.E. Brouwer we call decomposition, for constructing a class of permanental upper bounds for nonnegative matrices A from a single permanental upper bound u(B) for (0, 1)-matrices B. For certain feasible u, which include the Minc-Brègman bound u(B) = M(B) and the Jurkat-Ryser bound u(B) = J (B), we can identify the best and worst of these decomposition bounds. The best decomposition bound, the star bound U * (A), is the only decomposition bound which agrees with u on the (0, 1)-matrices.

If u = J , then U * (A) turns out to be the very bound U J (A) used by Jurkat and Ryser to obtain J as a special case. If u = M, then U * (A) is a new upper bound U M (A). We believe its sharpened version U M G (A) to be the best extant permanental upper bound for nonnegative matrices as well as for (0, 1)-matrices.