Opened 12 years ago

Closed 11 years ago

# Decomposition of a doubly stochastic matrix as a convex sum of permutations (Birkhoff–von Neumann Theorem)

Reported by: Owned by: ncohen mhansen major sage-4.4.4 combinatorics sage-4.4.4.alpha0 Nathann Cohen Mike Hansen, David Loeffler N/A

As the title says, the Birkhoff–von Neumann Theorem (http://en.wikipedia.org/wiki/Birkhoff%E2%80%93von_Neumann_Theorem) says that any doubly stochastic matrix ( http://en.wikipedia.org/wiki/Doubly_stochastic_matrix ) can be written as a convex sum of permutations.

This patch requires several other patches to be applied first ( or merged into Sage ) :

Nathann

### comment:1 Changed 12 years ago by ncohen

• Description modified (diff)
• Summary changed from Decomposition of a doubly stochastic matrix as a convex sum of permutations to Decomposition of a doubly stochastic matrix as a convex sum of permutations (Birkhoff–von Neumann Theorem)

### comment:2 Changed 12 years ago by ncohen

• Description modified (diff)
• Status changed from new to needs_review

### comment:3 Changed 12 years ago by ncohen

• Description modified (diff)
• Report Upstream set to N/A

### comment:4 Changed 12 years ago by ncohen

• Description modified (diff)

### comment:5 Changed 12 years ago by mhansen

• Authors set to Nathann Cohen
• Reviewers set to Mike Hansen
• Status changed from needs_review to needs_work

This patch needs to be updated as there is no max_matching method for graphs.

### comment:6 Changed 12 years ago by ncohen

• Status changed from needs_work to needs_review

### comment:7 follow-up: ↓ 8 Changed 11 years ago by davidloeffler

• Status changed from needs_review to needs_work

Needs work, I'm afraid.

• Firstly, there are no checks on the input type. It will happily accept non-doubly-stochastic matrices, and return garbage; and it seems to silently replace real numbers with rational approximations to them, which is frankly rather weird. The docstring should state clearly what base rings are allowed (integers? rationals? reals?) and there should be a check to make sure that the input matrix really is a doubly stochastic matrix over one of these base rings.
• The doctests won't work without an optional spkg, so they should be flagged as such.
• Non-ASCII character in the docstring (it reads as "Birkhoff[a-with-circumflex][empty-square-box][empty-square-box]von Neumann" on my system)
• There's not a lot of point in adding functions when there's no obvious way of calling them from the command line. Either this should be imported in an all.py somewhere, or (much preferably) there should be a method of one of the matrix classes that calls it.

### comment:8 in reply to: ↑ 7 Changed 11 years ago by davidloeffler

and it seems to silently replace real numbers with rational approximations to them, which is frankly rather weird.

Sorry, that was a mistake in my test script, not in your code. But I still think that the code should do some sanity checks on its input.

### comment:9 Changed 11 years ago by ncohen

• Description modified (diff)

### comment:10 Changed 11 years ago by ncohen

• Status changed from needs_work to needs_info

Hello !!

This patch needed to be updated anyway, as it was veeeeery old and many things changed since. I will gladly add a chechking that the matrix is indeed bistochastic if you think it necessary (though I like to think of functions doing just what they are meant to, and not spend too much time checking the user is not doing anything wrong). It is not very long anyway :-)

• Considering how the algorithm works, it does not really care about the base ring. Anyone will work (well, as long as it is completely ordered !), so Reals, Integers, Rationals are all ok. How would you like this to be mentionned ? I never use these types, and I do not know at all how it is usually done.
• The doctests *needed* an optional package. With #8166, they don't anymore, and I will update the patch in consequence :-)
• Sorry about the non-ASCII character !!
• Another place where I wouldn't know how to do otherwise. There are some graph functions which are not method of the Graph object, just because they are too specific to be, and the users can find out about them by reading the reference manual, or the correct module. If it is not the custom in this part of Sage, where would you like to see it ? I have to admit I have no clue... :-)

Thank you for your help !!

Nathann

### comment:11 Changed 11 years ago by davidloeffler

I think the standard practice is to have an optional argument "check", which defaults to True but can be set to False if you know your input is valid and you don't want to waste time checking.

Rather than having an explicit list of allowable base rings, I suggest checking that the base ring has a canonical coercion map to RR.

Maybe you could put in a method under (perhaps) sage.matrix.matrix2 that calls this, and cross-reference between the two docstrings.

David

### comment:12 Changed 11 years ago by ncohen

• Status changed from needs_info to needs_review

Well, it took me some time but.... Would this patch suit your taste ? :-)

Nathann

### Changed 11 years ago by davidloeffler

apply over previous patch

### comment:13 Changed 11 years ago by davidloeffler

• Reviewers changed from Mike Hansen to Mike Hansen, David Loeffler

Excellent! I only have one minor suggestion: I think it's also worth checking that the matrix has nonnegative entries. I've added a reviewer patch that makes this change, and also adds a couple more doctests. I'm happy with the code now, modulo these changes; so if you (or anyone else who happens to be reading this) could double-check my second patch, then we can call this a positive review.

### comment:14 Changed 11 years ago by ncohen

• Status changed from needs_review to positive_review

Thank you for your corrections ! It introduces no docstring error, is nicely applied, etc... Positive review to your changes, and hence to this whole ticket. It still depends on two other tickets waiting for review, though (#8364 and #8166) :-)

Nathann

### comment:15 Changed 11 years ago by ncohen

(if you have a few seconds for them, by the way ; ... they are very simple and require absolutely no knowledge of graph theory -- #8364 just adds arguments to graph functions that are immediately forwarded to a sub-function, and #8166 merges two functions which were doing the same thing in different ways ) :-)

Nathann

### comment:16 Changed 11 years ago by mhansen

• Merged in set to sage-4.4.4.alpha0
• Resolution set to fixed
• Status changed from positive_review to closed

Some of doctests had to be marked as optional as they required a linear programming solver.

### comment:17 Changed 11 years ago by mhansen

I somehow missed the dependence on #8166. I've removed the optional markings from the doctests in this patch.

Note: See TracTickets for help on using tickets.