distinct elements of $C$, and therefore satisfy

$d\left(q_{i},q_{j}\right)=\beta$ (39)

(by (37), applied to $a=q_{i}$ and $b=q_{j}$).

Recall that $p_{1},p_{2},\ldots,p_{m}$ are all the $m$ elements of $P$ (listed
without repetition). Hence, the definition of perimeter yields

$\displaystyle\operatorname*{PER}\left(P\right)$
$\displaystyle=\sum\limits_{i=1}^{m}\underbrace{w\left(p_{i}\right)}_{\begin{subarray}{c}=w\left(c\right)\\\
\text{(by (\ref{pf.cor.clique-and-
clball2.wp=wc}))}\end{subarray}}+\sum\limits_{1\leqslant i<j\leqslant
m}\underbrace{d\left(p_{i},p_{j}\right)}_{\begin{subarray}{c}\leqslant\beta\\\
\text{(by (\ref{pf.cor.clique-and-
clball2.dp}))}\end{subarray}}\leqslant\sum\limits_{i=1}^{m}\underbrace{w\left(c\right)}_{\begin{subarray}{c}=w\left(q_{i}\right)\\\
\text{(by (\ref{pf.cor.clique-and-
clball2.wq=wc}))}\end{subarray}}+\sum\limits_{1\leqslant i<j\leqslant
m}\underbrace{\beta}_{\begin{subarray}{c}=d\left(q_{i},q_{j}\right)\\\
\text{(by (\ref{pf.cor.clique-and-clball2.dq}))}\end{subarray}}$
$\displaystyle=\sum\limits_{i=1}^{m}w\left(q_{i}\right)+\sum\limits_{1\leqslant
i<j\leqslant m}d\left(q_{i},q_{j}\right)=\operatorname*{PER}\left(Q\right)$

(by the definition of $Q$, since $q_{1},q_{2},\ldots,q_{m}$ are all the $m$
elements of $Q$ (listed without repetition)).

But Corollary 11.8 (a) yields

$\operatorname*{PER}\left(N\cup Q\right)-\operatorname*{PER}\left(N\cup
P\right)=\operatorname*{PER}\left(Q\right)-\operatorname*{PER}\left(P\right)\geqslant
0$

(since
$\operatorname*{PER}\left(P\right)\leqslant\operatorname*{PER}\left(Q\right)$).
In other words, $\operatorname*{PER}\left(N\cup
Q\right)\geqslant\operatorname*{PER}\left(N\cup P\right)$. This proves
Corollary 11.8 (b).

######  Corollary 11.10.

Let $\mathcal{F}$ be the Bhargava greedoid of $\left(E,w,d\right)$. Assume
that the map $w:E\rightarrow\mathbb{V}$ is constant.

Let $\beta\in\mathbb{V}$. Let $C$ be a $\beta$-clique. Let
$B=B_{\beta}\left(c\right)$ for some $c\in C$.

Let $N$ be a subset of $E\setminus B$.

Let $P$ and $Q$ be two subsets of $B$ such that
$\left|P\right|=\left|Q\right|$ and $Q\subseteq C$ and $N\cup
P\in\mathcal{F}$. Then, $N\cup Q\in\mathcal{F}$.

######  Proof 11.11 (Proof of Corollary 11.10.).

Corollary 11.8 (b) yields $\operatorname*{PER}\left(N\cup
Q\right)\geqslant\operatorname*{PER}\left(N\cup P\right)$.

Also, the set $N$ is disjoint from $B$ (since $N\subseteq E\setminus B$), and
thus is disjoint from $P$ as well (since $P$ is a subset of $B$). Hence,
$\left|N\cup P\right|=\left|N\right|+\left|P\right|$. The same argument
(applied to $Q$ instead of $P$) shows that $\left|N\cup
Q\right|=\left|N\right|+\left|Q\right|$. Hence, $\left|N\cup
P\right|=\left|N\right|+\underbrace{\left|P\right|}_{=\left|Q\right|}=\left|N\right|+\left|Q\right|=\left|N\cup
Q\right|$.

We know that $\mathcal{F}$ is the Bhargava greedoid of $\left(E,w,d\right)$.
In other words,

$\mathcal{F}=\left\\{A\subseteq E\ \mid\ A\text{ has maximum perimeter among
all }\left|A\right|\text{-subsets of }E\right\\}$ (40)

(by Definition 2.6). Hence, from $N\cup P\in\mathcal{F}$, we conclude that the
set $N\cup P$ has maximum perimeter among all $\left|N\cup P\right|$-subsets
of $E$. In other words, the set $N\cup P$ has maximum perimeter among all
$\left|N\cup Q\right|$-subsets of $E$ (since $\left|N\cup P\right|=\left|N\cup
Q\right|$). Since $N\cup Q$ is a further $\left|N\cup Q\right|$-subset of $E$,
we thus conclude that $\operatorname*{PER}\left(N\cup
P\right)\geqslant\operatorname*{PER}\left(N\cup Q\right)$. Combining this with
$\operatorname*{PER}\left(N\cup
Q\right)\geqslant\operatorname*{PER}\left(N\cup P\right)$, we obtain
$\operatorname*{PER}\left(N\cup Q\right)=\operatorname*{PER}\left(N\cup
P\right)$. In other words, the subsets $N\cup Q$ and $N\cup P$ of $E$ have the
same perimeter. Therefore, the set $N\cup Q$ has maximum perimeter among all
$\left|N\cup Q\right|$-subsets of $E$ (because the set $N\cup P$ has maximum
perimeter among all $\left|N\cup Q\right|$-subsets of $E$). In view of (40),
this entails that $N\cup Q\in\mathcal{F}$. This proves Corollary 11.10.

###  11.3 Gaussian elimination greedoids in terms of determinants

Next, we introduce some notations for matrices.

######  Definition 11.12.

Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Let
$A=\left(a_{i,j}\right)_{1\leqslant i\leqslant n,\ 1\leqslant j\leqslant m}$
be an $n\times m$-matrix. Let $i_{1},i_{2},\ldots,i_{u}$ be some elements of
$\left\\{1,2,\ldots,n\right\\}$; let $j_{1},j_{2},\ldots,j_{v}$ be some
elements of $\left\\{1,2,\ldots,m\right\\}$. Then, we define
$\operatorname*{sub}\nolimits_{i_{1},i_{2},\ldots,i_{u}}^{j_{1},j_{2},\ldots,j_{v}}A$
to be the $u\times v$-matrix $\left(a_{i_{x},j_{y}}\right)_{1\leqslant
x\leqslant u,\ 1\leqslant y\leqslant v}$.

When $i_{1}<i_{2}<\cdots<i_{u}$ and $j_{1}<j_{2}<\cdots<j_{v}$, the matrix
$\operatorname*{sub}\nolimits_{i_{1},i_{2},\ldots,i_{u}}^{j_{1},j_{2},\ldots,j_{v}}A$
can be obtained from $A$ by crossing out all rows other than the $i_{1}$-th,
the $i_{2}$-th, etc., the $i_{u}$-th row and crossing out all columns other
than the $j_{1}$-th, the $j_{2}$-th, etc., the $j_{v}$-th column. Thus, in
this case,
$\operatorname*{sub}\nolimits_{i_{1},i_{2},\ldots,i_{u}}^{j_{1},j_{2},\ldots,j_{v}}A$
is called a submatrix of $A$.

######  Example 11.13.

If $n=3$ and $m=4$ and $A=\left(\begin{array}[c]{cccc}a&b&c&d\\\ e&f&g&h\\\
i&j&k&\ell\end{array}\right)$, then
$\operatorname*{sub}\nolimits_{1,3}^{1,3,4}A=\left(\begin{array}[c]{ccc}a&c&d\\\
i&k&\ell\end{array}\right)$ (this is a submatrix of $A$) and
$\operatorname*{sub}\nolimits_{2,3}^{3,2,1}A=\left(\begin{array}[c]{ccc}g&f&e\\\
k&j&i\end{array}\right)$ (this is not, in general, a submatrix of $A$).

We can now describe Gaussian elimination greedoids in terms of determinants:

######  Lemma 11.14.

Let $n\in\mathbb{N}$. Let $E$ be the set $\left\\{1,2,\ldots,n\right\\}$.

Let $m\in\mathbb{N}$ be such that $m\geqslant\left|E\right|$. Let $\mathbb{K}$
be a field. For each $e\in E$, let $v_{e}\in\mathbb{K}^{m}$ be a column
vector. Let $A$ be the $m\times n$-matrix whose columns (from left to right)
are $v_{1},v_{2},\ldots,v_{n}$.

Let $\mathcal{G}$ be the Gaussian elimination greedoid of the vector family
$\left(v_{e}\right)_{e\in E}$.

Let $p\in\mathbb{N}$. Let $i_{1},i_{2},\ldots,i_{p}\in E$ be $p$ distinct
numbers. Let $I=\left\\{i_{1},i_{2},\ldots,i_{p}\right\\}$. Then,

$I\in\mathcal{G}\text{ holds if and only if
}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\right)\neq
0.$

######  Proof 11.15 (Proof of Lemma 11.14.).

We have $I=\left\\{i_{1},i_{2},\ldots,i_{p}\right\\}$. Thus,
$\left|I\right|=p$ (since $i_{1},i_{2},\ldots,i_{p}$ are distinct) and
$I\subseteq E$ (since $i_{1},i_{2},\ldots,i_{p}\in E$).

Define the maps $\pi_{k}$ for all $k\in\left\\{0,1,\ldots,m\right\\}$ as in
Definition 1.1. Since $I\subseteq E$, we have
$\left|I\right|\leqslant\left|E\right|$. Hence,
$p=\left|I\right|\leqslant\left|E\right|\leqslant m$ (since
$m\geqslant\left|E\right|$), so that $p\in\left\\{0,1,\ldots,m\right\\}$.
Thus, the map $\pi_{p}:\mathbb{K}^{m}\rightarrow\mathbb{K}^{p}$ is well-
defined.

Write the $m\times n$-matrix $A$ in the form
$A=\left(a_{i,j}\right)_{1\leqslant i\leqslant m,\ 1\leqslant j\leqslant n}$.
Then, the definition of
$\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A$
yields

$\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A=\left(a_{x,i_{y}}\right)_{1\leqslant
x\leqslant p,\ 1\leqslant y\leqslant p}.$

Thus, for each $k\in\left\\{1,2,\ldots,p\right\\}$, we have

$\left(\text{the }k\text{-th column of
}\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\right)=\left(\begin{array}[c]{c}a_{1,i_{k}}\\\
a_{2,i_{k}}\\\ \vdots\\\ a_{p,i_{k}}\end{array}\right).$ (41)

The columns of the matrix $A$ (from left to right) are
$v_{1},v_{2},\ldots,v_{n}$. In other words, the $\ell$-th column of $A$ is
$v_{\ell}$ for each $\ell\in\left\\{1,2,\ldots,n\right\\}$. In other words,
for each $\ell\in\left\\{1,2,\ldots,n\right\\}$, we have $\left(\text{the
}\ell\text{-th column of }A\right)=v_{\ell}$. Thus, for each
$\ell\in\left\\{1,2,\ldots,n\right\\}$, we have

$v_{\ell}=\left(\text{the }\ell\text{-th column of
}A\right)=\left(\begin{array}[c]{c}a_{1,\ell}\\\ a_{2,\ell}\\\ \vdots\\\
a_{m,\ell}\end{array}\right)$

(since $A=\left(a_{i,j}\right)_{1\leqslant i\leqslant m,\ 1\leqslant
j\leqslant n}$) and therefore

$\pi_{p}\left(v_{\ell}\right)=\pi_{p}\left(\left(\begin{array}[c]{c}a_{1,\ell}\\\
a_{2,\ell}\\\ \vdots\\\
a_{m,\ell}\end{array}\right)\right)=\left(\begin{array}[c]{c}a_{1,\ell}\\\
a_{2,\ell}\\\ \vdots\\\ a_{p,\ell}\end{array}\right)$ (42)

(by the definition of $\pi_{p}$). Hence, for each
$k\in\left\\{1,2,\ldots,p\right\\}$, we have

$\displaystyle\pi_{p}\left(v_{i_{k}}\right)$
$\displaystyle=\left(\begin{array}[c]{c}a_{1,i_{k}}\\\ a_{2,i_{k}}\\\
\vdots\\\ a_{p,i_{k}}\end{array}\right)\ \ \ \ \ \ \ \ \ \ \left(\text{by
(\ref{pf.lem.geg.through-det.col3}), applied to }\ell=i_{k}\right)$
$\displaystyle=\left(\text{the }k\text{-th column of
}\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\right)\
\ \ \ \ \ \ \ \ \ \left(\text{by (\ref{pf.lem.geg.through-det.col1})}\right).$

In other words, the vectors
$\pi_{p}\left(v_{i_{1}}\right),\pi_{p}\left(v_{i_{2}}\right),\ldots,\pi_{p}\left(v_{i_{p}}\right)$
are the columns of the matrix
$\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A$.

We know that $\mathcal{G}$ is the Gaussian elimination greedoid of the vector
family $\left(v_{e}\right)_{e\in E}$. Thus, Definition 1.1 shows that

$\mathcal{G}=\left\\{F\subseteq E\ \mid\ \text{the family
}\left(\pi_{\left|F\right|}\left(v_{e}\right)\right)_{e\in
F}\in\left(\mathbb{K}^{\left|F\right|}\right)^{F}\text{ is linearly
independent}\right\\}.$

Hence, we have the following chain of logical equivalences:

