# Can we generalize parity to partial permutations?

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

• 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? – Arthur Mar 5 '18 at 12:41
• @Arthur Yes, exactly. – FUZxxl Mar 5 '18 at 12:41
• For the sum of permutations to make sense, you ought also to require that $\pi(S'_\pi)$ is disjoint from $\sigma(S'_\sigma)$. – Arthur Mar 5 '18 at 13:27
• @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? – FUZxxl Mar 5 '18 at 14:03
• I would delete the "How" from the question title -- it should just be "Can we generalize...?" – Rahul Mar 5 '18 at 14:18

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.

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.

• 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...) – Arthur Mar 5 '18 at 14:38
• @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. – FUZxxl Mar 5 '18 at 14:41