§ Birkhoff Von Neumann theorem
 By Frobenius Konig theorem, $A$ must have block structure:
r
s [BC]
+
[0D]
 The column sum of $B$ is $1$ for all $j$. So $B^i_j 1^j = 1$
 The row sum of $B$ is less than or equal to $1$ for all $j$. So $B^i_j 1_i \leq 1$
 From the first sum, we get the total sum as $\sum_{i, j} B[i][j] = sk$
 From the second sum, we get the total sum as $\sum_{i, j} B[i][j] \leq (nr)k$.
 In total, we get $(nr)k \leq sk$ which implies $s + r \leq n$ which is a contradiction because $s + r = n + 1$.
§ Proof 1 of BVN (Constructive)
 Let's take a
3x3
doubly stochastic matrix:
[#0.4 0.3 0.3]
[0.5 #0.2 0.3]
[0.1 0.5 #0.4]
 By some earlier lemma, since permanant is greater than zero, the graph has a perfect matching.
 Suppose we know how to find a perfect matching, which we know exists. Use flows (or hungarian?)
 Take the identity matching as the perfect matching (
11
, 22
, 33
).  Take the minimum of the matches,
min(0.4, 0.2, 0.4) = 0.2
. So we write the original matrix as:
0.2 [1 0 0] [0.2 0.3 0.3]
[0 1 0] + [0.5 0 0.3]
[0 0 1] [0.1 0.5 0.4]
 Second matrix has row/col sums of
0.8
. Rescale by dividing by 0.8
to get another doubly stochastic matrix.  Then done by induction on the number of zeroes amongst the matrix entries.
[0.2 0.3 0.3]
[0.5 0 0.3]
[0.1 0.5 0.4]
 (2) Take the matching given by:
[#0.2 0.3 0.3]
[0.5 0 #0.3]
[0.1 #0.5 0.4]
 (2) This can be written as:
[1 0 0] [0 0.3 0.3]
0.2[0 0 1] + [0.5 0 0.1]
[0 1 0] [0.1 0.3 0.4]
§ Nice method to find permutation that makes progress

NxN
doubly stochastic. We must have a permutation that forms a perfect matching. How to find it?  If all elements are
0/1
, then it's already a permutation.  Otherwise, find a row which has an element
a
between 0/1
. Then this means that the same row will have ANOTHER element b
betwene 0/1
.  Then the column of this element
b
will have another element c
between 0/1
. Keep doing this until you find a loop.  Then find the minimum of these elements, call it $\epsilon$.
 Subtract $\epsilon$ at the element that had value $\epsilon$. Then add epislon to the element that was in the same row(column). Then continue, subtract $\epsilon$ for the pair of this.