Browse Prior Art Database

THE ELIMINATION FORM OF THE INVERSE AND ITS APPLICATION TO LINEAR PROGRAMMING

IP.com Disclosure Number: IPCOM000128845D
Original Publication Date: 1955-Apr-08
Included in the Prior Art Database: 2005-Sep-19
Document File: 6 page(s) / 97K

Publishing Venue

Software Patent Institute

Related People

Markowitz, Harry: AUTHOR [+3]

Abstract

The inverse (A -1 ) of a matrix (A) is valuable when a number of sets of equations AX = -b are to be solved using different b's and the same A. A -1 , like any matrix, may be expressed as the product of other matrices A -1 = M m M m-1 ...M 1 in an infinite number of ways. E.g. (2) = (1/2) (4) = (1/8) (16) etc. If we have such M 1 , . . . , M m we can solve AX = b, X = A -l b in a series of steps: X (1) = M 1 b X (2) = M 2 X (1) . . . X = M m X (m-1) The expression M m . . . M 1 is referred to as a ";product form"; of inverse. In some problems there may be M i which are easier to obtain and apply than A -1 itself.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE ELIMINATION FORM OF THE INVERSE AND ITS APPLICATION TO LINEAR PROGRAMMING

Harry Markowitz

P-680

8 April 1955

The RAND CORPORATION 1700 MAIN ST. SANTA MONICA CALIFORNIA

ACKNOWLEDGEMENT

The writer is indebted to George Dantzig and Alan Manne for valuable suggestions.

THE ELIMINATION FORM OF THE INVERSE AND ITS APPLICATION TO LINEAR PROGRAMMING [ title ] e

The inverse (A-1) of a matrix (A) is valuable when a number of sets of equations AX = -b are to be solved using different b's and the same A. A-1, like any matrix, may be expressed as the product of other matrices A-1 = Mm Mm-1 ...M1 in an infinite number of ways. E.g. (2) = (1/2) (4) = (1/8) (16) etc. If we have such M1 , . . . , Mm we can solve AX = b, X = A-lb in a series of steps: X(1) = M1 b

X(2) = M2X(1)


.
.


.

X = Mm X(m-1)

The expression Mm . . . M1 is referred to as a "product form" of inverse. In some problems there may be Mi which are easier to obtain and apply than A-1 itself.

This paper will discuss a particular product form of inverse which is closely related to the Gaussian elimination method of solving a set of simultaneous equations. This "elimination form of the inverse," as we shall call it, is especially valuable when A has a large number of zero coefficients. If A has no zero coefficients, on the other hand, the elimination form of inverse is still generally as convenient as the conventional A-1.

The elimination form of inverse can be illustrated in terms of the solution of three equations in three unknowns:

Rand Corporation Page 1 Apr 08, 1955

Page 2 of 6

THE ELIMINATION FORM OF THE INVERSE AND ITS APPLICATION TO LINEAR PROGRAMMING

1) all X1 + al2 X2 + a13 X3 = r1
2) a21 X1 + a22 X2 + a23 X3 = r2
3) a31 X1 + a32 X2 + a33 X3 = r3

For the moment we will let the kth diagonal element be the kth pivotal element. From equation 1) we get the first equation of our back solution [ Equation omitted ]

We eliminate X1 from equations 2) and 3) by adding [ Equation omitted ] times the first equation to the ith equation, thus obtaining 2') b22 X2 + b23 X3 = r*2 3') b32 X2 + b33 X3 = r*3 where [ Equation omitted ]

Similarly we get [ Equation omitted ] and [ Equation omitted ] where [ Equation omitted ] . Finally [ Equation omitted ]

B3) gives us X3; X3 and B2)give X2; X2, X3 and B1) give X1 Consider the transformations which occurred to our original right hand side. First we formed [ Equation omitted ] then [ Equation omitted ] then [ Equation omitted ] then [ Equation omitted ] and finally [ Equation omitted ] Thus [ Equation omitted ] Since the aij bij cij do not depend on the ri we have [ Equation omitted ] Similarly if A is any m X m non-singular matrix we have A-1 = B1 B2 ... Bm Rm- 1...R1 where Rk is a matrix of the form [ Equation omitted ] and Bk is of the form [ Equation omitted ]

Although this elimination form of inverse consists of 2m-1 matrices it contains only n2 numbers which are not known a-prio...