$\displaystyle\ \left(I\in\mathcal{G}\right)$
$\displaystyle\Longleftrightarrow\ \left(\text{the family
}\left(\pi_{\left|I\right|}\left(v_{e}\right)\right)_{e\in
I}\in\left(\mathbb{K}^{\left|I\right|}\right)^{I}\text{ is linearly
independent}\right)$ $\displaystyle\Longleftrightarrow\ \left(\text{the family
}\left(\pi_{p}\left(v_{e}\right)\right)_{e\in
I}\in\left(\mathbb{K}^{p}\right)^{I}\text{ is linearly independent}\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(\text{since
}\left|I\right|=p\right)$ $\displaystyle\Longleftrightarrow\ \left(\text{the
vectors }\pi_{p}\left(v_{e}\right)\text{ for }e\in I\text{ are linearly
independent}\right)$ $\displaystyle\Longleftrightarrow\ \left(\text{the
vectors
}\pi_{p}\left(v_{i_{1}}\right),\pi_{p}\left(v_{i_{2}}\right),\ldots,\pi_{p}\left(v_{i_{p}}\right)\text{
are linearly independent}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \left(\begin{array}[c]{c}\text{since the vectors
}\pi_{p}\left(v_{e}\right)\text{ for }e\in I\text{ are precisely}\\\ \text{the
vectors
}\pi_{p}\left(v_{i_{1}}\right),\pi_{p}\left(v_{i_{2}}\right),\ldots,\pi_{p}\left(v_{i_{p}}\right)\end{array}\right)$
$\displaystyle\Longleftrightarrow\ \left(\text{the columns of the matrix
}\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\text{
are linearly independent}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \left(\begin{array}[c]{c}\text{since the vectors
}\pi_{p}\left(v_{i_{1}}\right),\pi_{p}\left(v_{i_{2}}\right),\ldots,\pi_{p}\left(v_{i_{p}}\right)\text{
are}\\\ \text{the columns of the matrix
}\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\end{array}\right)$
$\displaystyle\Longleftrightarrow\ \left(\text{the matrix
}\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\text{
is invertible}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\left(\begin{array}[c]{c}\text{since
}\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\text{
is a square matrix, and thus is invertible}\\\ \text{if and only if its
columns are linearly independent}\end{array}\right)$
$\displaystyle\Longleftrightarrow\
\left(\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,p}^{i_{1},i_{2},\ldots,i_{p}}A\right)\neq
0\right).$

This proves Lemma 11.14.

We can leverage Lemma 11.14 to obtain a criterion that, roughly speaking, says
that if a Gaussian elimination greedoid over a field $\mathbb{K}$ contains a
certain “constellation” (in an appropriate sense), then
$\left|\mathbb{K}\right|$ must be $\geqslant$ to a certain value. Namely:

######  Lemma 11.16.

Let $\mathbb{K}$ be a field. Let $E$ be a finite set. Let $\mathcal{F}$ be the
Gaussian elimination greedoid of a vector family $\left(v_{e}\right)_{e\in E}$
over $\mathbb{K}$. Let $N$ and $C$ be two disjoint subsets of $E$. Assume that
the following three conditions hold:

  1. (i)

For any $i\in C$, we have $N\cup\left\\{i\right\\}\in\mathcal{F}$.

  2. (ii)

For any distinct $i,j\in C$, we have
$N\cup\left\\{i,j\right\\}\in\mathcal{F}$.

  3. (iii)

For any $p\in N$ and any distinct $i,j\in C$, we have
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\notin\mathcal{F}$.

Then, $\left|\mathbb{K}\right|\geqslant\left|C\right|$.

######  Proof 11.17 (Proof of Lemma 11.16.).

Let $m\in\mathbb{N}$ be such that the vectors $v_{e}$ belong to
$\mathbb{K}^{m}$. Then, $m\geqslant\left|E\right|$ (since otherwise, the
Gaussian elimination greedoid of the vector family $\left(v_{e}\right)_{e\in
E}$ would not be well-defined).

Let $n=\left|E\right|$ and $r=\left|N\right|$. Hence, $N$ is an $r$-element
subset of the $n$-element set $E$. Thus, the set $E$ consists of the $r$
elements of $N$ and of the $n-r$ remaining elements of $E$.

Clearly, the claim we are proving will not change if we rename the elements of
$E$. Thus, we can rename the elements of $E$ arbitrarily. In particular, we
can rename them in such a way that the $r$ elements of the subset $N$ will
become $1,2,\ldots,r$ whereas all remaining $n-r$ elements of $E$ will become
$r+1,r+2,\ldots,n$. Thus, we can WLOG assume that the $r$ elements of $N$ are
$1,2,\ldots,r$ and the remaining $n-r$ elements of $E$ are $r+1,r+2,\ldots,n$.
Assume this. Hence, $N=\left\\{1,2,\ldots,r\right\\}$ and $E\setminus
N=\left\\{r+1,r+2,\ldots,n\right\\}$ and therefore
$E=\left\\{1,2,\ldots,n\right\\}$.

Since the subsets $N$ and $C$ of $E$ are disjoint, we have $C\subseteq
E\setminus N=\left\\{r+1,r+2,\ldots,n\right\\}$.

Let $A$ be the $m\times n$-matrix whose columns (from left to right) are
$v_{1},v_{2},\ldots,v_{n}$. Write this matrix $A$ in the form
$A=\left(a_{i,j}\right)_{1\leqslant i\leqslant m,\ 1\leqslant j\leqslant n}$.

We now make a few observations:

> Claim 1: We have
> $\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\neq
> 0$ for each $i\in C$.

[Proof of Claim 1: Let $i\in C$. Then, $i\in
C\subseteq\left\\{r+1,r+2,\ldots,n\right\\}$. Thus, the $r+1$ numbers
$1,2,\ldots,r,i$ are distinct. Also, $N\cup\left\\{i\right\\}\in\mathcal{F}$
(by condition (i) in Lemma 11.16). But
$N\cup\left\\{i\right\\}=\left\\{1,2,\ldots,r,i\right\\}$ (since
$N=\left\\{1,2,\ldots,r\right\\}$). Thus, Lemma 11.14 (applied to
$\mathcal{F}$, $N\cup\left\\{i\right\\}$, $r+1$ and
$\left(1,2,\ldots,r,i\right)$ instead of $\mathcal{G}$, $I$, $p$ and
$\left(i_{1},i_{2},\ldots,i_{p}\right)$) yields that
$N\cup\left\\{i\right\\}\in\mathcal{F}$ holds if and only if
$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\neq
0.$ Thus, we have
$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\neq
0$ (since $N\cup\left\\{i\right\\}\in\mathcal{F}$). This proves Claim 1.]

Now, for each $i\in C$, we define a scalar $r_{i}\in\mathbb{K}$ by

$r_{i}=\dfrac{a_{r+2,i}}{\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)}.$
(43)

This is well-defined, since Claim 1 yields
$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\neq
0$.

> Claim 2: The scalars $r_{i}$ for all $i\in C$ are distinct.

[Proof of Claim 2: We need to prove that $r_{i}\neq r_{j}$ for any two
distinct $i,j\in C$. So let us fix two distinct $i,j\in C$. We must prove that
$r_{i}\neq r_{j}$.

We have $i,j\in C\subseteq\left\\{r+1,r+2,\ldots,n\right\\}$. Thus, the $r+2$
numbers $1,2,\ldots,r,i,j$ are distinct (since $i$ and $j$ are distinct).
Also, $N\cup\left\\{i,j\right\\}\in\mathcal{F}$ (by condition (ii) in Lemma
11.16). But $N\cup\left\\{i,j\right\\}=\left\\{1,2,\ldots,r,i,j\right\\}$
(since $N=\left\\{1,2,\ldots,r\right\\}$). Thus, Lemma 11.14 (applied to
$\mathcal{F}$, $N\cup\left\\{i,j\right\\}$, $r+2$ and
$\left(1,2,\ldots,r,i,j\right)$ instead of $\mathcal{G}$, $I$, $p$ and
$\left(i_{1},i_{2},\ldots,i_{p}\right)$) yields that
$N\cup\left\\{i,j\right\\}\in\mathcal{F}$ holds if and only if
$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+2}^{1,2,\ldots,r,i,j}A\right)\neq
0.$ Thus, we have

$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+2}^{1,2,\ldots,r,i,j}A\right)\neq
0$ (44)

(since $N\cup\left\\{i,j\right\\}\in\mathcal{F}$).

Let us agree to use the following notation: If
$p\in\left\\{1,2,\ldots,r\right\\}$ is arbitrary, then
“$1,2,\ldots,\widehat{p},\ldots,r,i,j$” will denote the list
$1,2,\ldots,r,i,j$ with the entry $p$ omitted (i.e., the list
$1,2,\ldots,p-1,p+1,p+2,\ldots,r,i,j$).

Now, let us use Laplace expansion to expand the determinant of the
$\left(r+2\right)\times\left(r+2\right)$-matrix
$\operatorname*{sub}\nolimits_{1,2,\ldots,r+2}^{1,2,\ldots,r,i,j}A$ along its
last row. We thus obtain

$\displaystyle\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+2}^{1,2,\ldots,r,i,j}A\right)$
$\displaystyle=\sum\limits_{p=1}^{r}\left(-1\right)^{\left(r+2\right)+p}a_{r+2,p}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,\widehat{p},\ldots,r,i,j}A\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+\left(-1\right)^{\left(r+2\right)+\left(r+1\right)}a_{r+2,i}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+\left(-1\right)^{\left(r+2\right)+\left(r+2\right)}a_{r+2,j}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right).$
(45)

(Indeed, the entries of the last row of
$\operatorname*{sub}\nolimits_{1,2,\ldots,r+2}^{1,2,\ldots,r,i,j}A$ are

$\underbrace{a_{r+2,1},a_{r+2,2},\ldots,a_{r+2,r}}_{\text{these are the
}a_{r+2,p}\text{ for all
}p\in\left\\{1,2,\ldots,r\right\\}},a_{r+2,i},a_{r+2,j},$

and the cofactors corresponding to the first $r$ of these entries are

$\left(-1\right)^{\left(r+2\right)+p}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,\widehat{p},\ldots,r,i,j}A\right)\
\ \ \ \ \ \ \ \ \ \text{for all }p\in\left\\{1,2,\ldots,r\right\\},$

whereas the cofactors corresponding to the last two entries are

$\left(-1\right)^{\left(r+2\right)+\left(r+1\right)}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)\
\ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \
\left(-1\right)^{\left(r+2\right)+\left(r+2\right)}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right).$

)

Now, let us simplify the entries in the $\sum\limits_{p=1}^{r}$ sum on the
right hand side of (43).

Let $p\in\left\\{1,2,\ldots,r\right\\}$. Then,
$p\in\left\\{1,2,\ldots,r\right\\}=N$. Hence,
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\notin\mathcal{F}$
(by condition (iii) in Lemma 11.16). In other words, we don’t have
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\in\mathcal{F}$.
But from $N\cup\left\\{i,j\right\\}=\left\\{1,2,\ldots,r,i,j\right\\}$, we
obtain
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}=\left\\{1,2,\ldots,r,i,j\right\\}\setminus\left\\{p\right\\}=\left\\{1,2,\ldots,\widehat{p},\ldots,r,i,j\right\\}$
(since the $r+2$ numbers $1,2,\ldots,r,i,j$ are distinct). Of course, the
$r+1$ numbers $1,2,\ldots,\widehat{p},\ldots,r,i,j$ are distinct (since the
$r+2$ numbers $1,2,\ldots,r,i,j$ are distinct). Thus, Lemma 11.14 (applied to
$\mathcal{F}$,
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}$, $r+1$ and
$\left(1,2,\ldots,\widehat{p},\ldots,r,i,j\right)$ instead of $\mathcal{G}$,
$I$, $p$ and $\left(i_{1},i_{2},\ldots,i_{p}\right)$) yields that
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\in\mathcal{F}$
holds if and only if
$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,\widehat{p},\ldots,r,i,j}A\right)\neq
0.$ Thus, we don’t have
$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,\widehat{p},\ldots,r,i,j}A\right)\neq
0$ (since we don’t have
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\in\mathcal{F}$).
In other words, we have

$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,\widehat{p},\ldots,r,i,j}A\right)=0.$
(46)

Forget that we fixed $p$. We thus have proved (46) for each
$p\in\left\\{1,2,\ldots,r\right\\}$. Now, (45) becomes

$\displaystyle\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+2}^{1,2,\ldots,r,i,j}A\right)$
$\displaystyle=\sum\limits_{p=1}^{r}\left(-1\right)^{\left(r+2\right)+p}a_{r+2,p}\underbrace{\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,\widehat{p},\ldots,r,i,j}A\right)}_{\begin{subarray}{c}=0\\\
\text{(by (\ref{pf.lem.geg.K-bound.c2.pf.2}))}\end{subarray}}$ $\displaystyle\
\ \ \ \ \ \ \ \ \
+\underbrace{\left(-1\right)^{\left(r+2\right)+\left(r+1\right)}}_{=-1}a_{r+2,i}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+\underbrace{\left(-1\right)^{\left(r+2\right)+\left(r+2\right)}}_{=1}a_{r+2,j}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)$
$\displaystyle=\underbrace{\sum\limits_{p=1}^{r}\left(-1\right)^{\left(r+2\right)+p}a_{r+2,p}0}_{=0}-a_{r+2,i}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)+a_{r+2,j}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)$
$\displaystyle=-\underbrace{a_{r+2,i}}_{\begin{subarray}{c}=\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\cdot
r_{i}\\\ \text{(by
(\ref{pf.lem.geg.K-bound.1}))}\end{subarray}}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+\underbrace{a_{r+2,j}}_{\begin{subarray}{c}=\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)\cdot
r_{j}\\\ \text{(since (\ref{pf.lem.geg.K-bound.1})}\\\ \text{(applied to
}j\text{ instead of }i\text{)}\\\ \text{yields
}r_{j}=\dfrac{a_{r+2,j}}{\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)}\text{)}\end{subarray}}\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)$
$\displaystyle=-\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\cdot
r_{i}\cdot\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)\cdot
r_{j}\cdot\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)$
$\displaystyle=\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)\cdot\left(r_{j}-r_{i}\right).$

Hence,

$\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,i}A\right)\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+1}^{1,2,\ldots,r,j}A\right)\cdot\left(r_{j}-r_{i}\right)=\det\left(\operatorname*{sub}\nolimits_{1,2,\ldots,r+2}^{1,2,\ldots,r,i,j}A\right)\neq
0$

(by (44)). Thus, $r_{j}-r_{i}\neq 0$, so that $r_{i}\neq r_{j}$. This proves
Claim 2.]

Claim 2 shows that the scalars $r_{i}$ for all $i\in C$ are distinct. Thus, we
have found $\left|C\right|$ distinct elements of $\mathbb{K}$ (namely, these
scalars $r_{i}$ for all $i\in C$). Therefore, $\mathbb{K}$ must have at least
$\left|C\right|$ elements. In other words,
$\left|\mathbb{K}\right|\geqslant\left|C\right|$. Thus, Lemma 11.16 is proved.

###  11.4 Proving the theorem

We shall need one more lemma about Gaussian elimination greedoids:

######  Lemma 11.18.

Let $\mathbb{K}$ be a field. Let $\mathcal{F}$ be the Gaussian elimination
greedoid of a vector family over $\mathbb{K}$. If $B\in\mathcal{F}$ satisfies
$\left|B\right|>0$, then there exists $b\in B$ such that
$B\setminus\left\\{b\right\\}\in\mathcal{F}$.

######  Proof 11.19 (Proof of Lemma 11.18.).

We shall use the notion of a “strong greedoid”, as defined in Definition 12.1.

