Inverses

Try to visualize in your mind the graph of a function $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$. We can think of this as either a point of points $(i,f(i))$, $i=1,2,...,n$, or as a bar graph. In any case, we can look at this graph of $f$ and determine (a) if $f$ is injective, (b) if $f$ is surjective, (c) the inverse $f^{-1}$, if it exists. How? Well, from the graph of $f$ we can determine the image $f(\mathbb{Z}_n)$ and this determines if $f$ is surjective or not. The inverse exists only if f is injective (hence, in our case, surjective). Its graph is determined by reflecting the graph of f about the diagonal, $x=y$.

Lemma 4.3.1   The following statements are equivalent: (1) $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ is injective, (2) $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ is surjective, (3) $\vert f(\mathbb{Z}_n)\vert=\vert\mathbb{Z}_n\vert$.

proof: The equivalence of the first two statements is left to the interested reader (hints: first show (1) imples (2) using reductio ad absurdum, then show (2) imples (1), again using reductio ad absurdum). (2) is equivalent to (3), by definition of surjectivity. $\Box$

Example 4.3.2   The inverse of

$$\left( \begin{array}{ccc} 1&2&3\\ 3&1&2 \end{array} \right)$$

is

$$\left( \begin{array}{ccc} 1&2&3\\ 2&3&1 \end{array} \right)$$

There are two more commonly used ways of expressing a permutation. The first is the ``matrix notation":

Definition 4.3.3   To a permutation $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$, given by

$$f= \left( \begin{array}{cccc} 1&2&...&n\\ f(1)& f(2)&... &f(n) \end{array} \right)$$

we associate to it the matrix $P(f)$ of $0's$ and $1's$ defined as follows: the $ij$-th entry of $P(f)$ is $1$ if $j=f(i)$ and is 0 otherwise.

Definition 4.3.4   A square matrix which has exactly one 1 per row and per column (as $P(f)$ does) is called a permutation matrix .

Lemma 4.3.5   There are $n!$ distinct $n\times n$ permutation matrices and there are $n!$ distinct permutations of the set $\{1,2,...,n\}$.

Example 4.3.6   The matrix of the permutation f given by

$$f= \left( \begin{array}{ccc} 1&2&3\\ 2& 1& 3 \end{array} \right)$$

is

$$P(f)= \left( \begin{array}{ccc} 0&1&0\\ 1& 0& 0\\ 0&0&1 \end{array} \right)$$

Note that matrix multiplication gives

$$\left( \begin{array}{ccc} 0&1&0\\ 1& 0& 0\\ 0&0&1 \... ...eft( \begin{array}{c} 2\\ 1\\ 3 \end{array} \right)$$

from which we can recover the $2\times 3$ array. (b) If

$$h= \left( \begin{array}{cccc} 1&2&3&4\\ 2&3&1&4 \end{array} \right),$$

then

$$P(h)=\left( \begin{array}{cccc} 0&1&0&0\\ 0& 0& 1&0\\ 1&0&0&0\\ 0&0&0&1 \end{array} \right).$$

Theorem 4.3.7   If $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ is a permutation then

$$(a)\ \ \ \ \ P(f) \left( \begin{array}{c} 1\\ 2\\ ... ...c} f(1)\\ f(2)\\ \vdots\\ f(n) \end{array} \right)$$

Furthermore, the inverse of the matrix of the permutation is the matrix of the inverse of the permutation: (b) $P(f)^{-1} = P(f^{-1})$, and the matrix of the product is the product of the matrices: (c) $P(fg)=P(f)P(g)$.

proof: If $\vec{v}$ is the column vector with entries $v_1,v_2,...,v_n$ (the $v_i$ are arbitrary real numbers) then $P(f)\vec{v}$ is the column vector whose $i^{th}$ coordinate is equal to $v_j$ if $f$ sends $i$ to $j$, by definition of $P(f)$. Since, in this case, $j=f(i)$ (here we write $f(i)$ to denote the image of $i$ under the permutation $f$, even though $i$ really gets plugged into $f$ on the left), this implies that $P(f)\vec{v}$ is the column vector with entries $v_{f(1)},v_{f(2)},...,v_{f(n)}$. This proves (a). Note (b) is a consequence of (c) so we need only prove (c). We compute $P(fg)\vec{v}$ and $P(f)P(g)\vec{v}$. By the same reasoning as in (a), we find that the $i^{th}$ coordinate of $P(fg)\vec{v}$ is $v_{(fg)(i)}$. Similarly, the $i^{th}$ coordinate of $P(g)\vec{v}$ is $v'_i=v_{g(i)}$. Therefore, the $i^{th}$ coordinate of $P(f)(P(g)\vec{v})$ is $v'_{f(i)}=v_{g(f(i))}=v_{(fg)(i)}$. This implies $P(fg)\vec{v}=P(f)P(g)\vec{v}$. Since the $v_i$ were arbitrary real numbers, this implies the theorem. $\Box$ The matrix can be determined from the graph of the function $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ as follows: with $x$ and $y$ integers between $1$ and $n$ inclusive, let $P(f)_{ij}=1$ if and only if $(i,j)$ is a plotted point in the graph of $f$, and let $P(f)_{ij}=0$, otherwise. The resulting $n\times n$ array is the matrix $P(f)$.

Exercise 4.3.8   Let

$$f= \left( \begin{array}{ccc} 1&2&3\\ 2&1&3 \end{array... ...( \begin{array}{ccc} 1&2&3\\ 2&3&1 \end{array} \right),$$

(a) Show $f=f^{-1}$, $g=g^{-1}$, $h=fg$. (b) Show,

$$P(g)=\left( \begin{array}{ccc} 0&0&1\\ 0& 1& 0\\ 1&0&... ...ay}{ccc} 0&1&0\\ 0& 0& 1\\ 1&0&0 \end{array} \right).$$

(c) Show, using a direct matrix calculation, that $P(f)P(g)=P(fg)=P(h)$ and $P(h^{-1})=P(g^{-1}f^{-1}) =P(g^{-1})P(f^{-1})=P(g)P(f)$.

Exercise 4.3.9   Prove Lemma 4.3.5 using the multiplication counting principle from the section on counting in the previous chapter.

Exercise 4.3.10   Graph and determine the inverses of the following permutations:

$$(a)\ \ \ \ \ f= \left( \begin{array}{ccc} 1&2&3\\ 2& 1& 3 \end{array} \right)$$

$$(b)\ \ \ \ \ f= \left( \begin{array}{cccc} 1&2&3&4\\ 2& 3& 4& 1 \end{array} \right)$$

$$(c)\ \ \ \ \ f= \left( \begin{array}{ccccc} 1&2&3&4&5\\ 2&1&5&3&4 \end{array} \right)$$