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: sage-5.0
Component: combinatorics Keywords: symmetrizable matrix
Cc: franco.saliola@…, hthomas@… Merged in: sage-5.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)

trac_10347_is_skew_symmetrizable-cs.patch (10.0 KB) - added by stumpc5 6 years ago.
contains matrix methods is_symmetrizable, is_skew_symmetrizable, _check_symmetrizability, _travel_column

Download all attachments as: .zip

Change History (35)

comment:1 Changed 7 years ago by stumpc5

  • Component changed from PLEASE CHANGE to combinatorics
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by stumpc5

Apply only trac_10347_is_skew_symmetrizable-cs.patch

comment:3 follow-up: Changed 7 years ago by chapoton

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 ; follow-up: Changed 7 years ago by stumpc5

Replying to chapoton:

Then the buildbot will be more happy.

done, thanks.

comment:5 follow-up: Changed 7 years ago by hthomas

  • 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 stumpc5

  • 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 non-zero...

  • 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.

I moved this piece of code, so it is only used for skew-symmetrizable matrices.

  • Zelevinsky spells his name with a final "y".

:-)

Best, Christian

comment:7 in reply to: ↑ 4 Changed 7 years ago by stumpc5

Replying to stumpc5:

Replying to chapoton:

Then the buildbot will be more happy.

done, thanks.

A second try -- hopefully, the buildbot accepts it this time...

comment:8 follow-up: Changed 7 years ago by chapoton

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 mailing-list.

comment:9 in reply to: ↑ 8 Changed 7 years ago by stumpc5

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 mailing-list.

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 stumpc5

  • 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 follow-up: Changed 7 years ago by hthomas

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 time-critical. I am perhaps over-thinking 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 hthomas

  • Status changed from needs_review to needs_work

comment:13 in reply to: ↑ 11 Changed 7 years ago by stumpc5

  • 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 hthomas

  • Status changed from needs_review to positive_review

Hi Christian--

Okay, looks good!

cheers,

Hugh

comment:15 follow-up: Changed 7 years ago by hthomas

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 stumpc5

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 stumpc5

  • 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 follow-up: Changed 7 years ago by hthomas

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 stumpc5

  • 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 stumpc5

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:21 Changed 6 years ago by stumpc5

Fixed an issue with travel_column as described in #12408

comment:22 Changed 6 years ago by hthomas

The buildbot was unhappy because of some trailing whitespace, which I removed.

comment:23 Changed 6 years ago by hthomas

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 hthomas

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 stumpc5

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 follow-up: Changed 6 years ago by hthomas

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 stumpc5

Replying to hthomas:

Just put whatever you find in your patch, and we then fold them when you are done...

Best, Christian

comment:28 follow-up: Changed 6 years ago by hthomas

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 stumpc5

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 follow-up: Changed 6 years ago by hthomas

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 stumpc5

contains matrix methods is_symmetrizable, is_skew_symmetrizable, _check_symmetrizability, _travel_column

comment:31 in reply to: ↑ 30 Changed 6 years ago by stumpc5

  • Authors changed from Christian Stump to Christian Stump, Hugh Thomas

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 hthomas

  • Status changed from needs_review to positive_review

comment:33 Changed 6 years ago by hthomas

  • Authors changed from Christian Stump, Hugh Thomas to Christian Stump

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 jdemeyer

  • Merged in set to sage-5.0.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.