Theorem 1.3 shows that every Gaussian elimination greedoid is a strong
greedoid. Hence, $\mathcal{F}$ is a strong greedoid. In other words,
$\mathcal{F}$ is a set system that satisfies the four axioms (i), (ii), (iii)
and (iv) of Definition 12.1. Thus, in particular, $\mathcal{F}$ satisfies
axiom (ii). But this axiom says precisely that if $B\in\mathcal{F}$ satisfies
$\left|B\right|>0$, then there exists $b\in B$ such that
$B\setminus\left\\{b\right\\}\in\mathcal{F}$. Thus, Lemma 11.18 is proved.

We can now prove Theorem 5.1:

######  Proof 11.20 (Proof of Theorem 5.1.).

The definition of $\operatorname*{mcs}\left(E,w,d\right)$ shows that
$\operatorname*{mcs}\left(E,w,d\right)$ is the maximum size of a clique of
$\left(E,w,d\right)$. Thus, there exists a clique $C$ of size
$\operatorname*{mcs}\left(E,w,d\right)$. Consider this $C$. Thus,
$\operatorname*{mcs}\left(E,w,d\right)=\left|C\right|$ (since $C$ has size
$\operatorname*{mcs}\left(E,w,d\right)$).

We must prove that
$\left|\mathbb{K}\right|\geqslant\operatorname*{mcs}\left(E,w,d\right)$. In
other words, we must prove that
$\left|\mathbb{K}\right|\geqslant\left|C\right|$ (since
$\operatorname*{mcs}\left(E,w,d\right)=\left|C\right|$). If
$\left|C\right|\leqslant 1$, then this is obvious (since
$\left|\mathbb{K}\right|\geqslant 1$). Thus, we WLOG assume that
$\left|C\right|>1$. Hence, $\left|C\right|\geqslant 2$.

The set $C$ is a clique. In other words, there exists a $\beta\in\mathbb{V}$
such that $C$ is a $\beta$-clique. Consider this $\beta$.

Choose some $c\in C$. (We can do this, since $\left|C\right|\geqslant 2>0$.)
Set $B=B_{\beta}\left(c\right)$. Lemma 11.6 (b) yields $C\subseteq B$, so that
$B\supseteq C$.

A secant set shall mean a subset $S$ of $E$ satisfying $S\in\mathcal{F}$ and
$\left|S\cap B\right|\geqslant 2$.

The set $E$ itself satisfies $E\in\mathcal{F}$ (by Remark 2.9) and
$\left|E\cap B\right|\geqslant 2$ 222222Proof. Since $B$ is a subset of $E$,
we have $E\cap B=B\supseteq C$. Thus, $\left|E\cap
B\right|\geqslant\left|C\right|\geqslant 2$.. In other words, $E$ is a secant
set. Hence, there exists at least one secant set. Thus, there exists a secant
set of smallest size (since there are only finitely many secant sets).
Consider such a secant set, and call it $S$.

Thus, $S$ is a secant set of smallest size. Hence, $S$ is a secant set; in
other words, $S$ is a subset of $E$ satisfying $S\in\mathcal{F}$ and
$\left|S\cap B\right|\geqslant 2$. Since $S\cap B$ is a subset of $S$, we have
$\left|S\cap B\right|\leqslant\left|S\right|$, so that
$\left|S\right|\geqslant\left|S\cap B\right|\geqslant 2>0$. Thus, Lemma 11.18
(applied to $B=S$) yields that there exists $b\in S$ such that
$S\setminus\left\\{b\right\\}\in\mathcal{F}$. Consider this $b$.

We now shall show several claims:

> Claim 1: We have $\left|\left(S\cap
> B\right)\setminus\left\\{b\right\\}\right|<2$.

[Proof of Claim 1: The set $S\setminus\left\\{b\right\\}$ has smaller size
than $S$ (since $b\in S$), and thus cannot be a secant set (since $S$ is a
secant set of smallest size). In other words, $S\setminus\left\\{b\right\\}$
cannot be a subset of $E$ satisfying
$S\setminus\left\\{b\right\\}\in\mathcal{F}$ and
$\left|\left(S\setminus\left\\{b\right\\}\right)\cap B\right|\geqslant 2$ (by
the definition of “secant set”). Hence, we cannot have
$\left|\left(S\setminus\left\\{b\right\\}\right)\cap B\right|\geqslant 2$
(because $S\setminus\left\\{b\right\\}$ is a subset of $E$ satisfying
$S\setminus\left\\{b\right\\}\in\mathcal{F}$). In other words, we have
$\left|\left(S\setminus\left\\{b\right\\}\right)\cap B\right|<2$.

But it is known from basic set theory that $\left(X\cap Y\right)\setminus
Z=\left(X\setminus Z\right)\cap Y$ for any three sets $X$, $Y$ and $Z$.
Applying this to $X=S$, $Y=B$ and $Z=\left\\{b\right\\}$, we obtain
$\left(S\cap
B\right)\setminus\left\\{b\right\\}=\left(S\setminus\left\\{b\right\\}\right)\cap
B$. Hence, $\left|\left(S\cap
B\right)\setminus\left\\{b\right\\}\right|=\left|\left(S\setminus\left\\{b\right\\}\right)\cap
B\right|<2$. This proves Claim 1.]

> Claim 2: We have $b\in S\cap B$.

[Proof of Claim 2: Claim 1 yields $\left|\left(S\cap
B\right)\setminus\left\\{b\right\\}\right|<2\leqslant\left|S\cap B\right|$
(since $\left|S\cap B\right|\geqslant 2$). Hence, $\left|\left(S\cap
B\right)\setminus\left\\{b\right\\}\right|\neq\left|S\cap B\right|$, so that
$\left(S\cap B\right)\setminus\left\\{b\right\\}\neq S\cap B$. Therefore,
$b\in S\cap B$. This proves Claim 2.]

> Claim 3: We have $\left|S\cap B\right|=2$.

[Proof of Claim 3: Claim 1 says that $\left|\left(S\cap
B\right)\setminus\left\\{b\right\\}\right|<2$. But Claim 2 yields $b\in S\cap
B$. Thus, $\left|\left(S\cap
B\right)\setminus\left\\{b\right\\}\right|=\left|S\cap B\right|-1$. Hence,
$\left|S\cap B\right|=\underbrace{\left|\left(S\cap
B\right)\setminus\left\\{b\right\\}\right|}_{<2}+1<2+1=3$. In other words,
$\left|S\cap B\right|\leqslant 2$ (since $\left|S\cap B\right|$ is an
integer). Combining this with $\left|S\cap B\right|\geqslant 2$, we find
$\left|S\cap B\right|=2$. This proves Claim 3.]

Claim 3 shows that the set $S\cap B$ has exactly two elements. One of these
two elements is $b$ (since Claim 2 says that $b\in S\cap B$); let $a$ be the
other element. Thus, $a\neq b$ and $S\cap B=\left\\{a,b\right\\}$. Hence,
$\left\\{a,b\right\\}=S\cap B\subseteq B$. Also,
$\left|\left\\{a,b\right\\}\right|=2$ (since $a\neq b$).

Let $N=S\setminus B$. Then, it is easy to see that
$S=N\cup\left\\{a,b\right\\}$ 232323Proof. Any two sets $X$ and $Y$ satisfy
$X=\left(X\setminus Y\right)\cup\left(X\cap Y\right)$. Applying this to $X=S$
and $Y=B$, we obtain $S=\underbrace{\left(S\setminus
B\right)}_{=N}\cup\underbrace{\left(S\cap
B\right)}_{=\left\\{a,b\right\\}}=N\cup\left\\{a,b\right\\}$. and
$N\cap\left\\{a,b\right\\}=\varnothing$ 242424Proof. We have
$\left\\{a,b\right\\}\subseteq B$. Hence, $\underbrace{N}_{=S\setminus
B}\cap\underbrace{\left\\{a,b\right\\}}_{\subseteq B}\subseteq\left(S\setminus
B\right)\cap B=\varnothing$, so that $N\cap\left\\{a,b\right\\}=\varnothing$..
From $S=N\cup\left\\{a,b\right\\}$, we obtain

$\displaystyle\left|S\right|$
$\displaystyle=\left|N\cup\left\\{a,b\right\\}\right|=\left|N\right|+\underbrace{\left|\left\\{a,b\right\\}\right|}_{=2}\
\ \ \ \ \ \ \ \ \ \left(\text{since
}N\cap\left\\{a,b\right\\}=\varnothing\right)$
$\displaystyle=\left|N\right|+2.$ (47)

Moreover,

$N=\underbrace{S}_{\subseteq E}\setminus B\subseteq
E\setminus\underbrace{B}_{\supseteq C}\subseteq E\setminus C.$

Hence, the two subsets $N$ and $C$ of $E$ are disjoint.

Now, we have the following:

> Claim 4: Let $i\in C$. Then, $N\cap\left\\{i\right\\}=\varnothing$ and
> $N\cup\left\\{i\right\\}\in\mathcal{F}$.

[Proof of Claim 4: If we had $i\in N$, then we would have $i\notin B$ (since
$i\in N=S\setminus B$), which would contradict $i\in C\subseteq B$. Hence, we
cannot have $i\in N$. Thus, $N\cap\left\\{i\right\\}=\varnothing$. It remains
to prove that $N\cup\left\\{i\right\\}\in\mathcal{F}$.

If we had $b\in N$, then we would have $b\notin B$ (since $b\in N=S\setminus
B$), which would contradict $b\in\left\\{a,b\right\\}\subseteq B$. Hence, we
cannot have $b\in N$. Thus, $b\notin N$, so that
$N\setminus\left\\{b\right\\}=N$.

We have $S=N\cup\left\\{a,b\right\\}$, thus

$S\setminus\left\\{b\right\\}=\left(N\cup\left\\{a,b\right\\}\right)\setminus\left\\{b\right\\}=\underbrace{\left(N\setminus\left\\{b\right\\}\right)}_{=N}\cup\underbrace{\left(\left\\{a,b\right\\}\setminus\left\\{b\right\\}\right)}_{\begin{subarray}{c}=\left\\{a\right\\}\\\
\text{(since }a\neq b\text{)}\end{subarray}}=N\cup\left\\{a\right\\}.$

Hence, $N\cup\left\\{a\right\\}=S\setminus\left\\{b\right\\}\in\mathcal{F}$.
But $\left\\{a\right\\}$ and $\left\\{i\right\\}$ are subsets of $B$ (since
$a\in\left\\{a,b\right\\}\subseteq B$ and $i\in C\subseteq B$), and satisfy
$\left|\left\\{a\right\\}\right|=\left|\left\\{i\right\\}\right|$ (since both
$\left|\left\\{a\right\\}\right|$ and $\left|\left\\{i\right\\}\right|$ equal
$1$) and $\left\\{i\right\\}\subseteq C$ (since $i\in C$) and
$N\cup\left\\{a\right\\}\in\mathcal{F}$. Hence, Corollary 11.10 (applied to
$P=\left\\{a\right\\}$ and $Q=\left\\{i\right\\}$) yields
$N\cup\left\\{i\right\\}\in\mathcal{F}$. This finishes the proof of Claim 4.]

> Claim 5: Let $i,j\in C$ be distinct. Then,
> $N\cap\left\\{i,j\right\\}=\varnothing$ and
> $N\cup\left\\{i,j\right\\}\in\mathcal{F}$.

[Proof of Claim 5: If we had $i\in N$, then we would have $i\notin B$ (since
$i\in N=S\setminus B$), which would contradict $i\in C\subseteq B$. Hence, we
cannot have $i\in N$. In other words, $i\notin N$. Likewise, $j\notin N$.
Combining $i\notin N$ with $j\notin N$, we obtain
$N\cap\left\\{i,j\right\\}=\varnothing$. It remains to prove that
$N\cup\left\\{i,j\right\\}\in\mathcal{F}$.

Note that $\left|\left\\{a,b\right\\}\right|=2$ and
$\left|\left\\{i,j\right\\}\right|=2$ (since $i$ and $j$ are distinct). Hence,
$\left|\left\\{a,b\right\\}\right|=2=\left|\left\\{i,j\right\\}\right|$. Also,
$i,j\in C$, so that $\left\\{i,j\right\\}\subseteq C\subseteq B$.

We have $S=N\cup\left\\{a,b\right\\}$, thus
$N\cup\left\\{a,b\right\\}=S\in\mathcal{F}$. But $\left\\{a,b\right\\}$ and
$\left\\{i,j\right\\}$ are subsets of $B$ (since
$\left\\{a,b\right\\}\subseteq B$ and $\left\\{i,j\right\\}\subseteq B$), and
satisfy $\left|\left\\{a,b\right\\}\right|=\left|\left\\{i,j\right\\}\right|$
and $\left\\{i,j\right\\}\subseteq C$ and
$N\cup\left\\{a,b\right\\}\in\mathcal{F}$. Hence, Corollary 11.10 (applied to
$P=\left\\{a,b\right\\}$ and $Q=\left\\{i,j\right\\}$) yields
$N\cup\left\\{i,j\right\\}\in\mathcal{F}$. This finishes the proof of Claim
5.]

> Claim 6: Let $p\in N$. Let $i,j\in C$ be distinct. Then,
> $\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\notin\mathcal{F}$.

[Proof of Claim 6: Assume the contrary. Hence,
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\in\mathcal{F}$.
Also,
$\left|\left(\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\right)\cap
B\right|\geqslant 2$ 252525Proof. We have $p\in N=S\setminus B$, so that
$p\notin B$. Hence, $B\setminus\left\\{p\right\\}=B$. Also, $i,j\in C$, so
that $\left\\{i,j\right\\}\subseteq C\subseteq B$. But it is known from set
theory that $\left(X\setminus Y\right)\cap Z=X\cap\left(Z\setminus Y\right)$
for any three sets $X$, $Y$ and $Z$. Applying this to
$X=N\cup\left\\{i,j\right\\}$, $Y=\left\\{p\right\\}$ and $Z=B$, we obtain
$\left(\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\right)\cap
B=\underbrace{\left(N\cup\left\\{i,j\right\\}\right)}_{\supseteq\left\\{i,j\right\\}}\cap\underbrace{\left(B\setminus\left\\{p\right\\}\right)}_{=B}\supseteq\left\\{i,j\right\\}\cap
B=\left\\{i,j\right\\}$ (since $\left\\{i,j\right\\}\subseteq B$). Hence,
$\left|\left(\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\right)\cap
B\right|\geqslant\left|\left\\{i,j\right\\}\right|=2$ (since $i$ and $j$ are
distinct). Qed.. Therefore,
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}$ is a
secant set (by the definition of “secant set”). Hence,

$\left|\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\right|\geqslant\left|S\right|$
(48)

