Helper functions for polynomial matrices

[Vincent Neiger]

Functions:

• degree,
• row_degrees, column_degrees,
• row_pivots, column_pivots,
• degree_matrix,
• row_leading_matrix, column_leading_matrix,
• is_popov (row/column),
• is_reduced (row/column).

[Vincent Neiger]

Pushed the first function. Not ready for review.

---

New commits:

​ec172a4

degree matrix function working

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4aa4338

improved degree_matrix documentation

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​10be03d

function and doc degree of a matrix

[Vincent Neiger]

Cleaned documentation for the (shifted) degree matrix, and wrote function/doc for degree of a matrix. Not ready for review.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0fd8340	function and doc for column degree and row degree
​68de063	function and documentation for leading matrix, row wise and column wise

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​af59287

function and doc for is_reduced

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​baab67f	small correction for degree: case of empty matrix
​96c7e5a	testing corner cases with <<empty>> matrices
​205e188	is_popov and is_ordered_weak_popov are in good state now; missing examples in the latter

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c427947

class document, and cleaner documentation for methods

[Johan Rosenkilde]

The ticket is coming along very nicely. Some preliminary comments.

• In docs, prefer "Return the ..." over "Returns the ...". I personally prefer "this matrix" over the less specific "the matrix" when talking about self. I would even use this polynomial matrix if I need to set it apart from e.g. an integer or scalar matrix.

• degree, doc: "If the matrix is zero, this is a nonnegative integer" - do you mean "this is -\infty"?.

• degree: why does the 0x0 matrix have degree None? Such a matrix has e.g. rank 0 and characteristic polynomial 1. Similar question for row-degree.

• degree_matrix: I would prefer that you add a parameter check that the shift is a list of the right length. One could interpret the doc text as expecting the shift to be a vector of integers - is this a problem?

• degree_matrix, examples: a long line needs wrapping.

• About references: we don't have as high standards wrt. completeness of referencing all previous history as in journal publications. In fact, for a concept like row_degree I think Sage rarely has references - they are mostly used for algorithms. So I think 1 reference is plenty sufficient. I like your intention of drawing the reader to the related concept of defect but this maybe has most value if properly explained?

In any case, references have to be entered in the special file $SAGE/src/doc/en/reference/references/index.rst and referred to using the syntax [Kai80].

• leading_matrix, doc: Could you make a shorter explanation for the unshifted case first? I then prefer to define LM_s(M) := LM(M diag(x^{s_1},...,x^{s_n}) which I find easier to parse.

• leading_matrix: I don't think the self[i,j] == 0 or requirements are necessary in each of the four cases.

• is_reduced doc: first line, consider putting parentheses around "shifted". And later: "Equivalently, when considering ... left-multiplying", add "(resp. right-multiplying)".

• pivot: should the pivot degrees only be returned if the user wishes it (by setting a flag return_degree=False)?

• is_ordered_weak_popov: should this be merged with is_weak_popov by giving the latter an optional flag ordered?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7e0f5e8	added examples for is_ordered_weak_popov
​fff979b	Johan's comments and cleaner doc

[Vincent Neiger]

Thank you for your numerous comments.

All that is not commented below was taken into account in the last revision.

Replying to jsrn:

• degree: why does the 0x0 matrix have degree None? Such a matrix has e.g. rank 0 and characteristic polynomial 1. Similar question for row-degree.

This is a good question and I have no answer. Another choice would be -1, but so far I see no reason to prefer one or the other. Do you?

• degree_matrix: I would prefer that you add a parameter check that the shift is a list of the right length.

I was hesitating about such a parameter check. If we put one here, then we should do it for every method involving a shift, right?

One could interpret the doc text as expecting the shift to be a vector of integers - is this a problem?

I don't think this is a problem (if I understand well your question): we can input a vector (1,2,3) or a list [1,2,3], both will work.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3d5797d	shifts as list/vector: ok now
​817b81c	todo

[Johan Rosenkilde]

Hi, looking better and better :-)

• leading_matrix, perhaps elsewhere: Don't put parentheses around the condition of an if-statement
• Prefer a is None compared to a == None.
• Class doc: forget :meth: for leading_matrix reference.

Things we discussed face2face:

• pivot -> leading_positions
• add order_by_degree and order_by_leading_position
• Raise ValueError? on zero-row or zero-column matrices
• Check lengths of shifts everywhere

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fe37dee	row_reduced --> reduced, deprecation warning
​91db615	check shift length
​0545723	check shift length
​e3064b0	pivot index --> leading positions
​ee2f999	some small fixes
​e7d646f	pivot index --> leading positions
​660ab43	degrees and leading positions for empty matrices

[Johan Rosenkilde]

Changed some names in the description, as discussed f2f. The code still needs to be updated.

[Johan Rosenkilde]

Let's go plural.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c6da217	plural for row degree / column degree
​72fe310	now is_reduced accepts zero rows/columns

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b5aa3da	is_weak_popov now accepts zero rows / columns
​8064d7b	is_popov now accepts zero rows + option for up-to-permutation test
​489344a	remove old code
​7f6e36e	small code simplification

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3a336c9	working on is_hermite
​a266d99	now, in ordered weak Popov and in Popov the zero rows must appear at the end (bottom if row-wise, right-hand side if column-wise)
​dd920d4	is_hermite now works, it simply calls is_popov with the right shift
​92356cb	is_hermite cleaned, lower_echelon option correct now
​de58683	add test to support empty matrices in is_{hermite,popov,weak_popov,reduced}
​9ed9b40	added some SEEALSO blocks

[Johan Rosenkilde]

Author forgot to set needs_review (but said so in private conversation)

---

Last 10 new commits:

​c44832e	Fixed some doc-tests
​5d56351	Classical Reed-Solomon codes
​19ba6f5	Fixed small doc-test failure
​37515a0	Merge branch 'u/vneiger/23619_polmat_helper' of git://trac.sagemath.org/sage into 23619_polmat_helper
​c67c7a3	Spaces around operators
​805ecd7	Plural row/col degrees in various doc text
​bb7f3a6	Fixed a SEEALSO
​03cf1a8	Simplified some logic in is_reduced
​3a03af4	Improved reduced_form doc to conform to the rest of the file. A few other small fixes
​7af4cca	Improved doc and examples of weak_popov_form

[Johan Rosenkilde]

Hi Vincent,

I've carefully gone over the entire file now and I like it - we're almost there. I took the liberty to implement directly some smaller fixes, and also to use this ticket to include some improvements to existing docs and examples in that file. Please review these changes.

As to your changes, I'm ready to green light everything except for the following comments:

• What's the point of is_empty_popov? Why not just implement the empty case in is_*_popov? If you only have the method for this reason, then the function shoulde be hidden (i.e. start with an underscore). Besides, I find the convention strange: a 2*n matrix can be in Popov form for any n>0 (if n=1 then the second row must be zero for it to be in Popov form). Why disallow 2*0 matrices to be in Popov form?

• I'm thinking that the is_hermite argument lower_echelon is overkill. I'm not firm on this point since you already implemented it, but is it really useful? Just because not all papers ever agreed on this minor point doesn't mean we should support it everywhere. If the user really wants to, he can easily flip all the rows himself by M.permute_rows(Permutation(range(M.nrows(),0,-1))).

• If you keep lower_echelon=True, there should be an example using it where the answer is True.

Also, I like your fix for allowing other row orderings in is_popov!

Best, Johan

[Johan Rosenkilde]

Oh yeah, I also merged in 24640 since I was worried about a conflict. There seems to have been no conflict with 24640 itself, so technically, I should remove that merge, but there was a conflict with some other parts of rebasing this patch to a newer version of Sage.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​129aa97	Merge commit '9ed9b40' into 23619_polmat_helper_nodep
​7b51228	Plural row/col degrees in various doc text
​b70bb38	Fixed a SEEALSO
​376759f	Simplified some logic in is_reduced
​0a14228	Improved reduced_form doc to conform to the rest of the file. A few other small fixes
​4830af1	Improved doc and examples of weak_popov_form

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9eaf1f5

Spaces around operators

[Johan Rosenkilde]

