If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions?
Finding all n×n permutation matrices
-
0Would you edit your title and question (and tags) to that effect? – 2010-10-25
1 Answers
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 7.2.1.2. )
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
$\begin{matrix}1&2&3&4\\1&4&2&3\end{matrix}$
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.,
$\begin{pmatrix}1&0&0&0\\0&0&0&1\\0&1&0&0\\0&0&1&0\end{pmatrix}$
-
0Much better. Thanks. :) – 2010-10-26