Results 1 to 3 of 3

Math Help - convex set and extreme point

  1. #1
    Junior Member
    Joined
    Feb 2006
    From
    Canada
    Posts
    45

    Exclamation convex set and extreme point

    An nxn matrix is called a permutation matrix if there is exactly one 1 in each row and column, and all other entries are 0.

    An nxn matrix A=(aij) is called doubly stochastic if aij>=0 for all 1<=i,j<=n, and the sum of the entries in any row or column is 1.

    Let C denote the set of all doubly stochastic nxn matrices.
    (a) SHow that C is convex.
    (b) Show that if P is an nxn permutation matrix, then P is an extreme point of the convex set C(the converse is also true).


    Can anyone help? I have spent like 4 hours on this question and am going crazy. Thanks very much guys.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by suedenation
    [COLOR=Navy]An nxn matrix is called a permutation matrix if there is exactly one 1 in each row and column, and all other entries are 0.

    An nxn matrix A=(aij) is called doubly stochastic if aij>=0 for all 1<=i,j<=n, and the sum of the entries in any row or column is 1.

    Let C denote the set of all doubly stochastic nxn matrices.
    (a) SHow that C is convex.
    A set C is convex if:

    <br />
\forall x,y \in C ,\ \mbox{and}\ \lambda \in [0,1], \lambda x+(1-\lambda)y \in C<br />

    Now if C is the space of all doubly stochastic matrices,
    x,y \in C and \lambda \in [0,1], then if:

    <br />
B=\lambda x+(1-\lambda)y<br />

    then B is doubly stochastic, since:

    <br />
\sum_i B_{i,j}=\lambda \sum_i x_{i,j}+(1-\lambda) \sum_i y_{i,j}=\lambda+(1-\lambda)=1<br />

    and:

    <br />
\sum_j B_{i,j}=\lambda \sum_j x_{i,j}+(1-\lambda) \sum_j y_{i,j}=\lambda+(1-\lambda)=1<br />

    Hence C is convex.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by suedenation
    An nxn matrix is called a permutation matrix if there is exactly one 1 in each row and column, and all other entries are 0.

    An nxn matrix A=(aij) is called doubly stochastic if aij>=0 for all 1<=i,j<=n, and the sum of the entries in any row or column is 1.

    Let C denote the set of all doubly stochastic nxn matrices.


    (b) Show that if P is an nxn permutation matrix, then P is an extreme point of the convex set C(the converse is also true).
    1. Clearly P is a doubly stochastic matrix.

    2. For x\in C to be an extreme point of the convex set C means that:

    \forall a,b \in C \ :\   x=\lambda a+(1-\lambda)b,\ \lambda \in [0,1]\ \Rightarrow (x=a) \vee (x=b)

    That is x does not lie strictly between two points in C.

    (this is one definition; yours may be different but it should be equivalent)

    From this you should be able to prove that P is an extreme point of C

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Advanced Geometry - Convex sets and Extreme points proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: December 2nd 2011, 05:14 AM
  2. unique value and extreme point question
    Posted in the Calculus Forum
    Replies: 12
    Last Post: September 3rd 2011, 11:36 AM
  3. Replies: 4
    Last Post: June 2nd 2010, 12:00 PM
  4. The union of two convex sets is not convex
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 30th 2010, 04:23 PM
  5. Proving that f^2 is convex if f is convex and f>=0
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 3rd 2009, 10:51 AM

Search Tags


/mathhelpforum @mathhelpforum