×

\( \pm 1\)-matrices with vanishing permanent. (English. Russian original) Zbl 1468.15006

J. Math. Sci., New York 249, No. 2, 271-280 (2020); translation from Zap. Nauchn. Semin. POMI 482, 244-258 (2019).
Let \(\Omega_n\) denote the set of \(n\times n\) matrices in which every entry is \(-1\) or \(+1\). It is known that \(\Omega_n\) contains a matrix on which the permanent vanishes if and only if \(n+1\) is not a power of \(2\) (for a proof, see [I. M. Wanless, Linear Multilinear Algebra 53, No. 6, 427–433 (2005; Zbl 1085.15006)]). This paper is concerned with classifying matrices in \(\Omega_n\) that have zero permanent. Two matrices in \(\Omega_n\) are equivalent if one can be transformed into the other by negating rows and columns, permuting the rows and columns and/or transposing. Equivalent matrices have the same permanent, up to sign. In the present paper, the author gives some simple necessary conditions for a matrix to have zero permanent. These are then used in a case analysis to find 3 matrices in \(\Omega_4\) and 11 matrices in \(\Omega_5\), such that any \((\pm1)\)-matrix with vanishing permanent must be equivalent to one of the given matrices. It would have been nice to see an argument that no pair of the given matrices are equivalent.

MSC:

15A15 Determinants, permanents, traces, other special matrix functions
15A21 Canonical forms, reductions, classification

Citations:

Zbl 1085.15006
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bapat, RB, Recent developments and open problems in the theory of permanents, Math. Student, 76, 1-4, 55-69 (2007) · Zbl 1175.15007
[2] Brualdi, RA; Ryser, HJ, Combinatorial Matrix Theory (1991), Press: Cambridge Univ, Press · Zbl 0746.05002
[3] Brualdi, RA; Shader, BL, Matrices of Sign-Solvable Linear Systems (1995), Press: Cambridge Univ, Press · Zbl 0833.15002
[4] M. V. Budrevich and A. E. Guterman, “Kräuter conjecture on permanents is true,” J. Comb. Theory, Ser. A, 162, 306-343 (2019). · Zbl 1443.15005
[5] Budrevich, MV; Guterman, AE; Taranin, KA, On the divisibility of permanents for (±1)-matrices, Zap. Nauchn. Semin. POMI, 439, 26-37 (2015)
[6] Budrevich, MV; Guterman, AE; Taranin, KA, On the Kr¨auter-Seifter theorem on permanent divisibility, Zap. Nauchn. Semin. POMI, 463, 25-35 (2017)
[7] Cheon, G-S; Wanless, IM, An update on Minc’s survey of open problems involving permanents, Linear Algebra Appl., 403, 314-342 (2005) · Zbl 1078.15005 · doi:10.1016/j.laa.2005.02.030
[8] Guterman, AE; Taranin, KA, On the values of the permanent of (0, 1)-matrices, Linear Algebra Appl., 552, 256-276 (2018) · Zbl 1391.15019 · doi:10.1016/j.laa.2018.04.026
[9] Kiem, Y-H; Kye, S-H; Na, J., Product vectors in the ranges of multi-partite states with positive partial transposes and permanents of matrices, Commun. Math. Phys., 338, 2, 621-639 (2015) · Zbl 1316.81012 · doi:10.1007/s00220-015-2385-x
[10] Korshunov, AD, On the number of (−1, 1)-matrices of order n with a fixed permanent, Diskretn. Anal. Issled. Oper., 3, 1, 23-42 (1996) · Zbl 0980.15500
[11] A. R. Kräuter, “Recent results on permanents of (1,−1)-matrices,” Ber. Math.-Statist. Sekt. Forschungsgesellschaft Joanneum Graz, 249, 1-25 (1985). · Zbl 0593.15010
[12] A. R. Kräuter and N. Seifter, “On some questions concerning permanents of (1,−1)-matrices,” Isr. J. Math., 45, No. 1, 53-62 (1983). · Zbl 0517.15009
[13] McCuaig, W., P´olya’s permanent problem, Electron. J. Combin., 11, R79 (2004) · Zbl 1062.05066 · doi:10.37236/1832
[14] Minc, H., Permanents (1984), Press: Cambridge Univ, Press
[15] Simion, R.; Schmidt, FW, On (+1,−1)-matrices with vanishing permanent, Discrete Math., 46, 107-108 (1983) · Zbl 0512.15008 · doi:10.1016/0012-365X(83)90279-0
[16] Valiant, LG, The complexity of computing the permanent, Theor. Comput. Sci., 8, 189-201 (1979) · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6
[17] Wang, ETH, On permanents of (1,−1)-matrices, Isr. J. Math., 18, 353-361 (1974) · Zbl 0297.15007 · doi:10.1007/BF02760844
[18] I. M. Wanless, “Permanents of matrices of signed ones,” Linear Multilinear Algebra, 53, No. 6, 427-433 (2005). · Zbl 1085.15006
[19] T.-C.Wei and S. Severini, “Matrix permanent and quantum entanglement of permutation invariant states,” J. Math. Phys., 51, No. 9 (2010). · Zbl 1309.81039
[20] Zhang, F., An update on a few permanent conjectures, Spec. Matrices, 4, 305-316 (2016) · Zbl 1346.15009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.