# Comptes Rendus
Mathématique

Nicolau Saldanha, Boris Shapiro and Michael Shapiro

Finiteness of rank for Grassmann convexity

Volume 361 (2023), p. 445-451

Published online: 1 February 2023

https://doi.org/10.5802/crmath.343

<figure><img src="image_1.png" /></figure>

This article is licensed under the
CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.
http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_2.png" /></figure>
Combinatorics / Combinatoire

Finiteness of rank for Grassmann convexity

*Finitude de rang pour la connexité du Grassmannien*

Nicolau Saldanha*, a, Boris Shapiro b and Michael Shapiro c, d

<sup>a</sup> Departamento de Matemática, PUC-Rio, R. Mq. de S. Vicente 225, Rio de Janeiro, RJ 22451-900, Brazil

<sup>b</sup> Department of Mathematics, Stockholm University, SE-106 91, Stockholm, Sweden

<sup>c</sup> Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA

<sup>d</sup> National Research University Higher School of Economics, Moscow, Russia

*E-mails*: saldanha@puc-rio.br (N. Saldanha), shapiro@math.su.se (B. Shapiro), mshapiro@msu.edu (M. Shapiro)

**Abstract.** The Grassmann convexity conjecture, formulated in [8], gives a conjectural formula for the maximal total number of real zeroes of the consecutive Wronskians of an arbitrary fundamental solution to a dis-conjugate linear ordinary differential equation with real time. The conjecture can be reformulated in terms of convex curves in the nilpotent lower triangular group. The formula has already been shown to be a correct lower bound and to give a correct upper bound in several small dimensional cases. In this paper we obtain a general explicit upper bound.

**Résumé.** La conjecture sur la convexité du Grassmannien formulée dans [8] suggère une formule pour le nombre total maximal de zéros réels des Wronskiens consécutifs d'une solution fondamentale arbitraire d'un système disconjugué d'équations différentielles ordinaires linéaires à temps réel. La conjecture peut être formulée en termes de courbes convexes dans le groupe nilpotent triangulaire inférieur. Il a déjà été prouvé que la formule donne une borne inférieure correcte et que dans plusieurs cas de basse dimension, elle donne la borne supérieure correcte. Dans cet article nous obtenons une borne supérieure explicite générale.

**2020 Mathematics Subject Classification.** 34C10, 05B30, 57N80.

**Funding.** The first author is supported by CNPq, Capes and Faperj (Brazil). The third author is partially supported by International Laboratory of Cluster Geometry NRU HSE, RF Government grant, ag. N° 075-15-2021-608 dated 08.06.2021 and the NSF grant DMS 2100791.

*Manuscript received 15 October 2021, revised and accepted 31 January 2022.*

<footnote>* Corresponding author.</footnote>
# 1. Introduction

A linear homogeneous differential equation of order $n$ with real time has the form

$$y^{(n)}(t) + \cdots + c_k(t)y^{(k)}(t) + \cdots + c_0(t)y(t) = 0; \quad (1)$$

the real functions $c_k: I \to \mathbb{R}$ (for $0 \le k < n$) are called coefficients and are assumed to be continuous; the set $I \subseteq \mathbb{R}$ is assumed to be an interval. Such an equation defined on an open interval $I$ is called disconjugate on $I$ (see [2, 6]) if any of its nonzero solutions has at most $n-1$ real zeroes on $I$, counting multiplicities. Any differential equation as above is disconjugate on a sufficiently small interval $I \subset \mathbb{R}$.

The Grassmann convexity conjecture, formulated in [8], says that, for any positive integer $k$ satisfying $0 < k < n$, the number of real zeroes of the Wronskian of any $k$ linearly independent solutions to a disconjugate differential equation of order $n$ on $I$ is bounded from above by $k(n-k)$, which is the dimension of the Grassmannian $G(k, n; \mathbb{R})$. This conjecture can be reformulated in terms of convex curves in the nilpotent lower triangular group (see Section 2 and also [3-5]). The number $k(n-k)$ has already been shown to be a correct lower bound for all $k$ and $n$. Moreover it gives a correct upper bound for the case $k=2$ (see [7]). In this paper we obtain a general explicit upper bound for the above maximal total number of real zeroes which, although weaker than the one provided by the Grassmann convexity conjecture, still gives an interesting information.

