Volume 23, No 4, 2016, P. 35-101

UDC 519.1
A. A. Taranenko
Permanents of multidimensional matrices: properties and applications

Abstract:
The permanent of a multidimensional matrix is the sum of the products of entries over all diagonals. In this survey, we consider the basic properties of the multidimensional permanent, sufficient conditions for its positivity, available upper bounds, and the specifics of the permanents of polystochastic matrices. We prove that the number of various combinatorial objects can be expressed via multidimensional permanents. Special attention is paid to the number of 1-factors of uniform hypergraphs and the number of transversals in Latin hypercubes.
Tabl. 1, bibliogr. 63.

Keywords: permanent, multidimensional matrix, stochastic matrix, polystochastic matrix, transversal in a Latin hypercube, 1-factor of a uniform hypergraph.

DOI: 10.17377/daio.2016.23.517

Anna A. Taranenko ¹
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: taattg@mail.ru

Received 13 November 2015

References

[1] S. V. Avgustinovich, Multidimensional permanents in enumeration problems, Diskretn. Anal. Issled. Oper., 15, No. 5, 3–5, 2008. Translated in J. Appl. Ind. Math., 4, No. 1, 19–20, 2010.

[2] L. M. Bregman, Some properties of nonnegative matrices and their permanents, Dokl. Akad. Nauk SSSR, 211, No. 1, 27–30, 1973. Translated in Sov. Math., Dokl., 14, No. 1, 945–949, 1973.

[3] G. P. Egorychev, Proof of the van der Waerden conjecture for permanents, Sib. Mat. Zh., 22, No. 6, 65–71, 1981. Translated in Sib. Math. J., 22, No. 6, 854–859, 1981.

[4] H. Minc, Permanents, Addison-Wesley, Reading, MA, USA, 1978 (Encycl. Math. Its Appl., Vol. 6). Translated under the title Permanenty, Mir, Moscow, 1982.

[5] The On-Line Encyclopedia of Integer Sequences. Available at http://oeis.org. Accessed Apr. 25, 2016.

[6] N. P. Sokolov, Prostranstvennye matritsy i ikh prilozheniya (Space Matrices and Their Applications), Fizmatlit, Moscow, 1960.

[7] N. P. Sokolov, Vvedenie v teoriyu mnogomernykh matrits (Introduction to the Theory of Multidimensional Matrices), Naukova Dumka, Kiev, 1972.

[8] D. I. Falikman, Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix, Mat. Zametki, 29, No. 6, 931–938, 1981. Translated in Math. Notes Acad. Sci. USSR, 29, No. 6, 475–479, 1981.

[9] R. Aharoni, A. Georgakopoulos, and P. Sprüssel, Perfect matchings in $r$-partite $r$-graphs, Eur. J. Comb., 30, 39–42, 2009.

[10] N. Alon and S. Friedland, The maximum number of perfect matchings in graphs with a given degree sequence, Electron. J. Comb., 15, No. N13, 1–2, 2008.

[11] L. Balasubramanian, On transversals in Latin squares, Linear Algebra Appl., 131, 125–129, 1990.

[12] R. B. Bapat, A stronger form of the Egorychev–Falikman theorem on permanents, Linear Algebra Appl., 63, 95–100, 1984.

[13] Zs. Baranyai, On the factorization of the complete uniform hypergraph, in A. Hajnal, T. Rado, V. T. Sós, eds., Infinite and Finite Sets, Vol. 1, pp. 91–108, North-Holland, Amsterdam, 1975 (Colloq. Math. Soc. J. Bolyai, Vol. 10).

[14] A. Barvinok and A. Samorodnitsky, Computing the partition function for perfect matchings in a hypergraph, Comb. Probab. Comput., 20, No. 6, 815–835, 2011.

[15] R. A. Brualdi and J. Csima, Extremal plane stochastic matrices of dimension three, Linear Algebra Appl., 11, 105–133, 1975.

[16] A.-L. Cauchy, Mèmoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment, J. Éc. Polytech., 10, No. 17, 29–112, 1815 [French].

[17] A. Cayley, On the theory of determinants, Trans. Camb. Philos. Soc., 8, 75–88, 1849.

[18] G.-S. Cheon and I. M. Wanless, An update on Minc’ survey of open problems involving permanents, Linear Algebra Appl., 403, 314–342, 2005.

[19] D. Cifuentes and P. A. Parrilo, An efficient tree decomposition method for permanents and mixed discriminants, Linear Algebra Appl., 493, 45–81, 2016.

[20] J. Csima, Multidimensional stochastic matrices and patterns, J. Algebra, 14, 194–202, 1970.

[21] J. Cutler and A. J. Radcliffe, An entropy proof of the Kahn–Lovàsz theorem, Electron. J. Comb., 18, No. 1, P10, 1–9, 2011.

[22] D. E. Daykin and R. Häggkvist, Degrees giving independent edges in a hypergraph, Bull. Aust. Math. Soc., 23, No. 1, 103–109, 1981.

[23] D. Donovan, K. Johnson, and I. M. Wanless, Permanents and determinants of Latin squares, J. Comb. Des., 24, No. 3, 132–148, 2016.

[24] S. J. Dow and P. M. Gibson, An upper bound for the permanent of a 3-dimensional (0,1)-matrix, Proc. Amer. Math. Soc., 99, No. 1, 29–34, 1987.

[25] S. J. Dow and P. M. Gibson, Permanents of $d$-dimensional matrices, Linear Algebra Appl., 90, 133–145, 1987.

[26] S. Eberhard, F. Manners, and R. Mrazovic, Additive triples of bijections, or the toroidal semiqueens problem, 2016 (Cornell Univ. Libr. e-Print Archive, arXiv:1510.05987).

[27] P. M. Gibson, Combinatorial matrix functions and 1-factors of graphs, SIAM J. Appl. Math., 19, 330–333, 1970.

[28] R. Glebov and Z. Luria, On the maximum number of Latin transversals, J. Comb. Theory, Ser. A, 141, 136–146, 2016.

[29] L. Gurvits, Van der Waerden/Schrijver–Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all, Electron. J. Comb., 15, No. R66, 1–26, 2008.

[30] B. Gyires, Elementary proof for van der Waerden’s conjecture and related theorems, Comput. Math. Appl., 31, No. 10, 7–21, 1996.

[31] B. Gyires, Contribution to van der Waerden’s conjecture, Comput. Math. Appl., 42, No. 10–11, 1431–1437, 2001.

[32] S. Hell, On the number of Birch partitions, Discrete Comput. Geom., 40, 586–594, 2008.

[33] S. Hell, On the number of colored Birch and Tverberg partitions, Electron. J. Comb., 21, No. 3, P3.23, 2014.

[34] W. B. Jurkat and H. J. Ryser, Extremal configurations and decomposition theorems, J. Algebra., 8, 194–222, 1968.

[35] D. S. Krotov and V. N. Potapov, $n$-Ary quasigroups of order 4, SIAM J. Discrete Math., 23, No. 2, 561–570, 2009.

[36] D. Kühn and D. Osthus, Embedding large subgraphs into dense graphs, in Surveys in Combinatorics 2009, pp. 137–167, Cambridge Univ. Press, New York, 2009 (Lond. Math. Soc. Lect. Note Ser., Vol. 365).

[37] M. Laurent and A. Schriver, On Leonid Gurvits’s proof for permanents, Amer. Math. Mon., 117, 903–911, 2010.

[38] N. Linial and Z. Luria, An upper bound on the number of Steiner triple systems, Random Struct. Algorithms, 34, No. 4, 399–406, 2013.

[39] N. Linial and Z. Luria, An upper bound on the number of high-dimensional permutations, Combinatorica, 34, No. 4, 471–486, 2014.

