This exercise outlines a proof of the Birkhoff-von Neumann Theorem. (a) For n Z+, an n

This exercise outlines a proof of the Birkhoff-von Neumann Theorem.
(a) For n ˆˆ Z+, an n × n matrix is called a permutation matrix if there is exactly one 1 in each row and column, and all other entries are 0. How many 5 × 5 permutation matrices are there? How many n × n?
b) An n × n matrix B is called doubly stochastic if btJ > 0 for all 1

verify that B is doubly stochastic.
(c) Find four positive real numbers c1, c2, c3, and c4, and four permutation matrices P1, P2, P3, and P4, such that c1 + c2 + c3 + c4 = 1 and B = c1P1 + c2P2 + C3P3 + c4P4.
(d) Part (c) is a special case of the Birkhoff-von Neumann Theorem: If B is an n × n doubly stochastic matrix, then there exist positive real numbers c1, c2, . . . , ck and permutation matrices P1, P2, . . . , Pk such that ˆ‘ki=1 ci = 1 and ˆ‘ki=1. To prove this result, proceed as follows: Construct a bipartite graph G = (V, E) with V partitioned as X ˆª Y, where X = {x1, x2, . . . , xn] and Y = {y1, y2,......, yn}- The vertex xn for all 1 0. We claim that there is a complete matching of X into Y.
If not, there is a subset A of X with |A| > |R(A)|. That is, there is a set of r rows of B having positive entries in s columns and r > s. What is the sum of these r rows of P? Yet the sum of these same entries, when added column by column, is less than or equal to s. (Why?) Consequently, we have a contradiction.
As a result of the complete matching of X into Y, there are n positive entries in B that occur so that no two are in the same row or column. (Why?) If c is the smallest of these entries, then we may write B = c1P1 + B1, where Pi is an n Xn permutation matrix wherein the l's are located according to the positive entries in B that came about from the complete matching. What are the sums of the entries in the rows and columns of B1?
(e) How is the proof completed?

Transcribed Image Text:

0.2 0.1 07 B 0.4 0.5 0.1 0.4 0.4 0.2