Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a nice fundamental domain for the symmetric group $S_n$ acting on the Grassmannian of $k$-planes in $\mathbb{R}^n$? (The action of $S_n$ is by permuting the coordinates, of course.)

I'm looking for a way to efficiently test whether two subspaces of $\mathbb{R}^n$ are related by permuting and/or negating the coordinates. (So I really care not about $S_n$, but about $(\mathbb{Z}/2)^n \rtimes S_n$, the Weyl group of the B/C series.) I'm somewhat skeptical this is easy, but has anyone thought about it?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Here is a suggestion that ought to work generically.

A general point on $\operatorname{Gr}(k,n)$ corresponds to the graph of a linear transformation $\mathbb{R}^k \to \mathbb{R}^{n-k}$, and hence to an $(n-k) \times k$ matrix. In its $S_n$-orbit, there is one point that is distinguished by the following requirements (assuming that ties do not occur):

1) The maximum of the absolute values of the entries of the matrix is as large as possible (this determines a $k$-element subset of distinguished coordinates).

2) If $a_i$ is the maximum of the absolute values of the entries in the $i$-th row, then $a_1<a_2<\cdots<a_{n-k}$.

3) If $b_j$ is the maximum of the absolute values of the entries in the $j$-th column, then $b_1<b_2<\cdots<b_k$.

You can compute it by first trying all $k$-element subsets, and then permuting the rows and columns of the $(n-k) \times k$ matrix as needed. (Whether this is efficient enough for you will depend on the size of $n$ and $k$.)

If you also want to allow negating the coordinates, then you can choose the sign changes in a unique way (up to an overall sign change) so that all entries in the first row and first column are positive (assuming that the original point is general enough that these entries are nonzero).

share|improve this answer
    
An alternative first step might be to require that the corresponding Plucker coordinate be maximal. That way, you compute $\binom{n}{k}$ Plucker coordinates, rather than $\binom{n}{k} k (n-k)$ matrix entries. Not a big improvement, though. –  David Speyer May 7 '10 at 11:29
    
Well, it's not very "nice" nor efficient, but I'll accept it, since it does give a fundamental domain. –  Dylan Thurston May 7 '10 at 17:43

An observation: If you ask for an exact decision procedure for whether to points of $G(k,n)$ are in the same $S_n$ orbit, this problem includes the problem of bipartite graph isomorphism. Namely, if $A$ and $B$ are the adjacency matrices of bipartite graphs on $k$ white and $n-k$ black vertices, then the row spans of $$\begin{pmatrix} 2 \cdot \mathrm{Id} & A \end{pmatrix} \ \mbox{and} \ \begin{pmatrix} 2 \cdot \mathrm{Id} & B \end{pmatrix}$$ are in the same orbit if and only if the graphs are isomorphic.

Since you really care about generic points of $G(k,n)$, and since graph isomorphism is quite fast in practice, this shouldn't be considered to rule out the possibility of a good practical algorithm, but it does rule out certain strategies.

share|improve this answer
    
Isn't graph isomorphism NP-complete? How can there be a "quite fast" algorithm for that? –  Johannes Hahn May 7 '10 at 12:40
    
Graph isomorphism is not expected to be NP-complete; if it is, the polynomial hierarchy collapses. See qwiki.stanford.edu/wiki/Complexity_Zoo:G#gi –  David Speyer May 7 '10 at 13:25
1  
I knew a different reduction from graph isomorphism, but this is an interesting one. (And I'm not only interested in generic points; a fundamental domain should include edge cases.) –  Dylan Thurston May 7 '10 at 17:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.