An upper bound for the permanent of a $3$-dimensional $(0,1)$-matrix
HTML articles powered by AMS MathViewer
- by Stephen J. Dow and Peter M. Gibson PDF
- Proc. Amer. Math. Soc. 99 (1987), 29-34 Request permission
Abstract:
Let $A = ({a_{ijk}})$ be a $3$-dimensional matrix of order $n$. The permanent of $A$ is defined by \[ \operatorname {per} A = \sum \limits _{\sigma ,\tau \in {S_n}} {\prod \limits _{i = 1}^n {{a_{i\sigma (i)\tau (i)}},} } \] where ${S_n}$ is the symmetric group on $\{ 1,2, \ldots ,n\}$. Suppose that $A$ is a (0,1)-matrix and that ${r_i} = \sum \nolimits _{j,k = 1}^n {{a_{ijk}}} {\text { for }}i = 1,2, \ldots ,n$. In this paper it is shown that per $A \leq \prod \nolimits _{i = 1}^n {{r_i}{!^{1/{r_i}}}.}$ A similar bound is then obtained for a second function, the $2$-permanent of a $3$-dimensional matrix, that is another analogue of the permanent of an ordinary ($2$-dimensional) matrix.References
- L. M. Brègman, Certain properties of nonnegative matrices and their permanents, Dokl. Akad. Nauk SSSR 211 (1973), 27–30 (Russian). MR 0327788 S. J. Dow and P. M. Gibson, Permanents of $d$-dimensional matrices (submitted for publication).
- Henryk Minc, Upper bounds for permanents of $(0,\,1)$-matrices, Bull. Amer. Math. Soc. 69 (1963), 789–791. MR 155843, DOI 10.1090/S0002-9904-1963-11031-9
- A. Schrijver, A short proof of Minc’s conjecture, J. Combinatorial Theory Ser. A 25 (1978), no. 1, 80–83. MR 491216, DOI 10.1016/0097-3165(78)90036-5
Additional Information
- © Copyright 1987 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 99 (1987), 29-34
- MSC: Primary 15A15; Secondary 05B20
- DOI: https://doi.org/10.1090/S0002-9939-1987-0866424-7
- MathSciNet review: 866424