Opened 7 years ago
Closed 6 years ago
#10347 closed enhancement (fixed)
Implementation of is_(skew_)symmetrizable for matrices
Reported by:  stumpc5  Owned by:  tbd 

Priority:  major  Milestone:  sage5.0 
Component:  combinatorics  Keywords:  symmetrizable matrix 
Cc:  franco.saliola@…, hthomas@…  Merged in:  sage5.0.beta5 
Authors:  Christian Stump  Reviewers:  Hugh Thomas 
Report Upstream:  N/A  Work issues:  
Branch:  Commit:  
Dependencies:  Stopgaps: 
Description
matrices are lacking methods for testing (skew)symmetrizability. Those methods are needed for the cluster algebra and quiver package, see Ticket #10298.
Attachments (1)
Change History (35)
comment:1 Changed 7 years ago by
 Component changed from PLEASE CHANGE to combinatorics
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
comment:3 followup: ↓ 4 Changed 7 years ago by
You should modify the header of your patch : add something like
#10347 Implementation of is_(skew_)symmetrizable for matrices
Then the buildbot will be more happy.
comment:4 in reply to: ↑ 3 ; followup: ↓ 7 Changed 7 years ago by
comment:5 followup: ↓ 6 Changed 7 years ago by
 Reviewers set to hthomas@unb.ca
 Status changed from needs_review to needs_work

sage: M=matrix([[0,6],[0,0]]) sage: M.is_symmetrizable(return_diag=true) [1, 1]
This M is not symmetrizable, and the returned diagonal matrix doesn't symmetrize it.

sage: M=matrix([2]) sage: M.is_symmetrizable() False
The code is checking that the diagonal entries are all zero even when testing for symmetrizability.
 Zelevinsky spells his name with a final "y".
comment:6 in reply to: ↑ 5 Changed 7 years ago by
 Status changed from needs_work to needs_review
Replying to hthomas:
Hi Hugh,
Thanks for testing the code!
sage: M=matrix([[0,6],[0,0]]) sage: M.is_symmetrizable(return_diag=true) [1, 1]This M is not symmetrizable, and the returned diagonal matrix doesn't symmetrize it.
The problem here was that the algorithm checks conditions on columns (in _travel_column
), but didn't check if an entry
i,j
is zero, that than j,i
is zero as well. So the bottom left zero was read, but no check was made on the top right nonzero...
sage: M=matrix([2]) sage: M.is_symmetrizable() FalseThe code is checking that the diagonal entries are all zero even when testing for symmetrizability.
I moved this piece of code, so it is only used for skewsymmetrizable matrices.
 Zelevinsky spells his name with a final "y".
:)
Best, Christian
comment:7 in reply to: ↑ 4 Changed 7 years ago by
comment:8 followup: ↓ 9 Changed 7 years ago by
Hello Christian,
I guess the header is still bad. What did you do ? It seems that you modified the first line, and this is not good ! By hand ???
I think you need only to use "sage hg qrefresh e" and to give a commit message in the editor that should open. Compare for instance with the header of #11311. But I do not feel very competent on the build bot, alas.. Maybe one should ask the question on the mailinglist.
comment:9 in reply to: ↑ 8 Changed 7 years ago by
Replying to chapoton:
I guess the header is still bad. What did you do ? It seems that you modified the first line, and this is not good ! By hand ???
I think you need only to use "sage hg qrefresh e" and to give a commit message in the editor that should open. Compare for instance with the header of #11311. But I do not feel very competent on the build bot, alas.. Maybe one should ask the question on the mailinglist.
I did that now  the only difference to the first version I sent yesterday is that there is no space between # and the number. Maybe that was my mistake...
Thanks for rechecking!
comment:10 Changed 7 years ago by
 Cc hthomas@… added
 Reviewers changed from hthomas@unb.ca to Hugh Thomas
