Multidimensional permanents of polystochastic matrices

Billy Child, Ian M. Wanless

Research output: Contribution to journalArticleResearchpeer-review

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

Original languageEnglish
Pages (from-to)89-102
Number of pages14
JournalLinear Algebra and Its Applications
Volume586
DOIs
Publication statusPublished - 1 Feb 2020

Keywords

  • Birkhoff polytope
  • Hypercube
  • Permanent
  • Polystochastic
  • Transversal

Cite this

@article{2b79696c091b42a782bb54e934f852af,
title = "Multidimensional permanents of polystochastic matrices",
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 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.",
keywords = "Birkhoff polytope, Hypercube, Permanent, Polystochastic, Transversal",
author = "Billy Child and Wanless, {Ian M.}",
year = "2020",
month = "2",
day = "1",
doi = "10.1016/j.laa.2019.10.008",
language = "English",
volume = "586",
pages = "89--102",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier",

}

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

In: Linear Algebra and Its Applications, Vol. 586, 01.02.2020, p. 89-102.

Research output: Contribution to journalArticleResearchpeer-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 -