Changes between Initial Version and Version 1 of Ticket #7492


Ignore:
Timestamp:
11/19/09 11:16:21 (11 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #7492

    • Property Summary changed from Decomposition of a doubly stochastic matrix as a convex sum of permutations to Decomposition of a doubly stochastic matrix as a convex sum of permutations (Birkhoff–von Neumann Theorem)
  • Ticket #7492 – Description

    initial v1  
    1 As the title says, there is a theorem saying that any doubly stochastic matrix ( http://en.wikipedia.org/wiki/Doubly_stochastic_matrix ) can be written as a convex sum of permutations.
     1As 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
    33A proof and an algorithm can be found in this book : http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/