We now formulate a discrete problem which is equivalent to the above Grassmann convexity conjecture; the equivalence is discussed in Section 2. The statement and proof of our main theorem are self-contained and elementary.

Given integers $k$ and $n$ with $0 < k < n$, consider a collection $(v_j)_{1 \le j \le n}$ of vectors in $\mathbb{R}^k$, or, equivalently, a matrix $M \in \mathcal{C} = \mathbb{R}^{k \times n}$. Set $v_j = Me_j$, so that $v_j$ is the $j$th column of $M$:

$$M = \begin{pmatrix} | & | & | \\ v_1 & \cdots & v_j & \cdots & v_n \\ | & | & | \\ | & | & | \\ | & | & | \end{pmatrix}, \quad v_1, \dots, v_j, \dots, v_n \in \mathbb{R}^k.$$

For two matrices $M_0, M_1 \in \mathcal{C}$, we say that there exists a positive elementary move from $M_0$ to $M_1$ if there exists $j < n$ and $t \in (0, +\infty)$ such that $M_1 e_j = M_0 e_j + t M_0 e_{j+1}$ and $M_1 e_{j'} = M_0 e_{j'}$ for $j' \ne j$. In other words, the vector $v_j$ moves towards $v_{j+1}$ and the other vectors remain constant:

$$M_0 = \begin{pmatrix} | & | & | & | \\ v_1 & \cdots & v_j & v_{j+1} & \cdots & v_n \\ | & | & | & | & | \\ | & | & | & | & | \\ | & | & | & | & | \\ | & | & | & | & | \end{pmatrix}, \quad M_1 = \begin{pmatrix} | & | & | & | \\ v_1 & \cdots & v_j + t v_{j+1} & v_{j+1} & \cdots & v_n \\ | & | & | & | & | \\ | & | & | & | & | \\ | & | & | & | & | \\ | & | & | & | & | \end{pmatrix}, \quad t > 0.$$

We call a sequence $(M_s)_{0 \le s \le \ell}$ of $k \times n$-matrices convex if, for all $s < \ell$, there exists a positive elementary move from $M_s$ to $M_{s+1}$. The terminology is motivated by their relationship with convex curves in the lower triangular group $Lo_n^1$; see Section 2 and [7].

For $J = \{j_1 < \cdots < j_k\} \subset \{1, \dots, n\}$, define the function $m_J: \mathcal{C} \to \mathbb{R}$ by

$$m_J(M) = \det(\text{SubMatrix}(M, \{1, \dots, k\}, J)) = \det(v_{j_1}, \dots, v_{j_k}). \quad (2)$$

We are particularly interested in $m_\bullet = m_{\{1, \dots, k\}}$. Define an open dense subset of $(k \times n)$-matrices

$$\mathcal{C}^* = \bigcap_{J \subset \{1, \dots, k\}, |J| = k} m_J^{-1}[\mathbb{R} \setminus \{0\}] \subset \mathcal{C}.$$

For convex sequences $M = (M_s)_{0 \le s \le \ell}$ of matrices in $\mathcal{C}^*$, we are interested in the number of sign changes of $m_\bullet$:

$$\text{nsc}(M) = |\{s \in [0, \ell) \cap \mathbb{Z} \mid m_\bullet(M_s) m_\bullet(M_{s+1}) < 0\}|.$$

(Notice that $M$ is merely a sequence of matrices, not an actual path of matrices; equivalently, $s$ assumes integer values only.)
The Grassmann convexity conjecture, in the discrete model, states that for every convex sequence **M** we have:

$$ nsc(\mathbf{M}) \leq k(n-k). \qquad (3) $$

The equivalence between formulations is discussed in Section 2. The case $k=1$ is easy; the case $k=2$ is settled in [7]; in the same paper we prove that for all $k$ and $n$, there exists a convex sequence **M** with $nsc(\mathbf{M}) = k(n-k)$. In this paper we prove the following estimate.

**Theorem 1.** For any $2 < k < n$ and any convex sequence of matrices **M**, we have

