Inverses

Try to visualize in your mind the graph of a function . We can think of this as either a point of points , , or as a bar graph. In any case, we can look at this graph of and determine

(a) if is injective,

(b) if is surjective,

(c) the inverse , if it exists.

How? Well, from the graph of we can determine the image and this determines if 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, .

Lemma 4.3.1   The following statements are equivalent:

(1) is injective,

(2) is surjective,

(3) .

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.

Example 4.3.2   The inverse of

is

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

Definition 4.3.3   To a permutation , given by

we associate to it the matrix of and defined as follows: the -th entry of is if and is 0 otherwise.

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

Lemma 4.3.5   There are distinct permutation matrices and there are distinct permutations of the set .

Example 4.3.6   The matrix of the permutation f given by

is

Note that matrix multiplication gives

from which we can recover the array.

(b) If

then

Theorem 4.3.7   If is a permutation then

Furthermore, the inverse of the matrix of the permutation is the matrix of the inverse of the permutation:

(b) ,

and the matrix of the product is the product of the matrices:

(c) .

proof: If is the column vector with entries (the are arbitrary real numbers) then is the column vector whose coordinate is equal to if sends to , by definition of . Since, in this case, (here we write to denote the image of under the permutation , even though really gets plugged into on the left), this implies that is the column vector with entries . This proves (a).

Note (b) is a consequence of (c) so we need only prove (c). We compute and . By the same reasoning as in (a), we find that the coordinate of is . Similarly, the coordinate of is . Therefore, the coordinate of is . This implies . Since the were arbitrary real numbers, this implies the theorem.

The matrix can be determined from the graph of the function as follows: with and integers between and inclusive, let if and only if is a plotted point in the graph of , and let , otherwise. The resulting array is the matrix .

Exercise 4.3.8   Let

(a) Show , , .

(b) Show,

(c) Show, using a direct matrix calculation, that and .

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:

david joyner 2008-04-20