# convex set and extreme point

• May 17th 2006, 10: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, 07: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 $\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
• May 19th 2006, 12: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 $\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