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

In [S. Oum, Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices, Linear Algebra and its Applications 436 (7) (2012) 2008-2036] Oum proved that, for a fixed finite field F, any infinite sequence M-1, M-2, . . . of (skew) symmetric matrices over F of bounded F-rank-width has a pair i < j, such that M-i is isomorphic to a principal submatrix of a principal pivot transform of M-j. We generalise this result to sigma-symmetric matrices introduced by Rao and the author. (Skew) symmetric matrices are special cases of sigma-symmetric matrices. As a by-product, we obtain that for every infinite sequence G(1), G(2), . . . of directed graphs of bounded rank-width there exists a pair i < j such that G(i) is a pivot-minor of G(j). Another consequence is that non-singular principal submatrices of a sigma-symmetric matrix form a delta-matroid. We extend in this way the notion of representability of delta-matroids by Bouchet. (C) 2012 Elsevier Ltd. All rights reserved.