Yay to rewriting history! So I decided to untangle the dependency on #24640 after all, and this was not difficult at all (make new branch off develop, merge in your last commit, cherry-pick my commits). Except that I screwed up and cherry-picked one commit too little (doing git cherry-pick <commitA>..<commitB> does not include <commitA>!) and so ended up adding that after the others. Then git push --force and all is well :-) Now we also know that the patch merges on the latest develop.

[Vincent Neiger]

Oops, I just did "git trac push" just before reading your email. I hope I did not break everything...

---

Last 10 new commits:

​5d56351	Classical Reed-Solomon codes
​19ba6f5	Fixed small doc-test failure
​37515a0	Merge branch 'u/vneiger/23619_polmat_helper' of git://trac.sagemath.org/sage into 23619_polmat_helper
​c67c7a3	Spaces around operators
​805ecd7	Plural row/col degrees in various doc text
​bb7f3a6	Fixed a SEEALSO
​03cf1a8	Simplified some logic in is_reduced
​3a03af4	Improved reduced_form doc to conform to the rest of the file. A few other small fixes
​7af4cca	Improved doc and examples of weak_popov_form
​cfac2e4	some fixes + is_empty_popov now hidden

[Vincent Neiger]

Replying to jsrn:

Hi Vincent,

I've carefully gone over the entire file now and I like it - we're almost there. I took the liberty to implement directly some smaller fixes, and also to use this ticket to include some improvements to existing docs and examples in that file. Please review these changes.

I have checked all changes in the diff, and everything is good. Thank you for fixing this previously existing code (I was unsure if that needed a separate ticket... still learning :-) ).

• What's the point of is_empty_popov? Why not just implement the empty case in is_*_popov? If you only have the method for this reason, then the function shoulde be hidden (i.e. start with an underscore). Besides, I find the convention strange: a 2*n matrix can be in Popov form for any n>0 (if n=1 then the second row must be zero for it to be in Popov form). Why disallow 2*0 matrices to be in Popov form?

It is indeed used in is_reduced, is_weak_popov, and is_popov. So I wrote it only once. Now it is hidden (and it does not check anymore that the input is indeed empty). You are right that there were problems with some matrices; to make it behave like other is_* functions, I added a parameter "include_zero_vectors" (True by default, in which case any empty matrix is in shifted Popov form for any shift) and updated the code to reflect this. When one does not want zero rows/vectors in Popov forms, I still think that we should require the number of rows to be at most the number of columns even when the matrix is empty.

• I'm thinking that the is_hermite argument lower_echelon is overkill. I'm not firm on this point since you already implemented it, but is it really useful? Just because not all papers ever agreed on this minor point doesn't mean we should support it everywhere. If the user really wants to, he can easily flip all the rows himself by M.permute_rows(Permutation(range(M.nrows(),0,-1))).

It is in fact more complicated than this; it is not just a permutation, the two forms are actually quite different and can have very different degree profiles. Since both are in the literature and both seem to be used frequently, I really prefer keeping this optional argument.

• If you keep lower_echelon=True, there should be an example using it where the answer is True.

Done!

This made me realise that there is a bug with zero rows in is_weak_popov. I will fix this today.

Best,

Vincent

[Johan Rosenkilde]

Hi Vincent,

I think you did just bulldoze over my git magic. I'll try to redo it later, but I don't have time right now.

• What's the point of is_empty_popov? Why not just implement the empty case in is_*_popov? If you only have the method for this reason, then the function shoulde be hidden (i.e. start with an underscore). Besides, I find the convention strange: a 2*n matrix can be in Popov form for any n>0 (if n=1 then the second row must be zero for it to be in Popov form). Why disallow 2*0 matrices to be in Popov form?

It is indeed used in is_reduced, is_weak_popov, and is_popov. So I wrote it only once. Now it is hidden (and it does not check anymore that the input is indeed empty). You are right that there were problems with some matrices; to make it behave like other is_* functions, I added a parameter "include_zero_vectors" (True by default, in which case any empty matrix is in shifted Popov form for any shift) and updated the code to reflect this. When one does not want zero rows/vectors in Popov forms, I still think that we should require the number of rows to be at most the number of columns even when the matrix is empty.

OK, I can agree to this.