(since $S$ was defined to be a secant set of smallest size).

We have $\left|\left\\{i,j\right\\}\right|=2$ (since $i$ and $j$ are
distinct). But Claim 5 yields $N\cap\left\\{i,j\right\\}=\varnothing$, so that
$\left|N\cup\left\\{i,j\right\\}\right|=\left|N\right|+\underbrace{\left|\left\\{i,j\right\\}\right|}_{=2}=\left|N\right|+2=\left|S\right|$
(by (47)). But $p\in N\subseteq N\cup\left\\{i,j\right\\}$ and thus
$\left|\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\right|=\underbrace{\left|N\cup\left\\{i,j\right\\}\right|}_{=\left|S\right|}-1=\left|S\right|-1<\left|S\right|$.
This contradicts (48). This contradiction shows that our assumption was false.
Hence, Claim 6 is proved.]

But recall that $\mathcal{F}$ is the Gaussian elimination greedoid of a vector
family over $\mathbb{K}$ (by assumption). Let $\left(v_{e}\right)_{e\in E}$ be
this vector family. Recall that $N$ and $C$ are two disjoint subsets of $E$.
Moreover, the following facts hold:

  1. (i)

For any $i\in C$, we have $N\cup\left\\{i\right\\}\in\mathcal{F}$ (by Claim
4).

  2. (ii)

For any distinct $i,j\in C$, we have $N\cup\left\\{i,j\right\\}\in\mathcal{F}$
(by Claim 5).

  3. (iii)

For any $p\in N$ and any distinct $i,j\in C$, we have
$\left(N\cup\left\\{i,j\right\\}\right)\setminus\left\\{p\right\\}\notin\mathcal{F}$
(by Claim 6).

Hence, Lemma 11.16 shows that
$\left|\mathbb{K}\right|\geqslant\left|C\right|$. This proves Theorem 5.1.

##  12 Appendix: Gaussian elimination greedoids are strong

We shall now prove Theorem 1.3. In order to do so, we will first need to
recall the definition of a strong greedoid (see, e.g., [GriPet19, §6.1]):

######  Definition 12.1.

Let $E$ be a finite set. A set system $\mathcal{F}$ on ground set $E$ is said
to be a greedoid if it satisfies the following three axioms:

  1. (i)

We have $\varnothing\in\mathcal{F}$.

  2. (ii)

If $B\in\mathcal{F}$ satisfies $\left|B\right|>0$, then there exists $b\in B$
such that $B\setminus\left\\{b\right\\}\in\mathcal{F}$.

  3. (iii)

If $A,B\in\mathcal{F}$ satisfy $\left|B\right|=\left|A\right|+1$, then there
exists $b\in B\setminus A$ such that $A\cup\left\\{b\right\\}\in\mathcal{F}$.

Furthermore, $\mathcal{F}$ is said to be a strong greedoid if it satisfies the
following axiom (in addition to axioms (i), (ii) and (iii)):

  1. (iv)

If $A,B\in\mathcal{F}$ satisfy $\left|B\right|=\left|A\right|+1$, then there
exists $b\in B\setminus A$ such that $A\cup\left\\{b\right\\}\in\mathcal{F}$
and $B\setminus\left\\{b\right\\}\in\mathcal{F}$.

Note that axiom (iii) in Definition 12.1 clearly follows from axiom (iv);
thus, only axioms (i), (ii) and (iv) need to be checked in order to convince
ourselves that a set system is a strong greedoid.

We shall furthermore use a determinantal identity due to Plücker (one of
several facts known as the Plücker identities). To state this identity, we
will use the following notations:

######  Definition 12.2.

Let $\mathbb{K}$ be a commutative ring. Let $n\in\mathbb{N}$ and
$m\in\mathbb{N}$. Let $A\in\mathbb{K}^{n\times m}$ be an $n\times m$-matrix.
(Here and in the following, $\mathbb{K}^{n\times m}$ denotes the set of all
$n\times m$-matrices with entries in $\mathbb{K}$.)

(a) If $v\in\mathbb{K}^{n\times 1}$ is a column vector with $n$ entries, then
$\left(A\mid v\right)$ will denote the $n\times\left(m+1\right)$-matrix whose
$m+1$ columns are $A_{\bullet,1},A_{\bullet,2},\ldots,A_{\bullet,m},v$ (from
left to right). (Informally speaking, $\left(A\mid v\right)$ is the matrix
obtained when the column vector $v$ is “attached” to $A$ at the right edge.)

(b) If $j\in\left\\{1,2,\ldots,m\right\\}$, then $A_{\bullet,j}$ shall mean
the $j$-th column of the matrix $A$. This is a column vector with $n$ entries,
i.e., an $n\times 1$-matrix.

(c) If $i\in\left\\{1,2,\ldots,n\right\\}$, then $A_{\sim i,\bullet}$ shall
mean the matrix obtained from the matrix $A$ by removing the $i$-th row. This
is an $\left(n-1\right)\times m$-matrix.

(d) If $i\in\left\\{1,2,\ldots,n\right\\}$ and
$j\in\left\\{1,2,\ldots,m\right\\}$, then $A_{\sim i,\sim j}$ shall mean the
matrix obtained from $A$ by removing the $i$-th row and the $j$-th column.
This is an $\left(n-1\right)\times\left(m-1\right)$-matrix.

We can now state our Plücker identity:

######  Proposition 12.3.

Let $\mathbb{K}$ be a commutative ring. Let $n$ be a positive integer. Let
$X\in\mathbb{K}^{n\times\left(n-1\right)}$ and $Y\in\mathbb{K}^{n\times n}$.
Let $i\in\left\\{1,2,\ldots,n\right\\}$. Then,

$\det\left(X_{\sim i,\bullet}\right)\det
Y=\sum\limits_{q=1}^{n}\left(-1\right)^{n+q}\det\left(X\mid
Y_{\bullet,q}\right)\det\left(Y_{\sim i,\sim q}\right).$

######  Example 12.4.

If we set $n=3$, $X=\left(\begin{array}[c]{cc}a&a^{\prime}\\\ b&b^{\prime}\\\
c&c^{\prime}\end{array}\right)$,
$Y=\left(\begin{array}[c]{ccc}x&x^{\prime}&x^{\prime\prime}\\\
y&y^{\prime}&y^{\prime\prime}\\\
z&z^{\prime}&z^{\prime\prime}\end{array}\right)$ and $i=2$, then Proposition
12.3 states that

