### Abstract

A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least n^{n3/2(1/2−o(1))} 1-permutation matrices and contains a polytope of dimension at least cn^{3/2} for fixed c,d and even n→∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.

Original language | English |
---|---|

Pages (from-to) | 89-102 |

Number of pages | 14 |

Journal | Linear Algebra and Its Applications |

Volume | 586 |

DOIs | |

Publication status | Published - 1 Feb 2020 |

### Keywords

- Birkhoff polytope
- Hypercube
- Permanent
- Polystochastic
- Transversal

### Cite this

}

*Linear Algebra and Its Applications*, vol. 586, pp. 89-102. https://doi.org/10.1016/j.laa.2019.10.008

**Multidimensional permanents of polystochastic matrices.** / Child, Billy; Wanless, Ian M.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - Multidimensional permanents of polystochastic matrices

AU - Child, Billy

AU - Wanless, Ian M.

PY - 2020/2/1

Y1 - 2020/2/1

N2 - A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least nn3/2(1/2−o(1)) 1-permutation matrices and contains a polytope of dimension at least cn3/2 for fixed c,d and even n→∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.

AB - A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least nn3/2(1/2−o(1)) 1-permutation matrices and contains a polytope of dimension at least cn3/2 for fixed c,d and even n→∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.

KW - Birkhoff polytope

KW - Hypercube

KW - Permanent

KW - Polystochastic

KW - Transversal

UR - http://www.scopus.com/inward/record.url?scp=85073672990&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2019.10.008

DO - 10.1016/j.laa.2019.10.008

M3 - Article

AN - SCOPUS:85073672990

VL - 586

SP - 89

EP - 102

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -