§ Birkhoff Von Neumann theorem

• By Frobenius Konig theorem, $A$ must have block structure:

   r
s [B|C]
  --+---
  [0|D]

• Where $r + s = n + 1$

• 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 (n-r)k$.
• In total, we get $(n-r)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 ( 1-1, 2-2, 3-3).
• 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]

• And so on.

§ 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.