Permanental bounds for nonnegative matrices via decomposition Original Research Article

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 UJ(A) used by Jurkat and Ryser to obtain J as a special case. If u = M, then U*(A) is a new upper bound UM(A). We believe its sharpened version image to be the best extant permanental upper bound for nonnegative matrices as well as for (0, 1)-matrices.