• I'm thinking that the is_hermite argument lower_echelon is overkill. I'm not firm on this point since you already implemented it, but is it really useful? Just because not all papers ever agreed on this minor point doesn't mean we should support it everywhere. If the user really wants to, he can easily flip all the rows himself by M.permute_rows(Permutation(range(M.nrows(),0,-1))).

It is in fact more complicated than this; it is not just a permutation, the two forms are actually quite different and can have very different degree profiles. Since both are in the literature and both seem to be used frequently, I really prefer keeping this optional argument.

Ah, yes I see I was mistaken. But isn't it true that H is in upper-echelon Hermite form exactly when JHJ is in lower-echelon Hermite form, where J is the anti-diagonal unit matrix (i.e. JHJ is H with both columns and rows reversed). Equivalently, the upper-echelon Hermite form of M should be JHJ where H is the lower-echelon Hermite form of JMJ.

Note also that our current hermite_form algorithm does not support computing the upper-echelon variant. Are you planning to add that? (even if you're not, I'm not against keeping lower_echelon in is_hermite).

Best, Johan

[Vincent Neiger]

Replying to jsrn:

Hi Vincent,

I think you did just bulldoze over my git magic. I'll try to redo it later, but I don't have time right now.

Argh... sorry.

isn't it true that H is in upper-echelon Hermite form exactly when JHJ is in lower-echelon Hermite form, where J is the anti-diagonal unit matrix (i.e. JHJ is H with both columns and rows reversed). Equivalently, the upper-echelon Hermite form of M should be JHJ where H is the lower-echelon Hermite form of JMJ.

Yes, I agree, this seems correct.

Note also that our current hermite_form algorithm does not support computing the upper-echelon variant. Are you planning to add that? (even if you're not, I'm not against keeping lower_echelon in is_hermite).

In fact the current code computes the upper echelon and not the lower, and I am among the ones preferring the lower, this is what led me to put this option in is_hermite despite the existing code.

So I am considering adding support for lower echelon in hermite_form, simply by making sure your remark above is correct and using it in the straightforward way (if lower echelon, then start by replacing M by JMJ, run the current code, and then finish by replacing H by JHJ). Does this sound ok?

Best, Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a5d4b47

fixed bug in is_weak_popov

[Vincent Neiger]

Ok, the bug is fixed. All seems to work fine now.

There could be a line of work around making previously existing functions work with options in a more unified way: include-zero-vectors and row-wise options for Hermite form, reduced form, weak Popov form, lower-echelon option for Hermite form, etc.

In my opinion this could be a separate ticket about these computations of matrix forms, where we should also consider implementing Popov form computation (probably with Mulders-Storjohann algorithm, starting from a weak Popov matrix).

What do you think?

Best, -- Vincent

[Romain Lebreton]

Hey Vincent,

I have started to review your code and I want to give you my first comment since I don't know when I will have time to continue the review. First of all, your code is really nice to read, so thank you for your contribution

General Comments

Add your name as author ?

You should have created multiple small tickets, possibly one by small group of functions

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

Tests fail (see Continuous integration) in src/sage/coding/ because of deprecated row_reduced_form

sage -t src/sage/coding/extended_code.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/gs_decoder.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/interpolation.py  # 1 doctest failed
sage -t src/sage/coding/bch.py  # 1 doctest failed

_check_shift_dimension

What is the point of argument 'shifts' being optional ? If you check shifts dimension, you should provide shifts.

column_degrees

You should have a code closer to row_degrees, which is cleaner. In particular, please remove if self.nrows() == 0: ... on line 354

leading_matrix

Suggestion: I am not sure that the part "Going over the Laurent polynomials" is useful to understand the behavior of the function. It is important scientifically to manipulate leading matrices, in particular for understanding the leading matrix of the product, but not so much for its definition.

reduced_form

You should add documentation about option "row_wise"

Best, Romain

[Vincent Delecroix]

Side remark: error message should start with lower case and not have punctuation similarly to

sage: l = []
sage: l[1]
Traceback (most recent call last):
...
IndexError: list index out of range

[Romain Lebreton]

Hey Vincent,

here is the second and final part of my review. I really like your contribution and I appreciate the effort that you have put into it !

Here are my comments suggestions

_is_empty_popov

l501

if not include_zero_vectors:
   return True

should be

if include_zero_vectors:
   return True

