4
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented May 7, 2010 at 11:29
  • $\begingroup$ Well, it's not very "nice" nor efficient, but I'll accept it, since it does give a fundamental domain. $\endgroup$
    – Dylan Thurston
    Commented May 7, 2010 at 17:43
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Isn't graph isomorphism NP-complete? How can there be a "quite fast" algorithm for that? $\endgroup$
    – Johannes Hahn
    Commented May 7, 2010 at 12:40
  • $\begingroup$ 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 $\endgroup$
    – David E Speyer
    Commented May 7, 2010 at 13:25
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Dylan Thurston
    Commented May 7, 2010 at 17:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .