Opened 15 years ago
Closed 14 years ago
#1323 closed enhancement (fixed)
[with patch, positive review] generate all subspaces of a vector space/projective space
Reported by: | Jason Grout | Owned by: | Robert Miller |
---|---|---|---|
Priority: | major | Milestone: | sage-3.2 |
Component: | linear algebra | Keywords: | |
Cc: | Mike Hansen | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
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)
Change History (7)
comment:1 Changed 14 years ago by
comment:2 Changed 14 years ago by
Oh wait, to get projective space, just shift the dimension by one, duh...
comment:3 Changed 14 years ago by
Owner: | changed from William Stein to Robert Miller |
---|---|
Status: | new → assigned |
comment:4 Changed 14 years ago by
Cc: | Mike Hansen added |
---|---|
Summary: | generate all subspaces of a vector space/projective space → [with patch, needs review] generate all subspaces of a vector space/projective space |
Changed 14 years ago by
Attachment: | trac_1323-subspaces.patch added |
---|
comment:5 Changed 14 years ago by
Summary: | [with patch, needs review] generate all subspaces of a vector space/projective space → [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 14 years ago by
Milestone: | sage-wishlist → sage-3.2 |
---|---|
Resolution: | → fixed |
Status: | assigned → closed |
Merged in Sage 3.2.alpha0
Note: See
TracTickets for help on using
tickets.
Here is a method for iterating over dimension
k
subspaces of a space of dimensionn
:First, suppose that
F
is a finite field, and our ambient vector space is justF^n
.Any subspace of dimension
k
is uniquely described as the rowspace of ak 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 overk
-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 ofF
.Thus, for each
k
-subset of[0..n-1]
, call it[j_1, ..., j_k]
, construct a matrix with pivots as described by thej_i
. For them
entries that are nonzero, construct a vector space of dimensionm
, and iterate over it, using the resulting tuples to fill in the matrix.Voila!
I don't know about projective space, though.