Also your tests should capture this behavior.

is_reduced

• l518 with $k \leq n$ -> with $k \leq m$ ?
• l525 with $k \leq m$ -> with $k \leq n$ ?

• l578 return self._is_empty_popov(row_wise)

I'm not able to tell if it is correct or if it should be return self._is_empty_popov(row_wise,include_zero_vectors)

• l609 "The definition is similar if working column-wise"

It would be nice to mention here too that "we choose bottommost entry in case of degree equality"

leading_positions

• l594 "(also known as the pivot index)" -> pivot indices

• l594 pivot degree -> pivot degrees

• idem l772

• l602 "Then the pivot degree of the vector is the degree $\deg(p_j)$"

Is it really $\deg(p_j)$ or should it be $\deg(p_j) + s_j$ instead ?

is_weak_popov

l772 pivot index -> pivot indices

is_popov

l957 not up_to_permutation,

I don't understand why you negate up_to_permutation here. Can you please check ?

is_hermite

Maybe copy the sentence at l74 "In fact, if $d$ is the largest degree ..." relating Popov and Hermite at the end of the comments of the function

Is the "+ 1" in lines 1071 and 1073 really necessary ?

weak_popov_form

l1096 If this is True

Is there a good reason to not implement option row_wise here ?

reduced_form

Should add documentation about option "row_wise"

l1291 If this **is** ``True``

Best,

Romain

[Vincent Neiger]

Hi Romain,

Thank you very much for your careful review. I have worked on correcting/updating the code, and here are below some answers to specific points.

Replying to gh-romainlebreton:

General Comments

Add your name as author ?

Done.

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

I am not familiar with this: this was already imported in this file prior to that ticket. To avoid breaking something that others wrote, I prefer leaving it as is... but please advise me if you are certain of a solution to make this point cleaner.

Tests fail (see Continuous integration) in src/sage/coding/ because of deprecated row_reduced_form

sage -t src/sage/coding/extended_code.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/gs_decoder.py  # 1 doctest failed
sage -t src/sage/coding/guruswami_sudan/interpolation.py  # 1 doctest failed
sage -t src/sage/coding/bch.py  # 1 doctest failed

I have modified these files to use the new function name, thank you.

_check_shift_dimension

What is the point of argument 'shifts' being optional ? If you check shifts dimension, you should provide shifts.

This was corrected, thank you. Now, 'shifts' must be given, and is still allowed to be 'None' because this happens to be convenient in other functions.

column_degrees

You should have a code closer to row_degrees, which is cleaner. In particular, please remove if self.nrows() == 0: ... on line 354

This has been done. Thank you.

leading_matrix

Suggestion: I am not sure that the part "Going over the Laurent polynomials" is useful to understand the behavior of the function. It is important scientifically to manipulate leading matrices, in particular for understanding the leading matrix of the product, but not so much for its definition.

Thank you for the suggestion; I agree that this is not essential here and does not add much to the first definition given in the documentation. To make the documentation easier to follow, I removed this remark.

reduced_form

You should add documentation about option "row_wise"

Done, thank you for noticing.

I'll continue right now with your other batch of remarks.

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3a62826	add author name
​56a1427	updated author + corrected check_shifts + corrected column_degree
​38c2a94	simplified documentation of leading_matrix
​7b4944c	added row wise in input in documentation of row_reduced
​1bf254e	updating code with new function name

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​386ce50

format of error messages

[Vincent Neiger]

Replying to vdelecroix:

Side remark: error message should start with lower case and not have punctuation similarly to ...

Dear Vincent,

Thank you very much, this has been corrected.

Best,

Vincent

[Vincent Neiger]

Replying to gh-romainlebreton:

here is the second and final part of my review. I really like your contribution and I appreciate the effort that you have put into it !

Thank you :-) And I greatly appreciate your very careful and useful reviewing work.

_is_empty_popov

l501

if not include_zero_vectors:
   return True

should be

if include_zero_vectors:
   return True

Also your tests should capture this behavior.

Oh, big mistake, now corrected. Thank you for noticing.

is_reduced

• l518 with $k \leq n$ -> with $k \leq m$ ?
• l525 with $k \leq m$ -> with $k \leq n$ ?

