$$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

8.5: Review Problems

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?