to COMP 205 Homework 3--- Solutions to algebraic proofs

Problems

NOTE: there is no single correct proof for any of these problems; many approaches are possible, and solutions will be graded on correctness and clarity of reasoning and presentation.

1. (15 points) Given a vector , show that

   

   and

   

   (a)

   Since norms are always positive, we can equivalently prove . Now,

   

   and because the multiple summation term is , our proof is complete.

   (b) . Several different proofs of this were possible. Typically we could square both terms as before, then use the above formula and the theorem (since ), to get

   

   thus demonstrating the desired inequality. As an alternate proof, one might use the Cauchy-Schwarz inequality and let y be the vector

   

   The left-hand side is simply and the right hand side is , and our desired inequality is thus shown.

   (c) . Again we'll square both sides. Let . Then, clearly,

   

   completing our proof.

   (d) Squaring both sides, and letting as above,

   

   completing our proof.

   (e) . Fairly trivial,

   

   (f) . Similar to (d),

   

   It also follows simply from and , as proven above.

2. (15 points) Given matrices, and , let be operator norms, as defined in the class. Prove the following properties :
   1. , if is the operator norm induced by the vector norm .
   2. .
   3. .
   4. .

   (a) . By definition of operator norm,

   

   Therefore, . (If , trivially true.)

   (b) . This follows most simply from the previous result:

   

   and therefore .

   (c) . This problem gave folks a lot of trouble. The most straightforward proofs first established the max. column-sum as an upper bound, then showed that it was indeed achieved.

   From the definition, . Then, . Now,

   

   Let column k be the column of with the maximum absolute column sum, i.e.

   

   Then

   

   thus giving our upper bound .

   This bound is achieved if we let be a vector such that and for all . Then

   

   and therefore .

   (d) . (The last equality follows trivially, since the max abs row sum of = max abs column sum of , as shown in (c).) We'll proceed similarly as above, establishing the upper bound, then showing a vector that achieves it.

   From the definition, . Then, . Now,

   

   Therefore, we have the upper bound

   

   We now show that this bound is achieved. Let k be the row with the maximum abs row-sum, i.e.

   

   Then we create the vector x such that

   

   and note that . Then,

   

   Since we've already established this as an upper bound, the equality is proven, and thus, .

• About this document ...