A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case

DOI10.1016/0024-3795(84)90031-4MaRDI QIDQ801134zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 1984

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(84)90031-4

zbMATH Keywords

fully indecomposablemultigraphsnonnegative integer matrixpermanent

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15) Matrices of integers (15B36)

Review text

[For part I see ibid. 61, 187-198 (1984; reviewed above)]. Let A be a fully indecomposable \(n\times n\) matrix with integer entries and row and column sums \(r_ i\) and \(c_ i\), respectively. Matrices A are characterized for which per A\(=1+\min [\prod_{i}(r_ i- 1),\prod_{i}(c_ i-1)]\) holds.

Recommendations

• A graph theoretic upper bound on the permanent of a nonnegative integer matrix. I
• An upper bound for the permanent of a nonnegative matrix
• Maximum permanents on certain classes of nonnegative matrices
• Comparison of permanental bounds of \((0,1)\)-matrices
• A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\).

Cites work

• A graph theoretic upper bound on the permanent of a nonnegative integer matrix. I
• A graph theoretical interpretation of nonsymmetric permutation on sparse matrices
• A Simplified Form for Nearly Reducible and Nearly Decomposable Matrices
• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• Problems Involving Diagonal Products in Nonnegative Matrices

Cited in

(10)

• Handle bases and bounds on the number of subgraphs
• Partially decomposable and totally indecomposable nonnegative matrices
• Comparison of permanental bounds of \((0,1)\)-matrices
• An upper bound for the permanent of a nonnegative matrix
• Matrix choosability
• Geršgorin variations. III: On a theme of Brualdi and Varga
• Fully indecomposable and nearly decomposable matrices in Ω(r,s)
• Additive decomposition of nonnegative matrices with applications to permanents and scalingt
• Balancing permuted copies of multigraphs and integer matrices
• A graph theoretic upper bound on the permanent of a nonnegative integer matrix. I

This page was built for publication: A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q801134)