The Matrix Sortability Problem

Sorting is such a fundamental component of achieving efficiency that a significant body of mathematics is dedicated to the investigation of sorting. Any modern textbook on algorithms contains chapters on sorting. One approach to arranging a disorganized list of items into an organized list is to successively identify two blocks of contiguous items, and swap the two blocks. In a fundamental paper D.A. Christie showed that a special version of block swapping, in recent times called context directed swapping and abbreviated cds , is the most efficient among block swapping strategies to achieve an organized list of items. The cds sorting strategy is also the most robust among block swap based sorting methods. It has been discovered that the context directed block swap operation on a list of objects generalizes to an operation on simple graphs. In turn it has been discovered that this operation on simple graphs corresponds with an operation on the adjacency matrix of a simple graph. The adjacency matrix is a symmetric square matrix with entries 0 and 1, and all diagonal entries 0. The corresponding operation is denoted Mcds , abbreviating matrix context directed swap . The operation on the adjacency matrix naturally employs the arithmetic of GF(2) , the finite field of two elements. It has been speculated that the Mcds operation on these specific matrices over GF(2) corresponds with the more than a century old Schur complement operation on these matrices. In this thesis, we confirm this prior speculation about the correspondence between Mcds and the Schur complement, in the context of GF(2) . We generalize the Mcds operation to not necessarily square matrices over arbitrary fields and we prove that the generalized Mcds corresponds with the Schur complement also in the more general context of all fields.