5
$\begingroup$

Is there an easily definable projection $F$ from the orthogonal group $O(n)$ into the permutation group $S_n$, which has the following properties?

  1. $F(P_\sigma) = \sigma$ for all $\sigma \in S_n$

  2. $F^{-1}(\sigma)$ contains an open subset of $O(n)$ around $P_\sigma$

  3. $\mu(F^{-1}(\sigma)) = \mu(F^{-1}(\varphi))$ for all $\sigma, \varphi \in S_n$, where $\mu$ is the Haar measure on $O(n)$

  4. Optional: For any diagonal matrix $A$ the matrices $HAH^T$ and $P_{F(H)} \, A \, P_{F(H)}^T$ are in some sense close to each other. I realize this doesn't make much sense, since one is diagonal and the other is not, but maybe there is a projection where the diagonal entries of $HAH^T$ and $P_{F(H)} \, A \, P_{F(H)}^T$ are somewhat close to each other.

Any help is much appreciated.

PS. I would also be interested in the same setting with $U(n)$ instead of $O(n)$.

$\endgroup$
4
  • 11
    $\begingroup$ Does it really have to be defined for all $g \in O(n)$, or are you happy working up to a set of measure zero? If the latter, send any $g \in O(n)$ to the permutation $\sigma$ which maximizes $\sum_j g_{\sigma(j) j}$, discarding the matrices where ties occur. This is even rapidly computable, since it is an instance of maximum weight matching en.wikipedia.org/wiki/Maximum_weight_matching . $\endgroup$ Oct 17, 2022 at 14:58
  • $\begingroup$ Thank you! Up to a measure zero is fine. $\endgroup$
    – Tardis
    Oct 17, 2022 at 17:26
  • 3
    $\begingroup$ Using a Voronoi tiling you get 1,2,3 for free (define the projection arbitrarily on boundaries. However it's easily definable but maybe not easily computable. No idea about 4. $\endgroup$
    – YCor
    Oct 17, 2022 at 17:26
  • 1
    $\begingroup$ For an orthogonal matrix, is there such a thing as the permutation matrix that is closest to it? (If so, that should do it.) $\endgroup$ Oct 17, 2022 at 20:34

2 Answers 2

3
$\begingroup$

Here is a natural map $F\colon O(n)\to S_n$ which does not have the specified properties, because I did not read them correctly at first. Nonetheless, it may be of interest, if only as an example of something to avoid.

The idea is to use the Bruhat decomposition $GL_n(\mathbb{R})=\coprod_{\sigma\in S_n}B\sigma B$.

In more detail, consider two flags $0=U_0<U_1<\dotsb<U_n=\mathbb{R}^n$ and $0=V_0<V_1<\dotsb<V_n=\mathbb{R}^n$. For $0\leq i,j<n$ put $$ Q_{ij} = \frac{U_i\cap V_j}{(U_i\cap V_{j-1})+(U_{i-1}\cap V_j)} \simeq \frac{U_{i-1}+(U_i\cap V_j)}{U_{i-1}+(U_i\cap V_{j-1})} \simeq \frac{(U_i\cap V_j)+V_{j-1}}{(U_{i-1}\cap V_j)+V_{j-1}} $$ One can check that there is a unique permutation $\sigma$ such that $Q_{ij}=0$ unless $i=\sigma(j)$ in which case $Q_{ij}\simeq\mathbb{R}$. (Indeed, the third description of $Q_{ij}$ makes it clear that there is a unique function $\sigma$ with this property, the second description makes it clear that there is a unique function $\tau$ such that $Q_{ij}=0$ unless $j=\tau(i)$, and then we conclude that $\sigma$ and $\tau$ are inverse to each other and so must be permutations.)

Now consider an element $g\in O(n)$. Let $U_i$ be the span of $e_1,\dotsc,e_i$, and let $V_i$ be the span of $ge_1,\dotsc,ge_i$. Let $F(g)$ be the permutation corresponding to this pair of flags. This is a fairly natural map $O(n)\to S_n$ that is the identity on $S_n$. Everything works in essentially the same way over $\mathbb{C}$.

$\endgroup$
1
$\begingroup$

I give a positive answer when $n=3$. I work with $O(\mathbb{R}^3)$ (orthogonal endomorphisms) rather than $O(n)$ (orthogonal matrices).

I define $\mu$-almost surely $F$ as follows.

Given a reflexion $s$ with regard to $D^\perp$, set $F(s)$ equal to $(1~2)$ or $(1~3)$ or $(2~3)$ according the closer line to $D$ (in terms of angles between two lines) is $\mathbb{R}(e_1-e_2)$ or $\mathbb{R}(e_1-e_3)$ or $\mathbb{R}(e_2-e_3)$.

Given a rotation $r$ with axis $D$, call $u$ the unit vector of $D$ which closer to $e_1+e_2+e_3$, and $\theta \in ]-\pi,\pi[$ the angle (oriented by the vector $u$). Set $F(s)$ equal to $(3~2~1)$ or Id or $(1~2~3)$ according $-\pi < \theta < -\alpha$ or $-\alpha < \theta < \alpha$ or $\alpha < \theta < \pi$. The real number $\alpha$ is chosen in such a way that each possibility for a randomly chosen rotation occurs with probability $1/3$.

Since the distribution of $\theta$ admits the density $\theta \mapsto (1-\cos\theta)/(2\pi)$ over $]-\pi,\pi[$, the real number $\alpha$ is given by $(\alpha - \sin\alpha)/(2\pi)= 1/6$. Since $0 < \alpha <2\pi/3$, condition 1 holds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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