## 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