Applied Linear Algebra and Introductory Numerical Analysis

So, if you are stuck on one problem or another, the following may help. (If it doesn't, I have office hours Wednesday morning...)

no. 2 (a)
-- You can prove the existence of the LU factorization constructively (i.e. by showing how you would find it and that this method doesn't break down). Along the way, you will probably want to make use of the hint given in the book.
-- The other direction is most easily proved using determinants and the fact that a non-singular matrix has non-zero determinant. I wrote it as a proof by contradiction, but it is equally easy (though for me less intuitive) without using contradiction.
-- Uniqueness is almost always shown by assuming two solutions, substituting them both into the problem (here setting them both equal to A) and deriving that they are, in fact, the same.

no. 2 (b)
-- This is an inductive proof. The key is to show that the first step doesn't require any row swaps and the resulting submatrix (to be acted on next) is again strictly column diagonally dominant.

no. 3 (a)
-- I would suggest to look at an example. Start by checking out what happens to L and U if just the upper right and lower left corners of A are zeros. Then, what happens if the next sub-/super-diagonals of A are also 0? Induction will give you a general result.

no. 3 (b)
-- We know what the sparsity pattern of L and U will be if P=I. For other P's, is the banding pattern of A retained or destroyed? Is part of it retained? From 3(a) you can draw conclusions given the structure of PA.

no. 4
-- This is again an inductive proof. How is the largest entry in P_1 A related to the largest entry in A? How is the largest entry in L_1 P_1 A related to the largest entry in P_1 A? Then extend this insight to get the (k+1)th step from the kth.

no. 5
-- I already gave you this hint in class: The key here is that the P's applied to L_k leave the first k rows in place and only permute the others. Substitute the form with l_k and e_k in for L_k and see where this takes you. By the way, it suffices to show that P L_k P^(-1) has the purported properties of L'_k. One sentence can then extend this for multiple P's.

November 6: In class today, someone asked about the problem of multiplying a number by pi. At first I agreed that this could not be backward stable, because we cannot represent irrational numbers. However...

If the problem asked to multiply pi by a rational number (and we take the rationals as our vector space over rationals), this would be true. In the general (and realistic) case of a real number, the multiplication is backward stable!

In fact multiplication of any two real numbers is backward stable. You will prove this on your next homework.

Sorry for the confusion!

October 20: One of you pointed out to me that the last question on assignment #2 (question 6) asked whether one if-and-only-if statement was true, not whether one direction or the other is true. So technically finding one example where either direction is violated means the entire statement is false.

My interpretation (as well as my TA's) was that one should investigate either direction. This is how one would approach such a problem in research, where questions are more open-ended than in a textbook. If I can't quite get what I want, what does hold?

In view of the inconclusive phrasing of the question, however, I will accept an answer that provided only a counterexample for one direction. If you lost points because you didn't show that the other direction holds, please bring your homework to class on Monday and I will give you your points back. Note, however, that if you lost points because you showed only that one direction holds, you won't get them back, as this doesn't answer the question, interpreted either way.

Sorry for the mix-up.

Enjoy your weekend!

September 27: Welcome to class!