Implement orthogonal complement in vector spaces

[kcrisman]

It should be easy to get the orthogonal complement of a subspace W of a vector space V. From Jason Grout:

sage: def orthogonal_complement(space):
....:     if space.dimension()==0:
....:         return space.ambient_vector_space()
....:     else:
....:         return space.basis_matrix().right_kernel()

One would also want to add an option to specify the larger space in which you were dealing, with it defaulting to the ambient vector space. Probably 'perp()' should be an alias.

---

Apply: attachment: trac_7522-perp-ts.patch and attachment: trac_7522-finite.patch

CC: @jasongrout @rbeezer

Component: linear algebra

Keywords: sd48

Author: Jason Grout, Travis Scrimshaw

Reviewer: Karl-Dieter Crisman, Nils Bruin, Jason Grout, Gregory Bard

Merged: sage-5.11.beta3

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

[jasongrout]

Attachment: 7522-perp.patch.gz

[jasongrout]

comment:1

This adds the basic orthogonal complement command. Specifying a larger space can go on another ticket, if someone wants it.

[kcrisman]

comment:2

Replying to @jasongrout:

This adds the basic orthogonal complement command. Specifying a larger space can go on another ticket, if someone wants it.

Thanks for doing this - I never got to it, since I haven't used this lately. Agreed on the enhancement.

The documentation should make it clear what the ambient space is by default, perhaps by adding an example where things fail? Or at least commenting that the first example just shows itself as the ambient space. What would happen if one took a double subspace - what would it consider to be the ambient subspace?

[jasongrout]

apply on top of previous patches

[jasongrout]

comment:3

Attachment: 7522-review.patch.gz

Replying to @kcrisman:

The documentation should make it clear what the ambient space is by default, perhaps by adding an example where things fail? Or at least commenting that the first example just shows itself as the ambient space. What would happen if one took a double subspace - what would it consider to be the ambient subspace?

Review patch attached. Better now?

[kcrisman]

comment:4

I got a chance to look at this over the weekend. Unsurprisingly, in general it's great. But...

Since this is in the free module module (!), there should be a better error for

sage: c = FreeModule(Integers(8), 2)
sage: c.perp()
---------------------------------------------------------------------------
<snip>
NotImplementedError: Don't know how to compute kernels over Ring of integers modulo 8

I also noticed the following behavior, which is probably desirable, but which should then definitely be explicitly mentioned in the documentation for this function, since it does return a different type of object for the perp object:

sage: c = FreeModule(ZZ, 2)
sage: c
Ambient free module of rank 2 over the principal ideal domain Integer Ring
sage: c.perp()
Vector space of degree 2 and dimension 0 over Rational Field
Basis matrix:
[]

[kcrisman]

comment:5

By the way, why didn't TestSuite catch this?

    sage: M = ZZ^3
    sage: TestSuite(M).run()
    sage: W = M.span_of_basis([[1,2,3],[4,5,19]])
    sage: TestSuite(W).run()

[kcrisman]

Reviewer: Karl-Dieter Crisman

[tscrim]

comment:7

I've uploaded a new version of the patch which moves the perp() method to the free module with the PID as a base ring (so you shouldn't get the NotImplementedError) and made sure the submodules have the correct base rings.

[tscrim]

Changed author from Jason Grout to Jason Grout, Travis Scrimshaw

[tscrim]

comment:8

For patchbot:

Apply: trac_7522-perp-ts.patch

[kcrisman]

comment:9

perp() isn't documented in this patch. Also,

sage: c = FreeModule(Integers(8), 2)
sage: c.perp()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
AttributeError: 'FreeModule_ambient_with_category' object has no attribute 'perp'
<and later>
AttributeError: 'IntegerModRing_generic_with_category' object has no attribute 'parent'

Apparently Integers(8) isn't a PID, according to Sage? This isn't bad, but perhaps we should have a different error message... or maybe this is okay.

[kcrisman]

comment:10

Also, would it be better to do the kernel first and then change the ring? Just wondering if there might be any difference.

[nbruin]

comment:11

• You only have an orthogonal complement on an inner product space.
  • Whenever you have a canonical isomorphism between a vector space and its dual, you can do the "kernel trick" that you're doing (note you have to take a transpose somewhere). A basis choice induces such a canonical isomorphism, as does an inner product. For every subspace W subset V it gives you a complementary subspace W' such that V is a direct product of W and W'.
  • For (free) modules over rings this doesn't really work, because not every submodule is a direct summand.
  • Of course, if your ring is a domain, you can tensor with the field of fractions, take the complement, and intersect with the module inside to get another submodule. Doing that twice should get you the "saturation" of your original module.

I suggest you don't call it orthogonal complement. For instance, on vector spaces over finite fields, it's not (but a basis choice still induces an isomorphism to the dual).

[kcrisman]

comment:12