$\displaystyle\det\left(\begin{array}[c]{cc}a&a^{\prime}\\\
c&c^{\prime}\end{array}\right)\det\left(\begin{array}[c]{ccc}x&x^{\prime}&x^{\prime\prime}\\\
y&y^{\prime}&y^{\prime\prime}\\\
z&z^{\prime}&z^{\prime\prime}\end{array}\right)$
$\displaystyle=\det\left(\begin{array}[c]{ccc}a&a^{\prime}&x\\\
b&b^{\prime}&y\\\
c&c^{\prime}&z\end{array}\right)\det\left(\begin{array}[c]{cc}x^{\prime}&x^{\prime\prime}\\\
z^{\prime}&z^{\prime\prime}\end{array}\right)-\det\left(\begin{array}[c]{ccc}a&a^{\prime}&x^{\prime}\\\
b&b^{\prime}&y^{\prime}\\\
c&c^{\prime}&z^{\prime}\end{array}\right)\det\left(\begin{array}[c]{cc}x&x^{\prime\prime}\\\
z&z^{\prime\prime}\end{array}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
+\det\left(\begin{array}[c]{ccc}a&a^{\prime}&x^{\prime\prime}\\\
b&b^{\prime}&y^{\prime\prime}\\\
c&c^{\prime}&z^{\prime\prime}\end{array}\right)\det\left(\begin{array}[c]{cc}x&x^{\prime}\\\
z&z^{\prime}\end{array}\right).$

Proposition 12.3 is precisely [Grinbe15, Proposition 6.137] (with $A$, $C$ and
$v$ renamed as $X$, $Y$ and $i$).

######  Proof 12.5 (Proof of Theorem 1.3.).

We need to prove that $\mathcal{G}$ is a strong greedoid. In other words, we
need to prove that the axioms (i), (ii), (iii) and (iv) from Definition 12.1
are satisfied for $\mathcal{F}=\mathcal{G}$. Let us do this:

Proof of the axiom (i) for $\mathcal{F}=\mathcal{G}$: The vector family
$\left(\pi_{\left|\varnothing\right|}\left(v_{e}\right)\right)_{e\in\varnothing}\in\left(\mathbb{K}^{\left|\varnothing\right|}\right)^{\varnothing}$
is empty, and thus is linearly independent. In other words,
$\varnothing\in\mathcal{G}$. This proves that the axiom (i) from Definition
12.1 is satisfied for $\mathcal{F}=\mathcal{G}$.

Proof of the axiom (ii) for $\mathcal{F}=\mathcal{G}$: Let $B\in\mathcal{G}$
satisfy $\left|B\right|>0$. We shall show that there exists $b\in B$ such that
$B\setminus\left\\{b\right\\}\in\mathcal{G}$.

Let $n=\left|B\right|$. Thus, $n=\left|B\right|>0$.

We have $B\in\mathcal{G}$. In other words, the family
$\left(\pi_{\left|B\right|}\left(v_{e}\right)\right)_{e\in
B}\in\left(\mathbb{K}^{\left|B\right|}\right)^{B}$ is linearly independent (by
the definition of $\mathcal{G}$). In other words, the family
$\left(\pi_{n}\left(v_{e}\right)\right)_{e\in
B}\in\left(\mathbb{K}^{n}\right)^{B}$ is linearly independent (since
$\left|B\right|=n$).

Let $Y$ be the $n\times n$-matrix whose columns are the vectors
$\pi_{n}\left(v_{e}\right)$ for all $e\in B$ (in some order, with no
repetition). The columns of this $n\times n$-matrix $Y$ are thus linearly
independent (since the family $\left(\pi_{n}\left(v_{e}\right)\right)_{e\in
B}\in\left(\mathbb{K}^{\left|B\right|}\right)^{B}$ is linearly independent).
Hence, this $n\times n$-matrix $Y$ is invertible. In other words, $\det Y\neq
0$.

Now, let $y_{i,j}$ be the $\left(i,j\right)$-th entry of the matrix $Y$ for
each $i,j\in\left\\{1,2,\ldots,n\right\\}$. Then, Laplace expansion along the
$n$-th row yields

$\det Y=\sum\limits_{q=1}^{n}\left(-1\right)^{n+q}y_{n,q}\det\left(Y_{\sim
n,\sim q}\right).$

If every $q\in\left\\{1,2,\ldots,n\right\\}$ satisfied $\det\left(Y_{\sim
n,\sim q}\right)=0$, then this would become

$\det
Y=\sum\limits_{q=1}^{n}\left(-1\right)^{n+q}y_{n,q}\underbrace{\det\left(Y_{\sim
n,\sim q}\right)}_{=0}=0,$

which would contradict $\det Y\neq 0$. Hence, not every
$q\in\left\\{1,2,\ldots,n\right\\}$ satisfies $\det\left(Y_{\sim n,\sim
q}\right)=0$. In other words, there exists at least one
$q\in\left\\{1,2,\ldots,n\right\\}$ such that $\det\left(Y_{\sim n,\sim
q}\right)\neq 0$. Consider this $q$. The $q$-th column of $Y$ is the vector
$\pi_{n}\left(v_{f}\right)$ for some $f\in B$ (by the definition of $Y$);
consider this $f$. Note that
$\left|B\setminus\left\\{f\right\\}\right|=\left|B\right|-1=n-1$ (since
$\left|B\right|=n$).

The $\left(n-1\right)\times\left(n-1\right)$-matrix $Y_{\sim n,\sim q}$ is
invertible (since $\det\left(Y_{\sim n,\sim q}\right)\neq 0$); thus, its $n-1$
columns are linearly independent. But these $n-1$ columns are precisely the
$n-1$ vectors $\pi_{n-1}\left(v_{e}\right)$ for all $e\in
B\setminus\left\\{f\right\\}$ (by the definition of $Y$ and the choice of
$f$). Hence, the $n-1$ vectors $\pi_{n-1}\left(v_{e}\right)$ for all $e\in
B\setminus\left\\{f\right\\}$ are linearly independent. In other words, the
family $\left(\pi_{n-1}\left(v_{e}\right)\right)_{e\in
B\setminus\left\\{f\right\\}}$ is linearly independent. In other words, the
family
$\left(\pi_{\left|B\setminus\left\\{f\right\\}\right|}\left(v_{e}\right)\right)_{e\in
B\setminus\left\\{f\right\\}}$ is linearly independent (since
$\left|B\setminus\left\\{f\right\\}\right|=n-1$). In other words,
$B\setminus\left\\{f\right\\}\in\mathcal{G}$ (by the definition of
$\mathcal{G}$). Hence, there exists $b\in B$ such that
$B\setminus\left\\{b\right\\}\in\mathcal{G}$ (namely, $b=f$). This shows that
the axiom (ii) from Definition 12.1 is satisfied for
$\mathcal{F}=\mathcal{G}$.

Proof of the axiom (iv) for $\mathcal{F}=\mathcal{G}$: Let $A,B\in\mathcal{G}$
satisfy $\left|B\right|=\left|A\right|+1$. We shall show that there exists
$b\in B\setminus A$ such that $A\cup\left\\{b\right\\}\in\mathcal{G}$ and
$B\setminus\left\\{b\right\\}\in\mathcal{G}$.

Let $n=\left|B\right|$. Thus, $n=\left|B\right|=\left|A\right|+1\geqslant
1>0$. Also, from $n=\left|A\right|+1$, we obtain $\left|A\right|=n-1$.

We have $B\in\mathcal{G}$. In other words, the family
$\left(\pi_{\left|B\right|}\left(v_{e}\right)\right)_{e\in
B}\in\left(\mathbb{K}^{\left|B\right|}\right)^{B}$ is linearly independent (by
the definition of $\mathcal{G}$). In other words, the family
$\left(\pi_{n}\left(v_{e}\right)\right)_{e\in
B}\in\left(\mathbb{K}^{n}\right)^{B}$ is linearly independent (since
$\left|B\right|=n$). Similarly, the family
$\left(\pi_{n-1}\left(v_{e}\right)\right)_{e\in
A}\in\left(\mathbb{K}^{n-1}\right)^{A}$ is linearly independent.

Let $Y$ be the $n\times n$-matrix whose columns are the vectors
$\pi_{n}\left(v_{e}\right)$ for all $e\in B$ (in some order, with no
repetition). The columns of this $n\times n$-matrix $Y$ are thus linearly
independent (since the family $\left(\pi_{n}\left(v_{e}\right)\right)_{e\in
B}\in\left(\mathbb{K}^{\left|B\right|}\right)^{B}$ is linearly independent).
Hence, this $n\times n$-matrix $Y$ is invertible. In other words, $\det Y\neq
0$.

Let $X$ be the $n\times\left(n-1\right)$-matrix whose columns are the vectors
$\pi_{n}\left(v_{e}\right)$ for all $e\in A$ (in some order, with no
repetition). Then, the columns of the
$\left(n-1\right)\times\left(n-1\right)$-matrix $X_{\sim n,\bullet}$ are the
vectors $\pi_{n-1}\left(v_{e}\right)$ for all $e\in A$; thus, they are
linearly independent (since the family
$\left(\pi_{n-1}\left(v_{e}\right)\right)_{e\in
A}\in\left(\mathbb{K}^{n-1}\right)^{A}$ is linearly independent). Hence, this
$\left(n-1\right)\times\left(n-1\right)$-matrix $X_{\sim n,\bullet}$ is
invertible. In other words, $\det\left(X_{\sim n,\bullet}\right)\neq 0$.

But $\mathbb{K}$ is a field and thus an integral domain. Hence, from
$\det\left(X_{\sim n,\bullet}\right)\neq 0$ and $\det Y\neq 0$, we obtain

$\det\left(X_{\sim n,\bullet}\right)\det Y\neq 0.$ (49)

If every $q\in\left\\{1,2,\ldots,n\right\\}$ satisfied $\det\left(X\mid
Y_{\bullet,q}\right)\det\left(Y_{\sim n,\sim q}\right)=0$, then we would have

$\displaystyle\det\left(X_{\sim n,\bullet}\right)\det Y$
$\displaystyle=\sum\limits_{q=1}^{n}\left(-1\right)^{n+q}\underbrace{\det\left(X\mid
Y_{\bullet,q}\right)\det\left(Y_{\sim n,\sim q}\right)}_{=0}$ $\displaystyle\
\ \ \ \ \ \ \ \ \ \left(\text{by Proposition \ref{prop.desnanot.XY}, applied
to }i=n\right)$ $\displaystyle=0,$

which would contradict (49). Hence, not every
$q\in\left\\{1,2,\ldots,n\right\\}$ satisfies
$\det\left(X\mid Y_{\bullet,q}\right)\det\left(Y_{\sim n,\sim q}\right)=0$. In
other words, some $q\in\left\\{1,2,\ldots,n\right\\}$ satisfies
$\det\left(X\mid Y_{\bullet,q}\right)\det\left(Y_{\sim n,\sim q}\right)\neq
0$. Consider this $q$. The $q$-th column of $Y$ is the vector
$\pi_{n}\left(v_{f}\right)$ for some $f\in B$ (by the definition of $Y$);
consider this $f$. Thus, $Y_{\bullet,q}=\pi_{n}\left(v_{f}\right)$.

Note that $\left|B\setminus\left\\{f\right\\}\right|=\left|B\right|-1=n-1$
(since $\left|B\right|=n$).

From $\det\left(X\mid Y_{\bullet,q}\right)\det\left(Y_{\sim n,\sim
q}\right)\neq 0$, we obtain $\det\left(X\mid Y_{\bullet,q}\right)\neq 0$ and
$\det\left(Y_{\sim n,\sim q}\right)\neq 0$.

The $\left(n-1\right)\times\left(n-1\right)$-matrix $Y_{\sim n,\sim q}$ is
invertible (since $\det\left(Y_{\sim n,\sim q}\right)\neq 0$); thus, its $n-1$
columns are linearly independent. But these $n-1$ columns are precisely the
$n-1$ vectors $\pi_{n-1}\left(v_{e}\right)$ for all $e\in
B\setminus\left\\{f\right\\}$ (by the definition of $Y$ and the choice of
$f$). Hence, the $n-1$ vectors $\pi_{n-1}\left(v_{e}\right)$ for all $e\in
B\setminus\left\\{f\right\\}$ are linearly independent. In other words, the
family $\left(\pi_{n-1}\left(v_{e}\right)\right)_{e\in
B\setminus\left\\{f\right\\}}$ is linearly independent. In other words, the
family
$\left(\pi_{\left|B\setminus\left\\{f\right\\}\right|}\left(v_{e}\right)\right)_{e\in
B\setminus\left\\{f\right\\}}$ is linearly independent (since
$\left|B\setminus\left\\{f\right\\}\right|=n-1$). In other words,
$B\setminus\left\\{f\right\\}\in\mathcal{G}$ (by the definition of
$\mathcal{G}$).

The $n\times n$-matrix $\left(X\mid Y_{\bullet,q}\right)$ is invertible (since
$\det\left(X\mid Y_{\bullet,q}\right)\neq 0$); thus, its $n$ columns are
linearly independent. But these $n$ columns are precisely the $n-1$ vectors
$\pi_{n}\left(v_{e}\right)$ for all $e\in A$ as well as the extra vector
$Y_{\bullet,q}=\pi_{n}\left(v_{f}\right)$. Thus, if we had $f\in A$, then
these $n$ columns would contain two equal vectors (namely, the extra vector
$Y_{\bullet,q}=\pi_{n}\left(v_{f}\right)$ would be equal to one of the vectors
$\pi_{n}\left(v_{e}\right)$ with $e\in A$), and thus would be linearly
dependent. But this would contradict the fact that these $n$ columns are
linearly independent. Hence, we cannot have $f\in A$. Thus, $f\notin A$.
Combining $f\in B$ with $f\notin A$, we obtain $f\in B\setminus A$. From
$f\notin A$, we also obtain
$\left|A\cup\left\\{f\right\\}\right|=\left|A\right|+1=n$ (since
$\left|A\right|=n-1$).

Recall that the $n$ columns of the $n\times n$-matrix $\left(X\mid
Y_{\bullet,q}\right)$ are the $n-1$ vectors $\pi_{n}\left(v_{e}\right)$ for
all $e\in A$ as well as the extra vector
$Y_{\bullet,q}=\pi_{n}\left(v_{f}\right)$. In other words, they are the $n$
vectors $\pi_{n}\left(v_{e}\right)$ for all $e\in A\cup\left\\{f\right\\}$
(since $f\notin A$). Hence, the $n$ vectors $\pi_{n}\left(v_{e}\right)$ for
all $e\in A\cup\left\\{f\right\\}$ are linearly independent (since the $n$
columns of the $n\times n$-matrix $\left(X\mid Y_{\bullet,q}\right)$ are
linearly independent). In other words, the family
$\left(\pi_{n}\left(e\right)\right)_{e\in A\cup\left\\{f\right\\}}$ is
linearly independent. In other words, the family
$\left(\pi_{\left|A\cup\left\\{f\right\\}\right|}\left(e\right)\right)_{e\in
A\cup\left\\{f\right\\}}$ is linearly independent (since
$n=\left|A\cup\left\\{f\right\\}\right|$). In other words,
$A\cup\left\\{f\right\\}\in\mathcal{G}$ (by the definition of $\mathcal{G}$).

We now know that $f\in B\setminus A$ and
$A\cup\left\\{f\right\\}\in\mathcal{G}$ and
$B\setminus\left\\{f\right\\}\in\mathcal{G}$. Hence, there exists $b\in
B\setminus A$ such that $A\cup\left\\{b\right\\}\in\mathcal{G}$ and
$B\setminus\left\\{b\right\\}\in\mathcal{G}$ (namely, $b=f$). This shows that
the axiom (iv) from Definition 12.1 is satisfied for
$\mathcal{F}=\mathcal{G}$.

Proof of the axiom (iii) for $\mathcal{F}=\mathcal{G}$: Clearly, axiom (iii)
from Definition 12.1 follows from axiom (iv). Thus, axiom (iii) holds for
$\mathcal{F}=\mathcal{G}$ (since we already know that axiom (iv) holds for
$\mathcal{F}=\mathcal{G}$).

We have now showed that the system $\mathcal{G}$ satisfies the four axioms
(i), (ii), (iii) and (iv) from Definition 12.1. Thus, $\mathcal{G}$ is a
strong greedoid. This proves Theorem 1.3.

##  13 Appendix: Proof of Proposition 1.4

We shall now prove Proposition 1.4. This proof is mostly bookkeeping.

######  Proof 13.1 (Proof of Proposition 1.4 (sketched).).

If $\mathcal{G}_{k}$ is empty, then the claim is obvious. Thus, we WLOG assume
that $\mathcal{G}_{k}$ is nonempty.

We assumed that $\mathcal{G}$ is a Gaussian elimination greedoid. In other
words, there exist a field $\mathbb{K}$ and a vector family
$\left(v_{e}\right)_{e\in E}$ over $\mathbb{K}$ such that $\mathcal{G}$ is the
Gaussian elimination greedoid of this vector family $\left(v_{e}\right)_{e\in
E}$. Consider these $\mathbb{K}$ and $\left(v_{e}\right)_{e\in E}$. Let $X$ be
the $k\times\left|E\right|$-matrix whose columns are the vectors
$\pi_{k}\left(v_{e}\right)\in\mathbb{K}^{k}$ for all $e\in E$ (in some order).
Then, there is a bijection
$\phi:\left\\{1,2,\ldots,\left|E\right|\right\\}\rightarrow E$ such that the
columns of the matrix $X$ are
$\pi_{k}\left(v_{\phi\left(1\right)}\right),\pi_{k}\left(v_{\phi\left(2\right)}\right),\ldots,\pi_{k}\left(v_{\phi\left(\left|E\right|\right)}\right)$
(in this order). Consider this $\phi$. Hence,

$\left(f\text{-th column of
}X\right)=\pi_{k}\left(v_{\phi\left(f\right)}\right)$ (50)

for each $f\in\left\\{1,2,\ldots,\left|E\right|\right\\}$. Let $\mathcal{V}$
be the vector matroid262626See [Oxley11, §1.1] for the definition of a vector
matroid. of the matrix $X$. This is a matroid on the set
$\left\\{1,2,\ldots,\left|E\right|\right\\}$; its rank is at most $k$ (since
$X$ has $k$ rows and therefore rank $\leqslant k$).

The bijection $\phi$ can be used to transport the matroid $\mathcal{V}$ onto
the set $E$. More precisely, we can define a matroid $\mathcal{V}^{\prime}$ on
the set $E$ by

$\mathcal{V}^{\prime}=\left\\{\phi\left(I\right)\ \mid\
I\in\mathcal{V}\right\\}$

(where we regard a matroid as a collection of independent sets). The
independent sets of this matroid $\mathcal{V}^{\prime}$ are the subsets $I$ of
$E$ for which $\phi^{-1}\left(I\right)$ is an independent set of
$\mathcal{V}$. Moreover, the map $\phi$ is an isomorphism from the matroid
$\mathcal{V}$ to the matroid $\mathcal{V}^{\prime}$. Thus, the matroid
$\mathcal{V}^{\prime}$ is isomorphic to the vector matroid $\mathcal{V}$, and
hence is representable. Our goal is now to show that $\mathcal{G}_{k}$ is the
collection of bases of $\mathcal{V}$.

Let $F$ be a $k$-element subset of $E$. Then, we have the following chain of
logical equivalences:

$\displaystyle\ \left(F\in\mathcal{G}_{k}\right)$
$\displaystyle\Longleftrightarrow\ \left(F\in\mathcal{G}\right)\ \ \ \ \ \ \ \
\ \ \left(\text{since }\mathcal{G}_{k}\text{ is the set of all
}k\text{-element sets in }\mathcal{G}\right)$
$\displaystyle\Longleftrightarrow\ \left(\text{the family
}\left(\pi_{\left|F\right|}\left(v_{e}\right)\right)_{e\in
F}\in\left(\mathbb{K}^{\left|F\right|}\right)^{F}\text{ is linearly
independent}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\begin{array}[c]{c}\text{by the definition of a Gaussian elimination
greedoid,}\\\ \text{since }\mathcal{G}\text{ is the Gaussian elimination
greedoid of }\left(v_{e}\right)_{e\in E}\end{array}\right)$ (53)
$\displaystyle\Longleftrightarrow\ \left(\text{the family
}\left(\pi_{k}\left(v_{e}\right)\right)_{e\in
F}\in\left(\mathbb{K}^{k}\right)^{F}\text{ is linearly independent}\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since }\left|F\right|=k\text{
(because }F\text{ is a }k\text{-element set)}\right)$
$\displaystyle\Longleftrightarrow\ \left(\text{the family
}\left(\pi_{k}\left(v_{\phi\left(f\right)}\right)\right)_{f\in\phi^{-1}\left(F\right)}\in\left(\mathbb{K}^{k}\right)^{\phi^{-1}\left(F\right)}\text{
is linearly independent}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\begin{array}[c]{c}\text{since
}\phi:\left\\{1,2,\ldots,\left|E\right|\right\\}\rightarrow E\text{ is a
bijection, and thus the}\\\ \text{family
}\left(\pi_{k}\left(v_{\phi\left(f\right)}\right)\right)_{f\in\phi^{-1}\left(F\right)}\text{
is just a reindexing of the family
}\left(\pi_{k}\left(v_{e}\right)\right)_{e\in F}\end{array}\right)$ (56)
$\displaystyle\Longleftrightarrow\ \left(\text{the family }\left(f\text{-th
column of
}X\right)_{f\in\phi^{-1}\left(F\right)}\in\left(\mathbb{K}^{k}\right)^{\phi^{-1}\left(F\right)}\text{
is linearly independent}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\text{since (\ref{pf.prop.geg.matroid-rep.fcolX=}) yields
}\left(f\text{-th column of
}X\right)_{f\in\phi^{-1}\left(F\right)}=\left(\pi_{k}\left(v_{\phi\left(f\right)}\right)\right)_{f\in\phi^{-1}\left(F\right)}\right)$
$\displaystyle\Longleftrightarrow\ \left(\phi^{-1}\left(F\right)\text{ is an
independent set of the vector matroid of }X\right)$ $\displaystyle\ \ \ \ \ \
\ \ \ \ \left(\text{by the definition of a vector matroid}\right)$
$\displaystyle\Longleftrightarrow\ \left(\phi^{-1}\left(F\right)\text{ is an
independent set of }\mathcal{V}\right)$ (57) $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\text{since }\mathcal{V}\text{ is the vector matroid of }X\right).$

Forget that we fixed $F$. We thus have proved the equivalence (57) for each
$k$-element subset $F$ of $E$.

Recall that $\mathcal{G}_{k}$ is nonempty. In other words, there exists some
$B\in\mathcal{G}_{k}$. Consider this $B$. Thus, $B$ is a $k$-element set in
$\mathcal{G}$ (since $\mathcal{G}_{k}$ is the set of all $k$-element sets in
$\mathcal{G}$). Hence, the equivalence (57) (applied to $F=B$) yields the
equivalence

