[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

721.0. "Matrix question" by RDVAX::PERRONE () Tue Jun 23 1987 17:03

    Can anyone out there answer these questions:
    
    
    Who coined the word "matrix" in its mathematical sense?
    Who was the first person to use matrices as abstract objects?
T.RTitleUserPersonal
Name
DateLines
721.1KIRK::KOLKERTue Jun 23 1987 17:406
    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
    
721.2ENGINE::ROTHWed Jun 24 1987 12:325
    I thought it was Cayley (another British mathemetcian),  but it could
    be Sylvester.  They both proved a number of fundemental results on
    matrices...

    - Jim
721.3pivotingFRETZ::HEISERGrace changes everythingTue Sep 27 1994 15:065
    Anyone know the algorithm for performing a pivot on an augmented
    matrix?
    
    thanks,
    Mike
721.4Sedgewick' book might helpEVTSG8::ESANUAu temps pour moiWed Sep 28 1994 09:437
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.
721.5RUSURE::EDPAlways mount a scratch monkey.Wed Sep 28 1994 11:2530
    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.
721.6Pivoting on a Simplex TableauFRETZ::HEISERGrace changes everythingMon Oct 03 1994 21:1452
    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
721.7Sedgewick has the answerEVTSG8::ESANUAu temps pour moiTue Oct 04 1994 13:505
Mike,

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

Mihai.