Kräuter conjecture on permanents is true (Q1633378): Difference between revisions

In this paper, the authors present their successful confirmation of a conjecture on permanents of \(\pm 1\)-matrices that had remained unresolved for almost 35 years. Let \(M_n(\pm 1)\) denote the set of all \(n\)-square \(\pm 1\)-matrices, and let \(D(n,r) \in M_n(\pm 1), \, 0 \leq r \leq n,\) be the matrix with \(r \; -1\)'s in its main diagonal and +1's elsewhere. \textit{Standard transformations} (ST) in \(M_n(\pm 1)\) are: (i) multiplications of rows or columns by \(-1\), (ii) permutations of rows or columns, and (iii) transposing matrices. \textit{E. T. H. Wang} [Israel J. Math. 18, 353--361 (1974; Zbl 0297.15007)] asked for a `decent' upper bound for \(|\mbox{per}(A)|\) for nonsingular matrices in \(M_n(\pm 1).\) Ten years later, it was shown by the reviewer and \textit{N. Seifter} [Lin. Multilin. Algebra 15, 207--223 (1984; Zbl 0548.15007)] that, for \(n \geq 6,\) this bound is given by \(\mbox{per}(D(n,n-1)).\) Further research by \textit{N. Seifter} [Israel J. Math. 48, 69--78 (1984; Zbl 0567.15004)] lead to the following conjecture on matrices of arbitrary rank posed by the reviewer [Ber. Math.-Stat. Sekt. Forschungszentrum Graz 249, 1--25 (1985; Zbl 0593.15010)]: let \(A \in M_n(\pm 1), \, n \geq 5, \, \mbox{rank}(A) = r+1, \, 0 \leq r \leq n-1.\) Then \(|\mbox{per}(A)| \leq \mbox{per}(D(n,r))\), and equality holds if and only if \(A\) can be converted to \(D(n,r)\) by ST. In this paper, the authors prove a slightly modified version of Kräuter's conjecture: the previous assertion holds even for \(n \geq 2\) with the exception of the matrix \(D(4,4)\) which is unique up to ST. The proof is an intricate case-by-case study including a number of unexpected and clever tools. Chapter 3 considers `small' matrices \(A \in M_n(\pm 1)\) for \(n \leq 4\) including the mentioned exceptional case for \(n = 4\). In Chapter 4, several preparatory recurrence relations for the matrices \(D(n,r)\) are derived. Chapter 5 deals with an alternative proof of the conjecture for nonsingular matrices \((n \geq 5)\) that contains essential ideas for what follows. Important ingredients are rank vectors and a partial order on the set of these vectors; they are thoroughly studied in Chapters 6 and 7. Finally, the preceding findings are used to give the (inductive) proof of the conjecture in the case of singular matrices, too.