Free modules over PIDs

[adeines]

sage: F.<a> = NumberField(x^2-x-1)
sage: ZF = F.ring_of_integers()
sage: A = matrix(ZF,[[1,0,0,0],[0,-1,0,0],[0,0,1,0],[0,0,0,1]])
sage: B = identity_matrix(ZF,4)
sage: VA = (ZF^4).span(A)
sage: VB = (ZF^4).span(B)
sage: VB == VA
False

This should return true. As Sage is only checking the echelon form, it is not catching this.

To fix this I used the wrapped pseudo basis nfhnf and compute the Hermite normal form and the pseudo basis ideal list as _pseudo_hermite_matrix.

CC: @sagetrac-jakobkroeker

Component: linear algebra

Keywords: free modules, PID

Author: Aly Deines

Branch/Commit: u/aly.deines/ticket/16893 @ ac769b2

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/16893

[adeines]

Branch: u/aly.deines/free_modules_over_pids

[adeines]

Commit: 867b150

[adeines]

New commits:

5b40230	Added _pseudo_hermite_matrix so we can check equality of free modules over rings of integers of number fields.
867b150	Added a _pseudo_basis_matrix method to modules/free_module.py and

[adeines]

Author: aly.deines

[adeines]

Changed keywords from none to free modules, PID

[videlec]

comment:3

Hi,

There are (trivial) rebase to do on top of sage-6.7.beta2.

Apart that, in your commit there are a lot of trailing whitespaces (i.e. space before end of line) and you should get rid of them.

I did not check much about the code yet but I am currently doing it. Would be cool to have this integrated into Sage.

Vincent

[videlec]

comment:4

After a first lecture:

• self should not be mentioned in the INPUT section.

• in your example [ideal(ZZ(p)) for p in ...] you could remove the ZZ. The output of prime_range are already integers.

• ValueError("gens and ideal_list must have the same lenghth") chane lenghth into length

• it is better to use ZZ is ZF rather than ZZ == ZF. The reason is that it does not involve Python comparisons (which might be tedious). Similarly, you can safely replace ideal_list == None with ideal_list is None

• instead of pari(F) use F._pari_(). Doing that way you can remove pari from the imported modules. You can also go from pari to sage using .sage()

sage: m = matrix([[2,1],[1,1]])
sage: p = m._pari_()
sage: p
[2, 1; 1, 1]
sage: p.sage()
[2 1]
[1 1]

copying the entries one by one will be rather slow (it will not necessarily works well with number field elements).

• you can replace [F.ideal(1) for id in range(len(self.gens()))] with [F.ideal(1)] * len(self.gens()).

Vincent

[fchapoton]

Changed author from aly.deines to Aly Deines

[adeines]

Changed branch from u/aly.deines/free_modules_over_pids to u/aly.deines/ticket/16893

[adeines]

Changed commit from 867b150 to 79794d2

[sagetrac-git]

Changed commit from 79794d2 to ea49228

[sagetrac-git]

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

535ae3e	Cleaning up code.
ea49228	Cleaning up code.

[adeines]

comment:8

Cleaned up and rebased.

[videlec]

comment:9

You should not use assert to check a test that may fail. You would better raise a NotImplementedError. In other words use the following template

if ZF is sage.rings.integer_ring.ZZ and ideal_list is None:
    ... case1 ...
elif ZF is sage.rings.integer_ring.ZZ:
    ... case2 ...
elif nf_order.is_NumberFieldOrder(ZF):
    ... case3 ...
else:
    raise NotImplementedError("_pseudo_hermite_matrix not implemented for XYZ")

[videlec]

comment:10

Doctesting is very good.

1. The docstring should start with a one line description. Then a linebreak. And then an optional longer description. The comment about the genericity of the code would better be in a NOTE section (see developer guide).

2. Please fix the spaces in the definition of the function as

def _pseudo_hermite_matrix(self, ideal_list=None):

and always keep a space after a comma.

3. typo: pseodo

4. Would be good to point to a definition of pseudo-Hermite matrix.

5. This

+            #if the ideals are the same, compare the matrices
+            if Ids == OIds:
+                return cmp(Mat,Omat)
+            #otherwise, compare the ideals.
+            else:
+                return cmp(Ids,OIds)

can be replaced with

return cmp(Ids, OIds) or cmp(Mat, Omat)

6. Why did you move the position of import sage.misc.latex as latex in the list of imported modules at the top of the file?

[videlec]

Reviewer: Vincent Delecroix

[sagetrac-git]

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

08fe242	Edited to reflect reviewer suggestions.
092f96e	White space.

[sagetrac-git]

Changed commit from e64cf7c to 092f96e

[adeines]

comment:14

Thanks!

And the move of import sage.misc.latex as latex was a relic of rebasing, but I've moved that back.

[videlec]

comment:15

One backquote is for latex and two for displaying code. Hence you should change `ideal_list` to ``ideal_list``.

The examples need to be in an EXAMPLES section.

len(self.gens()) -> self.ngens()

len(HM) -> HM.nrows()

len(HM[0]) -> HM.ncols()

[sagetrac-git]

Changed commit from 092f96e to 2cd281f

[sagetrac-git]

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

e4b0fa2	A few more suggested changes.
2cd281f	Removed some unnecessary imports.

[videlec]

comment:18

Still from comment:15: the examples should be precedeed with EXAMPLES: (in the function _pseudo_hermite_matrix).

[sagetrac-git]

Changed commit from 2cd281f to ac769b2

[sagetrac-git]

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

ac769b2

Added Examples label to the examples in the doctest.

[videlec]

comment:20

The equality testing is likely to be broken on other PID too. Isn't it?

[videlec]

comment:21

Indeed

sage: R = QQ['x']
sage: A = matrix(R, 3, [1,0,0,0,1,0,0,0,1])
sage: B = matrix(R, 3, [1,0,0,0,-1,0,0,0,1])
sage: (R^3).submodule(A) == (R^3).submodule(B)
False

Would be better to find something to solve other cases (or raise in error in the comparison code if this is hard to implement in general).

[simonbrandhorst]

comment:24

Be aware of

• Coercion between Matrices over orders and over the number field #24031 Coercion between Matrices over orders and over the number field
• Rich comparison for Modules #23978 Rich comparison for Modules
• Free module equality, comparisons #11579 Free module equality, comparisons

[mkoeppe]

Both the example in the issue description and the one in #16893 (comment) work correctly in 10.0.beta6, so we can close this issue.

[jhpalmieri]

Both the example in the issue description and the one in #16893 (comment) work correctly in 10.0.beta6, so we can close this issue.

Agreed.