# 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:

1. Interchanging any two rows of the matrix
2. Multiplying one of its rows by a real nonzero number
3. Adding a scalar multiple of one row to another row

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 ...

Get An Introduction to Optimization, 4th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.