I think what is written is correct. What you suggest is correct too (the number of nonzero rows is obviously at most m). The fact that the number of nonzero rows must be at most the number n of columns is because a row reduced matrix represents a basis of some submodule of length-n polynomial vectors (such a submodule is free and its basis has at most n elements). In some papers the definition of reduced does not require this, but then it becomes relatively more complicated and makes it more difficult to manipulate reduced forms, while it is not clear to me what advantages this more general definition could bring except possibly in very particular cases.

• l578 return self._is_empty_popov(row_wise)

I'm not able to tell if it is correct or if it should be return self._is_empty_popov(row_wise,include_zero_vectors)

This should be the latter version indeed, thank you.

• l609 "The definition is similar if working column-wise"

It would be nice to mention here too that "we choose bottommost entry in case of degree equality"

Done.

leading_positions

• l594 "(also known as the pivot index)" -> pivot indices

• l594 pivot degree -> pivot degrees

• idem l772

There has been a small discussion with Johan on this; in the literature there is a mix of singular and plural. The 'pivot degree' is a tuple of pivot degrees... anyway, for me both are fine, and since we used plural for 'positions' I suppose we should use plural for indices/degrees.

• l602 "Then the pivot degree of the vector is the degree $\deg(p_j)$"

Is it really $\deg(p_j)$ or should it be $\deg(p_j) + s_j$ instead ?

The pivot degree is the actual degree of the polynomial, and if you add the shift this would be the (shifted) row degree. Both are useful.

is_popov

l957 not up_to_permutation,

I don't understand why you negate up_to_permutation here. Can you please check ?

The argument ordered of is_weak_popov will require that the leading positions are strictly increasing; so it should be false when we are testing that the matrix is in Popov form up to row permutation (and true otherwise).

is_hermite

Maybe copy the sentence at l74 "In fact, if $d$ is the largest degree ..." relating Popov and Hermite at the end of the comments of the function

I incorporated this remark, than you for the suggestion.

Is the "+ 1" in lines 1071 and 1073 really necessary ?

Yes, because of the way we choose leading positions (rightmost nonzero), and because there is an option to have the upper triangular row-wise Hermite form. For example, working row-wise and with upper-triangular Hermite, a 2x2 matrix with rows [X X] and [1 X^2] is (2,0)-Popov but not Hermite; so if we used this shift (2,0) instead of (2+1,0) (where 2 is the degree of the matrix), the Hermite test relying on (2,0)-Popov form would give a wrong answer.

weak_popov_form

l1096 If this is True

Corrected, thank you!

Is there a good reason to not implement option row_wise here ?

This was considered out of the scope of this ticket, since there is anyway some work to be done on these reduction functions (adding Popov form, cleaning existing code using the new functions...).

reduced_form

Should add documentation about option "row_wise"

l1291 If this **is** ``True``

Corrected, thank you!

Please let me know if you have further suggestions for improvements.

Best,

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2d85794	update doc to reflect updated error messages
​f05f3e3	corrected is_empty_popov
​6078e8e	corrected pivot index / leading positions
​1337eae	typo
​c0ffff7	typo

[Bruno Grenet]

Replying to vneiger:

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

I am not familiar with this: this was already imported in this file prior to that ticket. To avoid breaking something that others wrote, I prefer leaving it as is... but please advise me if you are certain of a solution to make this point cleaner.

It is actually used (the Matrix from sage.matrix.matrix2) at lines 1199-1200, so it should must be imported. You could also import Matrix from sage.matrix.constructor at the beginning of the file using another name for it as follows: from sage.matrix.constructor import Matrix as Matrix_constructor. I do not know which one is better...

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

[Vincent Neiger]

Hi Bruno,

Replying to bruno:

Replying to vneiger:

Why import from sage.matrix.matrix2 cimport Matrix if sage.matrix.matrix2.Matrix is never used ? However, it may be faster to call directly sage.matrix.matrix2.Matrix instead of sage.matrix.constructor.Matrix.

I am not familiar with this: this was already imported in this file prior to that ticket. To avoid breaking something that others wrote, I prefer leaving it as is... but please advise me if you are certain of a solution to make this point cleaner.

