Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



An upper bound for the permanent of a $ 3$-dimensional $ (0,1)$-matrix

Authors: Stephen J. Dow and Peter M. Gibson
Journal: Proc. Amer. Math. Soc. 99 (1987), 29-34
MSC: Primary 15A15; Secondary 05B20
MathSciNet review: 866424
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ A = ({a_{ijk}})$ be a $ 3$-dimensional matrix of order $ n$. The permanent of $ A$ is defined by

$\displaystyle \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 [Enhancements On Off] (What's this?)

  • [1] L. M. Brègman, Certain properties of nonnegative matrices and their permanents, Dokl. Akad. Nauk SSSR 211 (1973), 27-30; English transi., Soviet Math. Dokl. 14 (1973), 945-949. MR 0327788 (48:6130)
  • [2] S. J. Dow and P. M. Gibson, Permanents of $ d$-dimensional matrices (submitted for publication).
  • [3] H. Mine, Upper bounds for permanents of (0,1)-matrices, Bull. Amer. Math. Soc. 69 (1963), 789-791. MR 0155843 (27:5777)
  • [4] A. Schrijver, A short proof of Minc's conjecture, J. Combin. Theory Ser. A 25 (1978), 80-83. MR 0491216 (58:10481)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 15A15, 05B20

Retrieve articles in all journals with MSC: 15A15, 05B20

Additional Information

Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society