hwk10.1 - due tues 4/9
Practice using the method of induction we learned in class.
Computer scientists often try to measure the difficulty (often called the complexity) of an operation by counting only the number of times the computer will need to multiply 2 numbers. This is a rough estimate of the time the operation will take to run; in this rough estimate, we don't bother to count the number of times we need to add or deal with a +/-. Let us explore the complexity of the determinant.
Let C( n ) be the number of multiplications necessary to compute the determinant of an nxn matrix with no zero entries using only the cofactor expansion definition (meaning we don't use any theorems to make the calculation easier).
So, the first few are
Again recall that for this rough estimate we only count multiplications, and ignore additions and any times we deal with +/-.
This grows very very quickly. How quickly you ask? Recall the factorial of a number is the product of it and all the positive integers less than it.
Factorial is a common benchmark for "very rapidly growing".
Show by induction that C( n )>=n! for all n>=2.
Thus, determinant is a calculation that grows in complexity very quickly as the size of the matrix grows. Thus, we really need the theorems to make this calculation doable in a reasonable amount of time.
If you are curious, the exact answer (though you don't need to know this to do this problem) is
C( n )=floor(n!*(e-1))-1
6.2#9 (Is the matrix invertible?)
6.2#10 (Is the matrix invertible?)
6.2#31 (Yes, listed out of order. This one is involved and again uses the method of induction.
prove Thm 6.2.7 using Thm 6.2.6 (and Thm 6.2.8 if you wish).