2
$\begingroup$

A partial permutation $\pi$ is a permutation of the elements of some finite set $S$ with the location of all elements except those in some set $S'\subseteq S$ unknown. For example, a partial permutation of the subset $\{1,2,3\}$ to $\{1,2,3,4,5,6\}$ is $\pi=(\lozenge,\lozenge,3,\lozenge,1,2)$ where $\lozenge$ denotes a spot occupied by an unknown element.

Given two partial permutations $\pi$ and $\sigma$ for the same $S$ but disjoint $S'_\pi$ and $S'_\sigma$ as well as disjoint $\pi(S'_\pi)$ and $\sigma(S'_\sigma)$, we furthermore define their sum to be a partial permutation $\pi+\sigma$ such that $S'_{\pi+\sigma}=S'_\pi\cup S'_\sigma$ and $\pi+\sigma$ agrees with $\pi$ and $\sigma$ on the location of all elements the location is known of. A partial permutation $\pi$ is defined to be full if it accounts for the location of all elements, i.e. $S'_\pi=S$.

I would like to know if it is possible to generalize the parity of a permutation $\def\sgn{{\rm sgn}}\sgn(\pi)$ such that it agrees with the conventional parity of a permutation for full permutations and $\sgn(\pi+\sigma)=\sgn(\pi)\sgn(\sigma)$ for disjoint $S'_\pi$ and $S'_\sigma$.

$\endgroup$
  • $\begingroup$ When you write $\pi=(\lozenge,\lozenge,3,\lozenge,1,2)$, do you mean that $\pi(1) = 5, \pi(2) = 6, \pi(3) = 3$ while the other values of $\pi$ on $S$ are unknown / undefined? $\endgroup$ – Arthur Mar 5 '18 at 12:41
  • $\begingroup$ @Arthur Yes, exactly. $\endgroup$ – FUZxxl Mar 5 '18 at 12:41
  • $\begingroup$ For the sum of permutations to make sense, you ought also to require that $\pi(S'_\pi)$ is disjoint from $\sigma(S'_\sigma)$. $\endgroup$ – Arthur Mar 5 '18 at 13:27
  • $\begingroup$ @Arthur I added a proof idea to show that this can't be done but I'm a bit stuck towards the ends. Any idea? $\endgroup$ – FUZxxl Mar 5 '18 at 14:03
  • $\begingroup$ I would delete the "How" from the question title -- it should just be "Can we generalize...?" $\endgroup$ – Rahul Mar 5 '18 at 14:18
1
$\begingroup$

Here is a contradiction in the case of $3$ elements, following FUZxxl's answer post.

Let's say we can assign $\def\sgn{{\rm sgn}}\sgn(x_k, k)$ in a consistent manner. Let's put those assignments in a $3\times 3$ matrix where $a_{ij}$ is $\sgn(i, j)$. For this to give the correct sign to all full permutations, we would need the following relations to hold: $$ a_{11}a_{22}a_{33} = a_{12}a_{23}a_{31} = a_{13}a_{21}a_{32} = 1\\ a_{12}a_{21}a_{33} = a_{23}a_{32}a_{11} = a_{13}a_{31}a_{22} = -1 $$ I will show that this is, in fact, impossible.

I will divide into two cases: Either all of $a_{ii}$ are $1$, or exactly two of them are $-1$.

First case: The second relation above gives $a_{13} = -a_{31}, a_{23} = -a_{32}$ and $a_{12} =-a_{21}$. But inserting that into the first relation gives $a_{12}a_{23}(-a_{13}) = (-a_{12})(-a_{23})a_{13}$ which is a contradiction.

Second case: two of the $a_{ii}$ are $-1$. WLOG, assume that it's $a_{22}$ and $a_{33}$. The second relation then gives $a_{31} = a_{13}, a_{23} = -a_{32}$ and $a_{12} = a_{21}$. But then the first relation gives us $a_{12}a_{23}a_{13} = a_{13}a_{12}(-a_{23})$ which is again a contradiction.

$\endgroup$
1
$\begingroup$

I believe no such generalisation exists. Here is a proof idea by contradiction:

Suppose $\def\sgn{{\rm sgn}}\sgn(\pi)$ is such a parity such that $\sgn(\pi+\sigma)=\sgn(\pi)\sgn(\sigma)$. We can use this to represent the parity of a full permutation as a product of parities of partial permutations such that each partial permutation accounts for the location of a single element:

$$\sgn(x_1,x_2,\ldots,x_n)=\sgn(x_1,\lozenge,\ldots,\lozenge)\sgn(\lozenge,x_2,\ldots,\lozenge)\cdots\sgn(\lozenge,\lozenge,\ldots,x_n)$$

Let us now define

$$\sgn_n(x_k,k)=\sgn\underbrace{(\lozenge,\ldots,x_k,\ldots,\lozenge)}_{\mbox{$n$ elements}}$$

where $x_k$ is at location $k$ and we can write

$$\sgn(x_1,x_2,\ldots,x_n)=\sgn_n(x_1,1)\sgn_n(x_2,2)\cdots\sgn_n(x_n,n).$$

Now I'm pretty sure that the sign of a permutation cannot be expressed as a product of functions in the locations of individual elements, but I am not quite sure how to show that. My idea is to use that transposing the elements at indices $i$ and $j$ must flip the sign of exactly one of them but I'm not sure how to build a contradiction from that.

$\endgroup$
  • $\begingroup$ I worked out a contradiction for $n = 3$, see my answer (assuming the signs are $\pm 1$, and none of them are complex or anything...) $\endgroup$ – Arthur Mar 5 '18 at 14:38
  • $\begingroup$ @Arthur Thank you for your answer! Now it might be very interesting if you could assign a complex-valued signum to partial permutations. Though, I have no idea how this should work. $\endgroup$ – FUZxxl Mar 5 '18 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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