From: israel@math.ubc.ca (Robert Israel) Subject: Re: Extreme points of matrices Date: 1 Feb 2001 17:39:15 GMT Newsgroups: sci.math Summary: Extreme elements in convex set of symmetric doubly stochastic matrices In article <95b0pc$v64$1@nnrp1.deja.com>, wrote: >In article <955oq9$dq1$1@nnrp1.deja.com>, > danfux@my-deja.com wrote: >> The convex set of n by n doubly stochastic real matrices has the >> permutation matrices as the set of extreme points. >> What are the the extreme points in the convex set of n by n SYMMETRIC >> doubly stochastic real matrices ? >Conjecture: >R is an extreme symmetric doubly stochastic matrix if and only if it is >the symetric part of a permutation matrix. >That is: R = (P + P')/2 Sorry, no. If the order of any of the cycles in the permutation is even and greater than 2, R is not extreme. For example, in the case of a 4-cycle we have [ 0 1 0 0 ] [ 0 0 1 0 ] P = [ 0 0 0 1 ] [ 1 0 0 0 ] [ 0 1/2 0 1/2 ] [ 0 1 0 0 ] [ 0 0 0 1 ] [ 1/2 0 1/2 0 ] [ 1 0 0 0 ] [ 0 0 1 0 ] R = (P + P')/2 = [ 0 1/2 0 1/2 ] = 1/2 [ 0 0 0 1 ] + 1/2 [ 0 1 0 0 ] [ 1/2 0 1/2 0 ] [ 0 0 1 0 ] [ 1 0 0 0 ] For the (2n)-cycle permutation matrix P with P_{i,i+1 mod 2n} = 1 for 1 <= i <= 2n, R = (S+T)/2 where S_{i,i+1 mod 2n} = S_{i+1 mod 2n,i} = 1 when i is even and T_{i,i+1 mod 2n} = T_{i+1 mod 2n,i} = 1 when i is odd. The correct answer, equivalent to what I stated in a rather roundabout way in another posting, is that R is an extreme doubly stochastic matrix iff it is the symmetric part of a permutation matrix for a permutation whose disjoint-cycle representation consists only of transpositions and odd cycles. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: michael_berg@my-deja.com Subject: Re: Extreme points of matrices Date: Sun, 04 Feb 2001 13:06:00 GMT Newsgroups: sci.math Look at sequence A006847 in the encyclopedia of Sloan : http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.c gi?Anum=006847 The references are: M. Katz, On the extreme points of a certain convex polytope, J. Combin. Theory, 8 (1970), 417-423. R. P. Stanley, Differentiably finite power series, European J. Combin., 1 (1980), 175-188. R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.24(b). Michael In article <95c703$6kl$1@nntp.itservices.ubc.ca>, israel@math.ubc.ca (Robert Israel) wrote: [quote of previous article deleted --djr] Sent via Deja.com http://www.deja.com/