# Well-Quasi-Ordering of Matrices under Schur Complement and Applications to
Directed Graphs

Mamadou Moustapha Kanté  Clermont-Université, Université Blaise Pascal, LIMOS,
CNRS
Complexe Scientifique des Cézeaux 63173 Aubiére Cedex, France
<EMAIL_ADDRESS>
###### Abstract

In [Rank-Width and Well-Quasi-Ordering of Skew-Symmetric or Symmetric
Matrices, arXiv:1007.3807v1] Oum proved that, for a fixed finite field
$\mathbb{F}$, any infinite sequence $M_{1},M_{2},\ldots$ of (skew) symmetric
matrices over $\mathbb{F}$ of bounded _$\mathbb{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 myself in [The Rank-Width of Edge-
Coloured Graphs, arXiv:0709.1433v4]. (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},\ldots$ of directed graphs of bounded
rank-width there exist 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.

###### keywords:

rank-width; sigma-symmetry; edge-coloured graph; well-quasi-ordering;
principal pivot transform; pivot-minor.

††journal:

##  1 Introduction

_Clique-width_ [6] is a graph complexity measure that emerges in the works by
Courcelle et al. (see for instance the book [7]). It extends _tree-width_ [21]
in the sense that graph classes of bounded tree-width have bounded clique-
width, but the converse is false (distance hereditary graphs have clique-width
at most $3$ and unbounded tree-width). Clique-width has similar algorithmic
properties as tree-width and seems to be the right complexity measure for the
investigations of polynomial time algorithms in dense graphs for a large set
of NP-complete problems [7]. It is then important to identify graph classes of
bounded clique-width. Unfortunately, contrary to tree-width, there is no known
polynomial time algorithm that checks if a given graph has clique-width at
most $k$, for fixed $k\geq 4$ (for $k\leq 3$, see the algorithm by Corneil et
al. [5]). Furthermore, clique-width is not monotone with respect to _graph
minor_ (cliques have clique-width $2$) and is only known to be monotone with
respect to the _induced subgraph_ relation which is not a well-quasi-order on
graph classes of bounded clique-width (cycles have clique-width at most $4$
and are not well-quasi-ordered by the induced subgraph relation).

In their investigations for a recognition algorithm for graphs of clique-width
at most $k$, for fixed $k$, Oum and Seymour [20] introduced the complexity
measure _rank-width_ of undirected graphs. Rank-width and clique-width of
undirected graphs are equivalent in the sense that a class of undirected
graphs has bounded rank-width if and only if it has bounded clique-width. But,
if rank-width shares with clique-width its same algorithmic properties (see
for instance [8]), it has better combinatorial properties.

  1. 1.

There exists a cubic-time algorithm that checks whether an undirected graph
has rank-width at most $k$, for fixed $k$ [13].

  2. 2.

Rank-width is monotone with respect to the _pivot-minor_ relation. This
relation generalises the notion of graph minor because if $H$ is a minor of
$G$, then $I(H)$, the _incidence graph_ of $H$, is a pivot-minor of $I(G)$.
Undirected graphs of rank-width at most $k$ are characterised by a finite list
of undirected graphs to exclude as pivot-minors [17].

  3. 3.

Furthermore, rank-width is related to the _branch-width_ of binary matroids.
Branch-width of matroids plays an important role in the project by Geelen et
al. [12] aiming at extending techniques in the Graph Minors Project to
representable matroids over finite fields in order to prove that representable
matroids over finite fields are well-quasi-ordered by _matroid minors_. Such a
result would answer positively Rota’s Conjecture [12]. It turns out that the
branch-width of a binary matroid is one more than the rank-width of its
fundamental graphs and a fundamental graph of a minor of a matroid
$\mathcal{M}$ is a pivot-minor of a fundamental graph of $\mathcal{M}$.

It is then relevant to ask whether undirected graphs are well-quasi-ordered by
the pivot-minor relation. This would imply that binary matroids are well-
quasi-ordered by matroid minors, and hence the _Graph Minor Theorem_ [22].
This would also help understand the structure of graph classes of bounded
clique-width and of many dense graph classes where the Graph Minor Theorem
fails to explain their structure. Geelen et al. have successfully adapted many
techniques in the Graph Minors Project [23] and obtained generalisations of
some results in the Graph Minors Projects to representable matroids over
finite fields (see the survey [12]). Inspired by the links between rank-width
and branch-width of binary matroids, Oum [18] adapted the techniques by Geelen
et al. and proved that undirected graphs of bounded rank-width are well-quasi-
ordered by the pivot-minor relation. As for the Graph Minors Project, this
seems to be a first step towards a Graph Pivot-Minor Theorem.

However, rank-width has a drawback: it is defined in Oum’s works only for
undirected graphs. But, clique-width was originally defined for graphs
(directed or not, with edge-colours or not). Hence, one would know about the
structure of (edge-coloured) directed graphs of bounded clique-width. Rao and
myself [14] we have defined a notion of rank-width, called _$\mathbb{F}$
-rank-width_, for $\mathbb{F}^{*}$-graphs, _i.e._ , graphs with edge-colours
from a field $\mathbb{F}$, and explained how to use it to define a notion of
rank-width for graphs (directed or not, with edge-colours or not). Moreover,
the notion of rank-width of undirected graphs is a special case of it.
$\mathbb{F}$-rank-width is equivalent to clique-width and all the known
results, but the well-quasi-ordering theorem by Oum [18], concerning the rank-
width of undirected graphs have been generalised to the $\mathbb{F}$-rank-
width of $\mathbb{F}^{*}$-graphs. We complete the tableau in this paper by
proving a well-quasi-ordering theorem for $\mathbb{F}^{*}$-graphs of bounded
$\mathbb{F}$-rank-width, and hence for directed graphs.

In [19] Oum noticed that the _principal pivot transform_ introduced by Tucker
[25] can be used to obtain a well-quasi-ordering theorem for (skew) symmetric
matrices over finite fields of bounded $\mathbb{F}$-rank-width. This result
unifies his own result on the well-quasi-ordering of undirected graphs of
bounded rank-width by pivot-minor[18], the well-quasi-ordering by matroid
minor of matroids representable over finite fields of bounded branch-width
[11] and the well-quasi-ordering by graph minor of undirected graphs of
bounded tree-width [21]. In order to prove the well-quasi-ordering theorem for
$\mathbb{F}^{*}$-graphs of bounded $\mathbb{F}$-rank-width, we will adapt the
techniques used by Oum in [19] to _$\sigma$ -symmetric_ matrices. The notion
of $\sigma$-symmetric matrices were introduced by Rao and myself in [14] and
subsumes the notion of (skew) symmetric matrices. Oum’s proof can be
summarised into two steps.

  * (i)

He first developed a theory about the notion of _lagrangian chain-groups_ ,
which are generalisations of _isotropic systems_ [1] and of _Tutte chain-
groups_ [26]. Tutte chain-groups are another characterisation of representable
matroids, and isotropic systems are structures that extend some properties of
$4$-regular graphs and of circle graphs. Isotropic systems played an important
role in the proof of the well-quasi-ordering of undirected graphs of bounded
rank-width by pivot-minor. As for Tutte chain groups and isotropic systems,
lagrangian chain groups are vector spaces equipped with a bilinear form. Oum
introduced a notion of minor for lagrangian chain groups that subsumes the
matroid minor and the notion of minor of isotropic systems. He also defined a
connectivity function for lagrangian chain groups that generalises the
connectivity function of matroids and allows to define a notion of _branch-
width_ for them. He then proved that lagrangian chain-groups of bounded
branch-width are well-quasi-ordered by lagrangian chain groups minor.

  * (ii)

He secondly proved that to any lagrangian chain-group, one can associate a
(skew) symmetric matrix and vice-versa. These matrices are called _matrix
representations_ of lagrangian chain-groups. He can thus formulate the well-
quasi-ordering theorem of lagrangian chain-groups in terms of (skew) symmetric
matrices.

We will follow the same steps. We will extend the notion of lagrangian chain-
groups to make it compatible with $\sigma$-symmetric matrices. Then, we prove
that these lagrangian chain-groups admit representations by $\sigma$-symmetric
matrices.

The paper is organised as follows. We present some notations needed throughout
the paper in Section 2. Chain groups are revisited in Section 3. Section 4 is
devoted to the links between chain groups and $\sigma$-symmetric matrices. The
main theorem (Theorem 29) of the paper is presented in Section 4. Applications
to directed graphs and more generally to edge-coloured graphs is presented in
Section 5. An old result by Bouchet [3] states that non-singular principal
submatrices of a (skew) symmetric matrix form a _delta-matroid_. We extend
this result to $\sigma$-symmetric matrices and obtain a new notion of
representability of delta-matroids in Section 6.

##  2 Preliminaries

For two sets $A$ and $B$, we let $A\setminus B$ be the set $\\{x\in A\mid
x\notin B\\}$. The power-set of a set $V$ is denoted by $2^{V}$. We often
write $x$ to denote the set $\\{x\\}$. We denote by $\mathbf{N}$ the set
containing zero and the positive integers. If $f:A\to B$ is a function, we let
$\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.16167pt}}_{\,X}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.16167pt}}_{\,X}}$, the restriction of $f$ to
$X\subseteq A$, be the function $\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.16167pt}}_{\,X}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.16167pt}}_{\,X}}:X\to B$ where for every $a\in X,\
\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.16167pt}}_{\,X}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.16167pt}}_{\,X}}(a):=f(a)$. For a finite set $V$, we
say that the function $f:2^{V}\to\mathbf{N}$ is _symmetric_ if for any
$X\subseteq V,\leavevmode\nobreak\ f(X)=f(V\setminus X)$; $f$ is _submodular_
if for any $X,Y\subseteq V$, $f(X\cup Y)+f(X\cap Y)\leq f(X)+f(Y)$.

We denote by $+$ and $\cdot$ the binary operations of any field and by $0$ and
$1$ the identity elements of $+$ and $\cdot$ respectively. Fields are denoted
by the symbol $\mathbb{F}$ and finite fields of order $q$ by $\mathbb{F}_{q}$.
We recall that finite fields are commutative. For a field $\mathbb{F}$, we let
$\mathbb{F}^{*}$ be the set $\mathbb{F}\setminus\\{0\\}$. We refer to [16] for
our field terminology.

We use the standard graph terminology, see for instance [9]. A _directed
graph_ $G$ is a couple $(V_{G},E_{G})$ where $V_{G}$ is the set of vertices
and $E_{G}\subseteq V_{G}\times V_{G}$ is the set of edges. A directed graph
$G$ is said to be _undirected_ if $(x,y)\in E_{G}$ implies $(y,x)\in E_{G}$.
For a directed graph $G$, we denote by $G[X]$, called the subgraph of $G$
induced by $X\subseteq V_{G}$, the directed graph $(X,E_{G}\cap(X\times X))$.
The degree of a vertex $x$ in an undirected graph $G$ is the cardinal of the
set $\\{y\mid xy\in E_{G}\\}$. Two directed graphs $G$ and $H$ are
_isomorphic_ if there exists a bijection $h:V_{G}\to V_{H}$ such that
$(x,y)\in E_{G}$ if and only if $(h(x),h(y))\in E_{H}$. We call $h$ an
_isomorphism_ between $G$ and $H$. All directed graphs are finite and can have
loops.

A _tree_ is an acyclic connected undirected graph. A _cubic tree_ is a tree
such that the degree of each vertex is either $1$ or $3$. For a tree $T$ and
an edge $e$ of $T$, we let $T\textrm{-}e$ denote the graph
$(V_{T},E_{T}\setminus\\{e\\})$.

A _layout_ of a finite set $V$ is a pair $(T,\mathcal{L})$ of a cubic tree $T$
and a bijective function $\mathcal{L}$ from the set $V$ to the set
$\operatorname{L}_{T}$ of vertices of degree $1$ in $T$. For each edge $e$ of
$T$, the connected components of $T\textrm{-}e$ induce a bipartition
$(X_{e},V\setminus X_{e})$ of $\operatorname{L}_{T}$, and thus a bipartition
$(X^{e},V\backslash
X^{e})=(\mathcal{L}^{-1}(X_{e}),\mathcal{L}^{-1}(V\setminus X_{e}))$ of $V$.
Let $f:2^{V}\to\mathbf{N}$ be a symmetric function and $(T,\mathcal{L})$ a
layout of $V$. The _$f$ -width of each edge $e$ of $T$_ is defined as
$f(X^{e})$ and the _$f$ -width of $(T,\mathcal{L})$_ is the maximum $f$-width
over all edges of $T$. The _$f$ -width of $V$_ is the minimum $f$-width over
all layouts of $V$. The notions of layout and of $f$-width are commonly called
_branch-decomposition_ and _branch-width_ of $f$. However, this terminology is
not appropriate since $f$ is only a measure for the cuts
$(\mathcal{L}^{-1}(X_{e}),\mathcal{L}^{-1}(V\setminus X_{e}))$ and other
measures could be used with the same layout.

###  2.1 Well-Quasi-Order

We review in this section the _well-quasi-ordering_ notion. A binary relation
is a _quasi-order_ if it is reflexive and transitive. A quasi-order $\preceq$
on a set $\mathcal{U}$ is a _well-quasi-order_ , and the elements of
$\mathcal{U}$ are _well-quasi-ordered_ by $\preceq$, if for every infinite
sequence $x_{0},x_{1},\ldots$ in $\mathcal{U}$ there exist $i<j$ such that
$x_{i}\preceq x_{j}$. The notion of well-quasi-ordering is flourishing and
there exist several equivalent definitions of the well-quasi-ordering notion.
For instance, a quasi-order $\preceq$ on a set $\mathcal{U}$ is a well-quasi-
order if and only if $\mathcal{U}$ contains no infinite antichain and no
infinite strictly decreasing sequence. One consequence of this
characterisation is that every $\preceq$-closed set $X$ of $\mathcal{U}$,
_i.e._ , if $y\in X$ and $x\preceq y$ then $x\in X$, is characterised by a
finite list $Forb(X)$ such that $x\in X$ if and only if there is no $z\in
Forb(X)$ with $z\preceq x$. Hence, the well-quasi-ordering notion is an
interesting tool for characterising graph classes. There exist several well-
quasi-ordering theorems in the literature, see for instance [9, Chapter 12]
for some of them.

###  2.2 Sesqui-Morphism

We recall the notion of _sesqui-morphism_ introduced in [14] in order to
extend the notion of rank-width to directed graphs. Let $\mathbb{F}$ be a
field and $\sigma:\mathbb{F}\to\mathbb{F}$ a bijection. We recall that
$\sigma$ is an involution if $\sigma\circ\sigma$ is the identity. We call
$\sigma$ a _sesqui-morphism_ if $\sigma$ is an involution, and the function
$\tilde{\sigma}:=[x\mapsto\sigma(x)/\sigma(1)]$ is an automorphism. It is
worth noticing that if $\sigma:\mathbb{F}\to\mathbb{F}$ is a sesqui-morphism,
then $\sigma(0)=0$ and for every $a,b\in\mathbb{F}$,
$\sigma(a+b)=\sigma(a)+\sigma(b)$. Moreover, $\tilde{\sigma}$ is an
involution. The next proposition summarises some properties of sesqui-
morphisms.

###### Proposition 1

Let $\sigma:\mathbb{F}\to\mathbb{F}$ be a sesqui-morphism. Then, for all
$a,b,a_{i}\in\mathbb{F}$, $c\in\mathbb{F}^{*}$ and all $n\in\mathbf{N}$,

$\displaystyle\sigma(-a)$ $\displaystyle=-\sigma(a)$ (1)
$\displaystyle\sigma(a_{1}\cdot a_{2}\cdots a_{n})$
$\displaystyle=\frac{\sigma(a_{1})\cdot\sigma(a_{2})\cdots\sigma(a_{n})}{\sigma(1)^{n-1}}$
(2) $\displaystyle\sigma(a^{n})$
$\displaystyle=\frac{\sigma(a)^{n}}{\sigma(1)^{n-1}}$ (3)
$\displaystyle\sigma(a^{-n})$
$\displaystyle=\frac{\sigma(1)^{n+1}}{\sigma(a)^{n}}$ (4)
$\displaystyle\sigma\left(\frac{a}{c}\right)$
$\displaystyle=\frac{\sigma(1)\cdot\sigma(a)}{\sigma(c)}$ (5)
$\displaystyle\sigma\left(\frac{a\cdot b}{c}\right)$
$\displaystyle=\frac{\sigma(a)\cdot\sigma(b)}{\sigma(c)}$ (6)

Proof. Equation (1) is trivial since
$\sigma(a)+\sigma(-a)=\sigma(a-a)=\sigma(0)=0$.

Equation (2) will be proved by induction. The case $n=2$ is trivial since
$\tilde{\sigma}$ is an automorphism. Assume $n>2$. Then,

$\displaystyle\sigma(a_{1}\cdot a_{2}\cdots a_{n})$
$\displaystyle=\sigma(a_{1}\cdot a_{2}\cdots
a_{n-1})\cdot\frac{\sigma(a_{n})}{\sigma(1)}$
$\displaystyle=\frac{\sigma(a_{1})\cdot\sigma(a_{2})\cdots\sigma(a_{n-1})}{\sigma(1)^{n-2}}\cdot\frac{\sigma(a_{n})}{\sigma(1)}$

This proves the equation. Equation (3) is a direct consequence of Equation (2)
since $\sigma(a^{n})=\sigma(\underbrace{a\cdots a}_{n})$.

Since $\sigma(a^{-n})=\tilde{\sigma}(a^{-n})\cdot\sigma(1)$, Equation (4)
follows from this equality
$\tilde{\sigma}(a^{-n})=\frac{1}{\tilde{\sigma}(a^{n})}$. Equations (5) and
(6) are consequences of Equations (2)-(4). ∎

Examples of sesqui-morphisms are the identity automorphism (called _symmetric
sesqui-morphism_) and the function $[x\mapsto-x]$ (called _skew-symmetric
sesqui-morphism_). The next proposition states that they are the only ones in
prime fields.

###### Proposition 2

Let $p$ be a prime number and let $\sigma:\mathbb{F}_{p}\to\mathbb{F}_{p}$ be
a function. Then, $\sigma$ is a sesqui-morphism if and only if $\sigma$ is
symmetric or skew-symmetric.

Proof. Assume $\sigma:\mathbb{F}_{p}\to\mathbb{F}_{p}$ is a sesqui-morphism.
It is well-known that the only automorphism in $\mathbb{F}_{p}$, $p$ prime, is
the identity. Hence, $\tilde{\sigma}(a)=a$ for all $a\in\mathbb{F}_{p}$. Thus,
$\sigma(a)=a\cdot\sigma(1)$, and hence, $1=\sigma(\sigma(1))=\sigma(1)^{2}$.
Therefore, $\sigma(1)=\pm 1$.∎

Along this paper, sesqui-morphisms will be denoted by the Greek letter
$\sigma$, and then we will often omit to say "let
$\sigma:\mathbb{F}\to\mathbb{F}$ be a sesqui-morphism".

###  2.3 Matrices and $\mathbb{F}$-Rank-Width

For sets $R$ and $C$, an _$(R,C)$ -matrix_ is a matrix where the rows are
indexed by elements in $R$ and columns indexed by elements in $C$. If the
entries are over a field $\mathbb{F}$, we call it an $(R,C)$-matrix over
$\mathbb{F}$. For an $(R,C)$-matrix $M$, if $X\subseteq R$ and $Y\subseteq C$,
we let ${M}[{X},{Y}]$ be the submatrix of $M$ where the rows and the columns
are indexed by $X$ and $Y$ respectively. Along this paper matrices are denoted
by capital letters, which will allow us to write $m_{xy}$ for ${M}[{x},{y}]$
when it is possible. The matrix rank-function is denoted $\operatorname{rk}$.
We will write $M[X]$ instead of $M[X,X]$ and such submatrices are called
_principal submatrices_. The transpose of a matrix $M$ is denoted by $M^{t}$,
and the inverse of $M$, if it exists, _i.e._ , if $M$ is _non-singular_ , is
denoted by $M^{-1}$. The _determinant_ of $M$ is denoted by $\det(M)$. A
$(V_{1},V_{1})$-matrix $M$ is said _isomorphic_ to a $(V_{2},V_{2})$-matrix
$N$ if there exists a bijection $h:V_{1}\to V_{2}$ such that
$m_{xy}=n_{\scriptsize h(x)h(y)}$. We refer to [15] for our linear algebra
terminology.

For a sesqui-morphism $\sigma:\mathbb{F}\to\mathbb{F}$, a $(V,V)$-matrix $M$
over $\mathbb{F}$ is said _$\sigma$ -symmetric_ if $m_{yx}=\sigma(m_{xy})$ for
all $x,y\in V$. Examples of $\sigma$-symmetric matrices are (skew) symmetric
matrices with $\sigma$ being the (skew) symmetric sesqui-morphism. From
Proposition 2 they are the only $\sigma$-symmetric matrices over prime fields.
A $(V,V)$-matrix $M$ is said _$(\sigma,\epsilon)$ -symmetric_ if
$\epsilon(x)\cdot m_{xy}=\epsilon(y)\cdot\sigma(m_{yx})$ for all $x,y\in V$,
$\epsilon:V\to\\{-1,+1\\}$ being a function. If $\sigma$ is the (skew)
symmetric sesqui-morphism, $(\sigma,\epsilon)$-matrices are called matrices of
_symmetric type_ in [3]. It is worth noticing that a matrix is
$\sigma$-symmetric if and only if it is $(\sigma,\epsilon)$-symmetric with
$\epsilon$ a constant function.

We recall now the notion of _$\mathbb{F}$ -rank-width_ of
$(\sigma,\epsilon)$-matrices. It will be used to extend the notion of rank-
width to directed graphs. The _$\mathbb{F}$ -cut-rank_ function of a
$(\sigma,\epsilon)$-symmetric $(V,V)$-matrix $M$ is the function
$\operatorname{cutrk}^{{\mathbb{F}}}_{M}:2^{V}\to\mathbf{N}$ where
$\operatorname{cutrk}^{{\mathbb{F}}}_{M}(X)=\operatorname{rk}({M}[{X},{V\setminus
X}])$ for all $X\subseteq V$. From Proposition 15 and Theorem 22, the function
$\operatorname{cutrk}^{{\mathbb{F}}}_{M}$ is symmetric and submodular (a more
direct proof for $\sigma$-symmetric matrices can be found in [14], but it can
be easily adapted to $(\sigma,\epsilon)$-symmetric matrices). The
_$\mathbb{F}$ -rank-width_ of a $(\sigma,\epsilon)$-symmetric $(V,V)$-matrix
$M$ is the $\operatorname{cutrk}^{{\mathbb{F}}}_{M}$-width of $V$.

If $G$ is an undirected graph, then its adjacency matrix $A_{G}$ over
$\mathbb{F}_{2}$ is $\sigma_{1}$-symmetric, with $\sigma_{1}$ the identity
automorphism on $\mathbb{F}_{2}$. One easily checks that the rank-width of $G$
[17] is exactly the $\mathbb{F}_{2}$-rank-width of $A_{G}$.

Let $M$ be a matrix of the form $\left(\begin{smallmatrix}A&B\\\
C&D\end{smallmatrix}\right)$ where $A:=M[X]$ is non-singular. The _Schur
complement of $A$ in $M$_, denoted by $M/A$, is $D-C\cdot A^{-1}\cdot B$. Oum
proved the following.

######  Theorem 3 ([19])

Let $\mathbb{F}$ be a finite field and $k$ a positive integer. For every
infinite sequence $M_{1},M_{2},\ldots$ of symmetric or skew-symmetric matrices
over $\mathbb{F}$ of $\mathbb{F}$-rank-width at most $k$, there exist $i<j$
such that $M_{i}$ is isomorphic to a principal submatrix of $M_{j}/A$ for some
non-singular principal submatrix $A$ of $M_{j}$.

This theorem unifies in a single one the well-quasi-ordering theorems in [11,
18, 21]. We will show that this theorem still holds in the case of
$(\sigma,\epsilon)$-symmetric matrices that are not necessarily (skew)
symmetric. As a by product, we will get a well-quasi-ordering theorem for
directed graphs. In order to do so, we will adapt the same techniques as Oum’s
proof.

##  3 Chain Groups Revisited

_Chain groups_ were introduced by Tutte [26] for matroids and were also
studied by Bouchet in his series of papers dealing with circle graphs and
eulerian circuits of $4$-regular graphs (see for instance [1, 2, 3]).

The key point in the proof of Theorem 3 is to associate to each (skew)
symmetric matrix a chain group and then use the well-quasi-ordering theorem on
chain groups. We will revise the definitions by Oum so that to associate to
each $(\sigma,\epsilon)$-symmetric matrix a chain group. All the vector spaces
manipulated have finite dimension. The dimension of a vector space $W$ is
denoted by $\dim(W)$. If $f:W\to V$ is a linear transformation, we denote by
$Ker(f)$ the set $\\{u\in W\mid f(u)=0\\}$ and $Im(f)$ the set $\\{f(u)\in
V\mid u\in W\\}$. It is worth noticing that both are vector spaces. For a
vector space $K$, we let $K^{*}:=K\setminus\\{0\\}$.

For a field $\mathbb{F}$ and sesqui-morphism $\sigma:\mathbb{F}\to\mathbb{F}$,
we let $\mathbb{K}_{\sigma}$ be the $2$-dimensional vector space
$\mathbb{F}^{2}$ over $\mathbb{F}$ equipped with the application
$\mathbf{b}_{\sigma}:\mathbb{K}_{\sigma}\times\mathbb{K}_{\sigma}\to\mathbb{F}$
where $\mathbf{b}_{\sigma}(\left(\begin{smallmatrix}a\\\
b\end{smallmatrix}\right),\left(\begin{smallmatrix}c\\\
d\end{smallmatrix}\right))=\sigma(1)\cdot a\cdot\sigma(d)-b\cdot\sigma(c)$.
The application $\mathbf{b}_{\sigma}$ is not bilinear, however it is linear
with respect to its left operand, which is enough for our purposes. It is
worth noticing that if $\sigma$ is skew-symmetric (or symmetric), then
$\mathbf{b}_{\sigma}$ is what is called $b^{+}$ (or $b^{-}$) in [19]. The
following properties are easy to obtain from the definition of
$\mathbf{b}_{\sigma}$.

###### Property 4

Let $u,v,w\in\mathbb{K}_{\sigma}$ and $k\in\mathbb{F}$. Then,

$\displaystyle\mathbf{b}_{\sigma}(u+v,w)$
$\displaystyle=\mathbf{b}_{\sigma}(u,w)+\mathbf{b}_{\sigma}(v,w),$
$\displaystyle\mathbf{b}_{\sigma}(u,v+w)$
$\displaystyle=\mathbf{b}_{\sigma}(u,v)+\mathbf{b}_{\sigma}(u,w),$
$\displaystyle\mathbf{b}_{\sigma}(k\cdot u,v)$
$\displaystyle=k\cdot\mathbf{b}_{\sigma}(u,v),$
$\displaystyle\mathbf{b}_{\sigma}(u,k\cdot v)$
$\displaystyle=\tilde{\sigma}(k)\cdot\mathbf{b}_{\sigma}(u,v).$
$\displaystyle\sigma(\mathbf{b}_{\sigma}(u,v))$
$\displaystyle=\frac{-1}{\sigma(1)^{2}}\cdot\mathbf{b}_{\sigma}(v,u).$

###### Property 5

Let $u\in\mathbb{K}_{\sigma}$.

  1. (i)

If $\mathbf{b}_{\sigma}(u,v)=0$ for all $v\in\mathbb{K}_{\sigma}$, then $u=0$.

  2. (ii)

If $\mathbf{b}_{\sigma}(v,u)=0$ for all $v\in\mathbb{K}_{\sigma}$, then $u=0$.

Let $W$ be a vector space over $\mathbb{F}$ and $\varphi:W\times
W\to\mathbb{F}$ a function. If $\varphi$ satisfies equalities in Property 4,
we call it a _$\sigma$ -sesqui-bilinear form_. It is called a _non-degenerate_
$\sigma$-sesqui-bilinear form if it also satisfies Property 5.

Let $W$ be a vector space over $\mathbb{F}$ equipped with $\varphi$ a non-
degenerate $\sigma$-sesqui-bilinear form. A vector $u$ is said _isotropic_ if
$\varphi(u,u)=0$. A subspace $L$ of $W$ is called _totally isotropic_ if
$\varphi(u,v)=0$ for all $u,v\in L$. For a subspace $L$ of $W$, we let
$L^{\bot}:=\\{v\in W\mid\varphi(u,v)=0$ for all $u\in L\\}$. It is worth
noticing that if $L$ is totally isotropic, then $L\subseteq L^{\bot}$. The
following theorem is a well-known theorem in the case where $\varphi$ is a
non-degenerate bilinear form.

###### Theorem 6

Let $W$ be a vector space over $\mathbb{F}$ equipped with a non-degenerate
$\sigma$-sesqui-bilinear form $\varphi$. Then,
$\dim(L)+\dim(L^{\bot})=\dim(W)$ for any subspace $L$ of $W$.

Proof. The proof is a standard one. We denote by $W^{*}$ the set of linear
transformations $[W\to\mathbb{F}]$. It is well-known that $W^{*}$ is a vector
space. Let $\varphi_{R}:W\to W^{*}$ such that
$\varphi_{R}(u):=[w\mapsto\varphi(w,u)]$. From Property 4, $\varphi_{R}$ is
clearly a linear transformation. Let $\alpha$ be a restriction of
$\varphi_{R}$ to $L$. By a well-known theorem in linear algebra,
$\dim(L)=\dim(Ker(\alpha))+\dim(Im(\alpha))$.

By definition, $Ker(\alpha)=\\{u\in L\mid\varphi(w,u)=0$ for all $w\in W\\}$,
which is equal to $\\{0\\}$ since $\varphi$ is non-degenerate. Hence,
$\dim(Ker(\alpha))=0$, _i.e._ , $\dim(L)=\dim(Im(\alpha))$.

If we let $Im(\alpha)^{\circ}:=\\{v\in W\mid\theta(v)=0$ for all $\theta\in
Im(\alpha)\\}$, we know by a theorem in linear algebra that
$\dim(Im(\alpha))+\dim(Im(\alpha)^{\circ})=\dim(W^{*})$. But,

$\displaystyle Im(\alpha)^{\circ}$ $\displaystyle=\\{v\in W\mid\alpha(w)(v)=0\
\textrm{for all}\ w\in L\\}$ $\displaystyle=\\{v\in W\mid\varphi(v,w)=0\
\textrm{for all}\ w\in L\\}=L^{\bot}.$

Hence, $\dim(L)=\dim(W^{*})-\dim(L^{\bot})=\dim(W)-\dim(L^{\bot})$ since
$\dim(W^{*})=\dim(W)$. ∎

As a consequence, we get that $L=(L^{\bot})^{\bot}$. And, if $L$ is totally
isotropic, then $2\cdot\dim(L)\leq\dim(W)$.

Let $V$ be a finite set and $K$ a vector space over $\mathbb{F}$. A _$K$
-chain on $V$_ is a function $f:V\to K$. We let $K^{V}$ be the set of
$K$-chains on $V$. It is well-known that $K^{V}$ is a vector space over
$\mathbb{F}$ by letting $(f+g)(x):=f(x)+g(x)$ and $(k\cdot f)(x):=k\cdot f(x)$
for all $x\in V$ and $k\in\mathbb{F}$, and by setting the $K$-chain $[x\mapsto
0]$ as the zero vector. It is worth noticing that
$\dim(K^{V})=\dim(K)\cdot|V|$. If $K$ is equipped with a non-degenerate
$\sigma$-sesqui-bilinear form $\varphi$, we let
$\langle,\rangle_{\varphi}:K^{V}\times K^{V}\to\mathbb{F}$ be such that for
all $f,g\in K^{V}$,

$\displaystyle\langle f,g\rangle_{\varphi}$ $\displaystyle:=\sum\limits_{x\in
V}\varphi(f(x),g(x)).$

It is straightforward to verify that $\langle,\rangle_{\varphi}$ is a non-
degenerate $\sigma$-sesqui-bilinear form. (We will often write
$\langle,\rangle$ for convenience when the context is clear.) Subspaces of
$K^{V}$ are called _$K$ -chain groups on $V$_. A $K$-chain group $L$ on $V$ is
said _lagrangian_ if it is totally isotropic and $\dim(L)=|V|$.

A _simple isomorphism_ from a $K$-chain group $L$ on $V$ to a $K$-chain group
$L^{\prime}$ on $V^{\prime}$ is a bijection $\mu:V\to V^{\prime}$ such that
$L=\\{f\circ\mu\mid f\in L^{\prime}\\}$ where $(f\circ\mu)(x)=f(\mu(x))$ for
all $x\in V$. In this case we say that $L$ and $L^{\prime}$ are _simply
isomorphic_.

From now on, we are only interested in $\mathbb{K}_{\sigma}$-chain groups on
$V$. Recall that $\mathbb{K}_{\sigma}$ is the $2$-dimensional vector space
$\mathbb{F}^{2}$ over $\mathbb{F}$ equipped with the $\sigma$-sesqui-bilinear
form $\mathbf{b}_{\sigma}$. The following is a direct consequence of
definitions and Theorem 6.

###### Lemma 7

If $L$ is a totally isotropic $\mathbb{K}_{\sigma}$-chain group on $V$, then
$\dim(L)\leq|V|$. If $L$ is lagrangian, then $L=L^{\bot}$.

###### Lemma 8

Let $u,v\in\mathbb{K}_{\sigma}$ and assume $u\neq 0$ is isotropic. If
$\mathbf{b}_{\sigma}(u,v)=0$, then $v=c\cdot u$ for some $c\in\mathbb{F}$.

Proof. Since $\mathbf{b}_{\sigma}$ is non-degenerate, there exists
$u^{\prime}\in\mathbb{K}_{\sigma}$ such that
$\mathbf{b}_{\sigma}(u,u^{\prime})\neq 0$. In this case, $\\{u,u^{\prime}\\}$
is a basis for $\mathbb{K}_{\sigma}$ (Property 4). Hence, there exist
$c,d\in\mathbb{F}$ such that $v=c\cdot u+d\cdot u^{\prime}$. Therefore,

$\displaystyle\mathbf{b}_{\sigma}(u,v)$
$\displaystyle=\frac{\sigma(c)}{\sigma(1)}\cdot\mathbf{b}_{\sigma}(u,u)+\frac{\sigma(d)}{\sigma(1)}\cdot\mathbf{b}_{\sigma}(u,u^{\prime})=\frac{\sigma(d)}{\sigma(1)}\cdot\mathbf{b}_{\sigma}(u,u^{\prime}).$

Since $\mathbf{b}_{\sigma}(u,u^{\prime})\neq 0$ and
$\mathbf{b}_{\sigma}(u,v)=0$, we have that $\sigma(d)=0$, _i.e._ , $d=0$. ∎

We now introduce _minors_ for $\mathbb{K}_{\sigma}$-chain groups on $V$. If
$f$ is a $\mathbb{K}_{\sigma}$-chain on $V$, then $Sp(f):=\\{x\in V\mid
f(x)\neq 0\\}$. If $L\subseteq\mathbb{K}_{\sigma}^{V}$ and $X\subseteq V$, we
let $L_{\mid X}:=\\{\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.16167pt}}_{\,X}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.16167pt}}_{\,X}}\mid f\in L\\}$ and $L^{\mid
X}:=\\{\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.16167pt}}_{\,X}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.16167pt}}_{\,X}}\mid f\in L$ and $Sp(f)\subseteq
X\\}$. For $\alpha\in\mathbb{K}_{\sigma}^{*}$ and $X\subseteq V$, we let
$L\operatorname{\parallel}\limits_{\alpha}X$ be the
$\mathbb{K}_{\sigma}$-chain group

$\displaystyle L\operatorname{\parallel}\limits_{\alpha}X$
$\displaystyle:=\\{\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus X)}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus X)}}{{f\,\smash{\vrule
height=3.88889pt,depth=2.12502pt}}_{\,(V\setminus X)}}{{f\,\smash{\vrule
height=2.77777pt,depth=2.12502pt}}_{\,(V\setminus X)}}\mid f\in L\ \textrm{and
$\mathbf{b}_{\sigma}(f(x),\alpha)=0$ for all}\ x\in X\\}$

on $V\setminus X$. A pair $\\{\alpha,\beta\\}\subseteq\mathbb{K}_{\sigma}^{*}$
is said _minor-compatible_ if
$\mathbf{b}_{\sigma}(\alpha,\alpha)=\mathbf{b}_{\sigma}(\beta,\beta)=0$ and
$\\{\alpha,\beta\\}$ forms a basis for $\mathbb{K}_{\sigma}$. For a minor-
compatible pair $\\{\alpha,\beta\\}$, a $\mathbb{K}_{\sigma}$-chain group on
$V\setminus(X\cup Y)$ of the form
$L\operatorname{\parallel}\limits_{\alpha}X\operatorname{\parallel}\limits_{\beta}Y$
is called an _$\alpha\beta$ -minor_ of $L$.