• You only have an orthogonal complement on an inner product space.
• Whenever you have a canonical isomorphism between a vector space and its dual, you can do the "kernel trick" that you're doing (note you have to take a transpose somewhere). A basis choice induces such a canonical isomorphism, as does an inner product. For every subspace W subset V it gives you a complementary subspace W' such that V is a direct product of W and W'.
• For (free) modules over rings this doesn't really work, because not every submodule is a direct summand.

Aargh! You had to go remind us of the whole mathematical correctness thing. You're right, of course. Not every submodule is projective.

• Of course, if your ring is a domain, you can tensor with the field of fractions, take the complement, and intersect with the module inside to get another submodule. Doing that twice should get you the "saturation" of your original module.
  I suggest you don't call it orthogonal complement. For instance, on vector spaces over finite fields, it's not (but a basis choice still induces an isomorphism to the dual).

Then what do you suggest? Since this is primarily useful for pedagogical purposes, perhaps we can just raise an error outside of QQ, RR, and friends. In particular, I think it's definitely appropriate to not allow this for anything but vector spaces.

One interesting thing is that Sage is already doing something analogous to your suggestion about tensoring in getting the "basis matrix", which led to the workaround Travis made. Then again,

Vector space of degree 3 and dimension 2 over Integer Ring

shouldn't even be legal to appear in Sage, in some sense...

[nbruin]

comment:13

Replying to @kcrisman:

Then what do you suggest? Since this is primarily useful for pedagogical purposes, perhaps we can just raise an error outside of QQ, RR, and friends.

Even there it's only wrt the standard inner product (i.e., if your basis is orthogonal) that this complement is orthogonal.

Wouldn't just complement work? I think that's a reasonably established term for direct cofactor.

And indeed, you should probably only offer this for vector spaces, i.e., when the base ring is a field.

[tscrim]

comment:14

First, if the ring is not a PID, there are many attributes that are not there anymore (ex. span()), so getting the attribute error is consistent with the rest of free modules.

As for them being inner product spaces, we have this in sage:

sage: F = FreeModule(Integers(8), 3)
sage: v = F([1, 2, 3])
sage: v*v
6
sage: F.inner_product_matrix()
[1 0 0]
[0 1 0]
[0 0 1]

so I think sage always assumes it has an inner product (although not necessarily a nice inner product).

For the

Vector space of degree 3 and dimension 2 over Integer Ring

that was a doctest error coming from me thinking I know what the output should be >_<.

Anyways, new version of the patch with the method now called complement(), removed perp(), and only works for vector spaces.

For patchbot:

Apply: trac_7522-perp-ts.patch

[kcrisman]

comment:15

Question for Jason and Rob: for teaching linear algebra, would it be useful to have complement but not perp or orthogonal_complement? I think that the standard basis is always kind of implicit in such situations; we aren't asking for complements with respect to other (orthogonal or not) bases with this function, or at least originally weren't.

[nbruin]

comment:16

Rather than testing if the base ring is a field, shouldn't you place the method on sage.modules.free_module.FreeModule_generic_field or something like that? The usual idea is to let inheritance take care of which methods are available rather than explicit argument checking wherever possible.

[tscrim]

comment:17

Attachment: trac_7522-perp-ts.patch.gz

Here I was looking for something called VectorSpace... Done. Now just waiting on a response from Rob or Jason.

[kcrisman]

comment:18

I've just discussed this with Rob and Jason at Sage Days 48. The consensus is that the solution here is acceptable.

Patchbot, apply: trac_7522-perp-ts.patch

[kcrisman]

Changed reviewer from Karl-Dieter Crisman to Karl-Dieter Crisman, Nils Bruin

[kcrisman]

Changed keywords from none to sd48

[kcrisman]

comment:19

I'm going to add an example pointing out that over a finite field this gives a complement which intersects the original subspace, which 3 people here say is fine (in the sense that it's not wrong, but we should just point out it's not what one might expect from the "usual" case). Nils, is it okay as long as we don't call it orthogonal?

[kcrisman]

comment:20

Okay, Travis and/or Nils and/or anyone else, is this okay? The terminology is really the issue here, but hopefully this will satisfy everyone.

Patchbot, apply trac_7522-perp-ts.patch and trac_7522-finite.patch

[tscrim]

comment:21

There's a small typo:

a a vector

once that is fixed, I'm fine with this being set to positive reivew (but I'm probably one of the less opinionated people on this). Feel free to do this on my behalf because I'm going to sleep now to be ready for more Sage Days 49. Hope the 48 is going well.

Travis

[kcrisman]

comment:22

Attachment: trac_7522-finite.patch.gz

Thanks, fixed.

Patchbot, apply trac_7522-perp-ts.patch and trac_7522-finite.patch

[kcrisman]

Changed reviewer from Karl-Dieter Crisman, Nils Bruin to Karl-Dieter Crisman, Nils Bruin, Jason Grout, Gregory Bard

[jdemeyer]

Merged: sage-5.11.beta3