# Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions?

-
According to the link: "The principal fact about doubly stochastic matrices is the Birkhoff–von Neumann theorem. This states that the set $B_n$ of doubly stochastic matrices of order $n$ is the convex hull of the set of permutation matrices (of order $n$), and furthermore that the vertices (extreme points) of $B_n$ are precisely the permutation matrices." Since the basic feasible solutions (BFS) are the extreme points, is your question about how to find the set of all permutation matrices? –  Mike Spivey Oct 25 '10 at 20:29
Yes, is there an algorithm to do so? –  GBa Oct 25 '10 at 20:41
Would you edit your title and question (and tags) to that effect? –  Mike Spivey Oct 25 '10 at 21:00

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}$$

-
Nice! This neatly solves a problem I had a few months ago. Actually, if it were not for you, I'd not have known Knuth is writing new volumes of TAOCP. Thanks a bunch! –  Guess who it is. Oct 26 '10 at 2:55
@J.M.: Would you mind editing the title so that it better reflects what the OP really wanted? I had the rep to do that until they ended the public beta earlier today. :) –  Mike Spivey Oct 26 '10 at 2:58
I aim to please. Better? –  Guess who it is. Oct 26 '10 at 3:07
Much better. Thanks. :) –  Mike Spivey Oct 26 '10 at 3:14