Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs (Q1816947): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:35, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs |
scientific article |
Statements
Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs (English)
0 references
12 November 1997
0 references
This paper studies the problem of describing the convex hull \(\Omega_n^0\) of all nonidentity permutation matrices of order \(n\) by a system of linear inequalities. Such a description was first given by \textit{A. B. Cruse} [Linear Algebra Appl. 26, 45-57 (1979; Zbl 0412.15015)]. While this description involves infinitely many inequalities, it does provide an efficiently testable criterion for membership in \(\Omega_n^0\): a doubly stochastic matrix \(W\) is in \(\Omega_n^0\) if and only if \(\min\{\sum_{i,j}W_{i,j}X_{i,j}:X\in P_n\}\geq 1\), where \(P_n\) is a polytope defined by a system of inequalities of size polynomial in \(n\). The authors use this to provide an alternative criterion for membership in \(\Omega_n^0\) in terms of dicycle covers as follows. A dicycle cover in a digraph is an assignment of nonnegative values to arcs such that the sum of values on each dicycle it at least \(1\). They show that a doubly stochastic matrix \(W\) is in \(\Omega_n^0\) if and only if the minimum weight of a dicycle cover in the weighted digraph naturally associated with \(W\) is at least \(1\). Using this criterion, they show that the complete description of \(\Omega_n^0\) for \(n\leq 6\) by transitive tournament inequalities due to \textit{R. A. Brualdi} and \textit{G.-S. Hwang} [Linear Algebra Appl. 172, 151-168 (1992; Zbl 0755.15011)], is valid if and only if \(n\leq 6\). They also show that weighted Eulerian digraphs on \(n\leq 6\) vertices always have an integral minimum weight dicycle cover, and prove a min-max relation for such graphs.
0 references
doubly stochastic matrix
0 references
dicycle cover
0 references
Eulerian digraph
0 references
system of linear inequalities
0 references