Permanents of multidimensional matrices: properties and applications

A. A. Taranenko

Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 4, pp. 35-101.

Résumé

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.

Détail

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

Bibliographie

[1] S. V. Avgustinovich, “Multidimensional permanents in enumeration problems”, J. Appl. Ind. Math., 4:1 (2010), 19–20 | DOI | MR | Zbl

[2] L. M. Bregman, “Some properties of nonnegative matrices and their permanents”, Sov. Math., Dokl., 14:1 (1973), 945–949 | MR | Zbl

[3] G. P. Egorychev, “Proof of the van der Waerden conjecture for permanents”, Sib. Math. J., 22:6 (1981), 854–859 | DOI | MR | Zbl

[4] H. Minc, Permanents, Encycl. Math. Its Appl., 6, Addison-Wesley, Reading, MA, USA, 1978 | MR | MR | Zbl

[5] Onlain-entsiklopediya tselochislennykh posledovatelnostei, , Apr. 25, 2016 https://oeis.org

[6] N. P. Sokolov, Space Matrices and Their Applications, Fizmatlit, Moscow, 1960 | MR

[7] N. P. Sokolov, Introduction to the Theory of Multidimensional Matrices, Naukova Dumka, Kiev, 1972 | MR

[8] D. I. Falikman, “Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix”, Math. Notes Acad. Sci. USSR, 29:6 (1981), 475–479 | DOI | MR | Zbl

[9] Aharoni R., Georgakopoulos A., Sprüssel P., “Perfect matchings in $r$-partite $r$-graphs”, Eur. J. Comb., 30 (2009), 39–42 | DOI | MR | Zbl

[10] Alon N., Friedland S., “The maximum number of perfect matchings in graphs with a given degree sequence”, Electron. J. Comb., 15 (2008), Research Paper N13, 2 pp. | MR | Zbl

[11] Balasubramanian L., “On transversals in Latin squares”, Linear Algebra Appl., 131 (1990), 125–129 | DOI | MR | Zbl

[12] Bapat R. B., “A stronger form of the Egorychev–Falikman theorem on permanents”, Linear Algebra Appl., 63 (1984), 95–100 | DOI | MR | Zbl

[13] Baranyai Zs., “On the factorization of the complete uniform hypergraph”, Infinite and Finite Sets, v. 1, Colloq. Math. Soc. J. Bolyai, 10, eds. Hajnal A., Rado T., Sós V. T., North-Holland, Amsterdam, 1973, 91–108 | MR

[14] Barvinok A., Samorodnitsky A., “Computing the partition function for perfect matchings in a hypergraph”, Comb. Probab. Comput., 20:6 (2011), 815–835 | DOI | MR | Zbl

[15] Brualdi R. A., Csima J., “Extremal plane stochastic matrices of dimension three”, Linear Algebra Appl., 11 (1975), 105–133 | DOI | MR | Zbl

[16] Cauchy A.-L., “Mèmoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions operées entre les variables qu'elles renferment”, J. Éc. Polytech. Math., 10:17 (1815), 29–112

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

[18] Cheon G.-S., Wanless I. M., “An update on Minc's survey of open problems involving permanents”, Linear Algebra Appl., 403 (2005), 314–342 | DOI | MR | Zbl

[19] Cifuentes D., Parrilo P. A., “An efficient tree decomposition method for permanents and mixed discriminants”, Linear Algebra Appl., 493 (2016), 45–81 | DOI | MR | Zbl

[20] Csima J., “Multidimensional stochastic matrices and patterns”, J. Algebra, 14 (1970), 194–202 | DOI | MR | Zbl

[21] Cutler J., Radcliffe A. J., “An entropy proof of the Kahn–Lovàsz theorem”, Electron. J. Comb., 18:1 (2011), Research Paper P10, 9 pp. | MR

[22] Daykin D. E., Häggkvist R., “Degrees giving independent edges in a hypergraph”, Bull. Aust. Math. Soc., 23:1 (1981), 103–109 | DOI | MR | Zbl

[23] Donovan D., Johnson K., Wanless I. M., “Permanents and determinants of Latin squares”, J. Comb. Des., 24:3 (2016), 132–148 | DOI | MR | Zbl

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

[25] Dow S. J., Gibson P. M., “Permanents of $d$-dimensional matrices”, Linear Algebra Appl., 90 (1987), 133–145 | DOI | MR | Zbl

[26] Eberhard S., Manners F., Mrazović R., Additive triples of bijections, or the toroidal semiqueens problem, arXiv: 1510.05987

[27] Gibson P. M., “Combinatorial matrix functions and 1-factors of graphs”, SIAM J. Appl. Math., 19 (1970), 330–333 | DOI | MR | Zbl

[28] Glebov R., Luria Z., “On the maximum number of Latin transversals”, J. Comb. Theory Ser. A, 141 (2016), 136–146 | DOI | MR | Zbl

[29] Gurvits L., “Van der Waerden/Schrijver–Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all”, Electron. J. Comb., 15 (2008), Research Paper R66, 26 pp. | MR | Zbl

[30] Gyires B., “Elementary proof for a Van der Waerden's conjecture and related theorems”, Comput. Math. Appl., 31:10 (1996), 7–21 | DOI | MR | Zbl

[31] Gyires B., “Contribution to van der Waerden's conjecture”, Comput. Math. Appl., 42 (2001), 1431–1437 | DOI | MR | Zbl

[32] Hell S., “On the number of Birch partitions”, Discrete Comput. Geom., 40 (2008), 586–594 | DOI | MR | Zbl

[33] Hell S., “On the number of colored Birch and Tverberg partitions”, Electron. J. Comb., 21:3 (2014), Research Paper P3.23, 12 pp. | MR | Zbl

[34] Jurkat W. B., Ryser H. J., “Extremal configurations and decomposition theorems”, J. Algebra, 8 (1968), 194–222 | DOI | MR | Zbl

[35] Krotov D. S., Potapov V. N., “$n$-Ary quasigroups of order 4”, SIAM J. Discrete Math., 23:2 (2009), 561–570 | DOI | MR | Zbl

[36] Kühn D., Osthus D., “Embedding large subgraphs into dense graphs”, Surveys in Combinatorics 2009, London Math. Soc. Lect. Note Ser., 365, Cambridge Univ. Press, New York, 2009, 137–167 | MR | Zbl

[37] Laurent M., Schriver A., “On Leonid Gurvits's proof for permanents”, Amer. Math. Mon., 117 (2010), 903–911 | DOI | MR | Zbl

[38] Linial N., Luria Z., “An upper bound on the number of Steiner triple systems”, Random Struct. Algorithms, 34:4 (2013), 399–406 | DOI | MR

[39] Linial N., Luria Z., “An upper bound on the number of high-dimensional permutations”, Combinatorica, 34:4 (2014), 471–486 | DOI | MR | Zbl

[40] Linial N., Luria Z., “On the vertices of the $d$-dimensional Birkhoff polytope”, Discrete Comput. Geom., 51 (2014), 161–170 | DOI | MR | Zbl

[41] Lo A., Markström K., “Perfect matchings in 3-partite 3-uniform hypergraphs”, J. Comb. Theory Ser. A, 127 (2014), 22–57 | DOI | MR | Zbl

[42] Marcus M., Minc H., “On a conjecture of B. L. van der Waerden”, Proc. Camb. Philos. Soc., 63 (1967), 305–309 | DOI | MR | Zbl

[43] Marcus M., Newman M., “On the minimum of the permanent of a doubly stochastic matrix”, Duke Math. J., 26 (1959), 61–72 | DOI | MR | Zbl

[44] McKay B. D., McLeod J. C., Wanless I. M., “The number of transversals in a Latin square”, Des. Codes Cryptogr., 40 (2006), 269–284 | DOI | MR | Zbl

[45] McKay B. D., Wanless I. M., “A census of small Latin hypercubes”, SIAM J. Discrete Math., 22 (2008), 719–736 | DOI | MR | Zbl

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

[47] Muir T., A treatise on the theory of determinants, Macmillan and Co., London, 1882, 774 pp.

[48] Pikhurko O., “Perfect matchings and $K^3_4$-tilings in hypergraphs of large codegree”, Graphs Comb., 24:4 (2008), 391–404 | DOI | MR | Zbl

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

[50] Radhakrishnan J., “An entropy proof of Bregman's theorem”, J. Comb. Theory Ser. A, 77:1 (1997), 161–164 | DOI | MR | Zbl

[51] Rödl V., Ruciǹski A., Szemerèdi E., “Perfect matchings in large uniform hypergraphs with large minimum collective degree”, J. Comb. Theory Ser. A, 116:3 (2009), 613–636 | DOI | MR | Zbl

[52] Ryser H. J., “Neuere Probleme der Kombinatorik”, Vortrage über Kombinatorik (Germany, Oberwolfach, July 24–29, 1967), Math. Forschungsinst. Oberwolfach, Oberwolfach, 1967, 69–91 (German)

[53] Schrijver A., “A short proof of Minc's conjecture”, J. Comb. Theory Ser. A, 25:1 (1978), 80–83 | DOI | MR | Zbl

[54] Schrijver A., “Counting 1-factors in regular bipartite graphs”, J. Comb. Theory Ser. B, 72:1 (1998), 122–135 | DOI | MR | Zbl

[55] Soules G. W., “Permanental bounds for nonnegative matrices via decomposition”, Linear Algebra Appl., 394 (2005), 73–89 | DOI | MR | Zbl

[56] Sun Z.-W., “An additive theorem and restricted sumsets”, Math. Res. Lett., 15:6 (2008), 1263–1276 | DOI | MR | Zbl

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

[58] Taranenko A. A., “Multidimensional permanents and an upper bound on the number of transversals in Latin squares”, J. Comb. Des., 23 (2015), 305–320 | DOI | MR | Zbl

[59] Taranenko A. A., Upper bounds on the numbers of 1-factors and 1-factorizations of hypergraphs, arXiv: 1503.08270

[60] Tichy M. C., “Sampling of partially distinguishable bosons and the relation to the multidimensional permanent”, Phys. Rev. A, 91:2 (2015), 022316, 13 pp. | DOI

[61] Vardi I., Computational recreations in mathematics, Addison-Wesley, Redwood City, CA, 1991

[62] Wanless I. M., “Transversals in Latin squares: a survey”, Surveys in Combinatorics 2011, Lon. Math. Soc. Lect. Note Ser., 392, Cambridge Univ. Press, New York, 2011, 403–437 | MR | Zbl

[63] Wanless I. M., Webb B. S., “The existence of Latin squares without orthogonal mates”, Des. Codes Cryptogr., 40 (2006), 131–135 | DOI | MR | Zbl