One easily verifies that
$L\operatorname{\parallel}\limits_{\alpha}X\operatorname{\parallel}\limits_{\alpha}Y=L\operatorname{\parallel}\limits_{\alpha}(X\cup
Y)$, and
$L\operatorname{\parallel}\limits_{\alpha}X\operatorname{\parallel}\limits_{\beta}Y=L\operatorname{\parallel}\limits_{\beta}Y\operatorname{\parallel}\limits_{\alpha}X$.
Hence, we have the following which is already proved in [19] for a special
case of $\\{\alpha,\beta\\}$.

###### Proposition 9

Let $\\{\alpha,\beta\\}$ be minor-compatible. An $\alpha\beta$-minor of an
$\alpha\beta$-minor of $L$ is an $\alpha\beta$-minor of $L$.

We now prove that $\alpha\beta$-minors of lagrangian
$\mathbb{K}_{\sigma}$-chain groups are also lagrangian. The proofs are the
same as in [19]. We include some of them that we expect can convince the
reader that the proofs are not different.

###### Proposition 10

Let $\\{\alpha,\beta\\}$ be minor-compatible. An $\alpha\beta$-minor of a
totally isotropic $\mathbb{K}_{\sigma}$-chain group $L$ on $V$ is totally
isotropic.

Proof. Let
$L^{\prime}:=L\operatorname{\parallel}\limits_{\alpha}X\operatorname{\parallel}\limits_{\beta}Y$
be an $\alpha\beta$-minor of $L$ on $V^{\prime}:=V\setminus(X\cup Y)$. Let
$f^{\prime},g^{\prime}\in L^{\prime}$ and let $f,g\in L$ such that
$f^{\prime}=\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}$ and
$g^{\prime}=\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=2.41112pt,depth=1.53944pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=1.72221pt,depth=1.53944pt}}_{\,V^{\prime}}}$. By Lemma 8, for all $x\in
X\cup Y$, $\mathbf{b}_{\sigma}(f(x),g(x))=0$. Hence, $\sum\limits_{x\in
V}\mathbf{b}_{\sigma}(f(x),g(x))=\sum\limits_{x\in
V^{\prime}}\mathbf{b}_{\sigma}(f(x),g(x))=\langle
f^{\prime},g^{\prime}\rangle$. Therefore, $\langle
f^{\prime},g^{\prime}\rangle=0$. ∎

###### Lemma 11

Let $L$ be a $\mathbb{K}_{\sigma}$-chain group on $V$ and $X\subseteq V$.
Then, $\dim(L_{\mid X})+\dim(L^{\mid(V\setminus X)})=\dim(L)$

Proof. Let $\varphi:L\to L_{\mid X}$ be the linear transformation that maps
any $f\in L$ to $\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=5.55557pt,depth=1.65279pt}}_{\,X}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.16167pt}}_{\,X}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.16167pt}}_{\,X}}$. We have clearly $L_{\mid
X}=Im(\varphi)$. For any $f\in Ker(\varphi)$, we have $f(x)=0$ for all $x\in
X$. Hence, $L^{\mid(V\setminus X)}=Ker(\varphi)$. This concludes the lemma. ∎

For any $x\in V$ and $\gamma\in\mathbb{K}_{\sigma}^{*}$, we let $x^{\gamma}$
be the $\mathbb{K}_{\sigma}$-chain on $V$ such that

$\displaystyle x^{\gamma}(z)$ $\displaystyle:=\begin{cases}\gamma&\textrm{if
$z=x$},\\\ 0&\textrm{otherwise}.\end{cases}$

The following admits a similar proof as the one in [19, Proposition 3.6].

###### Proposition 12

Let $L$ be a $\mathbb{K}_{\sigma}$-chain group on $V$, $x\in V$ and
$\gamma\in\mathbb{K}_{\sigma}^{*}$. Hence,

$\displaystyle\dim(L\operatorname{\parallel}\limits_{\gamma}x)$
$\displaystyle=\begin{cases}\dim(L)&\textrm{if $x^{\gamma}\in
L^{\bot}\setminus L$},\\\ \dim(L)-2&\textrm{if $x^{\gamma}\in L\setminus
L^{\bot}$},\\\ \dim(L)-1&\textrm{otherwise}.\end{cases}$

###### Corollary 13

Let $\\{\alpha,\beta\\}$ be minor-compatible. If $L$ is a totally isotropic
$\mathbb{K}_{\sigma}$-chain group on $V$ and $L^{\prime}$ is an
$\alpha\beta$-minor of $L$ on $V^{\prime}$, then
$|V^{\prime}|-\dim(L^{\prime})\leq|V|-\dim(L)$.

Proof. By induction on $|V\setminus V^{\prime}|$. Since $L$ is totally
isotropic, for all $x\in V\setminus V^{\prime}$, we cannot have neither
$x^{\alpha}\in L\setminus L^{\bot}$ nor $x^{\beta}\in L\setminus L^{\bot}$.
Hence, $\dim(L)-\dim(L\operatorname{\parallel}\limits_{\alpha}x)\in\\{0,1\\}$
and $\dim(L)-\dim(L\operatorname{\parallel}\limits_{\beta}x)\in\\{0,1\\}$ by
Proposition 12. Hence, if $|V\setminus V^{\prime}|=1$, we are done.

If $|V\setminus V^{\prime}|>1$, let $x\in V\setminus V^{\prime}$. Hence,
$L^{\prime}$ is an $\alpha\beta$-minor of
$L\operatorname{\parallel}\limits_{\alpha}x$ or
$L\operatorname{\parallel}\limits_{\beta}x$. By inductive hypothesis,
$|V^{\prime}|-\dim(L^{\prime})\leq|V\setminus
x|-\dim(L\operatorname{\parallel}\limits_{\alpha}x)$ or
$|V^{\prime}|-\dim(L^{\prime})\leq|V\setminus
x|-\dim(L\operatorname{\parallel}\limits_{\beta}x)$. And since, $|V\setminus
x|-\dim(L\operatorname{\parallel}\limits_{\alpha}x)\leq|V|-\dim(L)$ and
$|V\setminus
x|-\dim(L\operatorname{\parallel}\limits_{\beta}x)\leq|V|-\dim(L)$, we are
done. ∎

###### Proposition 14

Let $\\{\alpha,\beta\\}$ be minor-compatible. An $\alpha\beta$-minor of a
lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$ is lagrangian.

Proof. Let $L^{\prime}$ be an $\alpha\beta$-minor of $L$ on $V^{\prime}$. By
Proposition 10, $L^{\prime}$ is totally isotropic, hence
$\dim(L^{\prime})\leq|V^{\prime}|$. By Corollary 13,
$|V^{\prime}|-\dim(L^{\prime})\leq 0$ since $\dim(L)=|V|$ ($L$ lagrangian).
Hence, $\dim(L^{\prime})\geq|V^{\prime}|$. ∎

We now define the connectivity function for lagrangian
$\mathbb{K}_{\sigma}$-chain groups. Let $L$ be a lagrangian
$\mathbb{K}_{\sigma}$-chain group on $V$. For every $X\subseteq V$, we let
$\lambda_{L}(X):=|X|-\dim(L^{\mid X})$. Since $L^{\mid X}$ is totally
isotropic, $\dim(L^{\mid X})\leq|X|$, and hence $\lambda_{L}(X)\geq 0$.

######  Proposition 15 ([19])

Let $L$ be a lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$. Then,
$\lambda_{L}$ is symmetric and submodular.

The proof of Proposition 15 uses the fact that
$2\cdot\lambda_{L}(X)=\dim(L)-\dim(L^{\mid X})-\dim(L^{\mid(V\setminus X)})$
and the following theorem by Tutte.

######  Theorem 16 ([19])

If $L$ is a $\mathbb{K}_{\sigma}$-chain group on $V$ and $X\subseteq V$, then
$(L_{\mid X})^{\bot}=(L^{\bot})^{\mid X}$.

The branch-width of a lagrangian $\mathbb{K}_{\sigma}$-chain group $L$ on $V$,
denoted by $\operatorname{bwd}(L)$, is then defined as the $\lambda_{L}$-width
of $V$.

We can now state the well-quasi-ordering of lagrangian
$\mathbb{K}_{\sigma}$-chain groups of bounded branch-width under
$\alpha\beta$-minor. Let us first enrich the $\alpha\beta$-minor to labelled
$\mathbb{K}_{\sigma}$-chain groups on $V$. Let $(Q,\preceq)$ be a well-quasi-
ordered set. A _$Q$ -labelling_ of a lagrangian $\mathbb{K}_{\sigma}$-chain
group $L$ on $V$ is a mapping $\gamma_{L}:V\to Q$. A _$Q$ -labelled_
lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$ is a couple
$(L,\gamma_{L})$ where $L$ is a lagrangian $\mathbb{K}_{\sigma}$-chain group
on $V$ and $\gamma_{L}$ a $Q$-labelling of $L$. A $Q$-labelled lagrangian
$\mathbb{K}_{\sigma}$-chain group $(L^{\prime},\gamma_{L^{\prime}})$ on
$V^{\prime}$ is an _$(\alpha\beta,Q)$ -minor_ of a $Q$-labelled lagrangian
$\mathbb{K}_{\sigma}$-chain group $(L,\gamma_{L})$ on $V$ if $L^{\prime}$ is
an $\alpha\beta$-minor of $L$ and $\gamma_{L^{\prime}}(x)\preceq\gamma_{L}(x)$
for all $x\in V^{\prime}$. $(L,\gamma_{L})$ is _simply isomorphic_ to
$(L^{\prime},\gamma_{L^{\prime}})$ if there exists a simple isomorphism $\mu$
from $L$ to $L^{\prime}$ and $\gamma_{L}=\gamma_{L^{\prime}}\circ\mu$. The
following is more or less proved in [19].

###### Theorem 17

Let $\mathbb{F}$ be a finite field and $k$ a positive integer, and let
$\\{\alpha,\beta\\}$ be minor-compatible. Let $(Q,\preceq)$ be a well-quasi-
ordered set and let $(L_{1},\gamma_{L_{1}}),(L_{2},\gamma_{L_{2}}),\ldots$ be
an infinite sequence of $Q$-labelled lagrangian
$\mathbb{K}_{\sigma_{i}}$-chain groups having branch-width at most $k$. Then,
there exist $i<j$ such that $(L_{i},\gamma_{L_{i}})$ is simply isomorphic to
an $(\alpha\beta,Q)$-minor of $(L_{j},\gamma_{L_{j}})$.

Theorem 17 is proved in [19] for $\alpha=\left(\begin{smallmatrix}1\\\
0\end{smallmatrix}\right),\ \beta=\left(\begin{smallmatrix}0\\\
1\end{smallmatrix}\right)$ and $\langle,\rangle_{\mathbf{b}_{\sigma_{i}}}$
being a (skew) symmetric bilinear form. However, the proof uses only the
axioms in Properties 4 and 5, and Theorem 6. The other necessary ingredients
are Lemmas 7, 8 and 11, Proposition 12, and Theorem 16. We refer to [19] for
the technical details. It is important that the reader keeps in mind that even
if $\mathbf{b}_{\sigma}$ is not a bilinear form, it shares with the bilinear
forms in [19] the necessary properties for proving Theorem 17.

##  4 Representations of $\mathbb{K}_{\sigma}$-Chain Groups by
$(\sigma,\epsilon)$-Symmetric Matrices

In this section we will use Theorem 17 to obtain a similar result for
$(\sigma,\epsilon)$-symmetric matrices. We recall that we use the Greek letter
$\sigma$ for sesqui-morphisms, and if $\mathbb{F}$ is a field, then we let
$\mathbb{K}_{\sigma}$ be the $2$-dimensional vector space $\mathbb{F}^{2}$
over $\mathbb{F}$ equipped with the $\sigma$-sesqui-bilinear form
$\mathbf{b}_{\sigma}$. We will associate with each
$(\sigma,\epsilon)$-symmetric matrix a lagrangian $\mathbb{K}_{\sigma}$-chain
group. These matrices are called _matrix representations_. We also need to
relate $\alpha\beta$-minors of lagrangian $\mathbb{K}_{\sigma}$-chain groups
to principal submatrices of their matrix representations, and relate
$\mathbb{F}$-rank-width of $(\sigma,\epsilon)$-symmetric matrices to branch-
width of lagrangian $\mathbb{K}_{\sigma}$-chain groups. We follow similar
steps as in [19].

Let $\epsilon:V\to\\{-1,+1\\}$ be a function. We say that two
$\mathbb{K}_{\sigma}$-chains $f$ and $g$ on $V$ are _$\epsilon$
-supplementary_ if, for all $x\in V$,

  1. (i)

$\mathbf{b}_{\sigma}(f(x),f(x))=\mathbf{b}_{\sigma}(g(x),g(x))=0$,

  2. (ii)

$\mathbf{b}_{\sigma}(f(x),g(x))=\epsilon(x)\cdot\sigma(1)$ and

  3. (iii)

$\mathbf{b}_{\sigma}(g(x),f(x))=-\epsilon(x)\cdot\sigma(1)^{2}$.

For any $c\in\mathbb{F}^{*}$, we let $c^{*}:=\left(\begin{smallmatrix}c\\\
0\end{smallmatrix}\right)$, $c_{*}:=\left(\begin{smallmatrix}0\\\
c\end{smallmatrix}\right)$, $\widetilde{c^{*}}:=\left(\begin{smallmatrix}0\\\
\sigma(c^{-1})\end{smallmatrix}\right)$ and
$\widetilde{c_{*}}:=\left(\begin{smallmatrix}-\sigma(1)\cdot\sigma(c)^{-1}\\\
0\end{smallmatrix}\right)$.

As a consequence of the following easy property, we get that for any
$\epsilon:V\to\\{-1,+1\\}$, we can construct $\epsilon$-supplementary
$\mathbb{K}_{\sigma}$-chains on $V$.

###### Property 18

For any $c\in\mathbb{F}^{*}$ and $\epsilon\in\\{-1,+1\\}$, we have

$\displaystyle\begin{cases}\mathbf{b}_{\sigma}\left(\epsilon\cdot
c^{*},\widetilde{c^{*}}\right)&=\epsilon\cdot\sigma(1)\\\
\mathbf{b}_{\sigma}\left(\widetilde{c^{*}},\epsilon\cdot
c^{*}\right)&=-\epsilon\cdot\sigma(1)^{2}\end{cases}$ $\displaystyle\
\textrm{and}\ \begin{cases}\mathbf{b}_{\sigma}\left(\epsilon\cdot
c_{*},\widetilde{c_{*}}\right)&=\epsilon\cdot\sigma(1)\\\
\mathbf{b}_{\sigma}\left(\widetilde{c_{*}},\epsilon\cdot
c_{*}\right)&=-\epsilon\cdot\sigma(1)^{2}\end{cases}$

The following associates with each $(\sigma,\epsilon)$-symmetric
$(V,V)$-matrix a lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$.

###### Proposition 19

Let $M$ be a $(\sigma,\epsilon)$-symmetric $(V,V)$-matrix over $\mathbb{F}$,
and let $f$ and $g$ be $\epsilon$-supplementaty $\mathbb{K}_{\sigma}$-chains
on $V$. For every $x\in V$, we let $f_{x}$ be the $\mathbb{K}_{\sigma}$-chain
on $V$ such that, for all $y\in V$,

$\displaystyle f_{x}(y)$ $\displaystyle:=\begin{cases}m_{xx}\cdot
f(x)+g(x)&\textrm{if $y=x$},\\\ m_{xy}\cdot
f(y)&\textrm{otherwise}.\end{cases}$

Then, the $\mathbb{K}_{\sigma}$-chain group on $V$ denoted by $(M,f,g)$ and
spanned by $\\{f_{x}\mid x\in V\\}$ is lagrangian.

Proof. It is enough to prove that for all $x,y$, $\langle
f_{x},f_{y}\rangle=0$ and the $f_{x}$’s are linearly independent.

For all $x,y\in V$ and all $z\in V\setminus\\{x,y\\}$,
$\mathbf{b}_{\sigma}(f_{x}(z),f_{y}(z))=\mathbf{b}_{\sigma}(m_{xz}\cdot
f(z),m_{yz}\cdot
f(z))=m_{xz}\cdot\sigma(m_{yz})\cdot\sigma(1)^{-1}\cdot\mathbf{b}_{\sigma}(f(z),f(z))=0$.
Hence for all $x,y\in V$,

$\displaystyle\langle f_{x},f_{y}\rangle$
$\displaystyle=\mathbf{b}_{\sigma}\left(f_{x}(x),f_{y}(x)\right)+\mathbf{b}_{\sigma}\left(f_{x}(y),f_{y}(y)\right)$
$\displaystyle=\mathbf{b}_{\sigma}\left(m_{xx}\cdot f(x)+g(x),m_{yx}\cdot
f(x)\right)+\mathbf{b}_{\sigma}\left(m_{xy}\cdot f(y),m_{yy}\cdot
f(y)+g(y)\right)$
$\displaystyle=\sigma(m_{yx})\cdot\sigma(1)^{-1}\cdot\mathbf{b}_{\sigma}\left(g(x),f(x)\right)+m_{xy}\cdot\mathbf{b}_{\sigma}\left(f(y),g(y)\right)$
$\displaystyle=\sigma(1)\cdot\left(\epsilon(y)\cdot
m_{xy}-\epsilon(x)\cdot\sigma(m_{yx})\right)$ $\displaystyle=0.$

It remains to prove that the $f_{x}$’s are linearly independent. Assume there
exist constants $c_{x}$ such that $\sum\limits_{x\in V}c_{x}\cdot f_{x}=0$.
Hence, for all $y\in V$, $\mathbf{b}_{\sigma}\left(f(y),\sum\limits_{x\in
V}c_{x}\cdot f_{x}(y)\right)=0$. But for all $x\in V$ and all $y\in V\setminus
x$, $\mathbf{b}_{\sigma}\left(f(y),c_{x}\cdot f_{x}(y)\right)=0$. Hence, for
all $y\in V$, $\mathbf{b}_{\sigma}\left(f(y),\sum\limits_{x\in V}c_{x}\cdot
f_{x}(y)\right)=\mathbf{b}_{\sigma}(f(y),c_{y}\cdot
f_{y}(y))=\epsilon(y)\cdot\sigma(c_{y})$, _i.e._ , $\sigma(c_{y})=0$. Hence,
we conclude that $c_{y}=0$ for all $y\in V$, _i.e._ , the $f_{x}$’s are
linearly independent. ∎

