Doubly Lexical Orderings of Matrices

Abstract

Every matrix has a doubly lexical ordering an ordering of the rows and columns so that the row vectors are lexically (or “lexicographically”) increasing and the column vectors are lexically increasing. Every graph has a lexical ordering: a vertex ordering making the neighbourhood matrix doubly lexical. An almost linear time doubly lexical ordering algorithm is given. Doubly lexical orderings unify the orderings characterizing certain classes of matrices and graphs, including totally balanced matrices, subtree matrices and chordal graphs.