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: |
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 13 years ago by
comment:2 Changed 13 years ago by
Oh wait, to get projective space, just shift the dimension by one, duh...
comment:3 Changed 13 years ago by
- Owner changed from was to rlm
- Status changed from new to assigned
comment:4 Changed 13 years ago by
- 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
comment:5 Changed 13 years ago by
- 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
- 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.
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.