Involution on set with odd cardinality fix point...

Question

I believe this questions wasn't raised yet. I am doing my homework and I am supposed to prove that if $X$ is a set of odd cardinality, then every involution has a Fix point...
Now, by making examples it becomes fairly obvious that it has to be like that.

However, I am strugling to find the formal proof and I am looking for a few hints, here are my ideas :

• I was thinking that you can simplify the problem by considering as Involutions in $\mathbb{Z}/|X|\mathbb{Z}$.

• Using Group Theory and the Set of all permutation functions.

• Using Induction.

• Using that even Sets do not need fix points.

Could you tell me wether or not one of these paths leads to the right solution ?

The most promising lead i had found was: If $X$ has Cardinality $n$, then you have two iterations to boomerang your element $x_{k}$. One way of doing is : $\phi(k) = k + \frac{n}{2} \mod(n)$
I feel like this is the only way to do it... But i don't know how to justify that all involutions are of that form (with some $\lambda n$). And since $2|n$ iff n is even. There must be some k that isn't thrown around and is just kept at it's place...
But it isn't formal, and maybe just wrong :/

Answer 1

Sometimes a good notation makes all the difference.

Think about labelling the $n$ elements of the set with the numbers $1, 2,3,\ldots,n$.

Involutions are a particular kind of permutation. One of the most common notations for conveying a permutation is cycle notation, in which, e.g.

$$(1,3,2) (4)$$ corresponds to the permutation function $$f(1) = 3$$ $$f(2) = 1$$ $$f(3) = 2$$ $$f(4) = 4$$

Here the fact that $4$ is a fixed point is immediately apparent in cycle notation: it's all alone in it's cycle. From the definition, can you characterize what involutions look like in cycle notation? In particular, if an involution has no fixed points, what are the sizes of its cycles?

Answer 2

By definition, the function $f$ sends each $x\in X$ to some $y \in X$ and it satisfies $f(f(x))=x$ for all $x \in X$.

Let us define the following relation on $X$ - $x \cong y$ if and only if $f(x)=y$. It's easy to see that the relation is symmetric because $f$ is an involution. It's also clear that each member of $X$ can only satisfy this relation with only one element of $X$ (because $f$ is a function). This tells us that the relation lets us divide $X$ into disjoint sets - each sets contains some $x \in X$ and its image under $f$ (sort of like an equivalence class, even though this is not a true equivalence relation). Now assume $f$ has no fixed points. This means that each such set contains exactly two elements - the two that are each other's image. But if $X$ can be divided into such pairs, $X$ can't be of odd cardinality.

This is not a full proof (you need to specify more on why you can divide $X$ into such disjoint pairs), but this is the general direction that comes to mind. Hope this helps.

Answer 3

Suppose that an involution has no fixed points.

Define $S_i=\{x_i,f(x_i)\}$ for every $x_i\in X$. Because $f$ has no fixed points, $|S_i|=2$.

I claim that if $S_i\not=S_j$, they are disjoint sets.

Indeed of they weren’t disjoint, we have $4$ possible intersections but none of them is permitted:

1. $x_i=x_j\Rightarrow f(x_i)=f(x_j)$. But this means $S_i=S_j$, which is absurd!

2. $x_i=f(x_j)\Rightarrow f(x_i)=x_j$. But this means $S_i=S_j$, which is absurd!

3. $f(x_i)=x_j\Rightarrow x_i=f(x_j)$. But this means $S_i=S_j$, which is absurd!

4. $f(x_i)=f(x_j) \Rightarrow x_i=x_j$. But this means $S_i=S_j$, which is absurd!

So far we have that the $S_i$ are either the same, or completely different. Remove identical $S_i$ sets to write a disjoint union:

$$X=\cup_{x_i \in X}S_i=\dot{\cup}_{x_{i_j}}S_{i_j}$$

But then $|X|=\sum_j |S_{i_j}|$ which is even! So the only way for an involution not to have fixed point is for $X$ to be even.