Opened 10 years ago

Closed 6 years ago

#7522 closed enhancement (fixed)

Implement orthogonal complement in vector spaces

Reported by: kcrisman Owned by: was
Priority: major Milestone: sage-5.11
Component: linear algebra Keywords: sd48
Cc: jason, rbeezer Merged in: sage-5.11.beta3
Authors: Jason Grout, Travis Scrimshaw Reviewers: Karl-Dieter Crisman, Nils Bruin, Jason Grout, Gregory Bard
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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: trac_7522-perp-ts.patch and trac_7522-finite.patch

Attachments (4)

7522-perp.patch (2.0 KB) - added by jason 9 years ago.
7522-review.patch (1.3 KB) - added by jason 9 years ago.
apply on top of previous patches
trac_7522-perp-ts.patch (2.2 KB) - added by tscrim 6 years ago.
trac_7522-finite.patch (1.5 KB) - added by kcrisman 6 years ago.

Download all attachments as: .zip

Change History (29)

Changed 9 years ago by jason

comment:1 follow-up: Changed 9 years ago by jason

  • Cc rbeezer added
  • Status changed from new to needs_review

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

comment:2 in reply to: ↑ 1 ; follow-up: Changed 9 years ago by kcrisman

Replying to jason:

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?

Changed 9 years ago by jason

apply on top of previous patches

comment:3 in reply to: ↑ 2 Changed 9 years ago by jason

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?

comment:4 Changed 9 years ago by kcrisman

  • Status changed from needs_review to needs_work

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:
[]

comment:5 Changed 9 years ago by kcrisman

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()

comment:6 Changed 9 years ago by kcrisman

  • Reviewers set to Karl-Dieter Crisman

comment:7 Changed 6 years ago by tscrim

  • Authors changed from Jason Grout to Jason Grout, Travis Scrimshaw
  • Status changed from needs_work to needs_review

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.

comment:8 Changed 6 years ago by tscrim

  • Description modified (diff)

For patchbot:

Apply: trac_7522-perp-ts.patch

comment:9 Changed 6 years ago by kcrisman

  • Status changed from needs_review to needs_work

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.

comment:10 Changed 6 years ago by kcrisman

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

comment:11 follow-up: Changed 6 years ago by nbruin

  • 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).

comment:12 in reply to: ↑ 11 ; follow-up: Changed 6 years ago by kcrisman

  • 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...

comment:13 in reply to: ↑ 12 Changed 6 years ago by nbruin

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.

comment:14 Changed 6 years ago by tscrim

  • Status changed from needs_work to needs_review

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

Last edited 6 years ago by tscrim (previous) (diff)

comment:15 Changed 6 years ago by kcrisman

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.

comment:16 Changed 6 years ago by nbruin

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.

Changed 6 years ago by tscrim

comment:17 Changed 6 years ago by tscrim

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

comment:18 Changed 6 years ago by kcrisman

  • Keywords sd48 added
  • Reviewers changed from Karl-Dieter Crisman to Karl-Dieter Crisman, Nils Bruin

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

comment:19 Changed 6 years ago by kcrisman

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?

comment:20 Changed 6 years ago by kcrisman

  • Description modified (diff)

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

comment:21 Changed 6 years ago by tscrim

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

Changed 6 years ago by kcrisman

comment:22 Changed 6 years ago by kcrisman

Thanks, fixed.

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

comment:23 Changed 6 years ago by kcrisman

  • Reviewers changed from Karl-Dieter Crisman, Nils Bruin to Karl-Dieter Crisman, Nils Bruin, Jason Grout, Gregory Bard
  • Status changed from needs_review to positive_review

comment:24 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:25 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.11.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.