$\left(B\in\mathcal{G}_{k}\right)\ \Longleftrightarrow\
\left(\phi^{-1}\left(B\right)\text{ is an independent set of
}\mathcal{V}\right).$

Thus, $\phi^{-1}\left(B\right)$ is an independent set of $\mathcal{V}$ (since
$B\in\mathcal{G}_{k}$). Since $\phi$ is a bijection, we have
$\left|\phi^{-1}\left(B\right)\right|=\left|B\right|=k$ (since $B$ is a
$k$-element set). In other words, $\phi^{-1}\left(B\right)$ is a $k$-element
set. Thus, the matroid $\mathcal{V}$ has a $k$-element independent set
(namely, $\phi^{-1}\left(B\right)$). Therefore, the rank of $\mathcal{V}$ is
at least $k$. Since we also know that the rank of $\mathcal{V}$ is at most
$k$, we thus conclude that the rank of $\mathcal{V}$ is exactly $k$. Hence,
the rank of $\mathcal{V}^{\prime}$ is exactly $k$ as well (since the matroid
$\mathcal{V}^{\prime}$ is isomorphic to the matroid $\mathcal{V}$). Therefore,
the bases of $\mathcal{V}^{\prime}$ are the $k$-element independent sets of
$\mathcal{V}^{\prime}$. Thus, a $k$-element set is an independent set of
$\mathcal{V}^{\prime}$ if and only if it is a basis of $\mathcal{V}^{\prime}$.

Now, let $F$ again be a $k$-element subset of $E$. Thus, $F$ is an independent
set of $\mathcal{V}^{\prime}$ if and only if $F$ is a basis of
$\mathcal{V}^{\prime}$ (since a $k$-element set is an independent set of
$\mathcal{V}^{\prime}$ if and only if it is a basis of
$\mathcal{V}^{\prime}$). Also, $\phi^{-1}\left(F\right)$ is an independent set
of $\mathcal{V}$ if and only if $F$ is an independent set of
$\mathcal{V}^{\prime}$ (since the independent sets of the matroid
$\mathcal{V}^{\prime}$ are the subsets $I$ of $E$ for which
$\phi^{-1}\left(I\right)$ is an independent set of $\mathcal{V}$).

Now, we have the following chain of logical equivalences:

$\displaystyle\left(F\in\mathcal{G}_{k}\right)\ $
$\displaystyle\Longleftrightarrow\ \left(\phi^{-1}\left(F\right)\text{ is an
independent set of }\mathcal{V}\right)\ \ \ \ \ \ \ \ \ \ \left(\text{by
(\ref{pf.prop.geg.matroid-rep.long-equiv})}\right)$
$\displaystyle\Longleftrightarrow\ \left(F\text{ is an independent set of
}\mathcal{V}^{\prime}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\begin{array}[c]{c}\text{since }\phi^{-1}\left(F\right)\text{ is an
independent set of }\mathcal{V}\\\ \text{if and only if }F\text{ is an
independent set of }\mathcal{V}^{\prime}\end{array}\right)$
$\displaystyle\Longleftrightarrow\ \left(F\text{ is a basis of
}\mathcal{V}^{\prime}\right)$

(since $F$ is an independent set of $\mathcal{V}^{\prime}$ if and only if $F$
is a basis of $\mathcal{V}^{\prime}$).

Forget that we fixed $F$. We thus have proved that, for each $k$-element
subset $F$ of $E$, we have the equivalence

$\left(F\in\mathcal{G}_{k}\right)\ \Longleftrightarrow\ \left(F\text{ is a
basis of }\mathcal{V}^{\prime}\right).$

Hence, $\mathcal{G}_{k}$ is the collection of all bases of
$\mathcal{V}^{\prime}$ (since all bases of $\mathcal{V}^{\prime}$ are
$k$-element subsets of $E$ (because $\mathcal{V}^{\prime}$ is a matroid of
rank $k$)). Hence, $\mathcal{G}_{k}$ is the collection of bases of a
representable matroid on the ground set $E$ (since $\mathcal{V}^{\prime}$ is a
representable matroid on the ground set $E$). This proves Proposition 1.4.

##  14 Appendix: Proofs of some properties of $\mathbb{L}$

We shall next prove four lemmas that were left unproven in Section 6: namely,
Lemma 6.4, Lemma 6.10, Lemma 6.13 and Lemma 6.14.

######  Proof 14.1 (Proof of Lemma 6.4.).

(a) Let $a\in\mathbb{L}$ be a nonzero element. We must prove that the element
$a$ belongs to $\mathbb{L}_{+}$ if and only if its order
$\operatorname*{ord}a$ is nonnegative (i.e., we have
$\operatorname*{ord}a\geqslant 0$). In other words, we must prove that
$a\in\mathbb{L}_{+}$ if and only if $\operatorname*{ord}a\geqslant 0$.

Recall that $\operatorname*{ord}a$ is defined as the smallest
$\beta\in\mathbb{V}$ such that $\left[t_{\beta}\right]a\neq 0$. Thus,
$\operatorname*{ord}a$ is a $\beta\in\mathbb{V}$ such that
$\left[t_{\beta}\right]a\neq 0$. In other words,
$\operatorname*{ord}a\in\mathbb{V}$ and
$\left[t_{\operatorname*{ord}a}\right]a\neq 0$.

We shall now prove the implication

$\left(a\in\mathbb{L}_{+}\right)\ \Longrightarrow\
\left(\operatorname*{ord}a\geqslant 0\right).$ (58)

[Proof of (58): Assume that $a\in\mathbb{L}_{+}$. Then,
$a\in\mathbb{L}_{+}=\mathbb{K}\left[\mathbb{V}_{\geqslant 0}\right]$. In other
words, $a$ is a $\mathbb{K}$-linear combination of the family
$\left(t_{\alpha}\right)_{\alpha\in\mathbb{V}_{\geqslant 0}}$. Thus, every
$\alpha\in\mathbb{V}$ that satisfies $\left[t_{\alpha}\right]a\neq 0$ is an
element of $\mathbb{V}_{\geqslant 0}$. Applying this to
$\alpha=\operatorname*{ord}a$, we conclude that $\operatorname*{ord}a$ is an
element of $\mathbb{V}_{\geqslant 0}$ (since
$\left[t_{\operatorname*{ord}a}\right]a\neq 0$). In other words,
$\operatorname*{ord}a\geqslant 0$. Thus, the implication (58) is proved.]

Next, let us prove the implication

$\left(\operatorname*{ord}a\geqslant 0\right)\ \Longrightarrow\
\left(a\in\mathbb{L}_{+}\right).$ (59)

[Proof of (59): Assume that $\operatorname*{ord}a\geqslant 0$. Now, let
$\alpha\in\mathbb{V}$ be such that $\alpha<0$. We shall show that
$\left[t_{\alpha}\right]a=0$.

Indeed, assume the contrary. Thus, $\left[t_{\alpha}\right]a\neq 0$. But
recall that $\operatorname*{ord}a$ is the smallest $\beta\in\mathbb{V}$ such
that $\left[t_{\beta}\right]a\neq 0$. Hence, for any $\beta\in\mathbb{V}$
satisfying $\left[t_{\beta}\right]a\neq 0$, we must have
$\beta\geqslant\operatorname*{ord}a$. Applying this to $\beta=\alpha$, we
obtain $\alpha\geqslant\operatorname*{ord}a\geqslant 0$. This contradicts
$\alpha<0$.

This contradiction shows that our assumption was wrong. Hence, we have proved
that $\left[t_{\alpha}\right]a=0$.

Forget that we fixed $\alpha$. We thus have proved that

$\left[t_{\alpha}\right]a=0\ \ \ \ \ \ \ \ \ \ \text{for each
}\alpha\in\mathbb{V}\text{ satisfying }\alpha<0.$ (60)

But $a\in\mathbb{L}=\mathbb{K}\left[\mathbb{V}\right]$. Thus,

$\displaystyle a$
$\displaystyle=\sum\limits_{\alpha\in\mathbb{V}}\left(\left[t_{\alpha}\right]a\right)\cdot
t_{\alpha}=\underbrace{\sum\limits_{\begin{subarray}{c}\alpha\in\mathbb{V};\\\
\alpha\geqslant
0\end{subarray}}}_{=\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}}\left(\left[t_{\alpha}\right]a\right)\cdot
t_{\alpha}+\sum\limits_{\begin{subarray}{c}\alpha\in\mathbb{V};\\\
\alpha<0\end{subarray}}\underbrace{\left(\left[t_{\alpha}\right]a\right)}_{\begin{subarray}{c}=0\\\
\text{(by (\ref{pf.lem.ord.triangle.a.2.pf.1}))}\end{subarray}}\cdot
t_{\alpha}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since each
}\alpha\in\mathbb{V}\text{ satisfies either }\alpha\geqslant 0\text{ or
}\alpha<0\text{ (but not both)}\right)$
$\displaystyle=\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}\left(\left[t_{\alpha}\right]a\right)\cdot
t_{\alpha}+\underbrace{\sum\limits_{\begin{subarray}{c}\alpha\in\mathbb{V};\\\
\alpha<0\end{subarray}}0t_{\alpha}}_{=0}=\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}\left(\left[t_{\alpha}\right]a\right)\cdot t_{\alpha}.$

Thus, $a$ is a $\mathbb{K}$-linear combination of the family
$\left(t_{\alpha}\right)_{\alpha\in\mathbb{V}_{\geqslant 0}}$. In other words,
$a\in\mathbb{K}\left[\mathbb{V}_{\geqslant 0}\right]$. In other words,
$a\in\mathbb{L}_{+}$ (since
$\mathbb{L}_{+}=\mathbb{K}\left[\mathbb{V}_{\geqslant 0}\right]$). This proves
the implication (59).]

Combining the two implications (58) and (59), we obtain the equivalence

$\left(a\in\mathbb{L}_{+}\right)\ \Longleftrightarrow\
\left(\operatorname*{ord}a\geqslant 0\right).$

In other words, $a\in\mathbb{L}_{+}$ if and only if
$\operatorname*{ord}a\geqslant 0$. This proves Lemma 6.4 (a).

(b) Let $a\in\mathbb{L}$ be nonzero. The definition of $\operatorname*{ord}a$
shows that

$\operatorname*{ord}a=\left(\text{the smallest }\beta\in\mathbb{V}\text{ such
that }\left[t_{\beta}\right]a\neq 0\right).$

The same argument (applied to $-a$ instead of $a$) yields

$\displaystyle\operatorname*{ord}\left(-a\right)$
$\displaystyle=\left(\text{the smallest }\beta\in\mathbb{V}\text{ such that
}\underbrace{\left[t_{\beta}\right]\left(-a\right)}_{=-\left[t_{\beta}\right]a}\neq
0\right)$ $\displaystyle=\left(\text{the smallest }\beta\in\mathbb{V}\text{
such that }-\left[t_{\beta}\right]a\neq 0\right)$
$\displaystyle=\left(\text{the smallest }\beta\in\mathbb{V}\text{ such that
}\left[t_{\beta}\right]a\neq 0\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\left(\text{since the condition \textquotedblleft}-\left[t_{\beta}\right]a\neq
0\text{\textquotedblright\ is equivalent to
\textquotedblleft}\left[t_{\beta}\right]a\neq
0\text{\textquotedblright}\right).$

Comparing these two equalities, we obtain
$\operatorname*{ord}\left(-a\right)=\operatorname*{ord}a$. This proves Lemma
6.4 (b).

(c) This is analogous to the standard fact that any two nonzero polynomials
$f,g\in\mathbb{K}\left[X\right]$ satisfy $fg\neq 0$ and
$\deg\left(fg\right)=\deg f+\deg g$. For the sake of completeness, let us
nevertheless present the proof.

Recall that $\operatorname*{ord}a$ is defined as the smallest
$\beta\in\mathbb{V}$ such that $\left[t_{\beta}\right]a\neq 0$. Thus,
$\operatorname*{ord}a$ is a $\beta\in\mathbb{V}$ such that
$\left[t_{\beta}\right]a\neq 0$. In other words,
$\operatorname*{ord}a\in\mathbb{V}$ and
$\left[t_{\operatorname*{ord}a}\right]a\neq 0$. The same argument (applied to
$b$ instead of $a$) yields $\operatorname*{ord}b\in\mathbb{V}$ and
$\left[t_{\operatorname*{ord}b}\right]b\neq 0$. From
$\left[t_{\operatorname*{ord}a}\right]a\neq 0$ and
$\left[t_{\operatorname*{ord}b}\right]b\neq 0$, we obtain
$\left(\left[t_{\operatorname*{ord}a}\right]a\right)\cdot\left(\left[t_{\operatorname*{ord}b}\right]b\right)\neq
0$ (since $\left[t_{\operatorname*{ord}a}\right]a$ and
$\left[t_{\operatorname*{ord}b}\right]b$ belong to the integral domain
$\mathbb{K}$).

Moreover,

$\left[t_{\beta}\right]a=0\ \ \ \ \ \ \ \ \ \ \text{for each
}\beta\in\mathbb{V}\text{ satisfying }\beta<\operatorname*{ord}a$ (61)

(since $\operatorname*{ord}a$ is the smallest $\beta\in\mathbb{V}$ such that
$\left[t_{\beta}\right]a\neq 0$). Similarly,

$\left[t_{\beta}\right]b=0\ \ \ \ \ \ \ \ \ \ \text{for each
}\beta\in\mathbb{V}\text{ satisfying }\beta<\operatorname*{ord}b.$ (62)

For any $\alpha\in\mathbb{V}$, we have

$\displaystyle\left[t_{\alpha}\right]\left(ab\right)$
$\displaystyle=\sum\limits_{\beta\in\mathbb{V}}\left(\left[t_{\beta}\right]a\right)\cdot\left(\left[t_{\alpha-\beta}\right]b\right)\
\ \ \ \ \ \ \ \ \ \left(\begin{array}[c]{c}\text{by the definition of the
multiplication}\\\ \text{in the group algebra
}\mathbb{L}=\mathbb{K}\left[\mathbb{V}\right]\end{array}\right)$ (65)
$\displaystyle=\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta<\operatorname*{ord}a\end{subarray}}\underbrace{\left(\left[t_{\beta}\right]a\right)}_{\begin{subarray}{c}=0\\\
\text{(by
(\ref{pf.lem.ord.triangle.c.1}))}\end{subarray}}\cdot\left(\left[t_{\alpha-\beta}\right]b\right)+\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta\geqslant\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot\left(\left[t_{\alpha-\beta}\right]b\right)$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \left(\text{since each
}\beta\in\mathbb{V}\text{ satisfies either }\beta<\operatorname*{ord}a\text{
or }\beta\geqslant\operatorname*{ord}a\text{ (but not both)}\right)$
$\displaystyle=\underbrace{\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta<\operatorname*{ord}a\end{subarray}}0\cdot\left(\left[t_{\alpha-\beta}\right]b\right)}_{=0}+\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta\geqslant\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot\left(\left[t_{\alpha-\beta}\right]b\right)$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta\geqslant\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot\left(\left[t_{\alpha-\beta}\right]b\right).$
(66)

