Sage: Ticket #7301: Gale Ryser theorem
https://trac.sagemath.org/ticket/7301
<p>
The Gale-Ryser theorem is about filling a matrix with 0 and 1 when you know the number of 0 and 1 in each column and in each row.
</p>
<p>
It would not be too much work to write in Sage a function filling a matrix with 0 and 1 when the data is correct, and returning an error otherwise...
</p>
<p>
More informations there : <a class="ext-link" href="http://mathworld.wolfram.com/Gale-RyserTheorem.html"><span class="icon"></span>http://mathworld.wolfram.com/Gale-RyserTheorem.html</a>
</p>
<p>
<strong></strong><strong></strong><strong> please set <a class="closed ticket" href="https://trac.sagemath.org/ticket/7590" title="enhancement: Create Bipartite Graph according to 2 degree sequences (closed: fixed)">#7590</a> as needing review when this receives a positive review ! </strong><strong></strong><strong></strong><strong>
</strong></p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7301
Trac 1.1.6ncohenThu, 03 Dec 2009 11:22:50 GMTstatus changed; upstream set
https://trac.sagemath.org/ticket/7301#comment:1
https://trac.sagemath.org/ticket/7301#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>upstream</strong>
set to <em>N/A</em>
</li>
</ul>
TicketncohenThu, 03 Dec 2009 11:23:15 GMT
https://trac.sagemath.org/ticket/7301#comment:2
https://trac.sagemath.org/ticket/7301#comment:2
<p>
Here it is ! :-)
</p>
TicketwdjThu, 03 Dec 2009 12:16:14 GMT
https://trac.sagemath.org/ticket/7301#comment:3
https://trac.sagemath.org/ticket/7301#comment:3
<p>
I can review this in a week or two since a colleague here is an expert in that area (and I'll be finished with teaching then:-).
</p>
<p>
Is the graph-theoretic analog of this theorem implemented? (The Haval-??? Theorem?)
</p>
TicketncohenThu, 03 Dec 2009 12:27:00 GMT
https://trac.sagemath.org/ticket/7301#comment:4
https://trac.sagemath.org/ticket/7301#comment:4
<p>
I'm glad to hear it !! This is my second attempt at a contribution to the Combinatorics section, and I hope you will find it useful :-)
</p>
<p>
The odd thing is that if I knew of the Gale Ryser theorem, I never heard of the theorem you are talking about, when it clearly should be the opposite... Could you tell me what this theorem is about ? I was not able to find it using "haval" on Google, and I am very interested in what it could be :-)
</p>
<p>
The only direct use I could make of this theorem in Graph Theory is deciding whether there exists a bipartite graph with a given degree sequence... Is that the result you are mentionning ? :-)
</p>
<p>
And by the way, I only wrote this function for squares matrices when it is not required.. Thinking about bipartite graphs helped me notice :-)
</p>
<p>
Nathann
</p>
TicketwdjThu, 03 Dec 2009 12:53:12 GMT
https://trac.sagemath.org/ticket/7301#comment:5
https://trac.sagemath.org/ticket/7301#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:4" title="Comment 4">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I'm glad to hear it !! This is my second attempt at a contribution to the Combinatorics section, and I hope you will find it useful :-)
</p>
<p>
The odd thing is that if I knew of the Gale Ryser theorem, I never heard of the theorem you are talking about, when it clearly should be the opposite... Could you tell me what this theorem is about ? I was not able to find it using "haval" on Google, and I am very interested in what it could be :-)
</p>
<p>
The only direct use I could make of this theorem in Graph Theory
is deciding whether there exists a bipartite graph with a given
degree sequence... Is that the result you are mentionning ? :-)
</p>
</blockquote>
<p>
Yes, I believe that is it. But I think the Haval-??? Theorem generalizes that a bit.
</p>
<blockquote class="citation">
<p>
And by the way, I only wrote this function for squares matrices when it is not required.. Thinking about bipartite graphs helped me notice :-)
</p>
<p>
Nathann
</p>
</blockquote>
TicketncohenFri, 04 Dec 2009 17:14:31 GMT
https://trac.sagemath.org/ticket/7301#comment:6
https://trac.sagemath.org/ticket/7301#comment:6
<p>
Now with non-square matrices ;-)
</p>
TicketmvnguSat, 05 Dec 2009 13:11:53 GMTcc set
https://trac.sagemath.org/ticket/7301#comment:7
https://trac.sagemath.org/ticket/7301#comment:7
<ul>
<li><strong>cc</strong>
<em>sage-combinat</em> added
</li>
</ul>
TickethivertMon, 07 Dec 2009 23:29:32 GMT
https://trac.sagemath.org/ticket/7301#comment:8
https://trac.sagemath.org/ticket/7301#comment:8
<p>
Hi there,
</p>
<p>
There is something I don't get in the doc:
</p>
<pre class="wiki">The Gale Ryser theorem asserts that if `p_1,p_2` are two
partitions of `n` of respective lengths `k_1,k_2`, then there is
a binary `k_1\times k_2` matrix `M` such that `p_1` is the vector
of row sums and `p_2` is the vector of column sums of `M`, if
and only if `p_2` dominates `p_1`.
</pre><p>
I suggest that the role of <code>p_1</code> and <code>p_2</code> are not symmetric... Is this really a "if and only if" ? If you transpose the matrix then the role of <code>p_1</code> and <code>p_2</code> are exchanged... Or dominate is not the same as dominance order...
</p>
<p>
Am I definitely confused ???
</p>
<p>
Florent
</p>
TicketncohenMon, 07 Dec 2009 23:32:28 GMT
https://trac.sagemath.org/ticket/7301#comment:9
https://trac.sagemath.org/ticket/7301#comment:9
<p>
oopsssssss !!! Would "if and only if the conjugate of p_2 dominates p_1"make you feel better ? :-)
</p>
<p>
This is what the code does ( and what the theorem says ) :-)
</p>
<p>
Nathann
</p>
TicketwdjTue, 08 Dec 2009 03:50:12 GMT
https://trac.sagemath.org/ticket/7301#comment:10
https://trac.sagemath.org/ticket/7301#comment:10
<p>
I am not an expert but I do have a colleague who not only wrote his thesis on a related result but claims that the Gale-Ryser theorem was one of the results which inspired him to become a combinatorialist.
</p>
<p>
He is not satisfied with your implementation. He had problems with the wording of the documentation, though he admitted this was only a minor issue. (For example, "dominated" should be "majorized"...) More important, he believed, was that the only construction implemented was a special one (in particular, Ryser's construction was not implemented). Without being specific, he said that more options should be available to the user, to allow for different types of features/constructions.
(For example, one could allow matrices taken from another subset of numbers, as opposed to just {0,1}.)
</p>
<p>
He was also hoping to have a construction of the graph-theoretic analog (given a possible degree sequence, construct a graph having that degree sequence). I presume though that, if you decided to implement that, you would create a separate ticket.
</p>
<p>
Thanks very much for working on this! I know this is a bit vague, so please ask questions and I will ask for more details from my colleague.
</p>
TickethivertTue, 08 Dec 2009 06:13:09 GMT
https://trac.sagemath.org/ticket/7301#comment:11
https://trac.sagemath.org/ticket/7301#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:10" title="Comment 10">wdj</a>:
</p>
<blockquote class="citation">
<p>
He is not satisfied with your implementation. He had problems with the wording of the documentation, though he admitted this was only a minor issue. (For example, "dominated" should be "majorized"...)
</p>
</blockquote>
<p>
This is clearly a question of community. Those kind of matrix problem arise in the representation theory of Symmetric Groups or in symmetric functions and in this context I've allways seen the order called dominance order. See eg: Macdonald, I. G. Symmetric Functions and Hall Polynomials, 2nd ed. Oxford, England: Oxford University Press, 1995.
</p>
<blockquote class="citation">
<p>
More important, he believed, was that the only construction implemented was a special one (in particular, Ryser's construction was not implemented). Without being specific, he said that more options should be available to the user, to allow for different types of features/constructions.
(For example, one could allow matrices taken from another subset of numbers, as opposed to just {0,1}.)
</p>
</blockquote>
<p>
Again in the theory of symmetric function and descent algebra of the symmetric group, it is useful not to give a single solution but to give all of them, without restricting et entries of the matrix to be smaller than one (i.e. any non negative integer). Moreover the order of the input is important so that I'd rather have the input to be composition rather than partition. However I don't know if in this case we need a different enumeration algorithm. You can have a look at <a class="ext-link" href="http://mupad-combinat.sourceforge.net/doc/en/combinat/integerMatrices.html"><span class="icon"></span>http://mupad-combinat.sourceforge.net/doc/en/combinat/integerMatrices.html</a>
to see what we had in MuPAD-Combinat.
</p>
<blockquote class="citation">
<p>
He was also hoping to have a construction of the graph-theoretic analog (given a possible degree sequence, construct a graph having that degree sequence). I presume though that, if you decided to implement that, you would create a separate ticket.
</p>
<p>
Thanks very much for working on this! I know this is a bit vague, so please ask questions and I will ask for more details from my colleague.
</p>
</blockquote>
TicketncohenTue, 08 Dec 2009 07:48:00 GMT
https://trac.sagemath.org/ticket/7301#comment:12
https://trac.sagemath.org/ticket/7301#comment:12
<p>
Hello everybody !!! Well, concerning the wording issue, I believe that it is correct in this case, or that at least it depends on communities, especially, when one looks at the code : "the conjugate of p2 dominates p1" is written "p2.conjugate().dominates(p1), so surely I am not the only one to give these definitions to these words :-)
</p>
<p>
The other issue seems for you to expect more than just a solution : you are both talking about the complete enumeration of the matrices corresponding to these criteria, and through Linear Programming I can olny give you a simple solution, as solvers are not that bright on the enumeration side... Would you happen to have a reference for this algorithm ? I was onnly able to find a proof to show one matrix existed, but nothing about enumerating them. I also have to admit that if writing this function was quick enough because I knew what I needed and how to use it, I may not have enough time available too look for a new ( and possibly long ) algorithm and implement it.
</p>
<p>
Do you feel like this algorithm is totally useless as it is, or could it be possible to take this function and create a ticket to move it to a enumeration problem ?
</p>
<p>
Besides, your friend was talking about "different subsets of numbers". Well, I only met this problem for 0-1 matrices and I assume your are not talking about replacing 0 by x and 1 by y... Do you mean that there is a version of this theorem working simultaneously for several types of different variables (with two partitions per type of variable, etc...) ?? This would interest me very much !!
</p>
<p>
Thank you for your interest !
</p>
<p>
Nathann
</p>
TicketwdjTue, 08 Dec 2009 13:11:48 GMT
https://trac.sagemath.org/ticket/7301#comment:13
https://trac.sagemath.org/ticket/7301#comment:13
<p>
No, I think this is a useful patch. Also, I agree that the enumeration problem is a separate ticket. I am not an expert, so to review your patch, which I think is interesting, I am told to read
</p>
<pre class="wiki">Combinatorial Matrix Theory
by Brualdi and Ryser, Chapter 6
Combinatorial Matrix Classes
By Brualdi (I think this has a whole chapter on A(R,S), the
set of (0,1)-matrices with prescribed row sums R and col sums S.
Combinatorial Mathematics
By Ryser (has a chapter on A(R,S))
</pre><p>
They shouldn't take long to read but I don't own these and will
have to make a trip to the library, which I will try to do tomorrow.
I was also told of a very interesting application of the Gale-Ryser
theorem to medical imaging (which you may already know about):
</p>
<pre class="wiki">Discrete tomography
http://en.wikipedia.org/wiki/Discrete_tomography
</pre>
TicketwdjTue, 08 Dec 2009 13:16:59 GMT
https://trac.sagemath.org/ticket/7301#comment:14
https://trac.sagemath.org/ticket/7301#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:12" title="Comment 12">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Hello everybody !!!
</p>
</blockquote>
<p>
...
</p>
<blockquote class="citation">
<p>
Besides, your friend was talking about "different subsets of numbers". Well,
I only met this problem for 0-1 matrices and I assume your are not talking about
replacing 0 by x and 1 by y... Do you mean that there is a version of this theorem
working simultaneously for several types of different variables (with two partitions
per type of variable, etc...) ?? This would interest me very much !!
</p>
</blockquote>
<p>
Yes, he indicated that a very simple modification of the construction should
allow one to construct matrices whose entries are in (say) {0,1, ..., m-1},
with give column sums and given row sums if one exists. (Here m > 1 is
a user-supplied integer which is m=2 in your current implementation.)
</p>
<blockquote class="citation">
<p>
Thank you for your interest !
</p>
<p>
Nathann
</p>
</blockquote>
TicketwdjThu, 10 Dec 2009 12:32:14 GMT
https://trac.sagemath.org/ticket/7301#comment:15
https://trac.sagemath.org/ticket/7301#comment:15
<p>
Nathann:
</p>
<p>
I have started reading these books and spoken to my colleague again. The book
</p>
<pre class="wiki">Combinatorial Mathematics
By Ryser (has a chapter on A(R,S))
</pre><p>
has a construction (due to Ryser) which is in many cases more valuable than the construction implemented (due to Gale). Moreover, the implementation of the construction assumes that the R,S have no
trailing 0's. It seems natural to assume that the user can simply remove any trailing 0's in the input sequence (I thought so myself). However, my colleague assures me that if you could implement the exact same function but allow for trailing 0's then the function would be more useful.
</p>
<p>
I need to digest the Ryser algorithm better but thought I would post this update FYI.
</p>
TicketncohenFri, 11 Dec 2009 15:19:52 GMT
https://trac.sagemath.org/ticket/7301#comment:16
https://trac.sagemath.org/ticket/7301#comment:16
<p>
I began to read the chapter six and it is indeed very interesting :-)
</p>
<p>
I did not get to the point where Ryser enumerates these matrices or speaks about multiple values beyong 0-1..
</p>
<p>
Thanks !!!
</p>
<p>
Nathann
</p>
TicketwdjSun, 13 Dec 2009 22:53:07 GMT
https://trac.sagemath.org/ticket/7301#comment:17
https://trac.sagemath.org/ticket/7301#comment:17
<p>
Please see
<a class="ext-link" href="http://sage.math.washignton.edu/home/wdj/sagefiles/gale-ryser.sage"><span class="icon"></span>http://sage.math.washignton.edu/home/wdj/sagefiles/gale-ryser.sage</a>
Hope it helps!
</p>
TicketwdjSun, 13 Dec 2009 22:53:55 GMT
https://trac.sagemath.org/ticket/7301#comment:18
https://trac.sagemath.org/ticket/7301#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:17" title="Comment 17">wdj</a>:
</p>
<blockquote class="citation">
<p>
Please see
<a class="ext-link" href="http://sage.math.washignton.edu/home/wdj/sagefiles/gale-ryser.sage"><span class="icon"></span>http://sage.math.washignton.edu/home/wdj/sagefiles/gale-ryser.sage</a>
Hope it helps!
</p>
</blockquote>
<p>
Make that <a class="ext-link" href="http://sage.math.washington.edu/home/wdj/sagefiles/gale-ryser.sage"><span class="icon"></span>http://sage.math.washington.edu/home/wdj/sagefiles/gale-ryser.sage</a>
</p>
TicketncohenMon, 14 Dec 2009 08:29:09 GMT
https://trac.sagemath.org/ticket/7301#comment:19
https://trac.sagemath.org/ticket/7301#comment:19
<p>
Excellent !!! Well, could you send your code as a patch to replace mine then, as it does not use LP ? :-)
</p>
<p>
two remarks though :
</p>
<ul><li>Perhaps "slider" could be defined inside the gale_ryser function, except if it can be useful in other parts of Sage
</li><li>The order defined on the partitions is equivalent to the the function "dominates" in the Partition class.. In my patch it was written as p2.conjugate().dominates(p1), so it may not be necessary to rewrite it
</li></ul><p>
Great work !! :-)
</p>
<p>
Nathann
</p>
TicketwdjMon, 14 Dec 2009 21:52:27 GMT
https://trac.sagemath.org/ticket/7301#comment:20
https://trac.sagemath.org/ticket/7301#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:19" title="Comment 19">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Excellent !!! Well, could you send your code as a patch to replace mine
then, as it does not use LP ? :-)
</p>
</blockquote>
<p>
I will submit my code to my colleague, who does not use Sage
or know how to program (as far as I know) but can read Python:-)
</p>
<p>
He already said that you have implemented Gale's algorithm, and
I have implemented Ryser. He does not agree that your implementation
should be replaced by mine. Perhaps we make my implementation
the default since it seems "more elementary" than yours?
</p>
<p>
More later when I receive his report.
</p>
<p>
</p>
<blockquote class="citation">
<p>
two remarks though :
</p>
<ul><li>Perhaps "slider" could be defined inside the gale_ryser function,
</li></ul><p>
except if it can be useful in other parts of Sage
</p>
<ul><li>The order defined on the partitions is equivalent to the the
</li></ul><p>
function "dominates" in the Partition class.. In my patch it was written
as p2.conjugate().dominates(p1), so it may not be necessary to rewrite it
</p>
<p>
Great work !! :-)
</p>
<p>
Nathann
</p>
</blockquote>
TicketncohenTue, 15 Dec 2009 08:27:30 GMTstatus changed
https://trac.sagemath.org/ticket/7301#comment:21
https://trac.sagemath.org/ticket/7301#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Your is both an algoorithm and a proof, which makes it more interesting than mine. Besides, yours does not require the package GLPK to be installed.. I even doubt my version could be faster so... :-)
</p>
TicketwdjThu, 17 Dec 2009 16:23:08 GMT
https://trac.sagemath.org/ticket/7301#comment:22
https://trac.sagemath.org/ticket/7301#comment:22
<p>
Just an update: My colleague agrees that my implementation is corect. There was a issue because I told him that in my opinion the
algorithm (due to Ryser) as stated in the literature was imcomplete.
(A loop was missing in the pseudocode.) He also said he proved that my version of the implementation was correct, though he did not write anything down. He also said he had some suggestions for me but did not say what they were.
</p>
<p>
Now he is grading finals but when he finishes, and I finish with my grading, I'll be able to add the two Gale-Ryser implementations together.
</p>
TicketncohenFri, 18 Dec 2009 08:09:50 GMT
https://trac.sagemath.org/ticket/7301#comment:23
https://trac.sagemath.org/ticket/7301#comment:23
<p>
Hello !! I just noticed some paper among today's publications that may interest people here :
On the number of matrices and a random matrix with prescribed row and column sums and 0–1 entries
</p>
<p>
You can get it there :
<a class="ext-link" href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6W9F-4XXNXT2-1&_user=6068170&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000016487&_version=1&_urlVersion=0&_userid=6068170&md5=431a8b6346a7a0a472ae72d9d21a5184"><span class="icon"></span>http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6W9F-4XXNXT2-1&_user=6068170&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000016487&_version=1&_urlVersion=0&_userid=6068170&md5=431a8b6346a7a0a472ae72d9d21a5184</a>
</p>
<p>
Nathann
</p>
TicketncohenFri, 18 Dec 2009 12:24:50 GMTdescription changed
https://trac.sagemath.org/ticket/7301#comment:24
https://trac.sagemath.org/ticket/7301#comment:24
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/7301?action=diff&version=24">diff</a>)
</li>
</ul>
TicketwdjSun, 27 Dec 2009 23:44:24 GMT
https://trac.sagemath.org/ticket/7301#comment:25
https://trac.sagemath.org/ticket/7301#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:6" title="Comment 6">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Now with non-square matrices ;-)
</p>
</blockquote>
<p>
What does this mean? You still have
</p>
<pre class="wiki"> if sum(p1) != sum(p2):
raise ValueError("The two partitions must sum to the same value.")
</pre>
TicketwdjMon, 28 Dec 2009 01:47:37 GMT
https://trac.sagemath.org/ticket/7301#comment:26
https://trac.sagemath.org/ticket/7301#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:25" title="Comment 25">wdj</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7301#comment:6" title="Comment 6">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Now with non-square matrices ;-)
</p>
</blockquote>
<p>
What does this mean? You still have
</p>
<pre class="wiki"> if sum(p1) != sum(p2):
raise ValueError("The two partitions must sum to the same value.")
</pre></blockquote>
<p>
Sorry, dumb question.
</p>
<p>
This is what I should have asked: The condition
</p>
<pre class="wiki"> if sum(p1) != sum(p2):
raise ValueError("The two partitions must sum to the same value.")
</pre><p>
should be replaced by a condition on p1 and the *conjugate* of p2,
shouldn't it?
</p>
TicketncohenMon, 28 Dec 2009 08:05:34 GMT
https://trac.sagemath.org/ticket/7301#comment:27
https://trac.sagemath.org/ticket/7301#comment:27
<p>
Well, the condition on the domination of p* may be fulfilled while the two partitions do not sum to the same value, which is clearly necessary, so we need the two conditions to be checked ( and summing the fastest of the two )...
</p>
<p>
well, actually I thought after out little chat that we should forget about the LP version and implement yours when you will have found the time to write it.
</p>
<p>
It's up to you ! :-)
</p>
<p>
Nathann
</p>
TicketwdjMon, 28 Dec 2009 18:53:13 GMTattachment set
https://trac.sagemath.org/ticket/7301
https://trac.sagemath.org/ticket/7301
<ul>
<li><strong>attachment</strong>
set to <em>trac_7301.2.patch</em>
</li>
</ul>
<p>
apply this patch only to 4.3.
</p>
TicketwdjMon, 28 Dec 2009 18:57:30 GMTstatus changed
https://trac.sagemath.org/ticket/7301#comment:28
https://trac.sagemath.org/ticket/7301#comment:28
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
This passes sage -testall on an ubuntu machine.
</p>
<p>
Nathann: Can you please look at this? Please check your LP code, which I modified slightly. Feel free to add a referee's patch (eg, adding an AUTHORS field, which I just noticed I forgot).
</p>
<p>
It turned out that partition was the wrong place to put it. My colleague who refereed it did not like that the integer vectors were not allowed to have trailing 0's and so that ruled out allowing gale_ryser_theorem to be a method for the Partition class.
</p>
TicketwdjWed, 06 Jan 2010 20:16:53 GMT
https://trac.sagemath.org/ticket/7301#comment:29
https://trac.sagemath.org/ticket/7301#comment:29
<p>
In reply to an email Nathann Cohen sent me:
</p>
<blockquote class="citation">
<p>
Several questions about your patch :
</p>
<ul><li>Do you think function slider01 is useful by itself in the
</li></ul><p>
integer_vector class ( and if so, under, should'nt it be renamed to be
more "explicit", if possible ? ) ? My advice is that it may be better
to move it *inside* of function fale_ryser_theorem
</p>
</blockquote>
<p>
Python has a mechanism for "private" functions like slider01, so
I renamed it _slider01. I think that is better than hiding it inside
gale_ryser_theorem. Is that okay?
</p>
<blockquote class="citation">
<ul><li>There is one commented line in is_gale_ryser
</li><li>Why don't you want to use the method Partition.dominates for
</li></ul><p>
your test in is_gale_ryser ?
</p>
</blockquote>
<p>
I think this will not work, if you want to allow trailing 0's.
Maybe I am missing something?
</p>
<blockquote class="citation">
<ul><li>Why do you say that the LP formulation is Gale's construction ?
</li></ul><p>
You mean that Gale proved this result using <a class="missing wiki">LinearProgramming?</a> ? If so,
do you have access to an electronic version of the text you are citing
? I'd be extremely interested in giving it a look... Very few
theretical results are proved using LP :-)
</p>
</blockquote>
<p>
I was told that by my colleague which is much much more of an expert on
this stuff. I have not read Gale's paper and don't know of an electronic version.
</p>
<blockquote class="citation">
<ul><li>In you docstrings you frequently use $$ for LaTeX expressions.
</li></ul><p>
As I never saw it anywhere in Sphinx, I do not know whether it works :
I always use ` instead of $. Is the documentation built correctly this
way ? I prefer your $ to my usual `, so I'm interested in the
answer....
</p>
</blockquote>
<p>
I changed all $ to '. Thanks!
</p>
<blockquote class="citation">
<ul><li>I will be running tests to compare the speed of your
</li></ul><p>
construction of the matrices... I expect your method to be much faster
than mine, perhaps something about it should be said in the docstrings
</p>
<ul><li>I do not know if it is a requirement of Sphinx, but Minh ( who I
</li></ul><p>
claim is perfection made flesh ) gave me several "needs work" because
of the way I formatted docstrings for References. What I take for
model now is the functions citing Cliquer in the graph.py file. The
document's keys are not integers but "the usual" concatenations of the
authors'initials and the year, for example [Ryser63] and [Gale57].
Besides, they appear with a trailing _ when used to cite the paper.
You are bound to find one if you look for the string "]_" in Sage's
files ( but you will definitely find them if you look for "Cliquer" in
sage/graphs/graph.py"
</p>
</blockquote>
<p>
Thank you for the reference! I think the docstrings are okay now.
</p>
<blockquote class="citation">
<ul><li>In gale_ryser_theorem the two :: after EXAMPLES should be
</li></ul><p>
removed for the generated documentation to be correct. Same thing
after References, and in slider01. The sign :: is saying to Sphinx
that what is following is a piece of Sage code. So you should only
write them when it is the case, for example after EXAMPLES in
is_gale_ryser. It may be better to generate the documentation to check
that it is visually correct :-)
</p>
</blockquote>
<p>
Done. Thanks.
</p>
<blockquote class="citation">
<p>
I will be keeping an eye on Sage-devel to be kept aware of the next
alpha release... I tried alpha0 which failed to compile on my computer
and I am at the moment without any Sage install available ( I have
sage.math in case of need, though ). I hope it will be available soon
:-))))))
</p>
</blockquote>
TicketwdjWed, 06 Jan 2010 20:18:15 GMTattachment set
https://trac.sagemath.org/ticket/7301
https://trac.sagemath.org/ticket/7301
<ul>
<li><strong>attachment</strong>
set to <em>trac_7301-referee.patch</em>
</li>
</ul>
<p>
seems to apply to 4.3* and test okay. Apply only this patch.
</p>
TicketncohenSat, 09 Jan 2010 11:18:15 GMT
https://trac.sagemath.org/ticket/7301#comment:30
https://trac.sagemath.org/ticket/7301#comment:30
<p>
I thought you could have sorted the lists, created the corresponding Partition objects, then used the dominates/conjugate methods... Well, it is not that bad a problem anyway :-)
I'll give it a look pretty soon... Sorry for the last two days, I was (against my will) kept away from internet !
</p>
<p>
Nathann
</p>
TicketncohenSun, 10 Jan 2010 08:56:18 GMTstatus changed
https://trac.sagemath.org/ticket/7301#comment:31
https://trac.sagemath.org/ticket/7301#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<blockquote class="citation">
<p>
Python has a mechanism for "private" functions like slider01, so
I renamed it _slider01. I think that is better than hiding it inside
gale_ryser_theorem. Is that okay?
</p>
</blockquote>
<p>
Well, do you think slider01 could be used by ither methods ?
</p>
<blockquote class="citation">
<p>
I think this will not work, if you want to allow trailing 0's.
Maybe I am missing something?
</p>
</blockquote>
<p>
The Gale-Ryser theorem tells you that given two partitions, there is a matrix satisfying the constraints if and only if the domination criterion is checked. Well, the point you made about trailing 0's is that you do not necessarily want the column's sums in your final matrix to be *sorted in decreasing order*. When you have a binary matrix, though, you can modify it by inverting two columns without changin the rows sums, and the columns sum still have the same set of sums. So instead of just taking care of trailing 0, the best may be to take care of non-sorted sequences, which is the general case of the theorem.
</p>
<blockquote class="citation">
<p>
I was told that by my colleague which is much much more of an expert on
this stuff. I have not read Gale's paper and don't know of an electronic version.
</p>
</blockquote>
<p>
Then the best is to :
</p>
<ul><li>Cite the reference to justify the names Gale's method and Ryser's method
</li><li>Alternatively, use algorithm="LP" instead of Gale, as we can not say more without references ( plus it gives some enlightenment as to the algorithm used and the complexity )
</li></ul><p>
Nathann
</p>
TicketncohenMon, 11 Jan 2010 11:27:24 GMTstatus changed
https://trac.sagemath.org/ticket/7301#comment:32
https://trac.sagemath.org/ticket/7301#comment:32
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
New version, after some emails exchanged :
</p>
<ul><li>The function is_gale_ryser does not apply only to "partitions"
</li></ul><p>
anymore, but to any sequence of integers. The purpose of the
Gale-Ryser theorem is to answer whether there exists a matrix with the
given row/column sums, which has nothing to do with Partitions, or
decreasings orders, or zeros, or anything else -- just positive
values. The function is_gale ryser only takes two integer lists as its
arguments, and answers yes if there exists a matrix satisfying the
constraints.
</p>
<ul><li>There is a new section ALGORITHM in is_gale_ryser
</li></ul><ul><li>Various fixes in the docstrings
</li></ul><ul><li>gale_ryser_theorem has been slightly modified to accept unordered
</li></ul><p>
sequences, and zeros. It involves marking a sorted copy of the list
without the zeros, using the algorithm you implemented, then add the
empty rows/columns and apply the reverse of the permutation applied by
the sorting.
</p>
<ul><li>Your comments made me think again about this definition inside a
</li></ul><p>
definition.... In the end I got convinced it was a very ugly way to
code and do not intend to say anything about it again :-)
</p>
<p>
Nathann
</p>
TicketncohenMon, 11 Jan 2010 11:28:16 GMTattachment set
https://trac.sagemath.org/ticket/7301
https://trac.sagemath.org/ticket/7301
<ul>
<li><strong>attachment</strong>
set to <em>trac_7301.patch</em>
</li>
</ul>
TicketncohenMon, 11 Jan 2010 11:28:49 GMT
https://trac.sagemath.org/ticket/7301#comment:33
https://trac.sagemath.org/ticket/7301#comment:33
<ul><li>THE LATEST PATCH IS NOW trac_7301.patch *
</li></ul>
TicketwdjMon, 11 Jan 2010 11:40:26 GMT
https://trac.sagemath.org/ticket/7301#comment:34
https://trac.sagemath.org/ticket/7301#comment:34
<p>
Thanks Nathann!
</p>
<p>
I'll start testing it now.
</p>
TicketwdjMon, 11 Jan 2010 15:40:42 GMTstatus changed
https://trac.sagemath.org/ticket/7301#comment:35
https://trac.sagemath.org/ticket/7301#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
applies to 4.3.a9 and 4.3 fine and passes testall except for some presumably unrelated failures on ubuntu 64bit and mac 10.6.2.
</p>
<p>
Positive review.
</p>
<p>
Thanks again Nathann!
</p>
TicketrlmWed, 13 Jan 2010 08:56:17 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/7301#comment:36
https://trac.sagemath.org/ticket/7301#comment:36
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>4.3.1.alpha2</em>
</li>
</ul>
<p>
David as Author and Nathann as Reviewer? It's not entirely clear to me, so can you fill out those slots for me?
</p>
TicketncohenWed, 13 Jan 2010 08:59:52 GMTreviewer, author set
https://trac.sagemath.org/ticket/7301#comment:37
https://trac.sagemath.org/ticket/7301#comment:37
<ul>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
<li><strong>author</strong>
set to <em>David Joyner</em>
</li>
</ul>
<p>
Considering the amount of work from David on this function, it seems fitting :-)
</p>
TicketmvnguWed, 13 Jan 2010 19:58:53 GMTmerged changed
https://trac.sagemath.org/ticket/7301#comment:38
https://trac.sagemath.org/ticket/7301#comment:38
<ul>
<li><strong>merged</strong>
changed from <em>4.3.1.alpha2</em> to <em>sage-4.3.1.alpha2</em>
</li>
</ul>
Ticket