On extreme infinite doubly stochastic matrices

Extremal problems in graph theory (05C35) Stochastic matrices (15B51) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Review text

Let \(\bar r=(r_ 1\), \(r_ 2\),...) and \(\bar s=(s_ 1\), \(s_ 2\),...) be given sequences of nonnegative real numbers. Matrices \(P=(p_{ij})\) with all \(p_{ij}\geq 0\), \(\sum^{\infty}_{k=1}p_{ik}\leq r_ i\) and \(\sum^{\infty}_{k=1}p_{kj}\leq s_ j\) are said to be doubly substochastic matrices with respect to \((\bar r,\bar s)\). The set of such matrices is denoted by \(D(\leq \bar r,\leq \bar s)\). If \(\sum^{\infty}_{i=1}r_ i=\sum^{\infty}_{j=1}s_ j\leq \infty\) and if all \(\sum^{\infty}_{k=1}p_{ik}=r_ i\) and \(\sum^{\infty}_{k=1}p_{kj}=s_ j\) these matrices are said to be doubly stochastic with respect to \((\bar r,\bar s)\). The set of such matrices is denotes by \(D(\bar r,\bar s)\). The sets \(D(\leq \bar r,\leq \bar s)\) and \(D(\bar r,\bar s)\) are each convex. It is shown that if \(\sum^{\infty}_{i=1}r_ i=\sum^{\infty}_{j=1}s_ j<\infty\), then \(P\in D(\bar r,\bar s)\) is extreme if and only if the connected components of the graph of P are trees. The extreme points of \(D(\bar r,\bar s)\) are precisely the exposed points in \(D(\bar r,\bar s)\). A matrix \(P\in D(\leq \bar r,\leq \bar s)\) is extreme if and only if the connected components of the graph of P are extreme trees. Some results are given concerning the dimension of \(D(\leq \bar r,\leq \bar s)\) when each of the sequences \(\bar r\) and \(\bar s\) is finite.

Recommendations

Cited in

(31)

This page was built for publication: On extreme infinite doubly stochastic matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579366)