I have just found a very beautiful and short proof for the birkhoff-von Neuman theorem that gives a new probabilistic approach.
Notations :
Let,
$S_{n}$ be the set of permutations of the set {$1,...,n$},
$K_{ij} = \{\sigma \in S_{n} / \sigma(i)=j\}$,
$H = \{\sum_{\sigma \in S_{n}}\mu(\sigma)P_{\sigma} $ / $\mu$ is a probability measure over $S_{n}\}$ be the convex hull of the set of permutation matrices.
A doubly stochastic matrix (also called bi-stochastic), is a square matrix A=$(a_{ij})$ of non negative real numbers, each of whose rows and columns sums to 1, wi will note their set $D$.
Birkhoff-von Neuman theorem :
The Birkhoff–von Neumann theorem states that $D$ is the convex hull of the set of n$\times$n permutation matrices.
Proof:
We will start in the proof by the most hard direction : $D \subset H$.
First, we will put the point on some properties of $K_{ij}$ that will be useful as we go in the proof.
- $K_{kj}\cap K_{ij}=\emptyset$ for any $k\not= i$ and $\cup_{i}K_{ij}=S_{n}$.
- $K_{il}\cap K_{ij}=\emptyset$ for any $l\not= j$ and $\cup_{j}K_{ij}=S_{n}$.
- $Card(K_{ij})=(n-1)!$
Now let $(\Pi_{ij}) \in D$,
To solve the problem we will construct a probability measure $\mu$ that verifies $\Pi = \sum_{\sigma\in S_{n}}\mu(\sigma)P_{\sigma}$.
We will define our probability measure $\mu$ on any subset $B$ of $S_{n}$ as the following:
$\mu : B\subset S_{n} \longmapsto \mu(B)=\frac{1}{(n-1)!}\sum_{\sigma \in B}\Pi_{i\sigma(i)}$.
With $\mu(\emptyset)=0$.
It is clear that $\mu$ is positive and $\sigma $-additive.
Lets demonstrate that it verify the third axiom :
$\sum_{\sigma\in S_{n}}\mu (\sigma) = \sum_{i}\sum_{\sigma\in K_{ij}}\mu (\sigma)$
And we have :
$\sum_{\sigma\in K_{ij}}\mu (\sigma)=\frac{1}{(n-1)!}\sum_{\sigma\in K_{ij}}\Pi_{ij}$
$=\Pi_{ij}$
So $\sum_{\sigma\in S_{n}}\mu (\sigma) = \sum_{i}\Pi_{ij} = 1$, and we are done.
Let's rappel that a permutation matrix can be written as :
$P_{\sigma} = \sum_{i} E_{i\sigma(i)}$, where $E_{ij}=(\delta_{ij}(k,l))_{k,l}$
Now,
$\sum_{\sigma\in S_{n}}\mu (\sigma)P_{\sigma}=\sum_{\sigma\in S_{n}}\mu (\sigma)\sum_{i}E_{i\sigma(i)}$
$=\sum_{i}\sum_{j}\sum_{\sigma \in K_{ij}}\mu(\sigma)E_{ij}$
$=\sum_{i}\sum_{j}\Pi_{ij}E_{ij}$
$=\Pi$.Witch means that $\Pi \in H$
Because,our proof of this direction is constructive, it suffices to do the back forward job to prove the other direction of the the problem.
To make it clear :
let $h=\sum_{\sigma\in S_{n}}\mu(\sigma)P_{\sigma}$ in H
$h=\sum_{\sigma\in S_{n}}\mu(K_{ij})E_{ij}$
we have, $\sum_{i}\mu(K_{ij})=\mu(\cup_{i}K_{ij})=\mu(S_{n})=1$.
and $\sum_{j}\mu(K_{ij})=\mu(\cup_{j}K_{ij})=\mu(S_{n})=1$.
conclusion
We demonstrated here, in addition to the Birkhof theorem, that any stochastic matrix can be associated to a class of probability measures on $S_{n}$.And its coefficients can be interpreted as the probability off the events $K_{ij}$ with respect to any of theses measures.
We can even go further and split $M(S_{n})$, the set of probability measures over $S_{n}$, into equivalence classes $\bar{\mu}^{\Pi}$ with $\bar{\mu}^\Pi=\{\mu\in M(S_{n}) , \mu(K_{i,j})_{ij} = \Pi\}$ and $\cup_{\Pi\in D}\bar{\mu}^\Pi = M(S_{n})$.With the equivalence relation $\mu R\nu \iff \mu(K_{i,j})_{ij}=\nu(K_{i,j})_{ij} $.
We can then define an isomorphism $\phi : D \to M(S_{n})/_{R}$ that associate to every $\Pi \in D$ a unique $\phi(\Pi)=\bar{\mu}^{\Pi}$ $\in$ $M(S_{n})/_{R}$.And try then to characterize entirely $M(S_{n})$.
Your proof is not valid because it equivocates with the letter $i$.
On the one hand, in your definition of $\mu(B)$ you use $i$ as a fixed index. Let's call this $i'$.
On the other hand, in your calculations you use $\sum_{\sigma\in K_{ij}}\mu(\sigma)=\Pi_{ij}$ as if it's true for arbitrary $i$, when actually the sum is equal to $\frac{1}{n-1}\sum_{j'\ne j}\Pi_{i'j'}$ for $i\ne i'$, which in general is not $\Pi_{ij}$.