5
$\begingroup$

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.

  • 2
    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?2010-10-25
  • 0
    Yes, is there an algorithm to do so?2010-10-25
  • 0
    Would you edit your title and question (and tags) to that effect?2010-10-25

1 Answers 1

8

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

  • 0
    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!2010-10-26
  • 2
    @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. :)2010-10-26
  • 0
    I aim to please. Better?2010-10-26
  • 0
    Much better. Thanks. :)2010-10-26