$$ nsc(\mathbf{M}) < \frac{(n-k+1)^{2k-3}}{2^{k-3}}. \qquad (4) $$

Inequality (4) appears to be the first known explicit upper bound for nsc(**M**) in terms of $k$ and $n$. This bound is a polynomial in $n$ of degree $2k-3$. Furthermore, by a well-known (Grassmann) duality interchanging $k \leftrightarrow (n-k)$, one can additionally obtain

$$ nsc(\mathbf{M}) < \min(2^{3-k}(n-k+1)^{2k-3}, 2^{3-n+k}(k+1)^{2(n-k)-3}). $$

We know however that the bound in Theorem 1 is not sharp; see Remark 5. Our current best guess is that the Grassmann convexity conjecture indeed holds for all $0 < k < n$; this is additionally supported by our recent computer-aided verification of the latter conjecture in case $k=3, n=6$.

## 2. Discrete and continuous versions

In this section we present an alternative continuous version of the Grassmann convexity conjecture already discussed in previous papers and prove that it is equivalent to the discrete version described in the introduction. We follow the notations of [5] and [7].

Consider the nilpotent Lie group of $Lo_n^1$ of real lower triangular matrices with diagonal entries equal to 1. Its corresponding Lie algebra is $lo_n^1$, the space of strictly lower triangular matrices. For $J \subset \{1, \dots, n\}$, $|J| = k$, define $m_J : Lo_n^1 \to \mathbb{R}$ as in Equation (2); thus, $m_\bullet(L) = m_{\{1, \dots, k\}}(L)$ is the determinant of the lower-left $k \times k$ minor of $L$. For $1 \le j < n$, let $l_j = e_{j+1}e_j^\top \in lo_n^1$ be the matrix with only one nonzero entry $(l_j)_{j+1,j} = 1$. Write $\lambda_j(t) = \exp(tl_j)$.

A smooth curve $\Gamma : [a, b] \to Lo_n^1$ is convex if there exist smooth positive functions $\beta_j : [a, b] \to (0, +\infty)$ such that, for all $t \in [a, b]$,

$$ (\Gamma(t))^{-1} \Gamma'(t) = \sum_j \beta_j(t) l_j. $$

We prove in [5] that all zeroes of $m_\bullet \circ \Gamma : [a, b] \to \mathbb{R}$ are isolated (and of finite multiplicity). Let $nz(\Gamma)$ be the number of zeroes of $m_\bullet \circ \Gamma$ counted without multiplicity. The Grassmann convexity conjecture states that $nz(\Gamma) \le k(n-k)$ for all convex $\Gamma$. (In fact, following the ideas presented in [7, the proof of Theorem 2], one can show that the maximal numbers of zeroes of $m_\bullet \circ \Gamma$ counted with and without multiplicity actually coincide.)

Let $S_n$ be the symmetric group with the standard generators $a_j = (j, j+1)$, $1 \le j < n$. Let $\eta \in S_n$ be the permutation with the longest reduced word; its length equals $n(n-1)/2$. Using the notation of [5], we define for each permutation $\sigma \in S_n$, a subset $\text{Pos}_\sigma \subset Lo_n^1$ whose dimension equals the length of $\sigma$ as follows. Let $\sigma = a_{i_1} \cdots a_{i_l}$ be a reduced word: if $L \in \text{Pos}_\sigma$ then there exist unique positive $t_1, \dots, t_l$ such that $L = \lambda_{i_1}(t_1) \cdots \lambda_{i_l}(t_l)$. Conversely, if $t_1, \dots, t_l > 0$ then $\lambda_{i_1}(t_1) \cdots \lambda_{i_l}(t_l) \in \text{Pos}_\sigma$. The set $\text{Pos}_\eta \subset Lo_n^1$ is the semigroup of totally positive matrices, an open subset (see [1]). The boundary of $\text{Pos}_\eta$ is stratified as

$$ \partial \text{Pos}_\eta = \bigsqcup_{\sigma \in S_n, \sigma \neq \eta} \text{Pos}_\sigma $$

(the subsets $\text{Pos}_\sigma \subset Lo_n^1$ and the above stratification are discussed in [5, Section 5]).
If $\Gamma$ is convex and $t_0 < t_1$ then $(\Gamma(t_0))^{-1}\Gamma(t_1) \in \mathrm{Pos}_{\eta}$. Conversely, if $L_0^{-1}L_1 \in \mathrm{Pos}_{\eta}$ then there exists a convex curve $\Gamma: [0, 1] \to \mathrm{Lo}_n^1$ with $\Gamma(0) = L_0$ and $\Gamma(1) = L_1$ (see [5, Lemma 5.7]).

**Lemma 2.** Fix $k, n, r \in \mathbb{N}$, with $0 < k < n$. If $\mathrm{nsc}(\mathbf{M}) \le r$ for every convex sequence $\mathbf{M} = (M_s)_{0 \le s \le l}$, then $\mathrm{nz}(\Gamma) \le r$ for every convex curve $\Gamma$. Conversely, if $\mathrm{nz}(\Gamma) \le r$ for every convex curve $\Gamma$ then $\mathrm{nsc}(\mathbf{M}) \le r$ for every convex sequence $\mathbf{M} = (M_s)_{0 \le s \le l}$.

**Proof.** Consider a convex curve $\Gamma_0$ with $\mathrm{nz}(\Gamma_0) = r$. We use $\Gamma_0$ to construct a convex sequence $\mathbf{M}$ with $\mathrm{nsc}(\mathbf{M}) \ge r$. Indeed, let $t_1 < \dots < t_r$ be such that $m_\bullet(\Gamma(t_s)) = 0$ for all $1 \le s \le r$. Take $\tilde{M}_s = \mathrm{SubMatrix}(\Gamma(t_s), \{n-k+1, \dots, n\}, \{1, \dots, n\})$ and corresponding vectors $\tilde{v}_{s,j}$:

$$ \Gamma(t_s) = \begin{pmatrix} * \\ \tilde{M}_s \end{pmatrix}, \quad \tilde{M}_s = \begin{pmatrix} | \\ \tilde{v}_{s,1} \\ \vdots \\ \tilde{v}_{s,j} \\ | \\ \vdots \\ \tilde{v}_{s,n} \\ | \end{pmatrix}. $$

By taking a small perturbation we may assume that $m_J(\tilde{M}_s) \ne 0$ for $|J| = k$, $J \ne \{1, \dots, k\}$. For $\tilde{n} = n(n-1)/2$ and a small positive number $\epsilon > 0$, set $M_{(\tilde{n}+1)s} := \tilde{M}_s\lambda_k(-\epsilon)$, $M_{(\tilde{n}+1)s+1} := \tilde{M}_s\lambda_k(\epsilon)$. Notice that there exists a positive elementary move from $M_{(\tilde{n}+1)s}$ to $M_{(\tilde{n}+1)s+1}$ and that $\mathrm{sign}(m_\bullet(M_{(\tilde{n}+1)s+1})) \ne \mathrm{sign}(m_\bullet(M_{(\tilde{n}+1)s}))$. If the above perturbation and $\epsilon > 0$ are sufficiently small, there exists $L_s \in \mathrm{Pos}_{\eta}$ such that $M_{(\tilde{n}+1)(s+1)} = M_{(\tilde{n}+1)s+1}L_s$. Write $L_s = \lambda_{i_1}(t_1) \cdots \lambda_{i_{\tilde{n}}}(t_{\tilde{n}})$ and, for $1 \le j \le \tilde{n}$, recursively define $M_{(\tilde{n}+1)s+j} = M_{(\tilde{n}+1)s+j}\lambda_{ij}(t_j)$. This is the desired convex sequence of matrices.

