Birkhoff-von Neumann theorem and decomposition for doubly stochastic tensors

Haibin Chen, Liqun Qi, Louis Caccetta, Guanglu Zhou

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

The well-known Birkhoff-von Neumann theorem states that a doubly stochastic matrix is a convex combination of permutation matrices. In this paper, we present a new concept for doubly stochastic tensors and study a generalization of this theorem for doubly stochastic tensors. Particularly, we prove that each permutation tensor is an extreme point of the set of doubly stochastic tensors, and the Birkhoff-von Neumann theorem holds for doubly stochastic tensors. Furthermore, an algorithm is proposed to find a convex combination of permutation tensors for any doubly stochastic tensor.

Original languageEnglish
Pages (from-to)119-133
Number of pages15
JournalLinear Algebra and Its Applications
Volume583
DOIs
Publication statusPublished - 15 Dec 2019

Keywords

  • Birkhoff-von Neumann theorem
  • Doubly stochastic tensor
  • Extreme point
  • Nonnegative tensor

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Cite this