Page 194 - 35Linear Algebra

194 Determinants

3. Let σ −1 denote the inverse permutation of σ. Suppose the function
f : {1, 2, 3, 4} → R. Write out explicitly the following two sums:

X X
−1
f σ(s) and f σ (s) .
σ σ
What do you observe? Now write a brief explanation why the following
equality holds
X X −1
F(σ) = F(σ ) ,
σ σ
where the domain of the function F is the set of all permutations of n
objects.

4. Suppose M = LU is an LU decomposition. Explain how you would
efficiently compute det M in this case. How does this decomposition
allow you to easily see if M is invertible?

5. In computer science, the complexity of an algorithm is (roughly) com-
puted by counting the number of times a given operation is performed.
Suppose adding or subtracting any two numbers takes a seconds, and
multiplying two numbers takes m seconds. Then, for example, com-
puting 2 · 6 − 5 would take a + m seconds.

(a) How many additions and multiplications does it take to compute
the determinant of a general 2 × 2 matrix?

(b) Write a formula for the number of additions and multiplications it
takes to compute the determinant of a general n × n matrix using
the definition of the determinant as a sum over permutations.
Assume that finding and multiplying by the sign of a permutation
is free.
(c) How many additions and multiplications does it take to compute
the determinant of a general 3 × 3 matrix using expansion by
minors? Assuming m = 2a, is this faster than computing the
determinant from the definition?

Hint

194