Changes between Version 1 and Version 2 of Ticket #7492
 Timestamp:
 11/20/09 09:27:28 (11 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #7492

Property
Status
changed from
new
toneeds_review

Property
Status
changed from

Ticket #7492 – Description
v1 v2 1 1 As the title says, the Birkhoff–von Neumann Theorem (http://en.wikipedia.org/wiki/Birkhoff%E2%80%93von_Neumann_Theorem) says that any doubly stochastic matrix ( http://en.wikipedia.org/wiki/Doubly_stochastic_matrix ) can be written as a convex sum of permutations. 2 2 3 A proof and an algorithm can be found in this book : http://www.thi.informatik.unifrankfurt.de/~jukna/EC_Book/ 3 This patch requires several other patches to be applied first ( or merged into Sage ) : 4 5 * #7270 Linear Programming class 6 * #7268 or #7333 as a LP solver 7 * #6680 Matching function 8 9 It may be better to review these patches before this very one. 4 10 5 11 Nathann