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 σ -symmetric matrices introduced by Rao and the author. (Skew) symmetric matrices are special cases of σ -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 σ -symmetric matrix form a delta-matroid. We extend in this way the notion of representability of delta-matroids by Bouchet.