No label defined (Q4133650)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3557805
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3557805

      Statements

      0 references
      1976
      0 references
      [This article was published in the book announced in Zbl 0348.00004] Let \(R=(r_1,\dots,r_m)\) and \(S=(s_1,\dots,s_n)\) be non-negative vectors with \(\sum_{i=1}^mr_1=\sum_{j=1}^ns_j\) Then \(\mathcal U\) \((R,S)\) denotes the convex set of all \(m\times n\) non-negative matrices with row sum vector \(R\) and column sum vector \(S\). The extreme points of \(\mathcal U\) \((R,S)\) have been given a combinatorial classification and the results are summarized in this paper. Let \(\mathcal U\) \((\leq R,\leq S)\) denote the convex set of all \(m\times n\) non-negative matrices with row sum vector dominated (componentwise) by \(R\) and column sum vector dominated by \(S\). We give a combinatorial classification of the extreme points of \(\mathcal U\) \((\leq R,\leq S)\) and then show how the extreme points can be obtained from the extreme points of \(\mathcal U\) \((R,S)\). Application is given to the convex sets of doubly stochastic and doubly substochastic matrices. Now let \(\mathcal U\) \(( R)\) denote the convex set of all non-negative symmetric matrices with row sum vector \(R\), and let \(\mathcal U\) \((\leq R)\) denote the convex set of all non-negative symmetric matrices with row sum vector dominated by \(R\). We characterize combinatorially the extreme points of \(\mathcal U\) \((R)\) and of \(\mathcal U\) \((\leq R)\) and show how to obtain the extreme points of \(\mathcal U\) \((\leq R)\) from those of \(\mathcal U\) \((R)\). Application is then made to the convex sets of doubly stochastic symmetric and doubly substochastic symmetric matrices. We also characterize the zero-nonzero patterns (associated graphs) of matrices in \(\mathcal U\) \((R)\). A special case is a theorem giving necessary and sufficient conditions for the existence of a non-negative symmetric matrix prescribed row sum vector and main diagonal. The corresponding results for \(\mathcal U\) \((R,S)\) had previously been obtained by the author and are summarized in this paper. Jurkat and Ryser have obtained a formula for the minimum term rank of matrices in \(\mathcal U\) \((R,S)\) (the maximum cardinality of a matching in the associated bipartite graphs of matrices in \(\mathcal U\) \((R,S)\). Here we define the symmetric term rank of a symmetric matrix to be the maximum cardinality of a symmetric set of positive entries of \(A\) with no two positive entries in the same row or column. In terms of the associated graph of \(A\), the symmetric term rank equals the maximum number of nodes which meet a matching (pairwise node disjoint edges with loops allowed). We derive a formula for the minimum symmetric term rank of matrices in \(\mathcal U\) \((R)\). We also derive a formula for the minimum symmetric term rank of matrices in the convex set of non-negative symmetric matrices with row sum vector \(R\) and zero trace (hence in the associated graphs there are no loops).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references