Conversely, let $\mathbf{M} = (M_s)_{1 \le s \le l}$ be a convex sequence of matrices with $\mathrm{nsc}(\mathbf{M}) = r$. We use $\mathbf{M}$ to construct a smooth convex curve $\Gamma$ with $\mathrm{nz}(\Gamma) \ge r$. For each $s$, we have $M_{s+1} = M_s\lambda_{is}(t_s)$, $t_s > 0$. Notice that $\lambda_{is}(t_s) \in \mathrm{Pos}_{a_{is}}$. If needed slightly perturb the matrices $(M_s)$ to obtain matrices $(\tilde{M}_s)$ such that $\tilde{M}_{s+1} = \tilde{M}_sL_s$, $L_s \in \mathrm{Pos}_{\eta}$. Define $\Gamma(1) \in \mathrm{Lo}_n^1$ such that $\tilde{M}_1 = \mathrm{SubMatrix}(\Gamma(1), \{n-k+1, \dots, n\}, \{1, \dots, n\})$. Recursively define $\Gamma(s+1) = \Gamma(s)L_s$ so that for all $s \in \mathbb{Z}$, $1 \le s \le l$, we have $\tilde{M}_s = \mathrm{SubMatrix}(\Gamma(s), \{n-k+1, \dots, n\}, \{1, \dots, n\})$. Notice that for each $s$, there exists a smooth convex arc from $\Gamma(s)$ to $\Gamma(s+1)$. As discussed in [4, Section 6], these arcs can be chosen in such a way that $\Gamma$ becomes smooth at all the integer glueing points as well. $\square$

### 3. Ranks

For $0 < k < n$, define $r(k, n) \in \mathbb{N} \cup \{\infty\} = \{0, 1, 2, \dots, \infty\}$ as

$$ r(k, n) = \sup_{\mathbf{M}} \mathrm{nsc}(\mathbf{M}); $$

where $\mathbf{M}$ runs over all convex sequences of matrices. By the main results of [7], $r(2, n) = 2(n-2)$; and, additionally for all $0 < k < n$, we have $r(k, n) \ge k(n-k)$. Moreover the examples for which $\mathrm{nsc}(\mathbf{M}) = k(n-k)$ provided by [7] imply that the Grassmann convexity conjecture (as in Equation (3)) is equivalent to

$$ r(k, n) = k(n-k). \qquad (5) $$

Given a subset of $k \times n$-matrices $X \subseteq \mathcal{C}^*$, a *prerank function* for $X$ is a function

$$ \mathrm{pr}: X \to \mathbb{N} = \{0, 1, 2, \dots\} $$

with the properties:

(1) if there exists a positive elementary move from $M_0 \in X$ to $M_1 \in X$ then $\mathrm{pr}(M_0) \ge \mathrm{pr}(M_1)$;

(2) if there exists a positive elementary move from $M_0 \in X$ to $M_1 \in X$ and $m_\bullet(M_0)m_\bullet(M_1) < 0$ then $\mathrm{pr}(M_0) > \mathrm{pr}(M_1)$.

When $X$ is not mentioned we assume that $X = \mathcal{C}^*$. A *prerank function* for a convex sequence $\mathbf{M}$ is, by definition, a *prerank function* for its image. A *prerank function* pr for $\mathcal{C}^*$ is called *regular* if $\mathrm{pr}(\mathrm{MD}) = \mathrm{pr}(\mathbf{M})$ for every $\mathbf{M} \in \mathcal{C}^*$ and every positive diagonal matrix $D \in \mathbb{R}^{n \times n}$; in terms of
sequences of vectors, this means that multiplication of each vector $v_j$ by a positive real number $d_j$ does not affect the rank. For $k=2$, a regular prerank function $\text{pr}: \mathscr{C}^* \to [0,2(n-2)] \cap \mathbb{N}$ has been constructed in [7]. In the next section, particularly in the proof of Lemma 4, we construct some prerank functions different from the actual rank function which is currently unknown. Thus, prerank functions serve as a tool to prove upper bounds for the actual rank.

**Lemma 3.** For $0 < k < n$, the following properties are equivalent:

(1) $r(k, n) \le r_0$;

(2) there exists a regular prerank function for $\mathscr{C}^*$ whose image is contained in $[0, r_0]$;

(3) there exists a prerank function for $\mathscr{C}^*$ whose image is contained in $[0, r_0]$;

(4) for every convex sequence $\mathbf{M}$ of matrices, there exists a prerank function for $\mathbf{M}$ whose image is contained in $[0, r_0]$.

**Proof.** Assuming the first item, let us construct a regular prerank function. For $M \in \mathscr{C}^*$, set

$$ \text{pr}(M) = \max_{\mathbf{M}=(M_s)_{0 \le s \le l}, M_0=M} \text{nsc}(\mathbf{M}). $$

