Opened 14 years ago

Closed 13 years ago

#1323 closed enhancement (fixed)

[with patch, positive review] generate all subspaces of a vector space/projective space

Reported by: jason Owned by: rlm
Priority: major Milestone: sage-3.2
Component: linear algebra Keywords:
Cc: mhansen Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

From Chris Godsil's wishlist:

>>> Sometimes I want to construct graphs whose vertices are subspaces of a
>>> vector space over a finite field. It could be useful to have a
>>> generator for
>>> the lines of the associated projective space, or even subspaces of a given
>>> dimension.
>> Is there an easy way to generate all of the subspaces of a vector space
>> already in Sage, maybe restricted to a particular dimension, from the
>> original vector space?
> Maybe make a ticket for this?

Attachments (1)

trac_1323-subspaces.patch (5.6 KB) - added by rlm 13 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 13 years ago by rlm

Here is a method for iterating over dimension k subspaces of a space of dimension n:

First, suppose that F is a finite field, and our ambient vector space is just F^n.

Any subspace of dimension k is uniquely described as the rowspace of a k x n matrix in reduced row echelon form. This is determined by which columns are pivots, and what the entries of the remaining positions are. Thus it suffices to iterate over k-subsets of [0..n-1], declaring those to be the pivots. Certain entries must be zero, according to row-reduced form, and the rest can be arbitrary elements of F.

Thus, for each k-subset of [0..n-1], call it [j_1, ..., j_k], construct a matrix with pivots as described by the j_i. For the m entries that are nonzero, construct a vector space of dimension m, and iterate over it, using the resulting tuples to fill in the matrix.

Voila!

I don't know about projective space, though.

comment:2 Changed 13 years ago by rlm

Oh wait, to get projective space, just shift the dimension by one, duh...

comment:3 Changed 13 years ago by rlm

  • Owner changed from was to rlm
  • Status changed from new to assigned

comment:4 Changed 13 years ago by rlm

  • Cc mhansen added
  • Summary changed from generate all subspaces of a vector space/projective space to [with patch, needs review] generate all subspaces of a vector space/projective space

Changed 13 years ago by rlm

comment:5 Changed 13 years ago by wdj

  • Summary changed from [with patch, needs review] generate all subspaces of a vector space/projective space to [with patch, positive review] generate all subspaces of a vector space/projective space

Applies cleanly and passes sage -testall. Looks good. GAP has this very useful function and now Sage does. Thanks Robert!

comment:6 Changed 13 years ago by mabshoff

  • Milestone changed from sage-wishlist to sage-3.2
  • Resolution set to fixed
  • Status changed from assigned to closed

Merged in Sage 3.2.alpha0

Note: See TracTickets for help on using tickets.