Now, let $\alpha\in\mathbb{V}$ be such that
$\alpha<\operatorname*{ord}a+\operatorname*{ord}b$. Then, for every
$\beta\in\mathbb{V}$ satisfying $\beta\geqslant\operatorname*{ord}a$, we have

$\underbrace{\alpha}_{<\operatorname*{ord}a+\operatorname*{ord}b}-\underbrace{\beta}_{\geqslant\operatorname*{ord}a}<\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\operatorname*{ord}a=\operatorname*{ord}b$

and thus

$\left[t_{\alpha-\beta}\right]b=0$ (67)

(by (62), applied to $\alpha-\beta$ instead of $\beta$). Hence, (66) becomes

$\left[t_{\alpha}\right]\left(ab\right)=\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta\geqslant\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot\underbrace{\left(\left[t_{\alpha-\beta}\right]b\right)}_{\begin{subarray}{c}=0\\\
\text{(by
(\ref{pf.lem.ord.triangle.c.4a}))}\end{subarray}}=\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta\geqslant\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot
0=0.$

Forget that we fixed $\alpha$. We thus have proved that

$\left[t_{\alpha}\right]\left(ab\right)=0\ \ \ \ \ \ \ \ \ \ \text{for any
}\alpha\in\mathbb{V}\text{ satisfying
}\alpha<\operatorname*{ord}a+\operatorname*{ord}b.$ (68)

On the other hand, for every $\beta\in\mathbb{V}$ satisfying
$\beta>\operatorname*{ord}a$, we have

$\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\underbrace{\beta}_{>\operatorname*{ord}a}<\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\operatorname*{ord}a=\operatorname*{ord}b$

and thus

$\left[t_{\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\beta}\right]b=0$
(69)

(by (62), applied to
$\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\beta$ instead of
$\beta$). Hence, (66) (applied to
$\alpha=\operatorname*{ord}a+\operatorname*{ord}b$) yields

$\displaystyle\left[t_{\operatorname*{ord}a+\operatorname*{ord}b}\right]\left(ab\right)$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta\geqslant\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot\left(\left[t_{\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\beta}\right]b\right)$
$\displaystyle=\left(\left[t_{\operatorname*{ord}a}\right]a\right)\cdot\underbrace{\left(\left[t_{\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\operatorname*{ord}a}\right]b\right)}_{\begin{subarray}{c}=\left[t_{\operatorname*{ord}b}\right]b\\\
\text{(since
}\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\operatorname*{ord}a=\operatorname*{ord}b\text{)}\end{subarray}}+\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta>\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot\underbrace{\left(\left[t_{\left(\operatorname*{ord}a+\operatorname*{ord}b\right)-\beta}\right]b\right)}_{\begin{subarray}{c}=0\\\
\text{(by (\ref{pf.lem.ord.triangle.c.6a}))}\end{subarray}}$ $\displaystyle\ \
\ \ \ \ \ \ \ \ \left(\text{here, we have split off the addend for
}\beta=\operatorname*{ord}a\text{ from the sum}\right)$
$\displaystyle=\left(\left[t_{\operatorname*{ord}a}\right]a\right)\cdot\left(\left[t_{\operatorname*{ord}b}\right]b\right)+\underbrace{\sum\limits_{\begin{subarray}{c}\beta\in\mathbb{V};\\\
\beta>\operatorname*{ord}a\end{subarray}}\left(\left[t_{\beta}\right]a\right)\cdot
0}_{=0}=\left(\left[t_{\operatorname*{ord}a}\right]a\right)\cdot\left(\left[t_{\operatorname*{ord}b}\right]b\right)\neq
0.$

Thus, $\operatorname*{ord}a+\operatorname*{ord}b$ is a $\beta\in\mathbb{V}$
such that $\left[t_{\beta}\right]\left(ab\right)\neq 0$. In view of (68), we
conclude that $\operatorname*{ord}a+\operatorname*{ord}b$ is the smallest such
$\beta$.

From
$\left[t_{\operatorname*{ord}a+\operatorname*{ord}b}\right]\left(ab\right)\neq
0$, we obtain $ab\neq 0$. Thus, $ab$ is a nonzero element of $\mathbb{L}$.
Hence, $\operatorname*{ord}\left(ab\right)$ is defined as the smallest
$\beta\in\mathbb{V}$ such that $\left[t_{\beta}\right]\left(ab\right)\neq 0$.
But we already know that $\operatorname*{ord}a+\operatorname*{ord}b$ is the
smallest such $\beta$. Comparing these two results, we conclude that
$\operatorname*{ord}\left(ab\right)=\operatorname*{ord}a+\operatorname*{ord}b$.
This proves Lemma 6.4 (c).

(d) Assume the contrary. Thus,
$\operatorname*{ord}\left(a+b\right)<\min\left\\{\operatorname*{ord}a,\operatorname*{ord}b\right\\}\leqslant\operatorname*{ord}a$.
Similarly, $\operatorname*{ord}\left(a+b\right)<\operatorname*{ord}b$.

Recall that $\operatorname*{ord}a$ is defined as the smallest
$\beta\in\mathbb{V}$ such that $\left[t_{\beta}\right]a\neq 0$. Hence, in
particular, no such $\beta$ is smaller than $\operatorname*{ord}a$. In other
words,

$\left[t_{\beta}\right]a=0\ \ \ \ \ \ \ \ \ \ \text{for each
}\beta\in\mathbb{V}\text{ satisfying }\beta<\operatorname*{ord}a.$

Applying this to $\beta=\operatorname*{ord}\left(a+b\right)$, we find
$\left[t_{\operatorname*{ord}\left(a+b\right)}\right]a=0$. Similarly,
$\left[t_{\operatorname*{ord}\left(a+b\right)}\right]b=0$.

But $\operatorname*{ord}\left(a+b\right)$ is defined as the smallest
$\beta\in\mathbb{V}$ such that $\left[t_{\beta}\right]\left(a+b\right)\neq 0$.
Thus, $\operatorname*{ord}\left(a+b\right)$ is a $\beta\in\mathbb{V}$ such
that $\left[t_{\beta}\right]\left(a+b\right)\neq 0$. In other words,
$\operatorname*{ord}\left(a+b\right)\in\mathbb{V}$ and
$\left[t_{\operatorname*{ord}\left(a+b\right)}\right]\left(a+b\right)\neq 0$.
But $\left[t_{\operatorname*{ord}\left(a+b\right)}\right]\left(a+b\right)\neq
0$ contradicts

$\left[t_{\operatorname*{ord}\left(a+b\right)}\right]\left(a+b\right)=\underbrace{\left[t_{\operatorname*{ord}\left(a+b\right)}\right]a}_{=0}+\underbrace{\left[t_{\operatorname*{ord}\left(a+b\right)}\right]b}_{=0}=0+0=0.$

This contradiction shows that our assumption was wrong. This proves Lemma 6.4
(d).

######  Proof 14.2 (Proof of Lemma 6.10.).

First, let us observe that the distance function
$d:E\mathbin{\underline{\times}}E\rightarrow\mathbb{V}$ in Definition 6.9 is
well-defined.

[Proof: We must show that $-\operatorname*{ord}\left(a-b\right)\in\mathbb{V}$
is well-defined for each $\left(a,b\right)\in E\mathbin{\underline{\times}}E$.

So let us fix $\left(a,b\right)\in E\mathbin{\underline{\times}}E$. Thus, $a$
and $b$ are two distinct elements of $E$ (by the definition of
$E\mathbin{\underline{\times}}E$). Since $a$ and $b$ are distinct, we have
$a-b\neq 0$. Hence, the element $a-b$ of $\mathbb{L}$ is nonzero, and
therefore $\operatorname*{ord}\left(a-b\right)\in\mathbb{V}$ is well-defined.
Thus, $-\operatorname*{ord}\left(a-b\right)\in\mathbb{V}$ is well-defined.

Forget that we fixed $\left(a,b\right)$. We thus have showed that
$-\operatorname*{ord}\left(a-b\right)\in\mathbb{V}$ is well-defined for each
$\left(a,b\right)\in E\mathbin{\underline{\times}}E$. This completes our
proof.]

Now, consider the distance function
$d:E\mathbin{\underline{\times}}E\rightarrow\mathbb{V}$ in Definition 6.9. Our
goal is to prove that $\left(E,w,d\right)$ is a $\mathbb{V}$-ultra triple
whenever $w:E\rightarrow\mathbb{V}$ is a function. According to the definition
of a “$\mathbb{V}$-ultra triple”, this boils down to proving the following two
statements:

> Statement 1: We have $d\left(a,b\right)=d\left(b,a\right)$ for any two
> distinct elements $a$ and $b$ of $E$.

> Statement 2: We have
> $d\left(a,b\right)\leqslant\max\left\\{d\left(a,c\right),d\left(b,c\right)\right\\}$
> for any three distinct elements $a$, $b$ and $c$ of $E$.

Let us prove these two statements.

[Proof of Statement 1: Let $a$ and $b$ be two distinct elements of $E$. Thus,
$a-b\neq 0$ (since $a$ and $b$ are distinct), so that $a-b$ is a nonzero
element of $\mathbb{L}$. Hence, Lemma 6.4 (b) (applied to $a-b$ instead of
$a$) yields
$\operatorname*{ord}\left(-\left(a-b\right)\right)=\operatorname*{ord}\left(a-b\right)$.
But the definition of $d$ yields
$d\left(a,b\right)=\operatorname*{ord}\left(a-b\right)$ and
$d\left(b,a\right)=\operatorname*{ord}\left(\underbrace{b-a}_{=-\left(a-b\right)}\right)=\operatorname*{ord}\left(-\left(a-b\right)\right)=\operatorname*{ord}\left(a-b\right)$.
Comparing these two equalities, we find $d\left(a,b\right)=d\left(b,a\right)$.
This proves Statement 1.]

[Proof of Statement 2: Let $a$, $b$ and $c$ be three distinct elements of $E$.
Then, Statement 1 (applied to $c$ instead of $a$) yields
$d\left(c,b\right)=d\left(b,c\right)$.

We have $a-b\neq 0$ (since $a$ and $b$ are distinct), so that $a-b$ is a
nonzero element of $\mathbb{L}$. Likewise, $a-c$ and $c-b$ are nonzero
elements of $\mathbb{L}$. Now, the nonzero elements $a-c$ and $c-b$ of
$\mathbb{L}$ have the property that their sum
$\left(a-c\right)+\left(c-b\right)$ is nonzero (since
$\left(a-c\right)+\left(c-b\right)=a-b$ is nonzero). Thus, Lemma 6.4 (d)
(applied to $a-c$ and $c-b$ instead of $a$ and $b$) yields
$\operatorname*{ord}\left(\left(a-c\right)+\left(c-b\right)\right)\geqslant\min\left\\{\operatorname*{ord}\left(a-c\right),\operatorname*{ord}\left(c-b\right)\right\\}$.
In view of $\left(a-c\right)+\left(c-b\right)=a-b$, this rewrites as

$\operatorname*{ord}\left(a-b\right)\geqslant\min\left\\{\operatorname*{ord}\left(a-c\right),\operatorname*{ord}\left(c-b\right)\right\\}.$

Hence,

$\displaystyle-\underbrace{\operatorname*{ord}\left(a-b\right)}_{\geqslant\min\left\\{\operatorname*{ord}\left(a-c\right),\operatorname*{ord}\left(c-b\right)\right\\}}$
$\displaystyle\leqslant-\min\left\\{\operatorname*{ord}\left(a-c\right),\operatorname*{ord}\left(c-b\right)\right\\}$
$\displaystyle=\max\left\\{-\operatorname*{ord}\left(a-c\right),-\operatorname*{ord}\left(c-b\right)\right\\}.$
(70)

But the definition of $d$ yields

$\displaystyle d\left(a,b\right)$
$\displaystyle=-\operatorname*{ord}\left(a-b\right)\ \ \ \ \ \ \ \ \ \
\text{and}$ $\displaystyle d\left(a,c\right)$
$\displaystyle=-\operatorname*{ord}\left(a-c\right)\ \ \ \ \ \ \ \ \ \
\text{and}\ $ $\displaystyle d\left(c,b\right)$
$\displaystyle=-\operatorname*{ord}\left(c-b\right).$

In view of these equalities, we can rewrite (70) as
$d\left(a,b\right)\leqslant\max\left\\{d\left(a,c\right),d\left(c,b\right)\right\\}$.
In view of $d\left(c,b\right)=d\left(b,c\right)$, this further rewrites as
$d\left(a,b\right)\leqslant\max\left\\{d\left(a,c\right),d\left(b,c\right)\right\\}$.
This proves Statement 2.]

We thus have proved both Statements 1 and 2. Therefore, $\left(E,w,d\right)$
is a $\mathbb{V}$-ultra triple whenever $w:E\rightarrow\mathbb{V}$ is a
function (by the definition of a “$\mathbb{V}$-ultra triple”). This proves
Lemma 6.10.

######  Proof 14.3 (Proof of Lemma 6.13.).

The unity of the $\mathbb{K}$-algebra
$\mathbb{L}_{+}=\mathbb{K}\left[\mathbb{V}_{\geqslant 0}\right]$ is
$1_{\mathbb{L}_{+}}=t_{0}$. Hence, the map $\pi$ sends this unity to
$\pi\left(1_{\mathbb{L}_{+}}\right)=\pi\left(t_{0}\right)=\left[t_{0}\right]t_{0}=1$.
Also, the map $\pi$ is clearly $\mathbb{K}$-linear (since any
$x,y\in\mathbb{L}_{+}$ satisfy
$\left[t_{0}\right]\left(x+y\right)=\left(\left[t_{0}\right]x\right)+\left(\left[t_{0}\right]y\right)$,
and since any $x\in\mathbb{L}_{+}$ and $\lambda\in\mathbb{K}$ satisfy
$\left[t_{0}\right]\left(\lambda x\right)=\lambda\left[t_{0}\right]x$).