Regularity follows from the observation that if $D \in \mathbb{R}^{n \times n}$ is a positive diagonal matrix and $(M_s)$ is a convex sequence then so is $(M_s D)$. The second item trivially implies the third. Assuming the third item, we obtain a prerank function for $\mathscr{C}^*$. To prove the fourth item, given a convex sequence, restrict the above prerank function to the image of $\mathbf{M}$ to obtain a prerank function for $\mathbf{M}$.

Given a convex sequence $\mathbf{M} = (M_s)_{0 \le s \le l}$ and a prerank function $\text{pr}$ for $\mathbf{M}$, we obtain that $\text{nsc}(\mathbf{M}) \le \text{pr}(M_0) - \text{pr}(M_l)$. Thus, the fourth item implies the first, completing the proof. $\square$

**4. Step lemma**

The following lemma provides the induction step necessary to settle Theorem 1.

**Lemma 4.** For all $2 < k < n$, we have that

$$ r(k, n) \le \frac{(n-k+1)^2}{2} r(k-1, n-1). $$

**Proof of Theorem 1.** In order to use induction on $k$, notice first that the inequality (4) holds for $k=2$. By inductive assumption and Lemma 4, we get

$$ \begin{aligned} \text{nsc}(\mathbf{M}) &\le r(k, n) \le \frac{(n-k+1)^2}{2} r(k-1, n-1) < \\ &< \frac{(n-k+1)^2}{2} 2^{3-(k-1)} (n-k+1)^{2(k-1)-3} = 2^{3-k} (n-k+1)^{2k-3}, \end{aligned} $$

completing the proof. $\square$

**Proof of Lemma 4.** Set $r_-= r(k-1, n-1)$ (assumed to be finite) and define $r_0 := (n-k+1)^2 r_- / 2$. Let $\mathscr{C}_-^* \subset \mathscr{C}_- = \mathbb{R}^{(k-1) \times (n-1)}$ be the set of matrices $M \in \mathscr{C}_-$ with $m_J(M) \ne 0$ for all $J \subset \{1, \dots, n-1\}$, $|J| = k-1$. By Lemma 3, there exists a regular prerank function $\text{pr}_- : \mathscr{C}_- \to [0, r_-] \cap \mathbb{N}$. Given a convex sequence $\mathbf{M} = (M_s)_{0 \le s \le l}$ of matrices in $\mathscr{C}^* \subset \mathscr{C} = \mathbb{R}^{k \times n}$, we construct a prerank function for $\mathbf{M}$ with image contained in $[0, r_0]$ by Lemma 3 this will complete the proof of Lemma 4.

Define $v_{s,j} = M_s e_j$. Let $H_0 \subset \mathbb{R}^k$ be a generic linear hyperplane, defined by a linear form $\omega : \mathbb{R}^k \to \mathbb{R}$; fix a basis of $H_0$ in order to identify it with $\mathbb{R}^{k-1}$. Let $H_1 = \omega^{-1}(\{1\})$ be an affine hyperplane parallel to $H_0$. We may assume that for all $s$ and $j$, we have $\omega(v_{s,j}) \ne 0$. Furthermore, we may assume that $\omega(v_{0,j}) > 0$ for $j > n-k$, which implies $\omega(v_{s,j}) > 0$ for $j > n-k$ and all $s$. Set
$\tilde{v}_{s,j} = v_{s,j}/\omega(v_{s,j})$ so that $\tilde{v}_{s,j} \in H_1$. For $j < n$, set $w_{s,j} = \omega(v_{s,j+1})(\tilde{v}_{s,j+1} - \tilde{v}_{s,j}) \in H_0$. For a given $s$, the sequence of vectors $(w_{s,j})_{1 \le j \le n-1}$ defines a matrix $\tilde{M}_s \in \mathscr{C}_- = \mathbb{R}^{(k-1) \times (n-1)}$:

$$ \tilde{M}_s = \left( \begin{array}{c|c|c} | & & | \\ w_{s,1} & \cdots & w_{s,j} \cdots w_{s,n-1} \\ | & & | \\ | & & | \end{array} \right). $$

