# convex set and extreme point

• May 17th 2006, 11:09 PM
suedenation
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. :)
• May 18th 2006, 08:59 AM
CaptainBlack
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:

$
\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
• May 19th 2006, 01:08 AM
CaptainBlack
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