If a lagrangian $\mathbb{K}_{\sigma}$-chain group $L$ is simply isomorphic to
$(M,f,g)$, we call $(M,f,g)$ a _matrix representation of $L$_. One easily
verifies from the definition of $(M,f,g)$, that for all non zero
$\mathbb{K}_{\sigma}$-chains $h\in(M,f,g)$, we do not have
$\mathbf{b}_{\sigma}(h(x),f(x))=0$ for all $x\in V$. We now make precise this
property.

A $\mathbb{K}_{\sigma}$-chain $f$ on $V$ is called an _eulerian chain_ of a
lagrangian $\mathbb{K}_{\sigma}$-chain group $L$ on $V$ if:

  1. (i)

for all $x\in V$, $f(x)\neq 0$ and $\mathbf{b}_{\sigma}(f(x),f(x))=0$, and

  2. (ii)

there is no non-zero $\mathbb{K}_{\sigma}$-chain $h$ in $L$ such that
$\mathbf{b}_{\sigma}(h(x),f(x))=0$ for all $x\in V$.

The proof of the following is the same as in [19].

######  Proposition 20 ([19])

Every lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$ has an eulerian
chain.

Proof. By induction on the size of $V$. We let $\alpha:=c^{*}$ and
$\beta:=\widetilde{c^{*}}$ for some $c\in\mathbb{F}^{*}$. Let $L$ be a
lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$. If $V=\\{x\\}$, then
$\dim(L)=1$, hence either $x^{\alpha}$ or $x^{\beta}$ is an eulerian chain.

Assume $|V|>1$ and let $V^{\prime}:=V\setminus x$ for some $x\in V$. Hence,
both $L\operatorname{\parallel}\limits_{\alpha}x$ and
$L\operatorname{\parallel}\limits_{\beta}x$ are lagrangian. By inductive
hypothesis, there exist $f^{\prime}$ and $g^{\prime}$ such that $f^{\prime}$
(resp. $g^{\prime}$) is an eulerian chain of
$L\operatorname{\parallel}\limits_{\alpha}x$ (resp.
$L\operatorname{\parallel}\limits_{\beta}x$).

Let $f$ and $g$ be $\mathbb{K}_{\sigma}$-chains on $V$ such that
$f(x)=\alpha$, $g(x)=\beta$, and $f^{\prime}=\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}$ and
$g^{\prime}=\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=2.41112pt,depth=1.53944pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=1.72221pt,depth=1.53944pt}}_{\,V^{\prime}}}$. We claim that either $f$
or $g$ is an eulerian chain of $L$. Otherwise, there exist non-zero
$\mathbb{K}_{\sigma}$-chains $h$ and $h^{\prime}$ in $L$ such that
$\mathbf{b}_{\sigma}(h(x),f(x))=0$ and
$\mathbf{b}_{\sigma}(h^{\prime}(x),g(x))=0$ for all $x\in V$. Hence, we have
$\mathbf{b}_{\sigma}(\mathchoice{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}(x),f^{\prime}(x))=0$ and
$\mathbf{b}_{\sigma}(\mathchoice{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=4.77779pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=3.66667pt,depth=1.53944pt}}_{\,V^{\prime}}}(x),g^{\prime}(x))=0$ for
all $x\in V^{\prime}$. Therefore, $\mathchoice{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}=\mathchoice{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=4.77779pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=3.66667pt,depth=1.53944pt}}_{\,V^{\prime}}}=0$, otherwise there is a
contradiction because $\mathchoice{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}\in
L\operatorname{\parallel}\limits_{\alpha}x$ and
$\mathchoice{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=4.77779pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=3.66667pt,depth=1.53944pt}}_{\,V^{\prime}}}\in
L\operatorname{\parallel}\limits_{\beta}x$ by construction of $f$ and $g$.
Thus, $h(x)\neq 0$ and $h^{\prime}(x)\neq 0$, and $\langle
h,h^{\prime}\rangle=\mathbf{b}_{\sigma}(h(x),h^{\prime}(x))$. By Lemma 8, we
have $h(x)=d\cdot\alpha$ and $h^{\prime}(x)=d^{\prime}\cdot\beta$ for some
$d,d^{\prime}\in\mathbb{F}^{*}$. Hence, $\langle
h,h^{\prime}\rangle=d\cdot\sigma(d^{\prime})\neq 0$, which contradicts the
totally isotropy of $L$.∎

The next proposition shows how to construct a matrix representation of a
lagrangian $\mathbb{K}_{\sigma}$-chain group.

###### Proposition 21

Let $L$ be a lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$. Let
$\epsilon:V\to\\{-1,+1\\}$, and let $f$ and $g$ be $\epsilon$-supplementary
with $f$ being an eulerian chain of $L$. For every $x\in V$, there exists a
unique $\mathbb{K}_{\sigma}$-chain $f_{x}\in L$ such that

  1. (i)

$\mathbf{b}_{\sigma}(f(y),f_{x}(y))=0$ for all $y\in V\setminus x$,

  2. (ii)

$\mathbf{b}_{\sigma}(f(x),f_{x}(x))=\epsilon(x)\cdot\sigma(1)$.

Moreover, $\\{f_{x}\mid x\in V\\}$ is a basis for $L$. If we let $M$ be the
$(V,V)$-matrix such that
$m_{xy}:=\mathbf{b}_{\sigma}(f_{x}(y),g(y))\cdot\sigma(1)^{-1}\cdot\epsilon(y)$,
then $M$ is $(\sigma,\epsilon)$-symmetric and $(M,f,g)$ is a matrix
representation of $L$.

Proof. The proof is the same as the one in [19]. We first prove that
$\mathbb{K}_{\sigma}$-chains verifying statements (i) and (ii) exist. For
every $x\in V$, let $g_{x}$ be the $\mathbb{K}_{\sigma}$-chain on $V$ such
that $g_{x}(x)=f(x)$ and $g_{x}(y)=0$ for all $y\in V\setminus x$. We let $W$
be the $\mathbb{K}_{\sigma}$-chain group spanned by $\\{g_{x}\mid x\in V\\}$.
The dimension of $W$ is clearly $|V|$. Let $L+W=\\{h+h^{\prime}\mid h\in L,\
h^{\prime}\in W\\}$. We have $L\cap W=\\{0\\}$ because $f$ is eulerian to $L$.
Hence, $\dim(L+W)=2\cdot|V|$, _i.e._ , $\mathbb{K}_{\sigma}^{V}=L+W$. For each
$x\in V$, let $h_{x}\in\mathbb{K}_{\sigma}^{V}$ such that $h_{x}(x)=g(x)$ and
$h_{x}(y)=0$ for all $y\in V\setminus x$. Hence, there exist $f_{x}\in L$ and
$g^{\prime}_{x}\in W$ such that $h_{x}=f_{x}+g^{\prime}_{x}$. We now prove
that these $f_{x}$’s verify statements (i) and (ii). Let
$g^{\prime}_{x}=\sum\limits_{z\in V}c_{z}\cdot g_{z}$. For all $x\in V$ and
all $y\in V\setminus x$,

$\displaystyle\mathbf{b}_{\sigma}(f(x),f_{x}(x))$
$\displaystyle=\mathbf{b}_{\sigma}(f(x),h_{x}(x)-g^{\prime}_{x}(x))$
$\displaystyle=\mathbf{b}_{\sigma}(f(x),h_{x}(x))-\mathbf{b}_{\sigma}(f(x),g^{\prime}_{x}(x))$
$\displaystyle=\mathbf{b}_{\sigma}(f(x),g(x))-\mathbf{b}_{\sigma}(f(x),c_{x}\cdot
f(x))$ $\displaystyle=\epsilon(x)\cdot\sigma(1)$ and
$\displaystyle\mathbf{b}_{\sigma}(f(y),f_{x}(y))$
$\displaystyle=\mathbf{b}_{\sigma}(f(y),h_{x}(y))-\mathbf{b}_{\sigma}(f(y),c_{y}\cdot
g_{y}(y))$
$\displaystyle=\mathbf{b}_{\sigma}(f(y),0)-\mathbf{b}_{\sigma}(f(y),c_{y}\cdot
f(y))=0.$

We now prove that each $f_{x}$ is unique. Assume there exist $f_{x}$’s and
$f^{\prime}_{x}$’s verifying statements (i) and (ii). For each $x\in V$, we
have
$\mathbf{b}_{\sigma}(f(x),f_{x}(x)-g(x))=\mathbf{b}_{\sigma}(f(x),f_{x}(x))-\mathbf{b}_{\sigma}(f(x),g(x))=0$.
Similarly, $\mathbf{b}_{\sigma}(f(x),f^{\prime}_{x}(x)-g(x))=0$. Hence, by
Lemma 8, $f_{x}(x)=c\cdot f(x)+g(x)$ and $f^{\prime}_{x}(x)=c^{\prime}\cdot
f(x)+g(x)$ for $c,c^{\prime}\in\mathbb{F}^{*}$. We let
$h^{\prime}_{x}=f_{x}-f^{\prime}_{x}$ which belongs to $L$. Therefore, for all
$z\in V$, we have $\mathbf{b}_{\sigma}(f(z),h^{\prime}_{x}(z))=0$. And since
$f$ is eulerian to $L$, we have $h^{\prime}_{x}=0$, _i.e._ ,
$f_{x}=f^{\prime}_{x}$.

By using the same technique as in the proof of Proposition 19, one easily
proves that $\\{f_{x}\mid x\in V\\}$ is linearly independent. It remains to
prove that $M:=(m_{xy})_{x,y\in V}$ with
$m_{xy}=\mathbf{b}_{\sigma}(f_{x}(y),g(y))\cdot\sigma(1)^{-1}\cdot\epsilon(y)$
is $(\sigma,\epsilon)$-symmetric and $L=(M,f,g)$.

We recall that $f(x)$ is isotropic for all $x\in V$. By statement (i) and
Lemma 8, for all $x\in V$ and all $y\in V\setminus x$, we have
$f_{x}(y)=c_{xy}\cdot f(y)$ for some $c_{xy}\in\mathbb{F}$. Hence,
$m_{xy}=c_{xy}$. Similarly, we have $f_{x}(x)=c_{xx}\cdot f(x)+g(x)$ for some
$c_{xx}\in\mathbb{F}$, _i.e._ , $m_{xx}=c_{xx}$. It is thus clear that
$L=(M,f,g)$. We now show that $M$ is $(\sigma,\epsilon)$-symmetric. Since $L$
is isotropic, we have for all $x,y\in V$, $\langle
f_{x},f_{y}\rangle=\mathbf{b}_{\sigma}(f_{x}(x),f_{y}(x))+\mathbf{b}_{\sigma}(f_{x}(y),f_{y}(y))=0$.
But,

$\displaystyle\mathbf{b}_{\sigma}(f_{x}(x),f_{y}(x))+\mathbf{b}_{\sigma}(f_{x}(y),f_{y}(y))$
$\displaystyle=\mathbf{b}_{\sigma}(m_{xx}\cdot f(x)+g(x),m_{yx}\cdot f(x))+$
$\displaystyle\qquad\qquad\qquad\mathbf{b}_{\sigma}(m_{xy}\cdot
f(y),m_{yy}\cdot f(y)+g(y))$
$\displaystyle=\sigma(m_{yx})\cdot\sigma(1)^{-1}\cdot\mathbf{b}_{\sigma}(g(x),f(x))+m_{xy}\cdot\mathbf{b}_{\sigma}(f(y),g(y))$
$\displaystyle=\sigma(1)\cdot(\epsilon(y)\cdot
m_{xy}-\epsilon(x)\cdot\sigma(m_{yx}))$

Hence, $\epsilon(y)\cdot m_{xy}=\epsilon(x)\cdot\sigma(m_{yx})$. ∎

From Proposition 19 (resp. 21), to every every $(\sigma,\epsilon)$-symmetric
$(V,V)$-matrix (resp. lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$) one
can associate a lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$ (resp. a
$(\sigma,\epsilon)$-symmetric $(V,V)$-matrix). The next theorem relates the
branch-width of a lagrangian $\mathbb{K}_{\sigma}$-chain group on $V$ to the
$\mathbb{F}$-rank-width of its matrix-representations. Its proof is present in
[19], but we give it for completeness.

######  Theorem 22 ([19])

Let $(M,f,g)$ be a matrix representation of a lagrangian
$\mathbb{K}_{\sigma}$-chain group $L$ on $V$. For every $X\subseteq V$, we
have $\operatorname{cutrk}^{{\mathbb{F}}}_{M}(X)=\lambda_{L}(X)$.

Proof. We let $\\{f_{x}\mid x\in V\\}$ be the basis of $L$ given in
Proposition 19. Let $A:={M}[{X},{V\setminus X}]$. It is well-known in linear
algebra that $\operatorname{rk}(A)=\operatorname{rk}(A^{t})=|X|-n(A^{t})$
where $n(A^{t})$ is $\dim\left(\\{p\in\mathbb{F}^{X}\mid A^{t}\cdot
p=0\\}\right)=\dim\left(\\{p\in\mathbb{F}^{X}\mid p^{t}\cdot A=0\\}\right)$.
Let $\varphi:\mathbb{F}^{V}\to L$ be such that $\varphi(p):=\sum\limits_{x\in
V}p(x)\cdot f_{x}$. It is clear that $\varphi$ is a linear transformation and
is therefore an isomorphism. Hence,

$\displaystyle\dim(L^{\mid X})$ $\displaystyle=\dim\left(\\{h\in L\mid
Sp(h)\subseteq X\\}\right)$ $\displaystyle=\dim\left(\varphi^{-1}\left(\\{h\in
L\mid Sp(h)\subseteq X\\}\right)\right)$
$\displaystyle=\dim\left(\\{p\in\mathbb{F}^{V}\mid\sum\limits_{x\in
V}p(x)\cdot f_{x}(y)=0\ \textrm{for all}\ y\in V\setminus X\\}\right).$

Now, let $p\in\mathbb{F}^{V}$ such that
$\mathchoice{{\varphi(p)\,\smash{\vrule
height=6.00002pt,depth=2.12502pt}}_{\,X}}{{\varphi(p)\,\smash{\vrule
height=6.00002pt,depth=2.12502pt}}_{\,X}}{{\varphi(p)\,\smash{\vrule
height=4.20001pt,depth=1.4875pt}}_{\,X}}{{\varphi(p)\,\smash{\vrule
height=3.0pt,depth=1.16167pt}}_{\,X}}\in L^{\mid X}$. Then, for all $y\in
V\setminus X$, $\varphi(p)(y)=0$, _i.e._ ,
$\mathbf{b}_{\sigma}(f(y),\varphi(p)(y))=0$. But,
$\varphi(p)(y)=\sum\limits_{x\in V}p(x)\cdot f_{x}(y)$. And, since
$\mathbf{b}_{\sigma}(f(y),f_{x}(y))=0$ for all $x\neq y$, we have
$\mathbf{b}_{\sigma}(f(y),\varphi(p)(y))=\mathbf{b}_{\sigma}(f(y),p(y)\cdot
f_{y}(y))=\sigma(p(y))\cdot\epsilon(y)$, _i.e._ , $p(y)=0$. Hence,

$\displaystyle\dim(L^{\mid X})$
$\displaystyle=\dim\left(\\{p\in\mathbb{F}^{X}\mid\sum\limits_{x\in
X}p(x)\cdot m_{xy}=0\ \textrm{for all}\ y\in V\setminus X\\}\right)$
$\displaystyle=\dim\left(\\{p\in\mathbb{F}^{X}\mid p^{t}\cdot A=0\\}\right)$
$\displaystyle=n(A^{t})$

Since, $\lambda_{L}(X)=|X|-\dim(L^{\mid X})$, we can conclude that
$\operatorname{cutrk}^{{\mathbb{F}}}_{M}(X)=\lambda_{L}(X)$. ∎

It remains now to relate $\alpha\beta$-minors of lagrangian
$\mathbb{K}_{\sigma}$-chain groups to principal submatrices of their matrix
representations. For doing so, we need to prove some technical lemmas. For
$X\subseteq V$, we let $P_{X}$ and $I_{X}$ be the non-singular diagonal
$(V,V)$-matrices where

$\displaystyle P_{X}[x,x]$ $\displaystyle:=\begin{cases}\sigma(-1)&\textrm{if
$x\in X$},\\\ 1&\textrm{otherwise},\end{cases}$ and $\displaystyle\quad
I_{X}[x,x]:=\begin{cases}-1&\textrm{if $x\in X$},\\\
1&\textrm{otherwise.}\end{cases}$

If $M$ is a matrix of the form $\left(\begin{smallmatrix}\alpha&\beta\\\
\gamma&\delta\end{smallmatrix}\right)$ where $\alpha:=M[X]$ is non-singular,
the _principal pivot transform_ of $M$ at $X$, denoted by $M*X$, is the matrix

$\displaystyle\centering\begin{pmatrix}\alpha^{-1}&\alpha^{-1}\cdot\beta\\\
-\gamma\cdot\alpha^{-1}&\ \ M/\alpha\end{pmatrix}.\@add@centering$

The principal pivot transform was introduced by Tucker [25] in an attempt to
understand the linear algebraic structure of the _simplex method_ by Dantzig.
It appeared to have wide applicability in many domains; without being
exhaustive we can cite linear algebra [24], graph theory [3] and biology [4].

###### Proposition 23

Let $(M,f,g)$ be a matrix representation of a lagrangian
$\mathbb{K}_{\sigma}$-chain group $L$ on $V$. Let $X\subseteq V$ such that
$M[X]$ is non-singular. Let $f^{\prime}$ and $g^{\prime}$ be
$\mathbb{K}_{\sigma}$-chains on $V$ such that, for all $x\in V$,

$\displaystyle f^{\prime}(x)$ $\displaystyle:=\begin{cases}f(x)&\textrm{if
$x\notin X$},\\\ g(x)&\textrm{otherwise},\end{cases}$ and $\displaystyle\quad
g^{\prime}(x)$ $\displaystyle:=\begin{cases}g(x)&\textrm{if $x\notin X$},\\\
\sigma(-1)\cdot f(x)&\textrm{otherwise}.\end{cases}$

Then, $(P_{X}\cdot(M*X),f^{\prime},g^{\prime})$ is a matrix representation of
$L$.

Proof. Let $\epsilon$ be such that $M$ is $(\sigma,\epsilon)$-symmetric,
_i.e._ , $f$ and $g$ are $\epsilon$-supplementary. Let us first show that
$f^{\prime}$ and $g^{\prime}$ are $\epsilon$-supplementary. Since for all
$x\notin X$, we have $f^{\prime}(x)=f(x)$ and $g^{\prime}(x)=g(x)$, we need to
verify the properties of $\epsilon$-supplementary for the $x\in X$. For each
$x\in X$, we have:

$\displaystyle\mathbf{b}_{\sigma}(f^{\prime}(x),f^{\prime}(x))$
$\displaystyle=\mathbf{b}_{\sigma}(g(x),g(x))=0$
$\displaystyle\mathbf{b}_{\sigma}(g^{\prime}(x),g^{\prime}(x))$
$\displaystyle=\mathbf{b}_{\sigma}(\sigma(-1)\cdot f(x),\sigma(-1)\cdot f(x))$
$\displaystyle=\mathbf{b}_{\sigma}(f(x),f(x))=0$
$\displaystyle\mathbf{b}_{\sigma}(f^{\prime}(x),g^{\prime}(x))$
$\displaystyle=\mathbf{b}_{\sigma}(g(x),\sigma(-1)\cdot f(x))$
$\displaystyle=\frac{-1}{\sigma(1)}\cdot\mathbf{b}_{\sigma}(g(x),f(x))=\epsilon(x)\cdot\sigma(1)$
$\displaystyle\mathbf{b}_{\sigma}(g^{\prime}(x),f^{\prime}(x))$
$\displaystyle=\mathbf{b}_{\sigma}(\sigma(-1)\cdot f(x),g(x))$
$\displaystyle=-\sigma(1)\cdot\mathbf{b}_{\sigma}(f(x),g(x))=-\epsilon(x)\cdot\sigma(1)^{2}$

Hence, $f^{\prime}$ and $g^{\prime}$ are $\epsilon$-supplementary. It remains
to show that $f^{\prime}$ is eulerian to $L$. For each $x\in V$, we let
$f_{x}$ be the $\mathbb{K}_{\sigma}$-chain on $V$ such that

$\displaystyle f_{x}(y)$ $\displaystyle:=\begin{cases}m_{xy}\cdot
f(y)&\textrm{if $y\neq x$},\\\ m_{xx}\cdot
f(x)+g(x)&\textrm{otherwise}\end{cases}$

By Propositions 19 and 21 the set $\\{f_{x}\mid x\in V\\}$ is a basis for $L$.
Let $h\in L$ such that $\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))=0$ for all
$y\in V$. Let $h=\sum\limits_{z\in V}c_{z}\cdot f_{z}$. For all $y\notin X$,
we have

$\displaystyle\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$
$\displaystyle=\mathbf{b}_{\sigma}\left(\sum\limits_{z\in V}\left(c_{z}\cdot
m_{zy}\cdot f(y)\right)+c_{y}\cdot g(y),f(y)\right)$
$\displaystyle=\mathbf{b}_{\sigma}(c_{y}\cdot g(y),f(y))$
$\displaystyle=-c_{y}\cdot\epsilon(y)\cdot\sigma(1)^{2}.$

Hence, $c_{y}=0$ for all $y\notin X$. If $y\in X$, then

$\displaystyle\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$
$\displaystyle=\mathbf{b}_{\sigma}\left(\sum\limits_{z\in X}\left(c_{z}\cdot
m_{zy}\cdot f(y)\right)+c_{y}\cdot g(y),g(y)\right)$
$\displaystyle=\sum\limits_{z\in X}\left(c_{z}\cdot
m_{zy}\cdot\mathbf{b}_{\sigma}(f(y),g(y))\right)$
$\displaystyle=\sigma(1)\cdot\epsilon(y)\cdot\sum\limits_{z\in X}c_{z}\cdot
m_{zy}.$

And for $\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$ to being $0$, we must have
$\sum\limits_{z\in X}\left(c_{z}\cdot m_{zy}\right)=0$. But, since $M[X]$ is
non-singular, we have $\sum\limits_{z\in X}\left(c_{z}\cdot m_{zy}\right)=0$
for all $y\in X$ if and only if $c_{z}=0$ for all $z\in X$. Therefore, we have
$h=0$, _i.e._ , $f^{\prime}$ is eulerian.

By Proposition 21 there exists a unique matrix $M^{\prime}$ such that
$L=(M^{\prime},f^{\prime},g^{\prime})$. We will show that
$M^{\prime}=P_{X}\cdot(M*X)$. Assume
$M=\left(\begin{smallmatrix}\alpha&\beta\\\
\gamma&\delta\end{smallmatrix}\right)$ with $\alpha:=M[X]$. Let $I_{f}$ and
$I_{\bar{f}}$ be respectively $(X,X)$ and $(V\setminus X,V\setminus
X)$-diagonal matrices with diagonal entries being the $f(x)$’s. We define
similarly, $I_{g}$ and $I_{\bar{g}}$, but diagonal entries are $g(x)$’s. We
let $A$ be the $(V,V)$-matrix, where $a_{xy}:=f_{x}(y)$. Hence,

$\displaystyle A$ $\displaystyle=\begin{pmatrix}\alpha\cdot
I_{f}+I_{g}&\beta\cdot I_{\bar{f}}\\\ \gamma\cdot I_{f}&\delta\cdot
I_{\bar{f}}+I_{\bar{g}}\end{pmatrix}.$

The row space of $A$ is exactly $L$. Let $B$ be the non-singular
$(V,V)$-matrix

$\displaystyle\begin{pmatrix}\alpha^{-1}&0\\\ -\gamma\cdot\alpha^{-1}&\quad
I\end{pmatrix}.$

Therefore,

$\displaystyle B\cdot A$ $\displaystyle=\begin{pmatrix}\alpha^{-1}\cdot
I_{g}+I_{f}&\alpha^{-1}\cdot\beta\cdot I_{\bar{f}}\\\
-\gamma\cdot\alpha^{-1}\cdot
I_{g}&(\delta-\gamma\cdot\alpha^{-1}\cdot\beta)\cdot
I_{\bar{f}}+I_{\bar{g}}\end{pmatrix}.$

Let $A^{\prime}:=P_{X}\cdot B\cdot A$, and for each $x\in V$, let
$f^{\prime}_{x}$ be the $\mathbb{K}_{\sigma}$-chain on $V$ with
$f^{\prime}_{x}(y):=a^{\prime}_{xy}$. From above, we have that
$\\{f^{\prime}_{x}\mid x\in V\\}$ is a basis for $L$. Let
$C:=P_{X}\cdot(M*X)$. Then, for every $x,y\in V$, we have

$\displaystyle f^{\prime}_{x}(y)$ $\displaystyle=\begin{cases}c_{xy}\cdot
f(y)&\textrm{if $y\neq x$ and $y\notin X$},\\\ c_{xy}\cdot g(y)&\textrm{if
$y\neq x$ and $y\in X$},\\\ c_{xx}\cdot f(x)+g(x)&\textrm{if $y=x\notin
X$},\\\ c_{xx}\cdot g(x)+\sigma(-1)\cdot f(x)&\textrm{if $y=x\in
X$}.\end{cases}$ Hence,
$\displaystyle\mathbf{b}_{\sigma}(f^{\prime}(y),f^{\prime}_{x}(y))$
$\displaystyle=\begin{cases}\mathbf{b}_{\sigma}(f(y),c_{xy}\cdot
f(y))&\textrm{if $y\neq x$ and $y\notin X$},\\\
\mathbf{b}_{\sigma}(g(y),c_{xy}\cdot g(y))&\textrm{if $y\neq x$ and $y\in
X$},\\\ \mathbf{b}_{\sigma}(f(x),c_{xx}\cdot f(x)+g(x))&\textrm{if $y=x\notin
X$},\\\ \mathbf{b}_{\sigma}(g(x),c_{xx}\cdot g(x)+\sigma(-1)\cdot
f(x))&\textrm{if $y=x\in X$}.\end{cases}$

Hence, for all $x\in V$ and all $y\in V\setminus x$, we have
$\mathbf{b}_{\sigma}(f^{\prime}(x),f^{\prime}_{x}(x))=\epsilon(x)\cdot\sigma(1)$
and $\mathbf{b}_{\sigma}(f^{\prime}(y),f^{\prime}_{x}(y))=0$. Therefore, by
Propositions 19 and 21 $\\{f^{\prime}_{x}\mid x\in V\\}$ is the basis
associated with $(M^{\prime},f^{\prime},g^{\prime})$ and
$M^{\prime}=C=P_{X}\cdot(M*X)$. ∎

###### Proposition 24

Let $(M,f,g)$ be a matrix representation of a lagrangian
$\mathbb{K}_{\sigma}$-chain group $L$ on $V$ and let $Z\subseteq V$. Let
$f^{\prime}$ and $g^{\prime}$ be $\mathbb{K}_{\sigma}$-chains on $V$ such that

$\displaystyle f^{\prime}(x)$ $\displaystyle:=\begin{cases}-f(x)&\textrm{if
$x\in Z$},\\\ f(x)&\textrm{otherwise},\end{cases}$ and $\displaystyle\quad
g^{\prime}(x)$ $\displaystyle:=\begin{cases}-g(x)&\textrm{if $x\in Z$},\\\
g(x)&\textrm{otherwise}.\end{cases}$

Then, $(I_{Z}\cdot M,f,g^{\prime})$ and $(M\cdot I_{Z},f^{\prime},g)$ are
matrix representations of $L$.

Proof. Let $\epsilon:V\to\\{+1,-1\\}$ be such that $M$ is
$(\sigma,\epsilon)$-symmetric, _i.e._ , $f$ and $g$ are
$\epsilon$-supplementary. Let $\\{f_{x}\mid x\in V\\}$ be the basis of $L$
associated with $f$ and $g$ by Proposition 19. One easily verifies that
$f^{\prime}$ and $g$, and $f$ and $g^{\prime}$ are
$\epsilon^{\prime}$-supplementary with $\epsilon^{\prime}(x)=-\epsilon(x)$ if
$x\in Z$, otherwise $\epsilon^{\prime}(x)=\epsilon(x)$. Moreover, $f^{\prime}$
is eulerian (because $f$ is eulerian). By Proposition 21, there exist unique
$f^{\prime}_{x}$’s and $f^{\prime\prime}_{x}$’s such that
$(M^{\prime},f^{\prime},g)$ and $(M^{\prime\prime},f,g^{\prime})$ are matrix
representations of $L$ with
$m^{\prime}_{xy}:=\mathbf{b}_{\sigma}(f^{\prime}_{x}(y),g^{\prime}(y))\cdot\sigma(1)^{-1}\cdot\epsilon^{\prime}(y)$
and
$m^{\prime\prime}_{xy}:=\mathbf{b}_{\sigma}(f^{\prime\prime}_{x}(y),g(y))\cdot\sigma(1)^{-1}\cdot\epsilon^{\prime}(y)$.

One easily checks that $\\{-f_{x}\mid x\in Z\\}\cup\\{f_{x}\mid x\in
V\setminus Z\\}$ is the basis of $L$ associated with $f$ and $g^{\prime}$ by
Proposition 21. It remains to prove that $M^{\prime}=M\cdot I_{Z}$. If $x,y\in
Z$, then
$m^{\prime}_{xy}=\mathbf{b}_{\sigma}(-f_{x}(y),-g(y))\cdot(-\epsilon(y))\cdot\sigma(1)^{-1}=-m_{xy}$.
If $x\in Z$ and $y\notin Z$, then
$m^{\prime}_{xy}=\mathbf{b}_{\sigma}(-f_{x}(y),g(y))\cdot\epsilon(y)\cdot\sigma(1)^{-1}=-m_{xy}$.
If $x,y\notin Z$, then
$m^{\prime}_{xy}=\mathbf{b}_{\sigma}(f_{x}(y),g(y))\cdot\epsilon(y)\cdot\sigma(1)^{-1}=m_{xy}$.
And finally if $x\notin Z$ and $y\in Z$,
$m^{\prime}_{xy}=\mathbf{b}_{\sigma}(f_{x}(y),-g(y))\cdot(-\epsilon(y))\cdot\sigma(1)^{-1}=m_{xy}$.
Therefore, $M^{\prime}=I_{Z}\cdot M$.

It is straightforward to check that $\\{f_{x}\mid x\in V\\}$ is the basis of
$L$ associated with $f^{\prime}$ and $g$ by Proposition 21. Then,
$f^{\prime\prime}_{x}=f_{x}$. Let $x\in V$. We have clearly that
$m^{\prime\prime}_{xy}=m_{xy}$ for all $y\in V\setminus Z$. Let now $y\in Z$.
Hence,
$m^{\prime\prime}_{xy}=-\mathbf{b}_{\sigma}(f_{x}(y),g(y))\cdot\epsilon(y)\cdot\sigma(1)^{-1}=-m_{xy}$.
Hence, $M^{\prime\prime}=M\cdot I_{Z}$. ∎

A pair $(p,q)$ of non-zero scalars in $\mathbb{F}$ is said $\sigma$-compatible
if $p^{-1}=\sigma(q)\cdot\sigma(1)^{-1}$ (equivalently
$q^{-1}=\sigma(p)\cdot\sigma(1)^{-1}$). That means that $(q,p)$ is also
$\sigma$-compatible. It is worth noticing that if $(p,q)$ is
$\sigma$-compatible, then $(p^{-1},q^{-1})$ is also $\sigma$-compatible. A
pair $(P,Q)$ of non-singular diagonal $(V,V)$-matrices is said
$\sigma$-compatible if $(p_{xx},q_{xx})$ is $\sigma$-compatible for all $x\in
V$. For instance the pair $(P_{X},P_{X}^{-1})$ is $\sigma$-compatible.

###### Proposition 25

Let $(M,f,g)$ be a matrix representation of a lagrangian
$\mathbb{K}_{\sigma}$-chain group $L$ on $V$ and let $(P,Q)$ be a
$\sigma$-compatible pair of diagonal $(V,V)$-matrices. Let $f^{\prime}$ and
$g^{\prime}$ be $\mathbb{K}_{\sigma}$-chains on $V$ such that for all $x\in
V$, $f^{\prime}(x):=q_{xx}\cdot f(x)$ and $g^{\prime}(x):=p_{xx}\cdot g(x)$.
Then, $(P\cdot M\cdot Q^{-1},f^{\prime},g^{\prime})$ is a matrix
representation of $L$.

Proof. Let $\epsilon:V\to\\{+1,-1\\}$ such that $M$ is
$(\sigma,\epsilon)$-symmetric, _i.e._ , $f$ and $g$ are
$\epsilon$-supplementary. It is a straightforward computation to check that
$f^{\prime}$ and $g^{\prime}$ are $\epsilon$-supplementary
$\mathbb{K}_{\sigma}$-chains on $V$. Moreover, $f^{\prime}$ is eulerian to $L$
(because $f$ is). By Proposition 21, there exists a unique basis
$\\{f^{\prime}_{x}\mid x\in V\\}$ of $L$ such that
$(M^{\prime},f^{\prime},g^{\prime})$ is a matrix representation of $L$ with
$m^{\prime}_{xy}:=\mathbf{b}_{\sigma}(f^{\prime}_{x}(y),g^{\prime}(y))\cdot\epsilon(y)\cdot\sigma(1)^{-1}$.
Let $\\{f_{x}\mid x\in V\\}$ be the basis of $L$ associated with $f$ and $g$
by Proposition 19.

For each $x\in V$, we clearly have
$\mathbf{b}_{\sigma}(f^{\prime}(y),p_{xx}\cdot f_{x}(y))=q_{yy}\cdot
q_{xx}^{-1}\cdot\mathbf{b}_{\sigma}(f(y),f_{x}(y))$ for all $x,y\in V$.
Therefore, for all $x\in V$ and all $y\in V\setminus x$, we have

$\displaystyle\mathbf{b}_{\sigma}(f^{\prime}(x),p_{xx}\cdot f_{x}(x))$
$\displaystyle=\epsilon(x)\cdot\sigma(1),$
$\displaystyle\mathbf{b}_{\sigma}(f^{\prime}(y),p_{xx}\cdot f_{x}(y))$
$\displaystyle=0.$

Hence, by Proposition 21 $f^{\prime}_{x}=p_{xx}\cdot f_{x}$. Then, for each
$x,y\in V$, we have

$\displaystyle m^{\prime}_{xy}$ $\displaystyle=\mathbf{b}_{\sigma}(p_{xx}\cdot
f_{x}(y),p_{yy}\cdot g(y))\cdot\epsilon(y)\cdot\sigma(1)^{-1}$
$\displaystyle=p_{xx}\cdot\sigma(p_{yy})\cdot\sigma(1)^{-1}\cdot\left(\mathbf{b}_{\sigma}(f_{x}(y),g(y))\cdot\epsilon(y)\cdot\sigma(1)^{-1}\right)=p_{xx}\cdot
q_{yy}^{-1}\cdot m_{xy}.$

Hence, $(P\cdot M\cdot Q^{-1},f^{\prime},g^{\prime})$ is a matrix
representation of $L$. ∎

We call $(M,f,g)$ a _special matrix representation_ of a lagrangian
$\mathbb{K}_{\sigma}$-chain group $L$ on $V$ if
$f(x),g(x)\in\\{c^{*},c_{*}\mid c\in\mathbb{F}^{*}\\}$ for all $x\in V$. A
special case of the following is proved in [19].

###### Lemma 26

Let $(M,f,g)$ be a special matrix representation of a lagrangian
$\mathbb{K}_{\sigma}$-chain group $L$ on $V$. Let $f^{\prime}$ be a
$\mathbb{K}_{\sigma}$-chain on $V$ such that
$f^{\prime}(x)\in\\{c^{*},c_{*}\mid c\in\mathbb{F}^{*}\\}$ for all $x\in V$.
Then, $f^{\prime}$ is eulerian if and only if $M[X]$ is non-singular with
$X:=\\{x\in V\mid f^{\prime}(x)\neq c\cdot f(x)$ for some
$c\in\mathbb{F}^{*}\\}$.

Proof. (Proof already present in [19].) Let $\\{f_{x}\mid x\in V\\}$ be the
basis of $L$ associated with $f$ and $g$ from Proposition 19. For each $y\in
X$, there exists $d_{y}\in\mathbb{F}^{*}$ such that

$\displaystyle f^{\prime}(y)$ $\displaystyle=\begin{cases}d_{y}\cdot
f(y)&\textrm{if $y\notin X$},\\\ d_{y}\cdot g(y)&\textrm{if $y\in
X$}.\end{cases}$

Assume that $M[X]$ is non-singular and let $h\in L$ such that
$\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))=0$ for all $y\in V$. Let
$h=\sum\limits_{z\in V}c_{z}\cdot f_{z}$. For all $y\notin X$, we have

$\displaystyle\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$
$\displaystyle=\mathbf{b}_{\sigma}\left(\sum\limits_{z\in V}\left(c_{z}\cdot
m_{zy}\cdot f(y)\right)+c_{y}\cdot g(y),d_{y}\cdot f(y)\right)$
$\displaystyle=\mathbf{b}_{\sigma}(c_{y}\cdot g(y),d_{y}\cdot f(y))$
$\displaystyle=-c_{y}\cdot\sigma(d_{y})\cdot\epsilon(y)\cdot\sigma(1).$

Hence, $c_{y}=0$ for all $y\notin X$. If $y\in X$, then

$\displaystyle\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$
$\displaystyle=\mathbf{b}_{\sigma}\left(\sum\limits_{z\in X}\left(c_{z}\cdot
m_{zy}\cdot f(y)\right)+c_{y}\cdot g(y),d_{y}\cdot g(y)\right)$
$\displaystyle=\sum\limits_{z\in X}\left(c_{z}\cdot
m_{zy}\cdot\frac{\sigma(d_{y})}{\sigma(1)}\cdot\mathbf{b}_{\sigma}(f(y),g(y))\right)$
$\displaystyle=(\sigma(d_{y})\cdot\epsilon(y))\cdot\sum\limits_{z\in
X}c_{z}\cdot m_{zy}.$

For $\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$ to being $0$, we must have
$\sum\limits_{z\in X}\left(c_{z}\cdot m_{zy}\right)=0$. But, since $M[X]$ is
non-singular, we have $\sum\limits_{z\in X}\left(c_{z}\cdot m_{zy}\right)=0$
for all $y\in X$ if and only if $c_{z}=0$ for all $z\in X$. Therefore, we have
$h=0$, _i.e._ , $f^{\prime}$ is eulerian.

Assume now that $M[X]$ is singular. Hence, there exist $c_{z}$ for $z\in X$,
not all zero, such that for all $y\in X$, $\sum\limits_{z\in
X}\left(c_{z}\cdot m_{zy}\right)=0$. Let $h:=\sum\limits_{z\in X}c_{z}\cdot
f_{z}$, which is not zero. Hence, for each $y\notin X$,

$\displaystyle\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$
$\displaystyle=\frac{\sigma(d_{y})}{\sigma(1)}\cdot\mathbf{b}_{\sigma}\left(\sum\limits_{z\in
X}\left(c_{z}\cdot f_{z}(y)\right),f(y)\right)$
$\displaystyle=\frac{\sigma(d_{y})}{\sigma(1)}\cdot\left(\sum\limits_{z\in
X}\left(c_{z}\cdot m_{zy}\cdot\mathbf{b}_{\sigma}(f(y),f(y))\right)\right)=0$

For each $y\in X$,

$\displaystyle\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))$
$\displaystyle=\frac{\sigma(d_{y})}{\sigma(1)}\cdot\mathbf{b}_{\sigma}\left(\sum\limits_{z\in
X}\left(c_{z}\cdot f_{z}(y)\right),g(y)\right)$
$\displaystyle=\frac{\sigma(d_{y})}{\sigma(1)}\cdot\left(\sum\limits_{z\in
X}\left(c_{z}\cdot m_{zy}\cdot\mathbf{b}_{\sigma}(f(y),g(y))\right)\right)$
$\displaystyle=\sigma(d_{y})\cdot\epsilon(y)\cdot\left(\sum\limits_{z\in
X}c_{z}\cdot m_{zy}\right)=0$

Since $h$ is not zero and $\mathbf{b}_{\sigma}(h(y),f^{\prime}(y))=0$ for all
$y\in V$, $f^{\prime}$ is not eulerian. ∎

We now relate special matrix representations of a lagrangian
$\mathbb{K}_{\sigma}$-chain group with the ones of its $\alpha\beta$-minors.

###### Lemma 27

Let $\\{\alpha,\beta\\}\subseteq\\{c^{*},c_{*}\mid c\in\mathbb{F}^{*}\\}$ be
minor-compatible. Let $(M,f,g)$ be a special matrix representation of a
lagrangian $\mathbb{K}_{\sigma}$-chain group $L$ on $V$, and let $x\in V$.
Then, $(M[V\setminus x],\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f\,\smash{\vrule
height=3.88889pt,depth=2.12502pt}}_{\,(V\setminus x)}}{{f\,\smash{\vrule
height=2.77777pt,depth=2.12502pt}}_{\,(V\setminus
x)}},\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{g\,\smash{\vrule
height=2.41112pt,depth=2.12502pt}}_{\,(V\setminus x)}}{{g\,\smash{\vrule
height=1.72221pt,depth=2.12502pt}}_{\,(V\setminus x)}})$ is a special matrix
representation of $L\operatorname{\parallel}\limits_{\alpha}x$ if
$f(x)=c\cdot\alpha$, otherwise of $L\operatorname{\parallel}\limits_{\beta}x$.

Proof. We can assume by symmetry that $f(x)=c\cdot\alpha$. Let $\\{f_{x}\mid
x\in V\\}$ be the basis of $L$ associated with $f$ and $g$ from Proposition
19.

For all $y\in V\setminus x$, we have $f_{y}(x)=m_{yx}\cdot c\cdot\alpha$.
Hence, $f_{y}\in L\operatorname{\parallel}\limits_{\alpha}x$ for all $y\in
V\setminus x$. We claim that the set $\\{\mathchoice{{f_{y}\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f_{y}\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f_{y}\,\smash{\vrule
height=3.88889pt,depth=2.12502pt}}_{\,(V\setminus x)}}{{f_{y}\,\smash{\vrule
height=2.77777pt,depth=2.12502pt}}_{\,(V\setminus x)}}\mid y\in V\setminus
x\\}$ is linearly independent. Suppose the contrary and let
$h:=\sum\limits_{y\in V\setminus x}c_{y}\cdot f_{y}\in L$ with
$\mathchoice{{h\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{h\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{h\,\smash{\vrule
height=3.88889pt,depth=2.12502pt}}_{\,(V\setminus x)}}{{h\,\smash{\vrule
height=2.77777pt,depth=2.12502pt}}_{\,(V\setminus x)}}=0$. Hence,
$h(x)=\sum\limits_{y\in V\setminus x}\left(c_{y}\cdot m_{yx}\cdot
c\cdot\alpha\right)$ and $h(y)=0$ for all $y\in V\setminus x$. Therefore,
$\mathbf{b}_{\sigma}(h(z),f(z))=0$ for all $z\in V$, contradicting the
eulerian of $f$. By Proposition 14,
$L\operatorname{\parallel}\limits_{\alpha}x$ is lagrangian, _i.e._ ,
$\dim(L\operatorname{\parallel}\limits_{\alpha}x)=|V\setminus x|$, hence
$\\{\mathchoice{{f_{y}\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f_{y}\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f_{y}\,\smash{\vrule
height=3.88889pt,depth=2.12502pt}}_{\,(V\setminus x)}}{{f_{y}\,\smash{\vrule
height=2.77777pt,depth=2.12502pt}}_{\,(V\setminus x)}}\mid y\in V\setminus
x\\}$ is a basis for $L\operatorname{\parallel}\limits_{\alpha}x$. But, this
is actually the basis of $(M[V\setminus x],\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{f\,\smash{\vrule
height=3.88889pt,depth=2.12502pt}}_{\,(V\setminus x)}}{{f\,\smash{\vrule
height=2.77777pt,depth=2.12502pt}}_{\,(V\setminus
x)}},\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.97502pt}}_{\,(V\setminus x)}}{{g\,\smash{\vrule
height=2.41112pt,depth=2.12502pt}}_{\,(V\setminus x)}}{{g\,\smash{\vrule
height=1.72221pt,depth=2.12502pt}}_{\,(V\setminus x)}})$ from Proposition 19.
∎

We have then the following.

###### Proposition 28

Let $\\{\alpha,\beta\\}\subseteq\\{c^{*},c_{*}\mid c\in\mathbb{F}^{*}\\}$ be
minor-compatible. Let $L$ and $L^{\prime}$ be lagrangian
$\mathbb{K}_{\sigma}$-chain groups on $V$ and $V^{\prime}$ respectively. Let
$(M,f,g)$ and $(M^{\prime},f^{\prime},g^{\prime})$ be special matrix
representations of $L$ and $L^{\prime}$ respectively with $f(x):=\pm\alpha,\
g(x):=\beta$ for all $x\in V$, and $f^{\prime}(x):=\pm\alpha,\
g^{\prime}(x):=\beta$ for all $x\in V^{\prime}$. If
$L^{\prime}=L\operatorname{\parallel}\limits_{\beta}X\operatorname{\parallel}\limits_{\alpha}Y$,
then $M^{\prime}=\big{(}(M/M[A])[V^{\prime}]\big{)}\cdot I_{Z}$ with
$A\subseteq X$ and $Z:=\\{x\in V^{\prime}\mid f^{\prime}(x)=-f(x)\\}$.

Proof. If $X=\emptyset$, then by Lemma 27
$(M[V^{\prime}],\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}},\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=2.41112pt,depth=1.53944pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=1.72221pt,depth=1.53944pt}}_{\,V^{\prime}}})$ is a special matrix
representation of $L^{\prime}$. By hypothesis,
$g^{\prime}=\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=2.41112pt,depth=1.53944pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=1.72221pt,depth=1.53944pt}}_{\,V^{\prime}}}$. If we let $Z:=\\{x\in
V^{\prime}\mid f^{\prime}(x)=-f(x)\\}$, then by Proposition 24
$(M[V^{\prime}]\cdot I_{Z},f^{\prime},g^{\prime})$ is a special matrix
representation of $L^{\prime}$. Therefore, $M^{\prime}=M[V^{\prime}]\cdot
I_{Z}$ by Proposition 21. We can now assume that $X\neq\emptyset$ and is
minimal with the property that there exists $Y$ such that
$L^{\prime}=L\operatorname{\parallel}\limits_{\beta}X\operatorname{\parallel}\limits_{\alpha}Y$.

We claim that $M[X]$ is non-singular. Assume the contrary and let $f_{1}$ be
the $\mathbb{K}_{\sigma}$-chain on $V$ where $f_{1}(x)=f(x)$ if $x\notin X$,
and $f_{1}(x)=g(x)$ otherwise. By Lemma 26, $f_{1}$ is not eulerian. Hence,
there exists $h\in L$ a non-zero $\mathbb{K}_{\sigma}$-chain on $V$ such that
$\mathbf{b}_{\sigma}(h(x),f_{1}(x))=0$ for all $x\in V$. Then,
$\mathchoice{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}\in L^{\prime}$. And since
$\mathchoice{{f_{1}\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f_{1}\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f_{1}\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{f_{1}\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}=\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}=f^{\prime}$, we have
$\mathchoice{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}=0$ ($f^{\prime}$ is
eulerian). Moreover, there exists $z\in X$ such that $h(z)\neq 0$, otherwise
it contradicts the fact that $f$ is eulerian (recall that for all $y\in
V\setminus X,\ f_{1}(y)=f(y)$). By Lemma 8, we have $h(z)=c_{z}\cdot\beta$,
$c_{z}\in\mathbb{F}^{*}$. Let $h^{\prime}\in L$ such that
$\mathchoice{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=4.77779pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=3.66667pt,depth=1.53944pt}}_{\,V^{\prime}}}\in L^{\prime}$. Then,
$\mathbf{b}_{\sigma}(h^{\prime}(z),\beta)=0$, and hence
$\mathbf{b}_{\sigma}(h(z),h^{\prime}(z))=0$. Thus by Lemma 8,
$h^{\prime}(z)=c_{h^{\prime}}\cdot h(z)$. Hence,
$\mathchoice{{(h^{\prime}-c_{h^{\prime}}\cdot h)\,\smash{\vrule
height=6.80002pt,depth=2.12502pt}}_{\,V^{\prime}}}{{(h^{\prime}-c_{h^{\prime}}\cdot
h)\,\smash{\vrule
height=6.80002pt,depth=2.12502pt}}_{\,V^{\prime}}}{{(h^{\prime}-c_{h^{\prime}}\cdot
h)\,\smash{\vrule
height=4.77779pt,depth=1.55833pt}}_{\,V^{\prime}}}{{(h^{\prime}-c_{h^{\prime}}\cdot
h)\,\smash{\vrule height=3.66667pt,depth=1.55833pt}}_{\,V^{\prime}}}\in
L\operatorname{\parallel}\limits_{\beta}(X\setminus
z)\operatorname{\parallel}\limits_{\alpha}(Y\cup z)$. But, we have
$\mathchoice{{(h^{\prime}-c_{h^{\prime}}\cdot h)\,\smash{\vrule
height=6.80002pt,depth=2.12502pt}}_{\,V^{\prime}}}{{(h^{\prime}-c_{h^{\prime}}\cdot
h)\,\smash{\vrule
height=6.80002pt,depth=2.12502pt}}_{\,V^{\prime}}}{{(h^{\prime}-c_{h^{\prime}}\cdot
h)\,\smash{\vrule
height=4.77779pt,depth=1.55833pt}}_{\,V^{\prime}}}{{(h^{\prime}-c_{h^{\prime}}\cdot
h)\,\smash{\vrule
height=3.66667pt,depth=1.55833pt}}_{\,V^{\prime}}}=\mathchoice{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=6.80002pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=4.77779pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h^{\prime}\,\smash{\vrule
height=3.66667pt,depth=1.53944pt}}_{\,V^{\prime}}}$ because
$\mathchoice{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{h\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}=0$. Therefore,
$L\operatorname{\parallel}\limits_{\beta}X\operatorname{\parallel}\limits_{\alpha}Y\subseteq
L\operatorname{\parallel}\limits_{\beta}(X\setminus
z)\operatorname{\parallel}\limits_{\alpha}(Y\cup z)$. By Proposition 14,
$\dim(L\operatorname{\parallel}\limits_{\beta}X\operatorname{\parallel}\limits_{\alpha}Y)=|V^{\prime}|$
and $\dim(L\operatorname{\parallel}\limits_{\beta}(X\setminus
z)\operatorname{\parallel}\limits_{\alpha}(Y\cup z))=|V\setminus(X\setminus
z)\setminus(Y\cup z)|=|V^{\prime}|$. Hence,
$L\operatorname{\parallel}\limits_{\beta}X\operatorname{\parallel}\limits_{\alpha}Y=L\operatorname{\parallel}\limits_{\beta}(X\setminus
z)\operatorname{\parallel}\limits_{\alpha}(Y\cup z)$. This contradicts the
assumption that $X$ is minimal. Hence, $M[X]$ is non-singular.

Let $M_{1}:=P_{X}\cdot(M*X)$. By Proposition 23, there exist $f_{2}$ and
$g_{2}$ such that $L=(M_{1},f_{2},g_{2})$. By Lemma 27, $(M_{1}[V\setminus
X],\mathchoice{{f_{2}\,\smash{\vrule
height=5.55557pt,depth=2.01506pt}}_{\,V\setminus X}}{{f_{2}\,\smash{\vrule
height=5.55557pt,depth=2.01506pt}}_{\,V\setminus X}}{{f_{2}\,\smash{\vrule
height=3.88889pt,depth=1.43933pt}}_{\,V\setminus X}}{{f_{2}\,\smash{\vrule
height=2.77777pt,depth=1.43933pt}}_{\,V\setminus
X}},\mathchoice{{g_{2}\,\smash{\vrule
height=3.44444pt,depth=2.01506pt}}_{\,V\setminus X}}{{g_{2}\,\smash{\vrule
height=3.44444pt,depth=2.01506pt}}_{\,V\setminus X}}{{g_{2}\,\smash{\vrule
height=2.41112pt,depth=1.43933pt}}_{\,V\setminus X}}{{g_{2}\,\smash{\vrule
height=1.72221pt,depth=1.43933pt}}_{\,V\setminus X}})$ is a matrix
representation of $L\operatorname{\parallel}\limits_{\beta}X$. Notice that
$\mathchoice{{f_{2}\,\smash{\vrule
height=5.55557pt,depth=2.01506pt}}_{\,V\setminus X}}{{f_{2}\,\smash{\vrule
height=5.55557pt,depth=2.01506pt}}_{\,V\setminus X}}{{f_{2}\,\smash{\vrule
height=3.88889pt,depth=1.43933pt}}_{\,V\setminus X}}{{f_{2}\,\smash{\vrule
height=2.77777pt,depth=1.43933pt}}_{\,V\setminus
X}}=\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.01506pt}}_{\,V\setminus X}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.01506pt}}_{\,V\setminus X}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.43933pt}}_{\,V\setminus X}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.43933pt}}_{\,V\setminus X}}$ and
$\mathchoice{{g_{2}\,\smash{\vrule
height=3.44444pt,depth=2.01506pt}}_{\,V\setminus X}}{{g_{2}\,\smash{\vrule
height=3.44444pt,depth=2.01506pt}}_{\,V\setminus X}}{{g_{2}\,\smash{\vrule
height=2.41112pt,depth=1.43933pt}}_{\,V\setminus X}}{{g_{2}\,\smash{\vrule
height=1.72221pt,depth=1.43933pt}}_{\,V\setminus
X}}=\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.01506pt}}_{\,V\setminus X}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.01506pt}}_{\,V\setminus X}}{{g\,\smash{\vrule
height=2.41112pt,depth=1.43933pt}}_{\,V\setminus X}}{{g\,\smash{\vrule
height=1.72221pt,depth=1.43933pt}}_{\,V\setminus X}}$. By Lemma 27,
$(M_{1}[V^{\prime}],\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}},\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=2.41112pt,depth=1.53944pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=1.72221pt,depth=1.53944pt}}_{\,V^{\prime}}})$ is a special matrix
representation of
$L\operatorname{\parallel}\limits_{\beta}X\operatorname{\parallel}\limits_{\alpha}Y$.
But, $f^{\prime}=\pm\mathchoice{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=5.55557pt,depth=2.00412pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=3.88889pt,depth=1.53944pt}}_{\,V^{\prime}}}{{f\,\smash{\vrule
height=2.77777pt,depth=1.53944pt}}_{\,V^{\prime}}}$ and
$g^{\prime}=\mathchoice{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=3.44444pt,depth=2.00412pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=2.41112pt,depth=1.53944pt}}_{\,V^{\prime}}}{{g\,\smash{\vrule
height=1.72221pt,depth=1.53944pt}}_{\,V^{\prime}}}$. Let $Z:=\\{x\in
V^{\prime}\mid f^{\prime}(x)=-f(x)\\}$. By Proposition 24,
$(M_{1}[V^{\prime}]\cdot I_{Z},f^{\prime},g^{\prime})$ is a special matrix
representation of $L^{\prime}$. Therefore, $M^{\prime}=M_{1}[V^{\prime}]\cdot
I_{Z}$ by Proposition 21. And, the fact that
$M_{1}[V^{\prime}]=(M/M[X])[V^{\prime}]$ finishes the proof. ∎

We are now ready to prove the principal result of the paper.

###### Theorem 29

Let $\mathbb{F}$ be a finite field and $k$ a positive integer. For every
infinite sequence $M_{1},M_{2},\ldots$ of
$(\sigma_{i},\epsilon_{i})$-symmetric $(V_{i},V_{i})$-matrices over
$\mathbb{F}$ of $\mathbb{F}$-rank-width at most $k$, there exist $i<j$ such
that $M_{i}$ is isomorphic to $\big{(}(M_{j}/M_{j}[A])[V^{\prime}]\big{)}\cdot
I_{Z}$ with $A\subseteq V_{j}\setminus V^{\prime}$ and $Z\subseteq
V^{\prime}$.

Proof. Let $\alpha:=c^{*}$ and $\beta:=\widetilde{c^{*}}$ for some
$c\in\mathbb{F}^{*}$. Since the set of sesqui-morphisms over $\mathbb{F}$ is
finite, we can assume by taking a sub-sequence that each matrix $M_{i}$ is
$(\sigma,\epsilon_{i})$-symmetric, for some sesqui-morphism
$\sigma:\mathbb{F}\to\mathbb{F}$. For each $i$, let $f_{i}$ and $g_{i}$ be
$\mathbb{K}_{\sigma}$-chains on $V_{i}$ with
$f_{i}(x):=\epsilon_{i}(x)\cdot\alpha$ and $g_{i}(x):=\beta$ for all $x\in
V_{i}$. Let $L_{i}$ be $(M_{i},f_{i},g_{i})$. By Theorem 17, there exist $i<j$
such that $L_{i}$ is simply isomorphic to an $\alpha\beta$-minor of $L_{j}$.
Let $X,Y\subseteq V_{j}$ such that $L_{i}$ is simply isomorphic to
$L_{j}\operatorname{\parallel}\limits_{\beta}X\operatorname{\parallel}\limits_{\alpha}Y$.
Let $V^{\prime}:=V_{j}\setminus(X\cup Y)$. By Proposition 28, $M_{i}$ is
isomorphic to $\big{(}(M_{j}/M_{j}[A])[V^{\prime}]\big{)}\cdot I_{Z}$ with
$A\subseteq X$ and $Z\subseteq V^{\prime}$.∎

Since each symmetric (or skew-symmetric) $(V,V)$-matrix is a
$(\sigma,\epsilon)$-symmetric $(V,V)$-matrix with $\epsilon(x)=1$ for all
$x\in V$, and $\sigma$ being symmetric (or skew-symmetric), Theorem 3 is a
corollary of Theorem 29. It is worth noticing as noted in [19] that the well-
quasi-ordering results in [11, 17, 21] are corollaries of Theorem 3, hence of
Theorem 29. We give some other corollaries about graphs in the next section.

##  5 Applications to Graphs

Clique-width was defined by Courcelle et al. [6] for graphs (directed or not,
with edge-colours or not). But, the notion of rank-width introduced by Oum and
Seymour in [20] and studied by Oum (see for instance [17, 18]) concerned only
undirected graphs. Rao and myself we generalised in [14] the notion of rank-
width to directed graphs, and more generally to edge-coloured graphs. We give
well-quasi-ordering theorems for directed graphs and edge-coloured graphs.

###  5.1 The Case of Edge-Coloured Graphs

Let $C$ be a (possibly infinite) set that we call the _colours_. A _$C$
-coloured graph_ $G$ is a tuple $(V_{G},E_{G},\ell_{G})$ where $(V_{G},E_{G})$
is a directed graph and $\ell_{G}:E_{G}\to 2^{C}\setminus\\{\emptyset\\}$ is a
function. Its associated _underlying graph_ $\mathpzc{u}(G)$ is the directed
graph $(V_{G},E_{G})$. Two $C$-coloured graphs $G$ and $H$ are isomorphic if
there is an isomorphism $h$ between $\mathpzc{u}(G)$ and $\mathpzc{u}(H)$ such
that for every $(x,y)\in E_{G}$, $\ell_{G}((x,y))=\ell_{H}((h(x),h(y))$. We
call $h$ an _isomorphism_ between $G$ and $H$. It is worth noticing that an
edge-uncoloured graph can be seen as an edge-coloured graph where all the
edges have the same colour.

The notion of rank-width of $C$-coloured graphs is based on the
$\mathbb{F}$-rank-width of $(\sigma,\epsilon)$-symmetric matrices. Let
$\mathbb{F}$ be a field. An _$\mathbb{F}^{*}$ -graph_ $G$ is an
$\mathbb{F}^{*}$-coloured graph where for every edge $(x,y)\in E_{G}$, we have
$\ell_{G}((x,y))\in\mathbb{F}^{*}$, _i.e._ , each edge has exactly one colour
in $\mathbb{F}^{*}$. It is clear that every directed graph is an
$\mathbb{F}_{2}^{*}$-graph. One interesting point is that every
$\mathbb{F}^{*}$-graph $G$ can be represented by a $(V_{G},V_{G})$-matrix
$M_{G}$ over $\mathbb{F}$, that generalises the adjacency matrix of directed
graphs, such that

$\displaystyle{M_{G}}[{x},{y}]:=\begin{cases}\ell_{G}((x,y))&\textrm{if
$(x,y)\in E_{G}$},\\\ 0&\textrm{otherwise}.\end{cases}$

If $M_{G}$ is $(\sigma,\epsilon)$-symmetric, we call $G$ a
_$(\sigma,\epsilon)$ -symmetric $\mathbb{F}^{*}$-graph_. It is worth noticing
that in this case $\mathpzc{u}(G)$ is undirected. Not all
$\mathbb{F}^{*}$-graphs are $(\sigma,\epsilon)$-symmetric, however we have the
following.

######  Proposition 30 ([14])

Let $\mathbb{F}$ be a finite field. Then, one can construct a sesqui-morphism
$\sigma:\mathbb{F}^{2}\to\mathbb{F}^{2}$ where $\mathbb{F}^{2}$ is an
algebraic extension of $\mathbb{F}$ of order $2$. Moreover, for every
$\mathbb{F}^{*}$-graph $G$, one can associate a $\sigma$-symmetric
$(\mathbb{F}^{2})^{*}$-graph $\widetilde{G}$ such that for every
$\mathbb{F}^{*}$-graphs $G$ and $H$, $\widetilde{G}$ and $\widetilde{H}$ are
isomorphic if and only if $G$ and $H$ are isomorphic.

In order to define a notion of rank-width for $C$-coloured graphs, we proceed
as follows. For a $C$-coloured graph $G$, let $\Pi(G)\subseteq 2^{C}$ be the
set of subsets of $C$ appearing as colours of edges in $G$.

  1. 1.

take an injection $i:\Pi(G)\to\mathbb{F}^{*}$ for a large enough finite field
$\mathbb{F}$ and let $G^{\prime}$ be the $\mathbb{F}^{*}$-graph obtained from
$G$ by replacing each edge colour $A\subseteq C$ by $i(A)$. If the
$\mathbb{F}^{*}$-graph $G^{\prime}$ is $(\sigma,\epsilon)$-symmetric for some
sesqui-morphism $\sigma:\mathbb{F}\to\mathbb{F}$, then define the
$\mathbb{F}$-rank-width of $G$ as the $\mathbb{F}$-rank-width of
$M_{G^{\prime}}$. Otherwise,

  2. 2.

take $\widetilde{G^{\prime}}$ from Proposition 30.
$M_{\widetilde{G^{\prime}}}$ is $\sigma$-symmetric for some
$\sigma:\mathbb{F}^{2}\to\mathbb{F}^{2}$. The _$\mathbb{F}^{2}$ -rank-width_
of $G$ will be defined as the $\mathbb{F}^{2}$-rank-width of
$M_{\widetilde{G^{\prime}}}$.

The choice of the injection in step (1) above is not unique and leads to
different representations of $C$-coloured graphs, and then different
parameters. However, as proved in [14], the parameters are equivalent.
Therefore, in order to investigate the structure of $C$-coloured graphs, we
can concentrate our efforts in $(\sigma,\epsilon)$-symmetric
$\mathbb{F}^{*}$-graphs. The authors in [14] did only consider
$\sigma$-symmetric graphs. We relax this constraint because we may have some
$\mathbb{F}^{*}$-graphs which are $(\sigma,\epsilon)$-symmetric but are not
$\sigma^{\prime}$-symmetric at all, for all sesqui-morphisms
$\sigma^{\prime}:\mathbb{F}\to\mathbb{F}$. Examples of such graphs are
$\mathbb{F}^{*}$-graphs $G$ where $M_{G}$ is obtained from a
$\sigma$-symmetric matrix by multiplying some rows and/or columns by $-1$.

All the results, but the well-quasi-ordering theorem, concerning the rank-
width of undirected graphs are generalised in [14] to the $\mathbb{F}$-rank-
width of $\sigma$-symmetric loop-free $\mathbb{F}^{*}$-graphs. These results
extend easily to $(\sigma,\epsilon)$-symmetric $\mathbb{F}^{*}$-graphs. We
prove here two well-quasi-ordering theorems for $(\sigma,\epsilon)$-symmetric
$\mathbb{F}^{*}$-graphs. For that, we will derive from the principal pivot
transform two notions of pivot-minor: one that preserves the loop-freeness and
one that does not.

We recall that a pair $(P,Q)$ of non-singular diagonal $(V,V)$-matrices is
$\sigma$-compatible if $p_{xx}^{-1}=\sigma(q_{xx})\cdot\sigma(1)^{-1}$
(equivalently $q_{xx}^{-1}=\sigma(p_{xx})\cdot\sigma(1)^{-1}$) for all $x\in
V$, and for $X\subseteq V$, $P_{X}$ and $I_{X}$ are the non-singular diagonal
$(V,V)$-matrices where

$\displaystyle P_{X}[x,x]$ $\displaystyle:=\begin{cases}\sigma(-1)&\textrm{if
$x\in X$},\\\ 1&\textrm{otherwise},\end{cases}$ and $\displaystyle\quad
I_{X}[x,x]:=\begin{cases}-1&\textrm{if $x\in X$},\\\
1&\textrm{otherwise.}\end{cases}$

######  Definition 31 ($\sigma$-loop-pivot complementation)

Let $G$ be a $(\sigma,\epsilon)$-symmetric $\mathbb{F}^{*}$-graph and let
$X\subseteq V_{G}$ such that $M_{G}[X]$ is non-singular. An
$\mathbb{F}^{*}$-graph $G^{\prime}$ is a _$\sigma$ -loop-pivot complementation
of $G$ at $X$_ if $M_{G^{\prime}}:=I_{Z}\cdot P\cdot P_{X}\cdot(M*X)\cdot
Q^{-1}\cdot I_{Z^{\prime}}$ for some $Z,Z^{\prime}\subseteq V_{G}$, and
$(P,Q)$ a pair of $\sigma$-compatible diagonal $(V_{G},V_{G})$-matrices.

An $\mathbb{F}^{*}$-graph $G^{\prime}$ is _$\sigma$ -loop-pivot equivalent_ to
$G$ if $G^{\prime}$ is obtained from $G$ by applying a sequence of
$\sigma$-loop-pivot complementations. An $\mathbb{F}^{*}$-graph $H$ is a
$\sigma$-loop-pivot-minor of $G$ if $H$ is isomorphic to
$G^{\prime}[V^{\prime}],\ V^{\prime}\subseteq V_{G}$, where $G^{\prime}$ is
$\sigma$-loop-pivot equivalent to $G$.

The $\sigma$-loop-pivot complementation does not clearly preserve the loop-
freeness. A corollary of Theorem 22, and Propositions 23, 24 and 25 is the
following.

###### Corollary 32

  1. 1.

Let $G$ be a $(\sigma,\epsilon)$-symmetric $\mathbb{F}^{*}$-graph. If
$G^{\prime}$ is $\sigma$-loop-pivot equivalent to $G$, then $G^{\prime}$ is
$(\sigma,\epsilon^{\prime})$-symmetric for some
$\epsilon^{\prime}:V_{G}\to\\{+1,-1\\}$.

  2. 2.

Let $G$ and $G^{\prime}$ be respectively $(\sigma,\epsilon)$ and
$(\sigma,\epsilon^{\prime})$-symmetric $\mathbb{F}^{*}$-graphs. If
$G^{\prime}$ is $\sigma$-loop-pivot equivalent to $G$, then
$\operatorname{rwd}^{{\mathbb{F}}}(G^{\prime})=\operatorname{rwd}^{{\mathbb{F}}}(G)$.
If $G^{\prime}$ is a $\sigma$-loop-pivot-minor of $G$, then
$\operatorname{rwd}^{{\mathbb{F}}}(G^{\prime})\leq\operatorname{rwd}^{{\mathbb{F}}}(G)$.

We now introduce a variant of the $\sigma$-loop-pivot complementation that
preserves the loop-freeness and prove that Corollary 32 still holds.

######  Definition 33 ($\sigma$-pivot complementation)

Let $G$ be a $(\sigma,\epsilon)$-symmetric loop-free $\mathbb{F}^{*}$-graph
and let $X\subseteq V_{G}$ such that $M_{G}[X]$ is non-singular. A loop-free
$\mathbb{F}^{*}$-graph $H$ is a _$\sigma$ -pivot complementation of $G$ at
$X$_ if $M_{H}$ is obtained from $M_{G^{\prime}}$, $G^{\prime}$ a
$\sigma$-loop-pivot complementation of $G$ at $X$, by replacing each diagonal
entry by $0$.

A loop-free $\mathbb{F}^{*}$-graph $G^{\prime}$ is _$\sigma$ -pivot
equivalent_ to $G$ if $G^{\prime}$ is obtained from $G$ by applying a sequence
of $\sigma$-pivot complementations. A loop-free $\mathbb{F}^{*}$-graph $H$ is
a $\sigma$-pivot-minor of $G$ if $H$ is isomorphic to
$G^{\prime}[V^{\prime}],\ V^{\prime}\subseteq V_{G}$, where $G^{\prime}$ is
$\sigma$-pivot equivalent to $G$.

It is clear that the $\sigma$-pivot complementation preserves the loop-
freeness. The proof of the following is straightforward.

###### Proposition 34

Let $(M,f,g)$ be a matrix representation of a lagrangian
$\mathbb{K}_{\sigma}$-chain group $L$ on $V$ and let $M^{\prime}$ be obtained
from $M$ by replacing each diagonal entry by $0$. Let $g^{\prime}$ be the
$\mathbb{K}_{\sigma}$-chain on $V$ with $g^{\prime}(x):=m_{xx}\cdot
f(x)+g(x)$. Then, $(M^{\prime},f,g^{\prime})$ is a matrix representation of
$L$.

The following is hence true.

###### Corollary 35

  1. 1.

Let $G$ be a $(\sigma,\epsilon)$-symmetric loop-free $\mathbb{F}^{*}$-graph.
If $G^{\prime}$ is $\sigma$-pivot equivalent to $G$, then $G^{\prime}$ is
$(\sigma,\epsilon^{\prime})$-symmetric for some
$\epsilon^{\prime}:V_{G}\to\\{+1,-1\\}$.

  2. 2.

Let $G$ and $G^{\prime}$ be respectively $(\sigma,\epsilon)$ and
$(\sigma,\epsilon^{\prime})$-symmetric loop-free $\mathbb{F}^{*}$-graphs. If
$G^{\prime}$ is $\sigma$-pivot equivalent to $G$, then
$\operatorname{rwd}^{{\mathbb{F}}}(G^{\prime})=\operatorname{rwd}^{{\mathbb{F}}}(G)$.
If $G^{\prime}$ is a $\sigma$-pivot-minor of $G$, then
$\operatorname{rwd}^{{\mathbb{F}}}(G^{\prime})\leq\operatorname{rwd}^{{\mathbb{F}}}(G)$.

As corollaries of Theorem 29, we have the following well-quasi-ordering
theorems for $\mathbb{F}^{*}$-graphs.

###### Theorem 36

Let $\mathbb{F}$ be a finite field and $k$ a positive integer. For every
infinite sequence $G_{1},G_{2},\ldots$ of
$(\sigma_{i},\epsilon_{i})$-symmetric $\mathbb{F}^{*}$-graphs of
$\mathbb{F}$-rank-width at most $k$, there exist $i<j$ such that $G_{i}$ is
isomorphic a $\sigma$-loop-pivot-minor of $G_{j}$.

Proof. Let $M_{G_{1}},M_{G_{2}},\ldots$ be the infinite sequence of
$(\sigma_{i},\epsilon_{i})$-symmetric $(V_{G_{i}},V_{G_{i}})$-matrices over
$\mathbb{F}$ associated with the infinite sequence $G_{1},G_{2},\ldots$. By
definition,
$\operatorname{rwd}^{{\mathbb{F}}}(G_{i})=\operatorname{rwd}^{{\mathbb{F}}}(M_{G_{i}})$.
From Theorem 29, there exist $i<j$ such that $M_{G_{i}}$ is isomorphic to
$\big{(}(M_{G_{j}}/M_{G_{j}}[A])[V^{\prime}]\big{)}\cdot I_{Z}$ with
$A,V^{\prime},Z\subseteq V_{G_{j}}$. But, that means that $G_{i}$ is
isomorphic to a $\sigma$-loop-pivot-minor of $G_{j}$. ∎

###### Theorem 37

Let $\mathbb{F}$ be a finite field and $k$ a positive integer. For every
infinite sequence $G_{1},G_{2},\ldots$ of
$(\sigma_{i},\epsilon_{i})$-symmetric loop-free $\mathbb{F}^{*}$-graphs of
$\mathbb{F}$-rank-width at most $k$, there exist $i<j$ such that $G_{i}$ is
isomorphic to a $\sigma$-pivot-minor of $G_{j}$.

Proof. Let $M_{G_{1}},M_{G_{2}},\ldots$ be the infinite sequence of
$(\sigma_{i},\epsilon_{i})$-symmetric $(V_{G_{i}},V_{G_{i}})$-matrices over
$\mathbb{F}$ associated with the infinite sequence $G_{1},G_{2},\ldots$. By
definition,
$\operatorname{rwd}^{{\mathbb{F}}}(G_{i})=\operatorname{rwd}^{{\mathbb{F}}}(M_{G_{i}})$.
From Theorem 29, there exist $i<j$ such that $M_{G_{i}}$ is isomorphic to
$((M_{G_{j}}/M_{G_{j}}[A])[V^{\prime}])\cdot I_{Z}$ with
$A,V^{\prime},Z\subseteq V_{G_{j}}$. Since, $G_{i}$ is loop-free, this means
that the diagonal entries of
$\big{(}(M_{G_{j}}/M_{G_{j}}[A])[V^{\prime}]\big{)}\cdot I_{Z}$ are equal to
$0$. Hence, $(M_{G_{j}}*A)[V^{\prime}]$ has only zero in its diagonal entries.
Then, $G_{i}$ is isomorphic to a $\sigma$-pivot-minor of $G_{j}$. ∎

###  5.2 A Specialisation to Directed Graphs

We discuss in this section a corollary about directed graphs. Let us first
recall the rank-width notion of directed graphs. We recall that
$\mathbb{F}_{4}$ is the finite field of order four. We let
$\\{0,1,\mathbb{a},{\mathbb{a}^{2}}\\}$ be its elements with the property that
$1+\mathbb{a}+{\mathbb{a}^{2}}=0$ and $\mathbb{a}^{3}=1$. Moreover, it is of
characteristic $2$. We let $\sigma_{4}:\mathbb{F}_{4}\to\mathbb{F}_{4}$ be the
automorphism where $\sigma_{4}(\mathbb{a})={\mathbb{a}^{2}}$ and
$\sigma_{4}({\mathbb{a}^{2}})=\mathbb{a}$. It is clearly a sesqui-morphism.

For every directed graph $G$, let
$\widetilde{G}:=(V_{G},E_{G}\cup\\{(y,x)|(x,y)\in
E_{G}\\},\ell_{\widetilde{G}})$ be the
$\operatorname{\mathbb{F}_{4}}^{*}$-graph where for every pair of vertices
$(x,y)$:

$\displaystyle\ell_{\widetilde{G}}((x,y))$
$\displaystyle:=\begin{cases}1&\textrm{if $(x,y)\in E_{G}\ \textrm{and}\
(y,x)\in E_{G}$},\\\ \mathbb{a}&\textrm{$(x,y)\in E_{G}\ \textrm{and}\
(y,x)\notin E_{G}$},\\\ {\mathbb{a}^{2}}&\textrm{$(y,x)\in E_{G}\
\textrm{and}\ (x,y)\notin E_{G}$},\\\ 0&\textrm{otherwise}.\end{cases}$

It is straightforward to verify that $\widetilde{G}$ is $\sigma_{4}$-symmetric
and there is a one-to-one correspondence between directed graphs and
$\sigma_{4}$-symmetric $\mathbb{F}_{4}^{*}$-graphs. The _rank-width_ of a
directed graph $G$, denoted by
$\operatorname{rwd}^{{\operatorname{\mathbb{F}_{4}}}}(G)$, is the
$\operatorname{\mathbb{F}_{4}}$-rank-width of $\widetilde{G}$ [14]. One easily
verifies that if $G$ is an undirected graph, then the rank-width of $G$ is
exactly the $\mathbb{F}_{4}$-rank-width of $\widetilde{G}$.

A directed graph $H$ is _loop-pivot equivalent_ (resp. _pivot equivalent_) to
a directed graph $G$ if $\widetilde{H}$ is $\sigma_{4}$-loop-pivot equivalent
(resp. $\sigma_{4}$-pivot equivalent) to $\widetilde{G}$; and $H$ is a _loop-
pivot-minor_ (resp. _pivot-minor_) of $G$ if $\widetilde{H}$ is a
$\sigma_{4}$-loop-pivot minor (resp. $\sigma_{4}$-pivot minor) of
$\widetilde{G}$. Since there is a one-to-one correspondence between
$\sigma_{4}$-symmetric $\mathbb{F}_{4}^{*}$-graphs and directed graphs, loop-
pivot equivalence (resp. pivot-equivalence) and loop-pivot minor (resp. pivot-
minor) are well-defined in directed graphs. Figure 1 shows an example of loop-
pivot complementation and pivot complementation.

$x_{2}$$x_{2}$$x_{3}$$x_{4}$$x_{1}$$x_{5}$$x_{6}$$x_{5}$$x_{3}$$x_{6}$$x_{4}$$x_{1}$

Figure 1: (a) A directed graph $G$. (b) The directed graph obtained after a
pivot-complementation of $G$ at $\\{x_{2},x_{5}\\}$. If you apply a loop-
pivot-complementation of $G$ at $\\{x_{2},x_{5}\\}$, you obtain the graph in
(b) with a loop at $x_{1}$.

As a consequence of Theorems 36 and 37 we have the following which generalises
[18, Theorem 4.1].

###### Theorem 38

Let $k$ be a positive integer.

  1. 1.

For every infinite sequence $G_{1},G_{2},\ldots$ of directed graphs of rank-
width at most $k$, there exist $i<j$ such that $G_{i}$ is isomorphic to a
loop-pivot-minor of $G_{j}$.

  2. 2.

For every infinite sequence $G_{1},G_{2},\ldots$ of loop-free directed graphs
of rank-width at most $k$, there exist $i<j$ such that $G_{i}$ is isomorphic
to a pivot-minor of $G_{j}$.

##  6 Delta-Matroids and Chain Groups

In this section we discuss some consequences of results in Sections 3 and 4
about _delta-matroids_. If $V$ is a finite set, then $\mathcal{F}\subseteq
2^{V}$ is said to satisfy the _symmetric exchange axiom_ if:

> (SEA) for $F,F^{\prime}\in\mathcal{F}$, for $x\in F\triangle F^{\prime}$,
> there exists $y\in F^{\prime}\triangle F$ such that
> $F\triangle\\{x,y\\}\in\mathcal{F}$.

A _set system_ is a pair $(V,\mathcal{F})$ where $V$ is finite and
$\emptyset\neq\mathcal{F}\subseteq 2^{V}$. A _delta-matroid_ is a set-system
$(V,\mathcal{F})$ such that $\mathcal{F}$ satisfies (SEA); the elements of
$\mathcal{F}$ are called _feasible sets_. Delta-matroids were introduced in
[2], and as for matroids, are characterised by the validity of a greedy
algorithm. We recall that a set system $\mathcal{M}:=(V,\mathcal{B})$ is a
_matroid_ if $\mathcal{B}$, called the set of _bases_ , satisfy the following
_Exchange Axiom_

> (EA) for $B,B^{\prime}\in\mathcal{B}$, for $x\in B\setminus B^{\prime}$,
> there exists $y\in B^{\prime}\setminus B$ such that
> $B\triangle\\{x,y\\}\in\mathcal{B}$.

It is worth noticing that a matroid is also a delta-matroid (see [2, 3, 10]
for other examples of delta-matroids).

For a set system $\mathcal{S}=(V,\mathcal{F})$ and $X\subseteq V$, we let
$\mathcal{S}\triangle X$ be the set system $(V,\mathcal{F}\triangle X)$ where
$\mathcal{F}\triangle X:=\\{F\triangle X\mid F\in\mathcal{F}\\}$. We have that
$\mathcal{F}\triangle X$ satisfies (SEA) if and only if $\mathcal{F}$
satisfies (SEA). Hence, $\mathcal{S}$ is a delta-matroid if and only if
$\mathcal{S}\triangle X$ is. A delta-matroid $\mathcal{S}=(V,\mathcal{F})$ is
said _equivalent_ to a delta-matroid
$\mathcal{S}^{\prime}=(V,\mathcal{F}^{\prime})$ if there exists $X\subseteq V$
such that $\mathcal{S}=\mathcal{S}^{\prime}\triangle X$. If $M$ is a
$(V,V)$-matrix over a field $\mathbb{F}$, we let $\mathcal{S}(M)$ be the set
system $(V,\mathcal{F}(M))$ where $\mathcal{F}(M):=\\{X\subseteq V\mid M[X]$
is non-singular$\\}$. The following is due to Bouchet [3].

######  Theorem 39 ([3])

Let $M$ be a matrix over $\mathbb{F}$ of symmetric type, _i.e._ , $M$ is
$(\sigma,\epsilon)$-symmetric with $\sigma$ (skew) symmetric. Then,
$\mathcal{S}(M)$ is a delta matroid.

Delta-matroids equivalent to $\mathcal{S}(M)$, for some matrix $M$ over
$\mathbb{F}$ of symmetric type, are called _representable over $\mathbb{F}$_
[3]. A slight modification of the proof given in [10] extends Theorem 39 to
all $(\sigma,\epsilon)$-symmetric matrices.

###### Theorem 40

Let $M$ be a $(\sigma,\epsilon)$-symmetric $(V,V)$-matrix over $\mathbb{F}$.
Then, $\mathcal{S}(M)$ is a delta matroid.

Let us recall the following from Tucker.

######  Theorem 41 ([25])

Let $M$ be a $(V,V)$-matrix such that $M[X]$ is non-singular. For any
$Z\subseteq V$, we have

$\displaystyle\det((M{*}X)[Z])$ $\displaystyle=\pm\frac{\det(M[Z\triangle
X])}{\det(A)}.$

Proof of Theorem 40. Let $X,Y\subseteq V$ such that $M[X]$ and $M[Y]$ are non-
singular. Let $x\in X\triangle Y$. Let $M^{\prime}:=P_{X}\cdot(M*X)$. By
Theorem 41, $M^{\prime}[Z]$ is non-singular if and only if $M[Z\triangle X]$
is non-singular. Assume $m^{\prime}_{xx}\neq 0$, then if we take $y:=x$, we
have that $M[X\triangle\\{x\\}]$ is non-singular. Suppose that
$m^{\prime}_{xx}=0$. Since $M^{\prime}[X\triangle Y]$ is non-singular, there
exists $y\in X\triangle Y$ such that $m^{\prime}_{xy}\neq 0$ and because
$M^{\prime}$ is $(\sigma,\epsilon)$-symmetric, $m^{\prime}_{yx}\neq 0$. Hence,
$M^{\prime}[\\{x,y\\}]$ is non-singular, _i.e._ ,
$M^{\prime}[X\triangle\\{x,y\\}]$ is non-singular. ∎

A consequence of Theorem 40 is that we can extend the notion of
representability of delta-matroids by the following.

> A delta-matroid is _representable over $\mathbb{F}$_ if it is equivalent to
> $\mathcal{S}(M)$ for some $(\sigma,\epsilon)$-symmetric matrix $M$ over
> $\mathbb{F}$.

It is worth noticing from Proposition 2 that over prime fields this notion of
representability is the same as the one defined by Bouchet [3]. We now discuss
some other corollaries. First, if $M$ is a $(\sigma,\epsilon)$-symmetric
$(V,V)$-matrix, then for any $X\subseteq V$ such that $M[X]$ is non-singular,
$\mathcal{S}(M)\triangle X=\mathcal{S}(M^{\prime})$ for any
$M^{\prime}:=I_{Z}\cdot P\cdot P_{X}\cdot(M*X)\cdot Q^{-1}\cdot
I_{Z^{\prime}}$ for some $Z,Z^{\prime}\subseteq V$, and $(P,Q)$ a pair of
$\sigma$-compatible diagonal $(V,V)$-matrices.

Lemma 26 characterises non-singular principal submatrices of
$(\sigma,\epsilon)$-symmetric matrices in terms of eulerian
$\mathbb{K}_{\sigma}$-chains of their associated lagrangian
$\mathbb{K}_{\sigma}$-chain groups. One can derive from this a
characterisation of representable delta-matroids in terms of lagrangian
$\mathbb{K}_{\sigma}$-chain groups.

One can derive from Theorem 29 a well-quasi-ordering theorem for representable
delta-matroids as follows. Let the _branch-width_ of a delta-matroid
$\mathcal{S}$ representable over $\mathbb{F}$ as
$\min\\{\operatorname{rwd}^{{\mathbb{F}}}(M)\mid\mathcal{S}(M)$ is equivalent
to $\mathcal{S}\\}$. A delta-matroid $\mathcal{S}^{\prime}$ is a _minor_ of a
delta-matroid $\mathcal{S}=(V,\mathcal{F})$ if there exist $X,Y\subseteq V$
such that $\mathcal{S}^{\prime}=(V\setminus(X\cup Y),\\{(F\triangle
X)\setminus Y\mid F\in\mathcal{F}\\})$. An extension of [19, Theorem 7.3] is
the following.

###### Theorem 42

Let $\mathbb{F}$ be a finite field and $k$ a positive integer. Every infinite
sequence $\mathcal{S}_{1},\mathcal{S}_{2},\ldots$ of delta-matroids
representable over $\mathbb{F}$ of branch-width at most $k$ has a pair $i<j$
such that $\mathcal{S}_{i}$ is isomorphic to a minor of $\mathcal{S}_{j}$.

Proof. Let $M_{1},M_{2},\ldots$ be $(\sigma_{i},\epsilon_{i})$-symmetric
matrices over $\mathbb{F}$ such that, for every $i$, $\mathcal{S}_{i}$ is
equivalent to $\mathcal{S}(M_{i})$ and the branch-width of $\mathcal{S}_{i}$
is equal to the $\mathbb{F}$-rank-width of $M_{i}$. By Theorem 29, there exist
$i<j$ such that $M_{i}$ is isomorphic to $(M_{j}/M_{j}[A])[V^{\prime}]\cdot
I_{Z}$ with $A\subseteq V_{j}\setminus V^{\prime}$ and $Z\subseteq
V^{\prime}\subseteq V_{j}$. Hence, $\mathcal{S}_{i}$ is isomorphic to a minor
of $\mathcal{S}_{j}$. ∎

We conclude by some questions. It is well-known that columns of a matrix over
a field yields a matroid. It would be challenging to characterise matrices
whose non-singular principal submatrices yield a delta-matroid. Currently,
there is no connectivity function for delta-matroids. Another challenge is to
find a connectivity function for delta-matroids that subsumes the connectivity
function of matroids and such that if a delta-matroid is equivalent to
$\mathcal{S}(M)$, then the branch-width of $\mathcal{S}(M)$ is proportional to
the $\mathbb{F}$-rank-width of $M$.

We would like to thank S. Oum for letting at our disposal a first draft of
[19], which was of great help for our understanding of the problem. We thank
also B. Courcelle and the anonymous referee for their helpful comments. The
author is supported by the DORSO project of “Agence Nationale Pour la
Recherche”.

## References

  * [1] A. Bouchet. Isotropic Systems. European Journal of Combinatorics 8(2):231–244, 1987.
  * [2] A. Bouchet. Greedy Algorithm and Symmetric Matroids. Mathematical Programming 38(2):147–159, 1987.
  * [3] A. Bouchet. Representability of $\triangle$-Matroids. In Proceedings of Combinatorics, volume 52, pages 167–182. Colloquia Mathematica Societatis János Bolyai, 1988\.
  * [4] R. Brijder and H.J. Hoogeboom. Maximal Pivots on Graphs with an Application to Gene Assembly. Discrete Applied Mathematics, in press, 2010\.
  * [5] D.G. Corneil, M. Habib, J. Lanlignel, B.A. Reed and U. Rotics. Polynomial Time Recognition of Clique-Width $\leq$ 3 Graphs. In G.H. Gonnet, D. Panario and A. Viola editors, LATIN, volume 1776 of LNCS, pages 126–134. Springer, 2000.
  * [6] B. Courcelle, J. Engelfriet and G. Rozenberg. Handle-Rewriting Hypergraph Grammars. Journal of Computer and System Sciences 46(2):218–270, 1993.
  * [7] B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic: a Language Theoretic Approach. To be published by Cambridge University Press.
  * [8] B. Courcelle and M.M. Kanté. Graph Operations Characterising Rank-Width. Discrete Applied Mathematics 157(4):627–640, 2009.
  * [9] R. Diestel. Graph Theory. Springer-Verlag, $3^{rd}$ edition, 2005.
  * [10] J.F. Geelen. Matchings, Matroids and Unimodular Matrices. PhD, University of Waterloo. 1995.
  * [11] J.F. Geelen, A.M.H. Gerards and G. Whittle. Branch-Width and Well-Quasi-Ordering in Matroids and Graphs. Journal of Combinatorial Theory, Series B 84(2):270–290, 2002.
  * [12] J.F. Geelen, A.M.H. Gerards and G.P. Whittle. Towards a Matroid Minor Structure Theory. In G. Grimmett and C. McDiarmid editors, Combinatorics, Complexity, and Chance - A Tribute to Dominic Welsh, chapter 5.
  * [13] P. Hlin$\check{\textrm{e}}$ný and S. Oum.  Finding Branch-Decompositions and Rank-Decompositions. SIAM Journal on Computing 38(3):1012–1032, 2008.
  * [14] M.M. Kanté and M. Rao. $\mathbb{F}$-Rank-Width of (Edge-Colored) Graphs. In F. Winkler, editor, _International Conference on Algebraic Informatics (CAI)_ , volume 6742 of LNCS, pages 158-173. Springer, 2011.
  * [15] S. Lipschutz. Schaum’s Outline of Theory and Problems of Linear Algebra. Mc-Graw Hill, $2^{nd}$ edition, 1991\.
  * [16] R. Lidl and H. Niederreiter. Finite Fields. Encyclopedia of Mathematics and its Applications, $2^{nd}$ edition, 1997.
  * [17] S. Oum. Rank-Width and Vertex-Minors. Journal of Combinatorial Theory, Series B 95(1):79–100, 2005.
  * [18] S. Oum. Rank-Width and Well-Quasi-Ordering. SIAM Journal on Discrete Mathematics 22(2):666–682, 2008.
  * [19] S. Oum. Rank-Width and Well-Quasi-Ordering of Skew-Symmetric or Symmetric Matrices. arXiv:1007.3807v1. Submitted, 2010.
  * [20] S. Oum and P.D. Seymour. Approximating Clique-Width and Branch-Width. Journal of Combinatorial Theory, Series B 96(4):514–528, 2006.
  * [21] N. Robertson and P.D. Seymour. Graph Minors IV : Tree-width and Well-Quasi-Ordering. Journal of Combinatorial Theory, Series B 48(2):227–254, 1990.
  * [22] N. Robertson and P.D. Seymour. Graph Minors XX: Wagner’s Conjecture. Journal of Combinatorial Theory, Series B 92(2):325–357, 2004.
  * [23] N. Robertson and P.D. Seymour. Graph Minors I to XX.
  * [24] M.J. Tsatsomeros. Principal Pivot Transforms: Properties and Applications. Linear Algebra and its Applications 307(1-3):151–165, 2000.
  * [25] A.W. Tucker. A Combinatorial Equivalence of Matrices. In R. Bellman and M. Hall Jr editors, _Combinatorial Analysis_ , pages 129–140. AMS, Providence, 1960.
  * [26] W.T. Tutte. Introduction to the Theory of Matroids. American Elsevier, 1971.