Chapter 12

Perfect Gaussian Elimination

Martin Charles Golumbic

Publisher Summary

This chapter describes perfect gaussian elimination. Perfect elimination matrices are presented. Let M be a nonsingular n × n matrix with entries mij in some field (like the real numbers). One reduce M to the identity matrix I by repeatedly: (a) choosing a nonzero entry mij to act as pivot and (b) updating the matrix by using elementary row and column operations to change mij to 1 and to make all other entries in the ith row and jth column equal to 0. This familiar technique is called Gaussian elimination. When performing Gaussian elimination on a sparse matrix, an arbitrary choice of pivots may result in the filling in of some zero positions with nonzeros. One may ...

Get Algorithmic Graph Theory and Perfect Graphs, 2nd Edition now with O’Reilly online learning.

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