Past exam of the computer science course of the University of Oxford 2018 Algorithms 3 d Solution 2026-10-31
Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight . Pairing everyone is a perfect matching, and its maximum total weight is . Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row and column both below one. Increasing by the smaller of their positive deficits remains feasible and increases the objective because , a contradiction.
Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence . One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.
The dual linear program assigns nonnegative dual variables to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is . It is feasible, for example by taking and . Strong duality now gives . In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.
For a direct weak duality check, sum over any pairing . Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 5 b Solution Created 2026-10-03 Updated 2026-10-06
The preceding perfect matching gives a permutation matrix supported on the positive entries of . LetIf , every row's selected entry is one and all other entries vanish, so . Otherwiseis a doubly stochastic matrix with strictly fewer positive entries. Induct on the number of positive entries: the base case has exactly positive entries and is a permutation matrix. By induction, write as a convex combination. Thenis another convex combination, with nonnegative coefficients summing to one. ThusThis constructive proof of the Birkhoff-von Neumann theorem is Birkhoff decomposition by support matchings.
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 4 20H b Solution Created 2026-09-24 Updated 2026-10-06
An extreme point of a convex set cannot be written as a nontrivial convex combination of two distinct members. If a permutation matrix with and doubly stochastic, each zero entry of forces the corresponding entries of to be zero by nonnegativity. The unique possible nonzero entry in each row must then be one by the row sum. Thus , proving that every permutation matrix is extreme.
Conversely, let be a doubly stochastic matrix that is not a permutation matrix. At least one entry lies strictly between zero and one. Form a bipartite graph whose two vertex classes are rows and columns, with edges precisely at these fractional entries. Every incident row has at least two fractional entries: a single fractional entry, with all other entries zero or one, could not give row sum one. The same holds for columns.
A finite nonempty graph whose incident vertices all have degree at least two contains a cycle. In a bipartite graph that cycle has even length. Assign alternating signs to its entries, giving a nonzero matrix with every row and column sum zero. Choose smaller than the distance of each cycle entry from both zero and one. Then and remain doubly stochastic matrices, are distinct, and satisfySo is not extreme. ThereforeThis alternating-cycle perturbation of a doubly stochastic matrix proves the extreme-point part of the Birkhoff-von Neumann theorem directly.