Conference rusure::math

    re .0
    
    I think it was the British Algebraist Sylvester. See E.T.Bell's
    book Men of Mathematics.  It has very good bios on the prominent
    mathematicians of the 18-th and 19-th century
    

    I thought it was Cayley (another British mathemetcian),  but it could
    be Sylvester.  They both proved a number of fundemental results on
    matrices...

    - Jim

    Anyone know the algorithm for performing a pivot on an augmented
    matrix?
    
    thanks,
    Mike

There is an algorithm for performing a pivot in Robert Sedgewick's book
'Algorithms', Addison-Wesley, 1984.

However, he doesn't speak about augmented matrices, and I don't know what
an augmented matrix is.

Mihai.

    I believe "augmented matrix" refers to a matrix of coefficients placed
    side-by-side with one or more columns of constants, often with a
    vertical solid or dashed line between them.  For example, from:
    
    	3x+4y=5
    	4x+6y=9
    
    the matrix of coefficients is
    
    	[3 4]
    	[4 6]
    
    and the augmented matrix is
    
    	[3 4 | 5]
    	[4 6 | 9].
        
    In such cases, the pivots and operations are selected just as if the
    matrix were not augmented.  It is merely necessary to extend each row
    operation to include the augmented columns.  Thus, if any row is
    multiplied by 3 and added to another, the numbers in the augmented
    columns of that row are also multiplied by 3 and added to the other
    row.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

    In case anyone else ever wonders about pivoting on a simplex tableau
    (augmented matrix), here it is.
    
    The goal is usually ot maximize an objective function given some
    constraints.  For example, suppose you want to maximize the function 
    z=x1 + 2x2 + x3 given these constraints:

 2x1 + 2x2 +  x3 <= 20
  x1 +  x2 - 2x3 <= 23
-2x1 +  x2 - 2x3 <=  8

and x1, x2, and x3 are >= 0.

You would set up the initial tableau (augmented matrix) to look like this:

  2    2     1    1   0  0  | 20
  1    1    -2    0   1  0  | 23
 -2    1    -2    0   0  1  |  8
  ------------------------------
 -1   -2    -1    0   0  0  |  0           objective function

                               ^ this is z, which you are trying to maximize

To pivot, you look along the bottom row to find the most negative number.  In
this case it's column 2 which has -2 on the bottom.  To find the pivot row, you
pick the one with the smallest ratio to its constraint (last column).  The
answer is row 3 because 8/1 is smaller than 23/1 or 20/2.

You then multiply that row (3) by the inverse of the pivot (1).  In this case
there is no change in the values.  You then do Gaussian elimination on the rest
of column 2.  In this case you will need to multiply row 3 by -2 and add it to 
    row 1.  Row 2 would be -1 multiplied by row 3 and added to row 2.
Row 4 would be 2 multiplied by row 3 and added to row 4.

The above is what one execution of a Pivot program should do.  When you have 
    all positive numbers in the last row (objective function) you can stop and 
    you will have maximum z in the bottom right corner.  In this example
it's 20 after 2 pivots.  This mainly comes in handy for profit and loss and
manufacturing estimates.
    
    So a simple algorithm would be:
    
    1.  Pivot cell Inverse multiplied by the pivot row
    2.  Using M as the # of rows...
    
        Do I = 1 to M
           If I = pivot row, Then I = I + 1
           Else
              (-[I,pivot column] x pivot row) + I
    
regards,
Mike

Mike,

Sedgewick's book (see .4) presents exactly this kind of algorithm.

Mihai.