The examples in previous chapters illustrate that solving linear programs involves the solution of systems of linear simultaneous algebraic equations. In this section we describe a method for solving a system of n linear equations in n unknowns that we use in subsequent sections. The method uses elementary row operations and corresponding elementary matrices. For a discussion of numerical issues involved in solving a system of simultaneous linear algebraic equations, we refer the reader to  and .
An elementary row operation on a given matrix is an algebraic manipulation of the matrix that corresponds to one of the following:
An elementary row operation on a matrix is equivalent to premultiplying the matrix by a corresponding elementary matrix, which we define next.
Definition 16.1 We call E an elementary matrix of the first kind if E is obtained from the identity matrix I by interchanging any two of its rows.
An elementary matrix of the first kind formed from I by interchanging the ith and the jth rows has the form
Note that E is invertible and E = E−1.
Definition 16.2 We call E an elementary matrix of the second kind if E is obtained from the ...