0

I know that the set of doubly stochastic matrices $(\Omega(n))$ form a polyhedron. I only know about polyhedron is that it is a $3$-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. Also, I read that

Birkhoff proof that set of all doubly stochastic matrices is a convex combination of permutation matrices.

I studied a statement form research article about doubly stochastic matrices is

doubly stochastic matrices $(\Omega(n))$ form a closed bounded convex polyhedron in Euclidean $n^2$ space whose dimension is $(n-1)^2$ and whose vertices are the $n\times n $ permutation matrices.

Can someone give advice on how to visualize this statement in $\mathbb{R}^{n^2}$? Or give some examples of this type polyhedron if exist? Also I am not getting that dimension part, namely, how it is $(n-1)^2$.

Any hint is appreciated.

Rodrigo de Azevedo
  • 1
Mathematics learner
  • 156
  • I find it extremely difficult to visualize anything in $\mathbb R^n$ when $n>3$. Have you tried to visualize the statements in $n=2$ and $n=3$? The dimension part is not that difficult to see there. – Kurt G. May 05 '22 at 11:34
  • @kurt G if $n=2$ then what is the order of doubly stochastic matrix in that case? – Mathematics learner May 05 '22 at 11:37
  • Please write down the constraints that the matrix elements must satisfy and make at least one attempt to think about it. The statements are saying the dimension is one. – Kurt G. May 05 '22 at 11:41
  • Hint : can you show that any doubly stochastic $2\times 2$-matrix must be of the form $$ \begin{pmatrix}a&1-a\1-a&a\end{pmatrix}\quad a\in[0,1]\quad ? $$ – Kurt G. May 05 '22 at 11:47
  • @KurtG. Yes sir I understand this hint and can we visualized the given in $\mathbb{R^{n^2}}$ not in $\mathbb{R^{n}}$ this statement for matrix of order $2,$ I have done mistake previousely – Mathematics learner May 05 '22 at 11:51
  • 1
    The doubly stochastics form a polytope, not a polyhedron; a polytope is a generalization of the concept of polyhedron to dimensions higher than three. What Birkhoff proved is that each doubly stochastic matrix is a convex combination of permutation matrices. – Gerry Myerson May 05 '22 at 11:54
  • @Mathematicslearner . Again if you want me to visualize anything in $\mathbb R^n$ $n>3$ I am sorry that I have to drop out. I am from planet Earth. – Kurt G. May 05 '22 at 11:55
  • Here's why the dimension is $(n-1)^2$. Fill in everything but the last row and last column anyway you like with non-negative numbers in such a way that no row sum and no column sum exceeds one – you have filled in $(n-1)^2$ numbers. Then there's a unique way to fill in the last row and column to make the matrix doubly-stochastic. – Gerry Myerson May 05 '22 at 12:00
  • @KurtG. So we can say that for a matrix $2$ can be written as convex combination of permutation matrices of order $2$ and if we vectorised these matrices they are in vectors dimension $4$ that is $\mathbb{R^4}$ that why we can not visualized it, still but we say that the closed figure we get after joining these vectors is finally a polytope right sir ?? – Mathematics learner May 05 '22 at 12:03
  • A very simple example of a polytope in, say, ${\bf R}^{17}$ is the set of all $17$-tuples with coordinates between zero and one, inclusive. This is the $17$-dimensional analogue of the unit square in two dimensions, and of the unit cube in three dimensions. As for visualization, the old joke goes, just visualize an infinite-dimensional cube, then cut it down to $17$ dimensions. – Gerry Myerson May 05 '22 at 12:03
  • The convex hull of a finite set of points in the plane is a polygon (provided the points don't all lie on the same line); the convex hull of a finite set of points in three dimensions is a polyhedron (provided ...); in general, the convex hull of a finite set of points in $n$ dimensions is in general, a polytope. The set of doubly stochastics is the convex hull of the finite set of permutation matrices. – Gerry Myerson May 05 '22 at 12:07
  • @GerryMyerson Sir Am i correct in my last comment? – Mathematics learner May 05 '22 at 12:09
  • In that comment, I don't know what you mean by "a matrix 2". – Gerry Myerson May 05 '22 at 12:14
  • @ a matrix $2 \times 2. $ – Mathematics learner May 05 '22 at 12:14
  • But not every $2\times2$ matrix is a convex combination of permutation matrices. – Gerry Myerson May 05 '22 at 12:16
  • But for a doubly stochastic matrix can we say that – Mathematics learner May 05 '22 at 12:22
  • If you mean a doubly stochastic matrix, you should say a doubly stochastic matrix. In the case $n=2$, the doubly stochastic matrices form a line segment joining $\pmatrix{1&0\cr0&1\cr}$ and $\pmatrix{0&1\cr1&0\cr}$ or, if you prefer, joining $(1,0,0,1)$ and $(0,1,1,0)$. A line segment is a degenerate polytope. – Gerry Myerson May 05 '22 at 12:43
  • @GerryMyerson okay, Sir can you share any notes or suggest some books for basics on these polyhedron or polytopes related to doubly stochastic matrices. – Mathematics learner May 05 '22 at 12:49
  • For arbitrary $n$ we know that a doubly stochastic matrix is in the convex hull of the $n!$ permutation matrices who themselves can be considered as being particular canonical basis vectors in $\mathbb R^{n^2}$. A polytope we can visualize in $\mathbb R^3$ is nothing else than the convex hull of $m$ points. Imho this kills (without reading a book) 90% of the question. The only thing that needed to be proven is the dimension $(n-1)^2$. – Kurt G. May 05 '22 at 14:38
  • @Kurt, I hope you aren't saying that the $n!$ permutation matrices form a basis for the $n^2$-dimensional vector space of matrices. – Gerry Myerson May 05 '22 at 23:38
  • You could start with https://en.wikipedia.org/wiki/Doubly_stochastic_matrix, MathLearner, and the references given there. – Gerry Myerson May 05 '22 at 23:41
  • @GerryMyerson . No no. I was very careful not saying that :) . – Kurt G. May 06 '22 at 05:55
  • @Mathematicslearner Take a look at this. – Rodrigo de Azevedo May 06 '22 at 11:49
  • Making any progress, MathLearner? Had a look at the Wikipedia link I gave? – Gerry Myerson May 08 '22 at 03:48
  • @GerryMyerson yes sir I am understanding Birkhoff polytopes and now thing related to this topic. – Mathematics learner May 08 '22 at 10:14
  • @RodrigodeAzevedo You already edited the question now what should i i have to do? – Mathematics learner May 08 '22 at 10:18
  • @Mathematicslearner Take what you learned from the comments to refine the question, then flag the comments as no longer needed. – Rodrigo de Azevedo May 08 '22 at 11:00

0 Answers0