16.1 Solving Linear Equations Using Row Operations
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 ...