(The normalized vectors $\tilde{v}_{s,j}$, the vectors $w_{s,j}$ and the matrix $\tilde{M}_s$ will be the main ingredients in the current proof.) We assume that $m_\bullet(M_s) \neq 0$, which implies $m_\bullet(\tilde{M}_s) \neq 0$.

Define the prerank as $\mathrm{pr}(M_s) = \mathrm{pr}_I(M_s) + \mathrm{pr}_{II}(M_s) \cdot r_-$, where

$$ \mathrm{pr}_I(M_s) = \mathrm{pr}_-(\tilde{M}_s), \quad \mathrm{pr}_{II}(M_s) = \sum_{1 \le j < n} [\omega(v_{s,j})\omega(v_{s,j+1}) < 0] \cdot j. $$

Here we use Iverson notation, i.e., $[\omega(v_{s,j})\omega(v_{s,j+1}) < 0]$ equals 1 if $\omega(v_{s,j})\omega(v_{s,j+1}) < 0$ and 0 otherwise. In particular, if $j > n-k$ then $[\omega(v_{s,j})\omega(v_{s,j+1}) < 0] = 0$. We therefore have

$$ \mathrm{pr}_I(M_s) \in [0, r_-] \cap \mathbb{Z}, \quad \mathrm{pr}_{II}(M_s) \in [0, \frac{(n-k+1)(n-k)}{2}] \cap \mathbb{Z}, $$

and thus

$$ \mathrm{pr}(M_s) \in [0, r_0] \cap \mathbb{Z}. $$

Next we need to verify that $\mathrm{pr}(M_s)$ is a prerank function. Indeed, recall that there exists a positive elementary move from $M_s$ to $M_{s+1}$, which we call the $s^{\mathrm{th}}$ move in $\mathbf{M}$. There are two kinds of positive elementary moves. Namely, if $\mathrm{sign}(\omega(v_{s,j})) = \mathrm{sign}(\omega(v_{s+1,j}))$ for all $j$ then we say the $s^{\mathrm{th}}$ move is of type I; otherwise it is of type II.

