convex set and extreme point

**suedenation** · May 17th 2006, 10:09 PM

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.

**CaptainBlack** · May 18th 2006, 07:59 AM

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:

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

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

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

then $B$ is doubly stochastic, since:

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

and:

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

Hence $C$ is convex.

RonL

**CaptainBlack** · May 19th 2006, 12:08 AM

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

Thread: convex set and extreme point

LinkBack

Thread Tools

Display

convex set and extreme point

Similar Math Help Forum Discussions

Advanced Geometry - Convex sets and Extreme points proof

unique value and extreme point question

Find the critical point(s) of f(x,y) = x + y^2 - e^x. Decide which are extreme points

The union of two convex sets is not convex

Proving that f^2 is convex if f is convex and f>=0

Search Tags