Free module equality, Hermite form over PIDs

[Rob Beezer]

Looks to me like there is a problem with free module equality. Note
that this seems to be for general PID's, but not ZZ, thus the simple
example over a polynomial ring.

sage: R = PolynomialRing(QQ, 'a')
sage: x = vector(R, [1, 0])
sage: y = vector(R, [0, 1])
sage: z = vector(R, [0,-1])
sage: A = (R^2).span([x, y])
sage: B = (R^2).span([x, z])
sage: A == B
False
sage: A.is_submodule(B)
True
sage: B.is_submodule(A)
True

Root cause looks like an assumption that echelon form (Hermite form)
over PIDs is unique.

sage: S = matrix([x, y])
sage: S._echelon_form_PID()[1]
[1 0]
[0 1]
sage: T = matrix([x, z])
sage: T._echelon_form_PID()[1]
[ 1 0]
[ 0 -1]

(a) Can this echelon form be made unique, or is that too much to
expect over general PIDs?

(b) Should __cmp__ for free modules be adjusted to test submodules,
as above, when the echelon forms are different?

It appears that it would be easy to exploit the non-uniqueness of the
echelon form to get inconsistencies in the ordering of free modules,
since presently the ordering of free modules uses the ordering of the
module's echelonized basis matrices as its final characterizing
property.

Rob

[John Cremona]

I think it is too much to expect general PIDs to have unique
(canonical) echelon forms, since that would, as a special case, mean a
canonical generator for each principal ideal. Of course there are
PIDs (such as Z) where there is a natural choice, but not in general.

John

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

[Rob Beezer]

On Jul 6, 1:45 am, John Cremona <john.crem...@gmail.com> wrote:
> I think it is too much to expect general PIDs to have unique
> (canonical) echelon forms,

Thanks for the reply, John. As I suspected, I guess.

This is now

http://trac.sagemath.org/sage_trac/ticket/11579

which I do not plan to pursue, though there is one suggestion there
for a fix. I solved my less tangential problem (surjectivity of free
module morphisms) with a call to .is_submodule().

Rob

[Francis Clarke]

On Jul 6, 9:45 am, John Cremona <john.crem...@gmail.com> wrote:
> I think it is too much to expect general PIDs to have unique
> (canonical) echelon forms, since that would, as a special case, mean a
> canonical generator for each principal ideal.  Of course there are
> PIDs (such as Z) where there is a natural choice, but not in general.

I'm not so sure, John.

Leslie Hogben's Handbook of Linear Algebra (Chapman and Hall/CRC 2006)
says that Hermite Normal Forms (HNFs) exist for matrices over Bezout
rings and are unique up to multiplication by units over PIDs. Though,
as you say, there is not over many PID's a canonical HNF, it is not
difficult to decide whether two HNF's are equivalent, i.e., the rows
generate the same submodule, which is what we want to know here: check
whether the leading entries are in the same positions and are
associates, then check the above-diagonal entries.

Unfortunately, over polynomial rings at least, echelon_form_PID
doesn't, as of 4.7, always yield the (or rather an) HNF:

sage: A = matrix(2,2,[QQ['t'].random_element() for i in range(4)]); A
[ 0 -t^2 + 7/2*t]
[ t^2 + 3/2 -11*t^2 - 7/2]

sage: A._echelon_form_PID()[1]
[ t^2 + 3/2 -11*t^2 - 7/2]
[ 0 t^2 - 7/2*t]

Clearly 11 times row 1 should be added to row 0 to obtain

[ t^2 + 3/2 -77/2*t - 7/2]
[ 0 t^2 - 7/2*t]

Of course in the case of polynomial rings over fields there is a
canonical HNF, as the leading entries can be chosen to be monic.

All this should be simple to fix.

Francis

[Francis Clarke]

On Jul 7, 8:55 am, Francis Clarke <francis.w.cla...@gmail.com> wrote:
> Hermite Normal Forms (HNFs) exist for matrices over Bezout
> rings and are unique up to multiplication by units over PIDs.

Correction: they're unique modulo units over Euclidean domains.

Francis

[Rob Beezer]

On Jul 7, 12:55 am, Francis Clarke <francis.w.cla...@gmail.com> wrote:
> All this should be simple to fix.

Sounds good. With a fix for equality, there is still an outstanding
problem with comparisons of free modules. Presently,

"Modules are ordered by their ambient spaces, then by dimension, then
in order by their echelon matrices."

So again, there is an assumption that the echelon matrix is unique.
Is there a critical reason free modules should be ordered at all?

Rob

[Nils Bruin]

On Jul 8, 10:05 pm, Rob Beezer <goo...@beezer.cotse.net> wrote:
> So again, there is an assumption that the echelon matrix is unique.
> Is there a critical reason free modules should be ordered at all?

No. Historically there was an expectation in Python that "<" defines a
total ordering on objects, but with "complex" (exception on
comparison) and sets (partial ordering) this is already not the case
in practice. In Python 3, "<" is expected to throw an exception unless
the operation makes sense.

In analogy with sets one could argue that "<=" should test correspond
to is_submodule.

[Rob Beezer]

Thanks, Nils. I've added a link to this discussion on the Trac
ticket.

I agree that it might be nice if <= behaved like .is_submodule().

Rob

[William Stein]

If there is no ordering on free modules, then any function that
outputs a list of free modules is not deterministic -- the answer is
randomly ordered. For testing purposes, this is a huge and annoying
loss. Of course, it isn't at all critical for this that the ordering
be the one used by __cmp__; one could define an ordering in some other
function, which is used for ordering lists of submodules. We could
instead have a method like M._useful_but_nanonical_total_ordering(N),
then define __cmp__ like Nils suggests.

-- William

>
> Rob
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org