Changes between Version 1 and Version 2 of Ticket #7492


Ignore:
Timestamp:
11/20/09 09:27:28 (11 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #7492

    • Property Status changed from new to needs_review

  • Ticket #7492 – Description

    v1 v2  
    11As 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.
    22
    3 A proof and an algorithm can be found in this book : http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/
     3This 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
     9It may be better to review these patches before this very one.
    410
    511Nathann