Implementation of is_(skew_)symmetrizable for matrices

[stumpc5]

matrices are lacking methods for testing (skew-)symmetrizability. Those methods are needed for the cluster algebra and quiver package, see Ticket #10298.

[stumpc5]

Apply only trac_10347_is_skew_symmetrizable-cs.patch

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

[stumpc5]

Replying to chapoton:

Then the buildbot will be more happy.

done, thanks.

[hthomas]

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

[stumpc5]

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

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

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

[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!

[stumpc5]

If I understand it right, the test failures are not related to the patch...

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

[stumpc5]

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

[hthomas]

Hi Christian--

Okay, looks good!

cheers,

Hugh

[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

[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

[stumpc5]

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

[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

[stumpc5]

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

[stumpc5]

Fixed an issue with travel_column as described in #12408

[hthomas]

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

[hthomas]

I think the format of the patch might be correct now! (I didn't know I should export it.)

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

[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

[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

[stumpc5]

Replying to hthomas:

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

Best, Christian

[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

[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

[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

[stumpc5]

contains matrix methods is_symmetrizable, is_skew_symmetrizable, _check_symmetrizability, _travel_column

[stumpc5]

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

[hthomas]

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