Opened 6 years ago

Closed 5 years ago

# Compute J-ideal of a matrix

Reported by: Owned by: cheuberg major sage-7.5 linear algebra dkrenn, rrissner Clemens Heuberger, Roswitha Rissner Daniel Krenn, Travis Scrimshaw N/A 079f8f1 079f8f1de35ab2eb3a5a964a7f9d8c642afe6b6e

In [HR2016], an algorithm for computing the J-ideal of a matrix is given: Given a matrix B over a principal ideal domain R and an ideal (a), the (a) ideal of B consists of those polynomials over R[X] which map B to a matrix in M_n((a)).

This ticket contains the accompanying code.

[HR2016] Clemens Heuberger and Roswitha Rissner, Computing J-Ideals of a Matrix Over a Principal Ideal Domain, arXiv 1611.10308 [math.AC], 2016.

### comment:1 Changed 6 years ago by cheuberg

• Branch set to u/cheuberg/compute-j-ideal
• Commit set to c3433e210fbd50348bdc22dbf900ee8bb6a5fbcc
• Status changed from new to needs_review

Last 10 new commits:

 ​c7837e7 adapt import statements ​56028e4 Cache G and previous nu ​458067e Avoid computing lifting twice for debugging ​902c344 Implement method integer_valued_polynomials ​c63f37b Improve documentation ​0291daa Merge stand alone branch 't/21992/compute-j-ideal' ​5ebd5e2 Trac #21992: fix doctests after integration into sage ​b9e7acf Trac #21992: include into documentation ​0324154 Trac #21992: Fix indentations ​c3433e2 Trac #21992: make compute_J_ideal accessible

### comment:2 Changed 6 years ago by git

• Commit changed from c3433e210fbd50348bdc22dbf900ee8bb6a5fbcc to 78f6f33d4879e0ff445a51e72d1a86a5e4befc0f

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

 ​78f6f33 Trac #21992: insert arXiv link

### comment:3 Changed 6 years ago by cheuberg

• Description modified (diff)

### comment:4 Changed 5 years ago by dkrenn

• Reviewers set to Daniel Krenn
• Status changed from needs_review to needs_work

Code looks good, is extensively tested, docs are fine. I only found the following minor issues / suggestions:

1. correct the 2 lines with whitespace errors
2. Python 3:
• imports at top of file
from __future__ import print_function
from __future__ import absolute_import

