Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Here's Wikipedia on doubly stochastic matrices.

share|improve this question
1  
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

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
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! –  J. M. Oct 26 '10 at 2:55
1  
@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? –  J. M. Oct 26 '10 at 3:07
    
Much better. Thanks. :) –  Mike Spivey Oct 26 '10 at 3:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.