chapter  6
30 Pages

Systems of Linear Equations

First, we give a brief introduction to the solution of a system of m linear equations in n unknowns. In particular, we introduce the socalled reduced row-echelon form of a matrix and explain how it can be used in solving a system of linear equations. Then, using results from Chapter 5 on the adjoint and inverse of a square matrix, we derive an explicit formula (known as Cramer’s formula) for the solution of a linear system of n equations in n unknowns whose coefficient matrix is invertible. We then turn to graph-theoretical techniques for solving systems. In Section 6.3 we show how to use the Coates digraph (flow digraph) to solve the linear system. In the next section, we discuss the signal flow digraph approach (a variation of the previous technique) for solving a linear system. These two techniques, although valid in general, are efficient if the system matrix is sparse, that is, if it contains a lot of zero entries and the other entries are variables. Finally, in the last section we explain how to use graph-theoretical tools to treat systems with sparse matrices whose entries are given numerically.