Let $x,y\in\mathbb{L}_{+}$. We shall prove that
$\pi\left(xy\right)=\pi\left(x\right)\cdot\pi\left(y\right)$.

We have $x\in\mathbb{L}_{+}=\mathbb{K}\left[\mathbb{V}_{\geqslant 0}\right]$.
In other words, $x$ is a $\mathbb{K}$-linear combination of the family
$\left(t_{\alpha}\right)_{\alpha\in\mathbb{V}_{\geqslant 0}}$. In other words,
we can write $x$ in the form $x=\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}\lambda_{\alpha}t_{\alpha}$ for some family
$\left(\lambda_{\alpha}\right)_{\alpha\in\mathbb{V}_{\geqslant
0}}\in\mathbb{K}^{\mathbb{V}_{\geqslant 0}}$ of coefficients
$\lambda_{\alpha}$ (such that all but finitely many
$\alpha\in\mathbb{V}_{\geqslant 0}$ satisfy $\lambda_{\alpha}=0$). Consider
this family $\left(\lambda_{\alpha}\right)_{\alpha\in\mathbb{V}_{\geqslant
0}}$. From $x=\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}\lambda_{\alpha}t_{\alpha}$, we obtain $\left[t_{0}\right]x=\lambda_{0}$.
Thus, the definition of $\pi$ yields

$\pi\left(x\right)=\left[t_{0}\right]x=\lambda_{0}.$ (71)

We have $y\in\mathbb{L}_{+}=\mathbb{K}\left[\mathbb{V}_{\geqslant 0}\right]$.
In other words, $y$ is a $\mathbb{K}$-linear combination of the family
$\left(t_{\alpha}\right)_{\alpha\in\mathbb{V}_{\geqslant
0}}=\left(t_{\beta}\right)_{\beta\in\mathbb{V}_{\geqslant 0}}$. In other
words, we can write $y$ in the form
$y=\sum\limits_{\beta\in\mathbb{V}_{\geqslant 0}}\mu_{\beta}t_{\beta}$ for
some family $\left(\mu_{\beta}\right)_{\beta\in\mathbb{V}_{\geqslant
0}}\in\mathbb{K}^{\mathbb{V}_{\geqslant 0}}$ of coefficients $\mu_{\beta}$
(such that all but finitely many $\beta\in\mathbb{V}_{\geqslant 0}$ satisfy
$\mu_{\beta}=0$). Consider this family
$\left(\mu_{\beta}\right)_{\beta\in\mathbb{V}_{\geqslant 0}}$. From
$y=\sum\limits_{\beta\in\mathbb{V}_{\geqslant 0}}\mu_{\beta}t_{\beta}$, we
obtain $\left[t_{0}\right]y=\mu_{0}$. Thus, the definition of $\pi$ yields

$\pi\left(y\right)=\left[t_{0}\right]y=\mu_{0}.$ (72)

For any pair $\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant 0}$ satisfying
$\left(\alpha,\beta\right)\neq\left(0,0\right)$, we have

$\left[t_{0}\right]\left(t_{\alpha+\beta}\right)=0$ (73) 272727Proof of (73):
Let $\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant 0}$ be a pair satisfying
$\left(\alpha,\beta\right)\neq\left(0,0\right)$. From
$\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant 0}$, we obtain $\alpha\in\mathbb{V}_{\geqslant
0}$. In other words, $\alpha\geqslant 0$ (by the definition of
$\mathbb{V}_{\geqslant 0}$). Similarly, $\beta\geqslant 0$. At least one of
the two elements $\alpha$ and $\beta$ is $\neq 0$ (since
$\left(\alpha,\beta\right)\neq\left(0,0\right)$). In other words, we have
$\alpha\neq 0$ or $\beta\neq 0$. Since $\alpha$ and $\beta$ play symmetric
roles in our setting, we can WLOG assume that $\alpha\neq 0$ (since otherwise,
we can achieve this by swapping $\alpha$ with $\beta$). Combining $\alpha\neq
0$ with $\alpha\geqslant 0$, we obtain $\alpha>0$. Adding this inequality to
$\beta\geqslant 0$, we obtain $\alpha+\beta>0+0=0$. Hence, $\alpha+\beta\neq
0$, so that $\left[t_{0}\right]\left(t_{\alpha+\beta}\right)=0$. This proves
(73).

.

Now, multiplying the equalities $x=\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}\lambda_{\alpha}t_{\alpha}$ and
$y=\sum\limits_{\beta\in\mathbb{V}_{\geqslant 0}}\mu_{\beta}t_{\beta}$, we
obtain

$\displaystyle xy$
$\displaystyle=\left(\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}\lambda_{\alpha}t_{\alpha}\right)\left(\sum\limits_{\beta\in\mathbb{V}_{\geqslant
0}}\mu_{\beta}t_{\beta}\right)=\underbrace{\sum\limits_{\alpha\in\mathbb{V}_{\geqslant
0}}\sum\limits_{\beta\in\mathbb{V}_{\geqslant
0}}}_{=\sum\limits_{\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant
0}}}\lambda_{\alpha}\mu_{\beta}\underbrace{t_{\alpha}t_{\beta}}_{=t_{\alpha+\beta}}$
$\displaystyle=\sum\limits_{\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant 0}}\lambda_{\alpha}\mu_{\beta}t_{\alpha+\beta}.$

Applying the map $\pi$ to both sides of this equality, we obtain

$\displaystyle\pi\left(xy\right)$
$\displaystyle=\pi\left(\sum\limits_{\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant
0}}\lambda_{\alpha}\mu_{\beta}t_{\alpha+\beta}\right)=\left[t_{0}\right]\left(\sum\limits_{\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant
0}}\lambda_{\alpha}\mu_{\beta}t_{\alpha+\beta}\right)$ $\displaystyle\ \ \ \ \
\ \ \ \ \ \left(\text{by the definition of }\pi\right)$
$\displaystyle=\sum\limits_{\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant
0}}\lambda_{\alpha}\mu_{\beta}\left[t_{0}\right]\left(t_{\alpha+\beta}\right)$
$\displaystyle=\underbrace{\lambda_{0}}_{\begin{subarray}{c}=\pi\left(x\right)\\\
\text{(by
(\ref{pf.lem.piLK.pix=}))}\end{subarray}}\underbrace{\mu_{0}}_{\begin{subarray}{c}=\pi\left(y\right)\\\
\text{(by
(\ref{pf.lem.piLK.piy=}))}\end{subarray}}\underbrace{\left[t_{0}\right]\left(t_{0+0}\right)}_{\begin{subarray}{c}=\left[t_{0}\right]\left(t_{0}\right)\\\
=1\end{subarray}}+\sum\limits_{\begin{subarray}{c}\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant 0};\\\
\left(\alpha,\beta\right)\neq\left(0,0\right)\end{subarray}}\lambda_{\alpha}\mu_{\beta}\underbrace{\left[t_{0}\right]\left(t_{\alpha+\beta}\right)}_{\begin{subarray}{c}=0\\\
\text{(by (\ref{pf.lem.piLK.tt=0}))}\end{subarray}}$ $\displaystyle\ \ \ \ \ \
\ \ \ \ \left(\text{here, we have split off the addend for
}\left(\alpha,\beta\right)=\left(0,0\right)\text{ from the sum}\right)$
$\displaystyle=\pi\left(x\right)\pi\left(y\right)+\underbrace{\sum\limits_{\begin{subarray}{c}\left(\alpha,\beta\right)\in\mathbb{V}_{\geqslant
0}\times\mathbb{V}_{\geqslant 0};\\\
\left(\alpha,\beta\right)\neq\left(0,0\right)\end{subarray}}\lambda_{\alpha}\mu_{\beta}0}_{=0}=\pi\left(x\right)\pi\left(y\right).$

Forget that we fixed $x$ and $y$. We thus have showed that
$\pi\left(xy\right)=\pi\left(x\right)\cdot\pi\left(y\right)$ for all
$x,y\in\mathbb{L}_{+}$. Hence, $\pi$ is a $\mathbb{K}$-algebra homomorphism
(since $\pi$ is $\mathbb{K}$-linear and
$\pi\left(1_{\mathbb{L}_{+}}\right)=1$). This proves Lemma 6.13.

######  Proof 14.4 (Proof of Lemma 6.14.).

Lemma 6.4 (a) shows that $a$ belongs to $\mathbb{L}_{+}$ if and only if its
order $\operatorname*{ord}a$ is nonnegative. Hence, $\operatorname*{ord}a$ is
nonnegative (since $a$ belongs to $\mathbb{L}_{+}$). In other words,
$\operatorname*{ord}a\geqslant 0$.

Recall that $\operatorname*{ord}a$ is defined as the smallest
$\beta\in\mathbb{V}$ such that $\left[t_{\beta}\right]a\neq 0$. Thus,
$\operatorname*{ord}a$ is a $\beta\in\mathbb{V}$ such that
$\left[t_{\beta}\right]a\neq 0$. In other words,
$\operatorname*{ord}a\in\mathbb{V}$ and
$\left[t_{\operatorname*{ord}a}\right]a\neq 0$.

We shall first prove the implication

$\left(\operatorname*{ord}a=0\right)\ \Longrightarrow\
\left(\pi\left(a\right)\neq 0\right).$ (74)

[Proof of (74): Assume that $\operatorname*{ord}a=0$. Then,
$0=\operatorname*{ord}a$, so that
$\left[t_{0}\right]a=\left[t_{\operatorname*{ord}a}\right]a\neq 0$. But the
definition of $\pi$ yields $\pi\left(a\right)=\left[t_{0}\right]a\neq 0$.
Thus, the implication (74) is proved.]

Next, let us prove the implication

$\left(\pi\left(a\right)\neq 0\right)\ \Longrightarrow\
\left(\operatorname*{ord}a=0\right).$ (75)

[Proof of (75): Assume that $\pi\left(a\right)\neq 0$. But the definition of
$\pi$ yields $\pi\left(a\right)=\left[t_{0}\right]a$. Hence,
$\left[t_{0}\right]a=\pi\left(a\right)\neq 0$.

Now, recall that $\operatorname*{ord}a$ is the smallest $\beta\in\mathbb{V}$
such that $\left[t_{\beta}\right]a\neq 0$. Hence, if $\beta\in\mathbb{V}$
satisfies $\left[t_{\beta}\right]a\neq 0$, then
$\beta\geqslant\operatorname*{ord}a$. Applying this to $\beta=0$, we obtain
$0\geqslant\operatorname*{ord}a$ (since $\left[t_{0}\right]a\neq 0$).
Combining this with $\operatorname*{ord}a\geqslant 0$, we find
$\operatorname*{ord}a=0$. This proves the implication (75).]

Combining the two implications (75) and (74), we obtain the logical
equivalence $\left(\pi\left(a\right)\neq 0\right)\ \Longleftrightarrow\
\left(\operatorname*{ord}a=0\right)$. In other words, $\pi\left(a\right)\neq
0$ holds if and only if $\operatorname*{ord}a=0$. This proves Lemma 6.14.

## References

  * [BjoZie92] Anders Björner, Günter M. Ziegler, Introduction to Greedoids, Chapter 8 in: Neil White (ed.), Matroid Applications, Cambridge University Press 1992.
https://doi.org/10.1017/CBO9780511662041

  * [BrySha99] Victor Bryant, Ian Sharpe, Gaussian, Strong and Transversal Greedoids, European Journal of Combinatorics 20, Issue 4, May 1999, pp. 259–262. https://doi.org/10.1006/eujc.1998.0287
  * [Eisenb95] David Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate texts in mathematics #150, Springer, 1995.
https://doi.org/10.1007/978-1-4612-5350-1

  * [FadSom72] D. Faddeev, I. Sominsky, Problems in Higher Algebra, Mir 1972.
  * [Grinbe11] Darij Grinberg, A hyperfactorial divisibility, brief version.
http://www.cip.ifi.lmu.de/~grinberg/hyperfactorialBRIEF.pdf

  * [Grinbe15] Darij Grinberg, Notes on the combinatorial fundamentals of algebra, 25 May 2021, arXiv:2008.09862v2. See also http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf for a version that gets updated.
  * [GriPet19] Darij Grinberg, Fedor Petrov, A greedoid and a matroid inspired by Bhargava’s $p$-orderings, arXiv:1909.01965v4, accepted at the Electronic Journal of Combinatorics.
  * [GriPet20] Darij Grinberg, Fedor Petrov, The Bhargava greedoid, extended abstract submitted to FPSAC 2020.
http://www.cip.ifi.lmu.de/~grinberg/algebra/fps20gfv.pdf

  * [Knapp18] Christopher N. Knapp, The complexity of greedoid Tutte polynomials, PhD thesis at Brunel University London, 2018\.
https://bura.brunel.ac.uk/bitstream/2438/15891/1/FulltextThesis.pdf

  * [KoLoSc91] Bernhard Korte, László Lovász, Rainer Schrader, Greedoids, Algorithms and Combinatorics #4, Springer 1991\.
https://doi.org/10.1007/978-3-642-58191-5

  * [Kratte99] Christian Krattenthaler, Advanced Determinant Calculus, Séminaire Lotharingien Combin. 42 (1999) (The Andrews Festschrift), paper B42q, 67 pp., arXiv:math/9902004v3.
  * [Lemin03] Alex J. Lemin, The category of ultrametric spaces is isomorphic to the category of complete, atomic, tree-like, and real graduated lattices LAT*, Algebra univers. 50 (2003), pp. 35–49.
https://doi.org/10.1007/s00012-003-1806-4

  * [Lovasz80] L. Lovász, Matroid matching and some applications, Journal of Combinatorial Theory, Series B 28, Issue 2, April 1980, pp. 208–236.
https://doi.org/10.1016/0095-8956(80)90066-0

  * [MoSeSt06] Vincent Moulton, Charles Semple, Mike Steel, Optimizing phylogenetic diversity under constraints, Journal of Theoretical Biology 246 (2007), pp. 186–194. https://doi.org/10.1016/j.jtbi.2006.12.021
  * [Muir60] Thomas Muir, William H. Metzler, A Treatise on the Theory of Determinants, Dover 1960.
  * [Oxley11] James Oxley, Matroid theory, Oxford Graduate Texts in Mathematics #21, 2nd edition, Oxford University Press 2011\.
https://doi.org/10.1093/acprof:oso/9780198566946.001.0001
See https://www.math.lsu.edu/~oxley/ for errata.

  * [PetDov14] Evgenii A. Petrov, Aleksei A. Dovgoshey, On the Gomory–Hu Inequality, Journal of Mathematical Sciences 198 (April 2014), Issue 4, pp. 392–411.
https://doi.org/10.1007/s10958-014-1798-y