s
Chapter 5 Review
473
11. Input: The number of elements in two finite sets
S and T
Output: The number of functions from S to T, the
number of one-to-one functions from S to T (or
an indication that none exist), and the number of
onto functions from S to T (or an indication that
none exist)
12. Input: Two lists of ordered pairs representing functions f and g from S to S
Output: List of ordered pairs representing the composition function g + f
13. Input: The elements in a finite set S and two lists
that represent (in cycle form) permutations f and
g on S
Output: One or more lists that represent the composition function g + f in cycle or product-of-cycle
form
14. Input: The number of elements in a finite set S
Output: The number of derangements on S
15. Input: n and the entries in two n × n matrices a
and b
Output: Sum a + b and products a # b and b # a
16. Input: Dimensions of a matrix a and the entries
in a
Output: a
T
(see Exercise 15 in Section 5.7)
17. Input: The augmented matrix of a system of n linear equations in n unknowns with a unique set of
n solutions
Output: The n solutions, determined by using
Gaussian elimination
18. The determinant of an n × n matrix can be used
in solving systems of linear equations, as well
as for other purposes. The determinant of a can
be defined in terms of minors and cofactors. The
minor of element a ij is the determinant of the
(n − 1) × (n − 1) matrix obtained from a by
crossing out the elements in row i and column j;
denote this minor by M ij . The cofactor of element
a ij , denoted by C ij , is defined by
C ij = (−1)
i+j
M ij
The determinant of a is computed by multiplying
all the elements in some fixed row of a by their
respective cofactors and summing the results. For
example, if the first row is used, then the determinant of a is given by
∙
n
k=1
(a 1k )(C 1k )
Write a program that, when given n and the entries
in an n × n array a as input, computes the determinant of a. Use a recursive algorithm.