Computer Science 15-199, Spring 2009 Mini 4
Class Notes:  Matrices and Sums of Powers

Note:  in general, the online notes for this mini course will be very lean (in some cases, perhaps non-existent).  They are just a sketch of what we did.  For the rest, you have to attend!  This week the notes are probably more complete than they will be in subsequent weeks...

This week, we wrote this program:  matrixInversion.jar  (also available as a jar-in-a-zip:  matrixInversion.zip).  Try running it!

Here are the steps we followed (give or take):

1. We started by adding the numbers from 1 to 100.  We observed that you can pair them as such:
   1 + ... + 100 = (1 + 100) + (2 + 99) + ... + (50 + 51) = 101  + ... + 101 = 101 * 50 = 5050
    
2. We generalized this to sum from 1 to n, as such:
   1 + ... + n = (1 + n) + (2 + (n-1)) + ..  = (n+1) * n/2 = 1/2*n^2 + 1/2*n
    
3. So we have a "closed-form polynomial solution" f1(n) = 1/2*n^2 + 1/2*n
    
4. We rewrote this as a 1d array of the coefficients, skipping the constant term n^0 (which is 0):  [ 1/2,  1/2 ]
    
5. We wondered if there was a similar way to find a close-form polynomial solution to the sums of higher powers:
       f2(n) = 1^2 + ... + n^2
       f3(n) = 1^3 + ... + n^3
       f4(n) = 1^4 + ... + n^4
       f5(n) = 1^5 + ... + n^5
    
6. In pursuit of this, we reconsidered a different way to solve f1(n), as such:
   1. We know it is of degree 2.  Why?  Well, we handwaved a little, but we know that f1(n) = f1(n-1) + n, so this means the derivative of f1(n) is approximately n (there's the handwaving), which clearly suggests that f1 is of degree 2.
   2. So f1(n) = an^2 + bn + c.  But we know f1(0) is 0, so c must be 0.
   3. So f1(n) = an^2 + bn.
   4. Now, we can find specific points that f1(n) goes through by directly computing them:
      1. f1(1) = 1
      2. f1(2) = 1 + 2 = 3
   5. Let's substitute those two points [ (1,1) and (2,3) ] back into the equation:
        f1(1) = a*1^2 + b*1 = 1
        f1(2) = a*2^2 + b*2 = 3
   6. Now we rewrite these slightly:
        1^2*a + 1*b = 1
        2^2*a + 2*b = 3
   7. Now we rewrite again in matrix form:
        | 1^2  1 | | a |    | 1 |
        | 2^2  2 | | b | =  | 3 |
7. So we have Ax=b (in matrices).  We discussed how this indicates that b=A^-1x.  So if we could invert A, we could solve for b, which would hold the coefficients of the closed-form polynomial solution f1(n).
    
8. So now we needed to invert a matrix A.  To do that, we followed these steps:
   1. Augment the matrix with the Identity matrix to get [ A | I ]
   2. Using only elementary row operations, convert A into I, which simultaneously converts I into A^-1.  The elementary row operations are:
         * multiply a row by a constant
         * add a multiple of one row to another
         * swap two rows
      The intuition as to why these are ok:  each row is basically an equation, and these are the things you can do to equations...  Anyhow, using only these operations, we proceeded as such:
      1. For each column, first place a 1 on the diagonal and then use that 1 on the diagonal to place zero's on all other rows of that column.
      2. To place the 1 on the diagonal, we multiplied the row by an appropriate factor.
         Note:  this does not work if there is a zero on the diagonal -- there is nothing you can multiply zero by to get it to be 1.  In this case, what you should do, and what we did not do, is find a row that has non-zero in that column, and swap the rows to place a 1 on the diagonal.  If no such row exists, then the matrix is non-invertible.  This happens when, say, trying to intersect two parallel lines.  In that case, our code would crash with a division by zero exception.
      3. To place the zero on each non-diagonal row of the column, we add a suitable multiple of the row that we just created the 1 on the diagonal of.  This will not corrupt previous columns because we are certain that row has a 0 in all preceding columns (why?).
          
9. We followed these steps and inverted the matrix and used that to solve our problem!  Wahoo!
    
10. We then moved on to the next power (ok, in class we started with sums-of-squares and moved on to sums-of-cubes, but here we started with sums-of-linears, so we'll move on to sums-of-squares):
    1. Following the same logic from step 6 above, only now solving for f2(n) = 1^2 + ... + n^2, we see:
       1. We know it is of degree 3.  Why?
       2. So f2(n) = an^3 + bn^2 + cn + d.  But we know f2(0) is 0, so d must be 0.
       3. So f2(n) = an^3 + bn^2 + cn.
       4. Now, we can find specific points that f1(n) goes through by directly computing them:
          1. f2(1) = 1^2 = 1
          2. f2(2) = 1^2 + 2^2 = 1 + 4 = 5
          3. f2(3) = 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14
       5. Let's substitute those three points [ (1,1), (2,5), and (3, 14) ] back into the equation:
            f2(1) = a*1^3 + b*1^2 + c*1 = 1
            f2(2) = a*2^3 + b*2^2 + c*2 = 5
            f2(3) = a*3^3 + b*3^2 + c*3 = 14
       6. Now we rewrite these slightly:
            1^3*a + 1^2*b + 1*c = 1
            2^3*a + 2^2*b + 2*c = 5
            3^3*a + 3^2*b + 3*c = 14
       7. Now we rewrite again in matrix form:
            | 1^3  1^2  1 | | a |    |  1 |
            | 2^3  2^2  2 | | b | =  |  5 |
            | 3^3  3^2  3 | | c |    | 14 |
    2. At this point, we proceeded exactly as above, where we have Ax=b so we invert A to solve for b, which gave us the coefficients of the closed-form polynomial solution to f2(n).  Wow.
        
11. Now we saw how to automate this.  The pattern for generating A and b for any given f_i(n) should be clear.  So you generate A and b, invert A, solve for b, and voila, you have the coefficients of f_i(n).  And that is precisely how we wrote this program:  matrixInversion.jar  (still available as a jar-in-a-zip:  matrixInversion.zip)

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem