Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices

Abstract

We prove that every infinite sequence of skew-symmetric or symmetric matrices M-1, M-2, ... over a fixed finite field must have a pair M-i, M-j (i < j) such that M-i is isomorphic to a principal submatrix of the Schur complement of a nonsingular principal submatrix in M-j, if those matrices have bounded rank-width. This generalizes three theorems on well-quasi-ordering of graphs or matroids admitting good tree-like decompositions; (1) Robertson and Seymour's theorem for graphs of bounded tree-width, (2) Geelen, Gerards, and Whittle's theorem for matroids representable over a fixed finite field having bounded branch-width, and (3) Oum's theorem for graphs of bounded rank-width with respect to pivot-minors. (C) 2011 Elsevier Inc. All rights reserved.