[40] N. Linial and Z. Luria, On the vertices of the $d$-dimensional Birkhoff polytope, Discrete Comput. Geom., 51, 161–170, 2014.

[41] A. Lo and K. Markström, Perfect matchings in 3-partite 3-uniform hypergraphs, J. Comb. Theory, Ser. A, 127, 22–57, 2014.

[42] M. Marcus and H. Minc, On a conjecture of B. L. van der Waerden, Proc. Camb. Philos. Soc., 63, 305–309, 1967.

[43] M. Marcus and M. Newman, On the minimum of the permanent of a doubly stochastic matrix, Duke Math. J., 26, 61–72, 1959.

[44] B. D. McKay, J. C. McLeod, and I. M. Wanless, The number of transversals in a Latin square, Des. Codes Cryptogr., 40, 269–284, 2006.

[45] B. D. McKay and I. M. Wanless, A census of small Latin hypercubes, SIAM J. Discrete Math., 22, 719–736, 2008.

[46] H. Minc, Upper bound for permanents of (0,1)-matrices, Bull. Amer. Math. Soc., 69, 789–791, 1963.

[47] T. Muir, A Treatise on the Theory of Determinants, Macmillan Co., London, 1933.

[48] O. Pikhurko, Perfect matchings and $K^{3}_{4}$-tilings in hypergraphs of large codegree, Graphs Comb., 24, No. 4, 391–404, 2008.

[49] V. N. Potapov, On the multidimensional permanent and $q$-ary designs, Sib. Elektron. Mat. Izv., 11, 451–456, 2014.

[50] J. Radhakrishnan, An entropy proof of Bregman’s theorem, J. Comb. Theory, Ser. A, 77, No. 1, 161–164, 1997.

[51] V. Rödl, A. Rucinski, and E. Szemerèdi, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Comb. Theory, Ser. A, 116, No. 3, 613–636, 2009.

[52] H. J. Ryser, Neuere Probleme der Kombinatorik, in Vorträge über Kombinatorik, Oberwolfach, Germany, July 24–29, 1967, pp. 69–91, Math. Forschungsinst. Oberwolfach, Oberwolfach, 1967 [German].

[53] A. Schrijver, A short proof of Minc’s conjecture, J. Comb. Theory, Ser. A, 25, No. 1, 80–83, 1978.

[54] A. Schrijver, Counting 1-factors in regular bipartite graphs, J. Comb. Theory, Ser. B, 72, No. 1, 122–135, 1998.

[55] G. W. Soules, Permanental bounds for nonnegative matrices via decomposition, Linear Algebra Appl., 394, 73–89, 2005.

[56] Z.-W. Sun An additive theorem and restricted sumsets, Math. Res. Lett., 15, No. 6, 1263–1276, 2008.

[57] A. A. Taranenko, Upper bounds on the permanent of multidimensional (0,1)-matrices, Sib. Elektron. Mat. Izv., 11, 958–965, 2014.

[58] A. A. Taranenko, Multidimensional permanents and an upper bound on the number of transversals in Latin squares, J. Comb. Des., 23, 305–320, 2015.

[59] A. A. Taranenko, Upper bounds on the numbers of 1-factors and 1-factorizations of hypergraphs, 2015 (Cornell Univ. Libr. e-Print Archive, arXiv:1503.08270).

[60] M. C. Tichy, Sampling of partially distinguishable bosons and the relation to the multidimensional permanent, Phys. Rev. A, 91, No. 2, 022316, 1–13, 2015.

[61] I. Vardi, Computational Recreations in Mathematics, Addison-Wesley, Redwood City, 1991.

[62] I. M. Wanless, Transversals in Latin squares: A survey, in Surveys in Combinatorics 2011, pp. 403–437, Cambridge Univ. Press, New York, 2011 (Lon. Math. Soc. Lect. Note Ser., Vol. 392).

[63] I. M. Wanless and B. S. Webb, The existence of Latin squares without orthogonal mates, Des. Codes Cryptogr., 40, 131–135, 2006.