Results 1 to 3 of 3

Thread: 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
    5
    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 $\displaystyle C$ is convex if:

    $\displaystyle
    \forall x,y \in C ,\ \mbox{and}\ \lambda \in [0,1], \lambda x+(1-\lambda)y \in C
    $

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

    $\displaystyle
    B=\lambda x+(1-\lambda)y
    $

    then $\displaystyle B$ is doubly stochastic, since:

    $\displaystyle
    \sum_i B_{i,j}=\lambda \sum_i x_{i,j}+(1-\lambda) \sum_i y_{i,j}=\lambda+(1-\lambda)=1
    $

    and:

    $\displaystyle
    \sum_j B_{i,j}=\lambda \sum_j x_{i,j}+(1-\lambda) \sum_j y_{i,j}=\lambda+(1-\lambda)=1
    $

    Hence $\displaystyle 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
    5
    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 $\displaystyle P$ is a doubly stochastic matrix.

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

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

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

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

    From this you should be able to prove that $\displaystyle P$ is an extreme point of $\displaystyle 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: Dec 2nd 2011, 04:14 AM
  2. unique value and extreme point question
    Posted in the Calculus Forum
    Replies: 12
    Last Post: Sep 3rd 2011, 10:36 AM
  3. Replies: 4
    Last Post: Jun 2nd 2010, 11:00 AM
  4. The union of two convex sets is not convex
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Jan 30th 2010, 03: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: Nov 3rd 2009, 09:51 AM

Search Tags


/mathhelpforum @mathhelpforum