AFAIK, we put this now in all SageMath-files which are already Python3-compatibel
• print_function in doctests (simply use print(...), which works in Python2 and 3
• iteritems/iterkeys: use e.g. six
3. refactor imports to be more locally: e.g. heapq is only needed in one function/method, so you can put it there. I tend to use file-global imports only when really needed there (e.g. SageObject?).
4. print *.null_ideal(...) in all doctests: maybe do not break 'Univariate Polynomial Ring'; I find this hard to read then. Maybe break already after the preceding 'of' Not sure if this helps, but and/or: indent the second line.
5. (Default: ...) vs. (default: ...); I think SageMath has a preference for the latter:
sage -grep "(default:" | wc -l
4920
sage -grep "(Default:" | wc -l
92

6. doc p_minimal_polynomial, INPUT s_max vs. last sentence before EXAMPLES: At first sight it seems weird that in the INPUT block it can easily be described what happens when s_max is set, whereas in the sentence before the EXAMPLES block a much longer explaination is needed. Also t <= s_max vs s <= s_max confuses when reading first. Moreover I find the sentence before the EXAMPLES block hard to read. So maybe could be rewritten to make it easier understandable. Adapt this in matrix_integer_dense as well.
7. L 328: "square matrix required." full stop at end, but in no other raised exception.
8. As we are already talking about exceptions and FYI, sometimes they are formulated as proper English sentences like s is not in N_{(%s^%s)}(B) (but omiting the full stop, where I personally would put one as the sentence ends here, but I am aware that there are different perspectives here), sometime not like %s not in (%s^%s)-ideal
9. L559: two blanks after "return"
10. FYI, between two methods there are two empty lines most of the time, but not always
11. matrix_integer_dense, p_minimal_polynomials: Should it be explained what the (p^t)-minimal polynomials \nu_t of this matrix are?

I am not sure, why no patchbot tested this ticket yet...

### comment:5 Changed 5 years ago by git

• Commit changed from 78f6f33d4879e0ff445a51e72d1a86a5e4befc0f to 0b218b1360af5b55354714cb9494c7e9b2fcd4f4

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

 ​361c8cf Trac #21992.1: remove trailing white space ​b50f81e Trac #21992.2: Python3 compatibility ​b157039 Trac #21992.3: refactor imports ​34b4d50 Trac #21992.4: Change linebreaks in doctests ​c79014a Trac #21992.5: "Default" -> "default" ​d7e519a Trac #21992.6: reformulate description of s_max ​7db28fe Trac #21992.7+8: rephrase exceptions ​f64dd65 Trac #21992.9: remove superfluous white space ​36b084d Trac #21992.10: Double blank line before methods ​0b218b1 Trac #21992.11: Explain p^s-minimal polynomial

### comment:6 follow-up: ↓ 7 Changed 5 years ago by cheuberg

• Status changed from needs_work to needs_review

1. I split the sentence into two parts, perhaps it is now easier to understand. I also added a "see below" in the documentation for the input parameter to at least announce that it is somewhat tricky. I replaced several t by s to have more homogeneous notation.
2. done
3. Abbreviated all but one exception to non-sentences without full stop; one exception has been upgraded to a full sentence with full stop because I did not see a concise non-sentence formulation.

I am not sure about the patchbot; I now added the "?kick" parameter.

### comment:7 in reply to: ↑ 6 Changed 5 years ago by dkrenn

LGTM.

1. I split the sentence into two parts, perhaps it is now easier to understand. I also added a "see below" in the documentation for the input parameter to at least announce that it is somewhat tricky. I replaced several t by s to have more homogeneous notation.

Ok, thank you. I think this is much better now.

1. Abbreviated all but one exception to non-sentences without full stop; one exception has been upgraded to a full sentence with full stop because I did not see a concise non-sentence formulation.

Ok.

I am not sure about the patchbot; I now added the "?kick" parameter.

So, this is a positive review from my side. I suggest to wait some more days to see if the patchbot with all plugins agrees as well.

### comment:8 follow-ups: ↓ 10 ↓ 11 Changed 5 years ago by tscrim

Some very minor points:

• References should go in the master reference file.
• INPUT's should not end in a period. One of the longer ones should be changed to:
  - G -- a matrix over D[X]; the columns of
\begin{pmatrix}p^{t-1}I& G\end{pmatrix} are generators
of \{ f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\};
can be set to None if t is zero

The other long one to change:
      - s_max -- a positive integer (default: None); if set, only
(p^s)-minimal polynomials for s <= s_max are computed
(see below for details)

• To one line:
-        raise ValueError(
-            "A*G not zero mod %s^%s" % (p, t-1))
+        raise ValueError("A*G not zero mod %s^%s" % (p, t-1))

• The asserts are just checking that the Smith normal form is correct? I know its considered good form, but all asserts are (currently) checked in Sage.
• This break is strange:
-    return sum(c//p * X**i for
-               i, c in enumerate(f.list())
+    return sum(c//p * X**i for i, c in enumerate(f.list())
if c % p == 0)

• Move the description of what the method does before the INPUT: and OUTPUT:. It makes it easier to parse and (IMO) is more important information.
• Use the Sage macro \ZZ instead of \mathbb{Z}. Same for \QQ.
• Add some whitespace around the latex. While it doesn't make a difference in the html/pdf rendered doc, it makes it easier to read when using the ?.
• You can freely split lines in .. MATH:: blocks.

### comment:9 Changed 5 years ago by git

• Commit changed from 0b218b1360af5b55354714cb9494c7e9b2fcd4f4 to 306cd06623c572d852041dd1e0a645893b7d6c1f

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

 ​b034597 Trac #21992: Merge 7.5.rc1 for master bibliography ​0fbef2c Trac #21992.12: Move references to master file ​7f4d71c Trac #21992.13: INPUT: do not end in a period ​87a11d7 Trac #21992.14: remove line break ​15f6cf9 Trac #21992.15: comment out assert ​e1c91c9 Trac #21992.16: change line break ​2f819d8 Trac #21192.17: use long descriptions ​25c6da2 Trac #21992.18: \mathbb{Z}->\ZZ, \mathbb{Q}->\QQ ​306cd06 Trac #21992.20: break lines in MATH

### comment:10 in reply to: ↑ 8 Changed 5 years ago by cheuberg

Some very minor points:

• References should go in the master reference file.

done. This required merging a 6.5.rc1 (until now, the branch was based on 6.4 which had no master reference file).

• The asserts are just checking that the Smith normal form is correct? I know its considered good form, but all asserts are (currently) checked in Sage.

Yes, and to recall what matrix is what. I commented out those asserts checking Smith normal form. There are several other asserts scattered through the code checking that our own code here works as expected. I kept those.

• Move the description of what the method does before the INPUT: and OUTPUT:. It makes it easier to parse and (IMO) is more important information.

I did this in two instances; it does not seem to be trivial because the information from the input section is somehow needed. So this introduces some redundancy.

• Add some whitespace around the latex. While it doesn't make a difference in the html/pdf rendered doc, it makes it easier to read when using the ?.

Please be more specific where you want to have whitespace added. There is quite a number of LaTeX formulae throughout the module.

### comment:11 in reply to: ↑ 8 ; follow-up: ↓ 12 Changed 5 years ago by dkrenn

Dear Travis,

• INPUT's should not end in a period. One of the longer ones should be changed to:
  - G -- a matrix over D[X]; the columns of
\begin{pmatrix}p^{t-1}I& G\end{pmatrix} are generators
of \{ f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\};
can be set to None if t is zero


I agree that constructs like

G -- a matrix over D[X]


should not end in a period (by our new convention), but the part after the first ; is a proper English sentence, thus I think it should end in a period.

Best, Daniel

Last edited 5 years ago by dkrenn (previous) (diff)

### comment:12 in reply to: ↑ 11 Changed 5 years ago by dkrenn

[...], but the part after the first ; is a proper English sentence, thus I think it should end in a period.

Maybe this would be a good compromise:

  - G -- a matrix over D[X]

The columns of
\begin{pmatrix}p^{t-1}I& G\end{pmatrix} are generators
of \{ f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\}.
This parameter can be set to None if t is zero.


### comment:13 follow-up: ↓ 15 Changed 5 years ago by tscrim

Redundancy is not necessarily a bad thing, especially when it comes to documenting inputs.

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

For the latex and spacing, I think this is the worst one (I'm also okay with no space after \max):

-        For 0<t\le \max\mathcal{S}, a (p^t)-minimal polynomial is
-        For 0 < t \le \max \mathcal{S}, a (p^t)-minimal polynomial is
given by \nu_s where
-        s=\min\{ r\in\mathcal{S}\mid r\ge t\}.
-        For t>\max\mathcal{S}, the minimal polynomial of B is
+        s = \min\{ r \in \mathcal{S} \mid r \ge t\}.
+        For t > \max \mathcal{S}, the minimal polynomial of B is
also a (p^t)-minimal polynomial.


Also, for null_ideal, I would be a bit more verbose and document it as:

     def null_ideal(self, b=0):
r"""
-        Return the (b)-ideal N_{(b)}(B)=\{f\in \ZZ[X] \mid f(B)\in M_n(b\ZZ)\} where B
-        is this matrix.
+        Return the null ideal corresponding to b of self.
+
+        Let B be an n \times n matrix. The *null ideal* of b, or (b)-ideal, is
+
+        .. MATH::
+
+            N_{(b)}(B) = \{f \in \ZZ[X] \mid f(B) \in M_n(b\ZZ)\}.
+


For integer_valued_polynomials, I would expect, based on the method name, that the output would be a list/tuple of polynomials. Also, overall, I'm far less convinced than other people about the necessity of an OUTPUT block when the documentation clearly described the output.

I like the compromise less than just allowing the periods. While I would like to adhere more to our (long standing) conventions of allowing things closer to run-on sentences to not end in periods in INPUT bullets, this is long enough that I am okay with it going in.

### comment:14 Changed 5 years ago by git

• Commit changed from 306cd06623c572d852041dd1e0a645893b7d6c1f to a915d564e6fbbf500d1cdecf2756a69a7b46ff1f

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

 ​b0104fc Trac #21992.19: Insert blanks into TeX code ​cce8dd4 Trac #21992.21: rewrite doc of null_ideal ​a915d56 Trac #21992: missing empty line

### comment:15 in reply to: ↑ 13 ; follow-up: ↓ 16 Changed 5 years ago by cheuberg

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

Because it does not work: First problem is that the first step (prime_candidates) needs Frobenius Rational Form and this is only implemented over ZZ.

Next problem is some kind of bug in lifting, cf. https://ask.sagemath.org/question/35555/lifting-a-matrix-from-mathbbqyy-1/ .

At this point, we stopped trying and decided to concentrate on the integer case first.

For the latex and spacing, I think this is the worst one (I'm also okay with no space after \max):

done.

Also, for null_ideal, I would be a bit more verbose and document it as:

done (in slightly different wording). This concerns the documentation in matrix_integer_dense. In compute_J_ideal.py, the explanation is at the top of the module.

For integer_valued_polynomials, I would expect, based on the method name, that the output would be a list/tuple of polynomials.

The set of integer valued polynomials of the matrix B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]]) is (x^3+x^2−12x−20)QQ[X]+ZZ[X]+(1/4)(x^2+3x+2)ZZ[X]. As a ZZ[X] module, this is not finitely generated. It is not a QQ[X] module. Therefore, its description needs two components. Therefore, the output is a pair where the second component is a list of polynomials.

I like the compromise less than just allowing the periods. While I would like to adhere more to our (long standing) conventions of allowing things closer to run-on sentences to not end in periods in INPUT bullets, this is long enough that I am okay with it going in.

Can we leave it in the current form?

### comment:16 in reply to: ↑ 15 ; follow-up: ↓ 18 Changed 5 years ago by tscrim

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

Because it does not work: First problem is that the first step (prime_candidates) needs Frobenius Rational Form and this is only implemented over ZZ.

Next problem is some kind of bug in lifting, cf. https://ask.sagemath.org/question/35555/lifting-a-matrix-from-mathbbqyy-1/ .

Could you add these to the .. TODO::, because I think anyone else reading the code will ask the same question I did.

For integer_valued_polynomials, I would expect, based on the method name, that the output would be a list/tuple of polynomials.

The set of integer valued polynomials of the matrix B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]]) is (x^3+x^2−12x−20)QQ[X]+ZZ[X]+(1/4)(x^2+3x+2)ZZ[X]. As a ZZ[X] module, this is not finitely generated. It is not a QQ[X] module. Therefore, its description needs two components. Therefore, the output is a pair where the second component is a list of polynomials.

I think a bit more verbose name is warranted here, something like generators_integer_valued_polynomials. If you want the method to be named integer_valued_polynomials, then it should return the set (algebra?) of integer valued polynomials.

I like the compromise less than just allowing the periods. While I would like to adhere more to our (long standing) conventions of allowing things closer to run-on sentences to not end in periods in INPUT bullets, this is long enough that I am okay with it going in.

Can we leave it in the current form?

Yes.

### comment:17 Changed 5 years ago by git

• Commit changed from a915d564e6fbbf500d1cdecf2756a69a7b46ff1f to 079f8f1de35ab2eb3a5a964a7f9d8c642afe6b6e

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

 ​3e31602 Trac #21992.22: expand TODO block: explain problem ​079f8f1 Trac #21992.23: integer_valued_polynomials_generators

### comment:18 in reply to: ↑ 16 Changed 5 years ago by cheuberg

Also, why did you leave in the .. TODO:: about the tests? I feel like that could be easily done.

Because it does not work: First problem is that the first step (prime_candidates) needs Frobenius Rational Form and this is only implemented over ZZ.

Next problem is some kind of bug in lifting, cf. https://ask.sagemath.org/question/35555/lifting-a-matrix-from-mathbbqyy-1/ .

Could you add these to the .. TODO::, because I think anyone else reading the code will ask the same question I did.

Done.

I think a bit more verbose name is warranted here, something like generators_integer_valued_polynomials. If you want the method to be named integer_valued_polynomials, then it should return the set (algebra?) of integer valued polynomials.

I renamed the method to integer_valued_polynomials_generators for the sake of tab completion.

### comment:19 follow-up: ↓ 20 Changed 5 years ago by tscrim

• Reviewers changed from Daniel Krenn to Daniel Krenn, Travis Scrimshaw

LGTM. Daniel, any other comments before we set this to a positive review.

### comment:20 in reply to: ↑ 19 Changed 5 years ago by dkrenn

• Status changed from needs_review to positive_review