If I understand it right, the test failures are not related to the patch...
comment:11 followup: ↓ 13 Changed 7 years ago by
Hi Christian!
Below are all my comments. The first one is something which should be fixed (but is trivial). For the others, I don't know if any change needs to be made. Suggestions occurred to me, but perhaps you had good reasons for doing things as you did, and in any case, it doesn't seem to me that these are likely to be routines that are timecritical. I am perhaps overthinking this process, because of its being the first time I am reviewing a patch.
 The description of the return value for is_skew_symmetrizable, is_skew_symmetric, and _check_symmetrizability when return_diag is true says that it returns the diagonal matrix, when in fact, it returns the diagonal of the diagonal matrix. (I like the output as is, I just think the documentation should change.)
 In _travel_column, technically, I think it makes more sense to check that i isn't in dict before getting self_ik and self_ki, and testing whether or not bool(self_ik) and bool(self_ki) agree  if i is in dict, this has already been checked.
 When return_diag is set, I don't see the point of saying [ d[i] for i in sorted( d.keys() ) ]. Why not just say [ d[i] for i in range( self._ncols ) ]?
 If the entries in the input matrix aren't in an integral domain, things will get ugly. I realize that's far from the intended use case. What's the protocol for something like that? Maybe just that the docstring should say that the input is a matrix in an integral domain? Or is it even necessary to do anything at all?
 I don't really like the following, but, again, it's far from the intended use case (and it's not the fault of the code here):
sage: R.<x>=PolynomialRing(QQ) sage: M=matrix([[1,x],[x,1]]) sage: M.is_symmetrizable(positive=true) True sage: M.is_symmetrizable(positive=true, return_diag=true) [1, 1]
I am happy to give a positive review as soon as you fix at least the first point above (assuming the tests, which are running on my computer right now, pass). Or should I wait until the patchbot is also happy? Unless you think someone else should also review it, since I'm pretty inexperienced.
comment:12 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:13 in reply to: ↑ 11 Changed 7 years ago by
 Status changed from needs_work to needs_review
Replying to hthomas:
Hi Hugh  thanks for your comments!
 The description of the return value for is_skew_symmetrizable, is_skew_symmetric, and _check_symmetrizability when return_diag is true says that it returns the diagonal matrix, when in fact, it returns the diagonal of the diagonal matrix. (I like the output as is, I just think the documentation should change.)
done.
 In _travel_column, technically, I think it makes more sense to check that i isn't in dict before getting self_ik and self_ki, and testing whether or not bool(self_ik) and bool(self_ki) agree  if i is in dict, this has already been checked.
done.
 When return_diag is set, I don't see the point of saying [ d[i] for i in sorted( d.keys() ) ]. Why not just say [ d[i] for i in range( self._ncols ) ]?
done.
 If the entries in the input matrix aren't in an integral domain, things will get ugly. I realize that's far from the intended use case. What's the protocol for something like that? Maybe just that the docstring should say that the input is a matrix in an integral domain? Or is it even necessary to do anything at all?
I added a sentence saying that the input matrix should be over an integral domain (we actually need to be able to invert all nonzero entries we see in the matrix  but the methods are not meant to be used like that and no one is going to do so I guess). Also I added that the base ring must be ordered if positive=True
.
 I don't really like the following, but, again, it's far from the intended use case
There are many methods which do only make sense in certain contexts, I don't really know how to avoid that...
Or should I wait until the patchbot is also happy?
I hope it is now...
Unless you think someone else should also review it, since I'm pretty inexperienced.
If someone wanna have a look that's fine, but you can also give it a positive review if no one is going to do so.
Thanks again! Christian
comment:14 Changed 7 years ago by
 Status changed from needs_review to positive_review
Hi Christian
Okay, looks good!
cheers,
Hugh
comment:15 followup: ↓ 16 Changed 7 years ago by
Hi Christian
I was reading a bit more about what referees are supposed to do, and one thing is that they should be enforcing the convention that every function, even those beginning with an underscore, should have examples showing it in action. (This is according to William Stein's blog post on refereeing.) This isn't true of _travel_column. Is this something that should be fixed, or should I not be taking what William Stein writes literally in this case?
cheers,
Hugh
comment:16 in reply to: ↑ 15 Changed 7 years ago by
Replying to hthomas:
Hi Hugh,
I was reading a bit more about what referees are supposed to do, and one thing is that they should be enforcing the convention that every function, even those beginning with an underscore, should have examples showing it in action. (This is according to William Stein's blog post on refereeing.) This isn't true of _travel_column. Is this something that should be fixed, or should I not be taking what William Stein writes literally in this case?
I don't really know  I added an example, but as this function is not used anywhere but inside _check_symm..., the example doesn't give any inside to the reader. On the other hand, if someone brakes this function for whatever reason, then the doctest catches this. That's a huge plus!
Best, Christian
comment:17 Changed 7 years ago by
 Status changed from positive_review to needs_work
Hi Hugh,
what do you think about always forcing the entries in the diagonal matrix D to be positive? Otherwise, people might get confused as without this positivity condition the notion does not appear in the literature (does it?).
Best, Christian
comment:18 followup: ↓ 19 Changed 7 years ago by
Hi Christian
Yeah, on reflection, I think that's a good idea. I'm pretty sure it's part of the standard definition of symmetrizable, too. (Though I just checked, and wikipedia doesn't think so.) Maybe you should just change the default setting of positive?
cheers,
Hugh
comment:19 in reply to: ↑ 18 Changed 7 years ago by
 Status changed from needs_work to needs_review
Replying to hthomas:
Yeah, on reflection, I think that's a good idea. I'm pretty sure it's part of the standard definition of symmetrizable, too. (Though I just checked, and wikipedia doesn't think so.) Maybe you should just change the default setting of positive?
done!
Now as you write it, I remember that I checked the wiki page when I first wrote the method and saw that positivity is not assumed there. Maybe there is another context where symmetrizability is used. (Actually, our algorithm only works for integral domains with certain elements being invertible, while the general definition of symmetrizability doesn't assume that.)
Best, Christian
comment:20 Changed 7 years ago by
 Milestone changed from sage4.7.1 to sage4.7.2
comment:21 Changed 6 years ago by
Fixed an issue with travel_column as described in #12408
comment:22 Changed 6 years ago by
The buildbot was unhappy because of some trailing whitespace, which I removed.
comment:23 Changed 6 years ago by
I think the format of the patch might be correct now! (I didn't know I should export it.)
comment:24 Changed 6 years ago by
The docstrings for is_symmetrizable and is_skewsymmetrizable said that they took a boolean argument "skew" which is not true. I have corrected this in my patch.
comment:25 Changed 6 years ago by
Hi Hugh,
do you mind if I fold your 3 lines into the first patch? Do you see other issues, or is the patch ready to go soon?
Thanks, Christian
comment:26 followup: ↓ 27 Changed 6 years ago by
Hi Christian
I don't expect to find anything else, but on the other hand, I am still looking. I will try to be fully done in a few days. So it's up to you if you'd like to fold the patch in now.
I did just notice something else, though. In the examples for "is_skew_symmetrizable", one of them actually calls is_symmetrizable, not is_skew_symmetrizable". This seems harmless but odd.
cheers,
Hugh
comment:27 in reply to: ↑ 26 Changed 6 years ago by
Replying to hthomas:
Just put whatever you find in your patch, and we then fold them when you are done...
Best, Christian
comment:28 followup: ↓ 29 Changed 6 years ago by
Hi Christian
I made a couple of very minor changes to documentation.
This is a positive review provided the patchbot is okay with it.
I have confused matters by uploading a second patch. I meant it to replace my other patch. I don't see how to remove attached patches, or I would fix this. (Nor could I easily find an explanation in the documentation.) How do you do it?
cheers,
Hugh
comment:29 in reply to: ↑ 28 Changed 6 years ago by
Replying to hthomas:
I have confused matters by uploading a second patch. I meant it to replace my other patch. I don't see how to remove attached patches, or I would fix this. (Nor could I easily find an explanation in the documentation.) How do you do it?
Hi Hugh, it is not possible to delete files except for admins (as this is not reversible). I can do it, so let me know which files to delete.
Best, Christian
comment:30 followup: ↓ 31 Changed 6 years ago by
Hi Christian
Thanks for the clarification.
The patch I added most recently (ht.2.patch) should be folded in with your patch (if you're happy with the changes, all minor). The older patch of mine (ht.patch) can be thrown out. (The changes in it are included also in ht.2.patch.)
Thanks!
cheers,
Hugh
Changed 6 years ago by
contains matrix methods is_symmetrizable, is_skew_symmetrizable, _check_symmetrizability, _travel_column
comment:31 in reply to: ↑ 30 Changed 6 years ago by
Replying to hthomas:
Thanks Hugh for the work  I folded both patches and add you as an author (which doesn't exclude you from being the reviewer). We might make it into 5.0 if you set the positive review.
Best, Christian
comment:32 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:33 Changed 6 years ago by
Hi Christian
I think I'm happier not claiming to have been an author  I think everything I did is appropriately described by saying that I was the reviewer.
cheers,
Hugh
comment:34 Changed 6 years ago by
 Merged in set to sage5.0.beta5
 Resolution set to fixed
 Status changed from positive_review to closed
Apply only trac_10347_is_skew_symmetrizablecs.patch