If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Don Knuth's Volume 4, Fascicle 2, of The Art of Computer Programming has a long section on generating all permutations, including algorithms for doing so. I found a draft here online. (Update: The link still works, but it is now to a zipped file. However, Knuth has since published Volume 4A: Combinatorial Algorithms, Part 1, which includes this material on generating permutations as Section 126.96.36.199. )
Then, going from a permutation to a permutation matrix is fairly straightforward. For example, suppose you have the permutation 1342 of the numbers 1, 2, 3, and 4. That can be represented in two-line form as
because the permutation sends 1 to the first position, 2 to the fourth position, etc.
Then the permutation matrix is the matrix with 1's in entries (1,1), (2,4), (3,2), (4,3), and 0's elsewhere; i.e.,