Birkhoff-von Neumann Theorem for Multistochastic Tensors

Lu Bin Cui; Wen Li; Michael K. Ng

doi:10.1137/120896499

Birkhoff-von Neumann Theorem for Multistochastic Tensors

Lu Bin Cui^*
, Wen Li
, Michael K. Ng

^*Corresponding author for this work

Research output: Contribution to journal › Journal article › peer-review

29 Citations (Scopus)

128 Downloads (Pure)

Abstract

In this paper, we study the Birkhoff-von Neumann theorem for a class of multistochastic tensors. In particular, we give a necessary and sufficient condition such that a multistochastic tensor is a convex combination of finitely many permutation tensors. It is well-known that extreme points in the set of doubly stochastic matrices are just permutation matrices. However, we find that extreme points in the set of multistochastic tensors are not just permutation tensors. We provide the other types of tensors contained in the set of extreme points.

Original language	English
Pages (from-to)	956-973
Number of pages	18
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	35
Issue number	3
DOIs	https://doi.org/10.1137/120896499
Publication status	Published - 17 Jul 2014

User-Defined Keywords

Doubly stochastic matrices
Multistochastic tensors
Permanent
Permutation tensors

Access to Document

10.1137/120896499

Full TextFinal published version, 330 KB

Cite this

@article{d1249827c9ab4475960997782777cd10,

title = "Birkhoff-von Neumann Theorem for Multistochastic Tensors",

abstract = "In this paper, we study the Birkhoff-von Neumann theorem for a class of multistochastic tensors. In particular, we give a necessary and sufficient condition such that a multistochastic tensor is a convex combination of finitely many permutation tensors. It is well-known that extreme points in the set of doubly stochastic matrices are just permutation matrices. However, we find that extreme points in the set of multistochastic tensors are not just permutation tensors. We provide the other types of tensors contained in the set of extreme points.",

keywords = "Doubly stochastic matrices, Multistochastic tensors, Permanent, Permutation tensors",

author = "Cui, \{Lu Bin\} and Wen Li and Ng, \{Michael K.\}",

note = "Funding information: t School of Mathematical Sciences, South China Normal University, Guangzhou, China (hnzkc@ 163.com, [email protected]). The first author was supported by the Scientific Research Foundation of Graduate School of South China Normal University (2013kyjj010). The second author was supported by NSF of Guangdong province (520130100112530, 52012010009985), NNSF of China (0971075. ll2Tll44), Research Fund for the Doctoral Program of Higher Education of China (2010440711000ll), and Project of Department of Education of Guangdong Province (2013KJCX0053). t Centre for Mathematical Imaging and Vision, and Department of Mathematics, Hong Kong Baptist University, Hong Kong ([email protected]). This author was supported in part by RGC GRF grant 201812. Publisher copyright: {\textcopyright} 2014, Society for Industrial and Applied Mathematics",

year = "2014",

month = jul,

day = "17",

doi = "10.1137/120896499",

language = "English",

volume = "35",

pages = "956--973",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "3",

}

TY - JOUR

T1 - Birkhoff-von Neumann Theorem for Multistochastic Tensors

AU - Cui, Lu Bin

AU - Li, Wen

AU - Ng, Michael K.

N1 - Funding information: t School of Mathematical Sciences, South China Normal University, Guangzhou, China (hnzkc@ 163.com, [email protected]). The first author was supported by the Scientific Research Foundation of Graduate School of South China Normal University (2013kyjj010). The second author was supported by NSF of Guangdong province (520130100112530, 52012010009985), NNSF of China (0971075. ll2Tll44), Research Fund for the Doctoral Program of Higher Education of China (2010440711000ll), and Project of Department of Education of Guangdong Province (2013KJCX0053). t Centre for Mathematical Imaging and Vision, and Department of Mathematics, Hong Kong Baptist University, Hong Kong ([email protected]). This author was supported in part by RGC GRF grant 201812. Publisher copyright: © 2014, Society for Industrial and Applied Mathematics

PY - 2014/7/17

Y1 - 2014/7/17

N2 - In this paper, we study the Birkhoff-von Neumann theorem for a class of multistochastic tensors. In particular, we give a necessary and sufficient condition such that a multistochastic tensor is a convex combination of finitely many permutation tensors. It is well-known that extreme points in the set of doubly stochastic matrices are just permutation matrices. However, we find that extreme points in the set of multistochastic tensors are not just permutation tensors. We provide the other types of tensors contained in the set of extreme points.

AB - In this paper, we study the Birkhoff-von Neumann theorem for a class of multistochastic tensors. In particular, we give a necessary and sufficient condition such that a multistochastic tensor is a convex combination of finitely many permutation tensors. It is well-known that extreme points in the set of doubly stochastic matrices are just permutation matrices. However, we find that extreme points in the set of multistochastic tensors are not just permutation tensors. We provide the other types of tensors contained in the set of extreme points.

KW - Doubly stochastic matrices

KW - Multistochastic tensors

KW - Permanent

KW - Permutation tensors

UR - https://www.scopus.com/pages/publications/84907809419

U2 - 10.1137/120896499

DO - 10.1137/120896499

M3 - Journal article

AN - SCOPUS:84907809419

SN - 0895-4798

VL - 35

SP - 956

EP - 973

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 3

ER -

Birkhoff-von Neumann Theorem for Multistochastic Tensors

Abstract

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this