Rank-width and Well-quasi-ordering of Skew-Symmetric or Symmetric Matrices

2010/07/22 by Sang-il Oum · 1 citation
Mathematics · #math.CO

paper · pdf · doi:10.1016/j.laa.2011.09.027

published as Linear Algebra Appl. 436(April 1, 2012)(7), pp. 2008-2036 · 43 pages

arxiv created 2010/07/22 · arxiv updated 2014/03/26

Abstract

We prove that every infinite sequence of skew-symmetric or symmetric matrices M₁, M₂, ... 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.

Cited by

• Well-quasi-ordering of matrices under Schur complement and applications to directed graphs

Related

• An Upper Bound on the Size of Obstructions for Bounded Linear Rank-Width
• Characterizing (0,± 1)-matrices with only even-rank principal submatrices in terms of skew-symmetry
• Skew-symmetric matrices and their principal minors
• The Factor Width Rank of a Matrix
• Twin-width IV: ordered graphs and matrices