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

We shall be considering square matrices over a fixed finite field \(\mathbb{F}\). If \(M\) is such a matrix with rows and columns indexed by the set \(V\), and \(X\) and \(Y\) are subsets of \(V\), then \(M[X,Y]\) denotes the submatrix with rows indexed by \(X\) and columns indexed by \(Y\) and \(M[X]:=\) \(M[X,X]\). If \(X\dot{\cup}Y\) is a partition of \(V\) and \(M[X]\) is nonsingular, then the corresponding Schur complement is \(M[Y]-M[Y,X]M[X]^{-1}M[X,Y]\). We now assume that \(M\) is symmetric or skew-symmetric and define the rank-width of \(M\). A rank-decomposition pair of \(M\) consists of a tree \(T\) for which each vertex has degree \(\leq3\) and a bijection \(\mathcal{L}\) from \(V\) onto the set of leaves of \(T\). For each edge \(e\) of \(T\), let \(X_{e}\) and \(Y_{e}\) denote the sets of leaves lying in the two connected components of \(T\setminus\left\{ e\right\} \); then the width of \(e\) is defined to be the rank of \(M\left[ \mathcal{L}^{-1}(X_{e}),\mathcal{L}^{-1}(Y_{e})\right] \). The width of \((T,\mathcal{L})\) is then defined to be the maximum of the widths of the edges \(e\) of \(T\), and the rank-width of \(M\) is defined to be the minimum of the width of \((T,\mathcal{L})\) over all rank-decomposition pairs. The main theorem (Theorem 7.1) of the paper is the following. Let \(M_{i}\) \((i=1,2,\dots)\) be an infinite sequence of skew or skew-symmetric matrices over \(\mathbb{F}\), and suppose their rank-widths are uniformly bounded; then for some \(i<j\) there is a permutation matrix \(P\) such that \(P^{-1}M_{i}P\) is equal to a principal submatrix of some Schur complement of \(M_{j}\). Actually the author proves a similar result in the more general context of a sequence of what he calls Lagrangian chain-groups, but the definitions are too complicated to be given here. The author shows that his theorem implies several known results of a similar nature: in every infinite sequence of graphs of bounded tree-width there is at least one graph which is isomorphic to the minor of another graph [\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 52, No. 2, 153--190 (1991; Zbl 0764.05069)]; in every infinite sequence of matroids representable over a fixed finite field and having bounded branch-width, there is at least one matroid isomorphic to a minor of another [\textit{J. F. Geelen} et al., J. Comb. Theory, Ser. B 84, No. 2, 270--290 (2002; Zbl 1037.05013)]; and in every infinite sequence of simple graphs of bounded rank-width there is at least one graph which is isomorphic to a pivot-minor of another [\textit{S.-I. Oum}, SIAM J. Discrete Math. 22, No. 2, 666--682 (2008; Zbl 1171.05048)].