Opened 10 years ago

Closed 9 years ago

Last modified 9 years ago

#7492 closed enhancement (fixed)

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

Reported by: ncohen Owned by: mhansen
Priority: major Milestone: sage-4.4.4
Component: combinatorics Keywords:
Cc: Merged in: sage-4.4.4.alpha0
Authors: Nathann Cohen Reviewers: Mike Hansen, David Loeffler
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

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

Attachments (2)

trac_7492.patch (8.8 KB) - added by ncohen 9 years ago.
trac_7492_review.patch (3.0 KB) - added by davidloeffler 9 years ago.
apply over previous patch

Download all attachments as: .zip

Change History (19)

comment:1 Changed 10 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 10 years ago by ncohen

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

comment:3 Changed 10 years ago by ncohen

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

comment:4 Changed 10 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 10 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 10 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:7 follow-up: Changed 9 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 9 years ago by davidloeffler

Replying to 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 9 years ago by ncohen

  • Description modified (diff)

comment:10 Changed 9 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 9 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 9 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 9 years ago by ncohen

Changed 9 years ago by davidloeffler

apply over previous patch

comment:13 Changed 9 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 9 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 9 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 9 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 9 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.