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, .
(1) is injective,
(2) is surjective,
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.
There are two more commonly used ways of expressing a permutation. The first is the ``matrix notation":
we associate to it the matrix of and defined as follows: the -th entry of is if and is 0 otherwise.
Note that matrix multiplication gives
from which we can recover the array.
Furthermore, the inverse of the matrix of the permutation is the matrix of the inverse of the permutation:
and the matrix of the product is the product of the matrices:
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 .
(a) Show , , .
(c) Show, using a direct matrix calculation, that and .