It is actually used (the Matrix from sage.matrix.matrix2) at lines 1199-1200, so it should must be imported. You could also import Matrix from sage.matrix.constructor at the beginning of the file using another name for it as follows: from sage.matrix.constructor import Matrix as Matrix_constructor. I do not know which one is better...

Me neither..

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

Now, the function computes either a row reduced form or a column reduced form, depending on the optional parameter row_wise (default: true). Most other functions are like this in this file; it seemed better and more compact than always having two extremely similar functions named row_X and column_X . There might be other solutions we did not think of...

Vincent

[Bruno Grenet]

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

Now, the function computes either a row reduced form or a column reduced form, depending on the optional parameter row_wise (default: true). Most other functions are like this in this file; it seemed better and more compact than always having two extremely similar functions named row_X and column_X . There might be other solutions we did not think of...

That's fine, but shouldn't the documentation reflect this? I now says Return a row reduced form of this matrix (and "row reduced" is used several other times in the doc).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​eb335fc

improve doc of reduced_form

[Vincent Neiger]

Replying to bruno:

Another point: I read that the renaming of row_reduced_form to reduced_form what discussed between Johan and you. What is the rationale?

Now, the function computes either a row reduced form or a column reduced form, depending on the optional parameter row_wise (default: true). Most other functions are like this in this file; it seemed better and more compact than always having two extremely similar functions named row_X and column_X . There might be other solutions we did not think of...

That's fine, but shouldn't the documentation reflect this? I now says Return a row reduced form of this matrix (and "row reduced" is used several other times in the doc).

