Opened 15 years ago

Closed 14 years ago

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

Reported by: Owned by: Jason Grout Robert Miller major sage-3.2 linear algebra Mike Hansen N/A

### 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?
```

### comment:1 Changed 14 years ago by Robert Miller

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 14 years ago by Robert Miller

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

### comment:3 Changed 14 years ago by Robert Miller

Owner: changed from William Stein to Robert Miller new → assigned

### comment:4 Changed 14 years ago by Robert Miller

Cc: Mike Hansen added generate all subspaces of a vector space/projective space → [with patch, needs review] generate all subspaces of a vector space/projective space

### comment:5 Changed 14 years ago by David Joyner

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 Michael Abshoff

Milestone: sage-wishlist → sage-3.2 → fixed assigned → closed

Merged in Sage 3.2.alpha0

Note: See TracTickets for help on using tickets.