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.
- scientific article; zbMATH DE number 3998017
- Upper bounds for permanents of (1,-1)-matrices
- Upper bounds for the permanents of (1,-1)-matrices
- Some properties of the permanent of (1, -1)-matrices
- scientific article; zbMATH DE number 3952967
- A lower bound for permanents of (0,1)-matrices
- On convertible (0,1) matrices
- An upper bound for the permanent of \((0,1)\)-matrices.
- Permanents -- a concise survey
- Permanents of matrices of signed ones
- An asymptotic solution of the multidimensional dimer problem
- An update on a few permanent conjectures
- An update on Minc's survey of open problems involving permanents
- Another Solution of an Old Problem of Polya
- Combinatorial matrix theory
- scientific article; zbMATH DE number 3998017 (Why is no real title available?)
- scientific article; zbMATH DE number 825098 (Why is no real title available?)
- Inequalities for the permanent function
- Inequalities: theory of majorization and its applications
- On permanents of (1,-1)-matrices
- On some questions concerning permanents of \((1,-1)\)-matrices
- Permanents
- Permanents of matrices of signed ones
- Positive diagonals of \(\pm 1\)-matrices
- Pólya's permanent problem
- Recent developments and open problems in the theory of permanents
- Some properties of the permanent of (1, -1)-matrices
- The complexity of computing the permanent
- Theory of permanents 1978–1981
- Theory of permanents 1982–1985
- Upper bounds for permanents of (1,-1)-matrices
- On the Kräuter-Seifter theorem on permanent divisibility
- On the permanent of a random symmetric matrix
- \( \pm 1\)-matrices with vanishing permanent
- On the Marcus-Wang conjecture
- Graph characterization of fully indecomposable nonconvertible (0, 1)-matrices with minimal number of ones
- Absence of linear permanent-determinant converters on skew-symmetric matrices
- Permanents of matrices of signed ones
- Upper bounds for the permanents of (1,-1)-matrices
- New inequalities for permanents and hafnians and some generalizations
- On the range of the permanent of ( 1)-matrices
- Values of the permanent function on (0, 1)- and (-1,0,1)-matrices
This page was built for publication: Kräuter conjecture on permanents is true
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633378)