Indeed, for this method the doc was not well written. I have made an attempt at improving it. For the other methods, "row reduced" is indeed used but with the explicit mention "if working row-wise", and with a word about how things differ (or don't) if working column-wise.

[Romain Lebreton]

Replying to vneiger:

Replying to gh-romainlebreton:

Is the "+ 1" in lines 1071 and 1073 really necessary ?

Yes, because of the way we choose leading positions (rightmost nonzero), and because there is an option to have the upper triangular row-wise Hermite form. For example, working row-wise and with upper-triangular Hermite, a 2x2 matrix with rows [X X] and [1 X^2] is (2,0)-Popov but not Hermite; so if we used this shift (2,0) instead of (2+1,0) (where 2 is the degree of the matrix), the Hermite test relying on (2,0)-Popov form would give a wrong answer.

I think that your comment on line 992 had me confused:

"Note that, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincide with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension."

Is it really $d$ or should it be $d+1$ in this comment ?

[Vincent Neiger]

Replying to gh-romainlebreton:

Replying to vneiger:

Replying to gh-romainlebreton:

Is the "+ 1" in lines 1071 and 1073 really necessary ?

Yes, because of the way we choose leading positions (rightmost nonzero), and because there is an option to have the upper triangular row-wise Hermite form. For example, working row-wise and with upper-triangular Hermite, a 2x2 matrix with rows [X X] and [1 X^2] is (2,0)-Popov but not Hermite; so if we used this shift (2,0) instead of (2+1,0) (where 2 is the degree of the matrix), the Hermite test relying on (2,0)-Popov form would give a wrong answer.

I think that your comment on line 992 had me confused:

"Note that, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincide with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension."

Is it really $d$ or should it be $d+1$ in this comment ?

I see: in this comment, the "shifted Popov form" is understood as the lower triangular row-wise one, or as the upper triangular column-wise one. For the two others (upper triangular row-wise and lower triangular column-wise), these forms do not coincide anymore as showed by the example in my previous answer; the difference comes from the way pivots are chosen (rightmost nonzero for row-wise, bottommost nonzero for column-wise).

My suggestion is to make this more clear on line 992, as follows: "Note that, working row-wise, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincides with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working row-wise but with upper triangular Hermite forms, one would need to take $d+1$ in the shifts instead of $d$.)"

Would this remove any confusion?

Vincent

[Romain Lebreton]

Replying to vneiger:

I see: in this comment, the "shifted Popov form" is understood as the lower triangular row-wise one, or as the upper triangular column-wise one. For the two others (upper triangular row-wise and lower triangular column-wise), these forms do not coincide anymore as showed by the example in my previous answer; the difference comes from the way pivots are chosen (rightmost nonzero for row-wise, bottommost nonzero for column-wise).

My suggestion is to make this more clear on line 992, as follows: "Note that, working row-wise, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincides with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working row-wise but with upper triangular Hermite forms, one would need to take $d+1$ in the shifts instead of $d$.)"

Would this remove any confusion?

Hi Vincent, thank you for the explanation, it is now clear for me. I would suggest that you keep it simple in the comments : take $d$ (strictly) greater than all degrees in the matrix (so d would be "d+1") and shifts $(0,d,2d,\ldots,(n-1)d)$.

Best,

R.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b677052

right shift for Hermite form (d > deg(H))

[Vincent Neiger]

Replying to gh-romainlebreton:

Replying to vneiger:

I see: in this comment, the "shifted Popov form" is understood as the lower triangular row-wise one, or as the upper triangular column-wise one. For the two others (upper triangular row-wise and lower triangular column-wise), these forms do not coincide anymore as showed by the example in my previous answer; the difference comes from the way pivots are chosen (rightmost nonzero for row-wise, bottommost nonzero for column-wise).

My suggestion is to make this more clear on line 992, as follows: "Note that, working row-wise, if $d$ is the largest degree appearing in the Hermite form, then the Hermite form coincides with the shifted Popov form with the shifts $(0,d,2d,\ldots,(n-1)d)$, where $n$ is the column dimension. (This is valid with lower triangular Hermite forms; if working row-wise but with upper triangular Hermite forms, one would need to take $d+1$ in the shifts instead of $d$.)"

Would this remove any confusion?

Hi Vincent, thank you for the explanation, it is now clear for me. I would suggest that you keep it simple in the comments : take $d$ (strictly) greater than all degrees in the matrix (so d would be "d+1") and shifts $(0,d,2d,\ldots,(n-1)d)$.

Best,

R.

Ok, I have chosen this solution which is indeed simpler.

Vincent

---

New commits:

​b677052

right shift for Hermite form (d > deg(H))

[Romain Lebreton]

Replying to vneiger:

Ok, I have chosen this solution which is indeed simpler.

Great! However I am still unsure about line 1070

shift = [j*self.degree() + 1 for j in range(self.ncols())]

which gives [1, d + 1, 2*d + 1, 3*d + 1, ...] with d the degree. It does not seem coherent with what we said ; I seems to me that it should be

shift = [j*(self.degree() + 1) for j in range(self.ncols())]

R.

[Vincent Neiger]

Replying to gh-romainlebreton:

Replying to vneiger:

Ok, I have chosen this solution which is indeed simpler.

Great! However I am still unsure about line 1070

shift = [j*self.degree() + 1 for j in range(self.ncols())]

which gives [1, d + 1, 2*d + 1, 3*d + 1, ...] with d the degree. It does not seem coherent with what we said ; I seems to me that it should be

shift = [j*(self.degree() + 1) for j in range(self.ncols())]

R.

Oh... you are totally right. This is a bug, thank you for noticing. Adding 1 to all entries of the shift is useless concerning normal forms and so this shift is equivalent to (0,d,2d,...). Which is not right: I have just actually tested my example above, of a matrix which is not even triangular, and it does wrongly return True :

sage: pR.<x> = GF(7)[]
sage: M = Matrix(pR,2,2,[[x,x],[1,x^2]])
sage: M
[  x   x]
[  1 x^2]
sage: M.is_popov(shifts=[2,0])
True
sage: M.is_hermite()  # defaut is row-wise upper triangular
True

The shift in this example should of course be (d+1,0) = (3,0), while the current code uses (d+1,1) = (3,1), which is equivalent to (2,0) and not the right one as we discussed above.

I'm going to fix this in a commit in a few seconds.

Thank you again.

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​17b068c

corrected shift used for is_hermite test

[Romain Lebreton]

In is_hermite, the block SEEALSO requires :: at the end

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5fc5fd6

colon SEEALSO::

[Vincent Neiger]

Replying to gh-romainlebreton:

In is_hermite, the block SEEALSO requires :: at the end

Hi Romain, Thank you for noticing this. This is fixed.

Best,

Vincent

[Romain Lebreton]

Looks good to me :-)