First consider $s$ of type II. Let $j$ be such that $v_{s+1,j} = v_{s,j} + tv_{s,j+1}$, $t > 0$. By taking $H$ in general position and introducing, if necessary, intermediate points we may assume that $\mathrm{sign}(m_\bullet(M_s)) = \mathrm{sign}(m_\bullet(M_{s+1}))$. For $j' \neq j$, we have $v_{s+1,j'} = v_{s,j'}$ implying that $\mathrm{sign}(\omega(v_{s+1,j'})) = \mathrm{sign}(\omega(v_{s,j'}))$. Therefore we have

$$ \mathrm{sign}(\omega(v_{s+1,j})) = \mathrm{sign}(\omega(v_{s+1,j+1})) = \mathrm{sign}(\omega(v_{s,j+1})) = -\mathrm{sign}(\omega(v_{s,j})) $$

and thus (again using Iverson notation)

$$ [\omega(v_{s,j})\omega(v_{s,j+1}) < 0] = 1, \quad [\omega(v_{s+1,j})\omega(v_{s+1,j+1}) < 0] = 0. $$

For $j' = j - 1$, we get

$$ [\omega(v_{s,j'})\omega(v_{s,j'+1}) < 0] = 1 - [\omega(v_{s+1,j'})\omega(v_{s+1,j'+1}) < 0]; $$

while for $j' \notin \{j-1, j\}$, we get

$$ [\omega(v_{s,j'})\omega(v_{s,j'+1}) < 0] = [\omega(v_{s+1,j'})\omega(v_{s+1,j'+1}) < 0]. $$

Thus, in all cases we obtain that $\mathrm{pr}_{II}(M_{s+1}) < \mathrm{pr}_{II}(M_s)$ which implies that $\mathrm{pr}(M_{s+1}) \le \mathrm{pr}(M_s)$ independently of the values of $\mathrm{pr}_I(M_s)$ and $\mathrm{pr}_I(M_{s+1})$.

Consider now $s$ of type I so that $\mathrm{pr}_{II}(M_s) = \mathrm{pr}_{II}(M_{s+1})$. Again, let $j$ be such that $v_{s+1,j} = v_{s,j} + tv_{s,j+1}$, $t > 0$. For $j' \neq j$, we obtain $v_{s+1,j'} = v_{s,j'}$ and therefore $\tilde{v}_{s+1,j'} = \tilde{v}_{s,j'}$. Thus

$$ \tilde{v}_{s+1,j} = \frac{\omega(v_{s,j})}{\omega(v_{s+1,j})} \tilde{v}_{s,j} + \frac{t\omega(v_{s,j+1})}{\omega(v_{s+1,j})} \tilde{v}_{s,j+1}, \quad \frac{\omega(v_{s,j})}{\omega(v_{s+1,j})} > 0; $$

implying that $\tilde{v}_{s+1,j}$ is an affine combination of $\tilde{v}_{s,j}$ and $\tilde{v}_{s,j+1}$. For $j' \notin \{j-1, j\}$, we obtain $w_{s+1,j'} = w_{s,j'}$. Finally, notice that $w_{s+1,j}$ is a positive multiple of $w_{s,j}$ and $w_{s+1,j-1}$ is a positive linear combination of $w_{s,j-1}$ and $w_{s,j}$. More exactly,

$$ w_{s+1,j} = \frac{\omega(v_{s,j})}{\omega(v_{s+1,j})} w_{s,j}, \quad w_{s+1,j-1} = \frac{\omega(v_{s+1,j})}{\omega(v_{s,j})} w_{s,j-1} + t w_{s,j}. $$
Therefore, up to multiplication by a positive diagonal matrix, the move from $\tilde{M}_s$ to $\tilde{M}_{s+1}$ is a positive elementary move. Thus $\mathrm{pr}_-(\tilde{M}_{s+1}) \le \mathrm{pr}_-(\tilde{M}_s)$, or, equivalently, $\mathrm{pr}_I(M_{s+1}) \le \mathrm{pr}_I(M_s)$. Finally, notice that the inequality $m_\bullet(M_s)m_\bullet(M_{s+1}) < 0$ implies that $m_\bullet(\tilde{M}_s)m_\bullet(\tilde{M}_{s+1}) < 0$ and therefore $\mathrm{pr}_I(M_{s+1}) < \mathrm{pr}_I(M_s)$. □

**Remark 5.** The careful reader might have noticed that, in fact, the proof of Lemma 4 implies a somewhat sharper claim which is however more difficult to state explicitly. Together with $r(2, n) = 2(n-2)$, this results in a somewhat stronger statement than Theorem 1. However under such minor improvement the leading term of (4) will stay the same. In particular, this refinement will not be sufficient to obtain a linear upper bound for $r(3, n)$ instead of the cubic one given by (4). (Recall that the Grassmann convexity conjecture claims that $r(3, n) = 3(n-3)$, see Equation (5).)

## References

[1] A. Berenstein, S. Fomin, A. Zelevinsky, "Parametrizations of Canonical Bases and Totally Positive Matrices", *Adv. Math.* **122** (1996), no. 1, p. 49-149.

[2] W. A. Coppel, *Disconjugacy*, Lecture Notes in Mathematics, vol. 220, Springer, 1971.

[3] V. Goulart, N. Saldanha, "Combinatorialization of spaces of nondegenerate spherical curves", https://arxiv.org/abs/1810.08632, 2018.

[4] ——, "Stratification by itineraries of spaces of locally convex curves", https://arxiv.org/abs/1907.01659v1, 2019.

[5] ——, "Locally convex curves and the Bruhat stratification of the spin group", *Isr. J. Math.* **242** (2021), no. 2, p. 565-604.

[6] P. Hartmann, "On disconjugate differential equations", *Trans. Am. Math. Soc.* **134** (1968), no. 1, p. 53-70.

[7] N. Saldanha, B. Shapiro, M. Shapiro, "Grassmann convexity and multiplicative Sturm theory, revisited", *Mosc. Math. J.* **21** (2021), no. 3, p. 613-637.

[8] B. Shapiro, M. Shapiro, "Projective convexity in $P^3$ implies Grassmann convexity", *Int. J. Math.* **11** (2000), no. 4, p. 579-588.