Doubly Stochastic Matrices and the Assignment Problem

Abstract

The topic of this thesis is linear optimization in relation to doubly stochastic matrices, which constitute the Birkhoff polytope. This polytope is closely related to the concept of majorization, which will be defined and yield some results regarding both the Birkhoff polytope and permutation matrices. An important result in this setting is the Birkhoff and von Neumann theorem, which states that the permutation matrices constitute the extreme points of the Birkhoff polytope. This will be the main theorem of this thesis and will be proved in two different ways. This theory will be connected to the assignment problem, which will be presented with both matrix and graph notation, together with some theoretical results, algorithms and applications. Applying more or less constraints to the problems presented will result in numerous variations for which some will be presented and discussed in this thesis. Since this thesis has been written as part of my teacher education, a didactical discussion regarding whether and how assignment problems could be introduced in the mathematics curriculum.