$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 8.5: Review Problems

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

1. Find the determinant via expanding by minors.

$$\left(\begin{array}{rrrr} 2 & 1 & 3 & 7 \\ 6 & 1 & 4 & 4 \\ 2 & 1 & 8 & 0 \\ 1 & 0 & 2 & 0\end{array}\right)$$

2. Even if $$M$$ is not a square matrix, both $$MM^{T}$$ and $$M^{T} M$$ are square. Is it true that $$\det(MM^{T}) = \det(M{T} M)$$ for all matrices $$M$$? How about $$tr(MM^{T}) = tr(M^{T} M)$$?

3. Let $$\sigma^{-1}$$ denote the inverse permutation of $$\sigma$$. Suppose the function $$f : {1, 2, 3, 4} \rightarrow R$$. Write out explicitly the following two sums:

$$\sum_{\sigma}f(\sigma(s))~and~\sum_{\sigma}f(\sigma^{-1}(s)).$$

What do you observe? Now write a brief explanation why the following equality holds

$$\sum_{\sigma}F(\sigma) = \sum_{\sigma}F(\sigma^{-1}).$$

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) computed 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, computing 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 \rightarrow 2$$ matrix?

(b) Write a formula for the number of additions and multiplications it takes to compute the determinant of a general $$n \rightarrow 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 \rightarrow 3$$ matrix using expansion by minors? Assuming $$m = 2a$$, is this faster than computing the determinant from the definition?