# Sign variation, the Grassmannian, and total positivity

Steven N. Karp

► To cite this version:

Steven N. Karp. Sign variation, the Grassmannian, and total positivity. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.121-132, 10.46298/dmtcs.2518 . hal-01337834

HAL Id: hal-01337834

https://hal.science/hal-01337834

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# Sign variation, the Grassmannian, and total positivity

Steven N. Karp¹†

¹Department of Mathematics, University of California, Berkeley, USA

**Abstract.** The totally nonnegative Grassmannian is the set of $k$-dimensional subspaces $V$ of $\mathbb{R}^n$ whose nonzero Plücker coordinates (i.e. $k \times k$ minors of a $k \times n$ matrix whose rows span $V$) all have the same sign. Total positivity has been much studied in the past two decades from an algebraic, combinatorial, and topological perspective, but first arose in the theory of oscillations in analysis. It was in the latter context that Gantmakher and Krein (1950) and Schoenberg and Whitney (1951) independently showed that a subspace $V$ is totally nonnegative iff every vector in $V$, when viewed as a sequence of $n$ numbers and ignoring any zeros, changes sign fewer than $k$ times. We generalize this result, showing that the vectors in $V$ change sign fewer than $l$ times iff certain sequences of the Plücker coordinates of some generic perturbation of $V$ change sign fewer than $l - k + 1$ times. We give an algorithm which constructs such a generic perturbation. Also, we determine the positroid cell of each totally nonnegative $V$ from sign patterns of vectors in $V$. These results generalize to oriented matroids.

**Résumé.** La grassmannienne totalement non négative est l'ensemble des sous-espaces $V$ de $\mathbb{R}^n$ de dimension $k$ dont coordonnées plückeriennes non nulles (mineurs de l'ordre $k$ d'une matrice $k \times n$ dont les lignes engendrent $V$) ont toutes le même signe. La positivité totale a beaucoup été étudiée durant les deux dernières décennies d'une perspective algébrique, combinatoire, et topologique, mais a pris naissance dans la théorie analytique des oscillations. C'est dans ce contexte que Gantmakher et Krein (1950) et Schoenberg et Whitney (1951) ont indépendamment démontré qu'un sous-espace $V$ est totalement non négatif ssi chaque vecteur dans $V$, lorsque considéré comme une séquence de $n$ nombres et dont on ignore les zéros, change de signe moins de $k$ fois. Nous généralisons ce résultat, démontrant que les vecteurs dans $V$ changent de signe moins de $l$ fois ssi certaines séquences des coordonnées plückeriennes d'une perturbation générique de $V$ changent de signe moins de $l - k + 1$ fois. Un algorithme construisant une telle perturbation générique est obtenu. De plus, nous déterminons la cellule positroïde de chaque $V$ totalement non négatif à partir des données de signe des vecteurs dans $V$. Ces résultats sont valides pour les matroïdes orientés.

**Keywords:** sign variation, totally nonnegative Grassmannian, oriented matroid, positroid, Grassmann necklace

## 1 Introduction

The (real) Grassmannian $\text{Gr}_{k,n}$ is the set of $k$-dimensional subspaces of $\mathbb{R}^n$. Given $V \in \text{Gr}_{k,n}$, take a $k \times n$ matrix $A$ whose rows span $V$; then for $k$-subsets $I \subseteq \{1, \dots, n\}$, we let $\Delta_I(V)$ be the $k \times k$ minor

<footnote>†Email: skarp@berkeley.edu. I am partially supported by an NSERC postgraduate scholarship and a Chateaubriand fellowship.</footnote>
of A with columns I. (The $\Delta_I(V)$ depend on our choice of A only up to a global constant.) If all nonzero $\Delta_I$ have the same sign, then V is called totally nonnegative. For example, the span of $(1, 0, 0, -1)$ and $(-1, 2, 1, 3)$ is a totally nonnegative element of $Gr_{2,4}$. The set of such V, called the totally nonnegative Grassmannian, has become a hot topic in algebraic combinatorics in the past two decades. The general algebraic study of total positivity (for reductive algebraic groups G and partial flag varieties $G/P$) was initiated by Lusztig [Lus94]. The totally nonnegative Grassmannian (the particular case $G/P = \text{Gr}_{k,n}$) was later studied from a combinatorial perspective by Postnikov [Pos]. Of particular interest to us is the stratification of the totally nonnegative Grassmannian by whether each $\Delta_I$ is zero or nonzero. This stratification is a cell decomposition, which was conjectured by Lusztig [Lus94] and proved by Rietsch [Rie99] (for the general case $G/P$), and later proved combinatorially by Postnikov [Pos]. Total positivity originated, however, in the 1930's in oscillation theory in analysis, where positivity conditions on matrices can imply special oscillation and spectral properties. It was in this context that Gantmakher and Krein [GK50], and independently Schoenberg and Whitney [SW51], proved the first result about (what would later be called) the totally nonnegative Grassmannian.

**Theorem 1.1 (5.3 of [GK50], [SW51]).** An element $V$ of $\text{Gr}_{k,n}$ is totally nonnegative iff all vectors in $V$ (viewed as sequences of $n$ numbers, ignoring any zeros) change sign fewer than $k$ times.

For example, the two vectors $(1, 0, 0, -1)$ and $(-1, 2, 1, 3)$ each change sign exactly once, and we can check that any vector in their span changes sign at most once. Every element of $\text{Gr}_{k,n}$ has a vector which changes sign at least $k-1$ times (put a $k \times n$ matrix whose rows span $V$ into row reduced echelon form, and take the alternating sum of the rows), so the totally nonnegative elements are those whose vectors change sign as few times as possible.

There are two main results in this paper. The first generalizes Theorem 1.1 to all $V \in \text{Gr}_{k,n}$ by giving a criterion for when the vectors in $V$ change sign fewer than $l$ times, in terms of the $\Delta_I(V)$. (Theorem 1.1 is the case $l=k$; see Corollary 4.7 for details.) The second shows, in the case that $V$ is totally nonnegative, how to determine the cell of $V$ in the cell decomposition of the totally nonnegative Grassmannian.

We now describe our first main result, split into two parts (Theorem 1.2 and Theorem 1.4). For more details see Section 2, specifically Theorem 2.1 and Theorem 2.7.

**Theorem 1.2.** (i) If the vectors in $V \in \text{Gr}_{k,n}$ change sign fewer than $l$ times, then $(\Delta_{J \cup \{i\}}(V))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $(k-1)$-subsets $J \subseteq \{1, \dots, n\}$.

(ii) If $V \in \text{Gr}_{k,n}$ such that $\Delta_I(V) \neq 0$ for all $k$-subsets $I \subseteq \{1, \dots, n\}$, and $(\Delta_{J \cup \{i\}}(V))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $(k-1)$-subsets $J \subseteq \{1, \dots, n\}$, then the vectors in $V$ change sign fewer than $l$ times.

**Example 1.3.** Let $V \in \text{Gr}_{2,4}$ be the row span of the matrix $\begin{bmatrix} 1 & 0 & -2 & 3 \\ 0 & 2 & 1 & 4 \end{bmatrix}$. Then $\Delta_I(V) \neq 0$ for all $2$-subsets $I \subseteq \{1, 2, 3, 4\}$, so the fact that the vectors in $V$ change sign fewer than $l:= 3$ times is equivalent to the fact that the 4 sequences

$$ \begin{align*} (\Delta_{\{1,2\}}(V), \Delta_{\{1,3\}}(V), \Delta_{\{1,4\}}(V)) &= (2, 1, 4), \\ (\Delta_{\{1,2\}}(V), \Delta_{\{2,3\}}(V), \Delta_{\{2,4\}}(V)) &= (2, 4, -6), \\ (\Delta_{\{1,3\}}(V), \Delta_{\{2,3\}}(V), \Delta_{\{3,4\}}(V)) &= (1, 4, -11), \\ (\Delta_{\{1,4\}}(V), \Delta_{\{2,4\}}(V), \Delta_{\{3,4\}}(V)) &= (4, -6, -11) \end{align*} $$

each change sign fewer than $l-k+1=2$ times.

◇
Part (ii) of Theorem 1.2 applies only to generic elements of $Gr_{k,n}$, i.e. those $V$ such that $\Delta_I(V) \neq 0$ for all $I$. In the case that $V$ is not generic, we show how to construct a generic perturbation $W$ of $V$, such that if the vectors in $V$ change sign fewer than $l$ times, then so do the vectors in $W$. (A perturbation of $V$ is an element $V' \in Gr_{k,n}$ such that for all $k$-subsets $I \subseteq \{1, \dots, n\}$ with $\Delta_I(V)$ nonzero, $\Delta_I(V')$ is also nonzero with the same sign as $\Delta_I(V)$.) This gives the following generalization of Theorem 1.2 to non-generic $V$.

**Theorem 1.4.** The vectors in $V \in Gr_{k,n}$ change sign fewer than $l$ times iff there exists a generic perturbation $V'$ of $V$ such that

$$ (\Delta_{J \cup \{i\}}(V'))_{i \notin J} \text{ changes sign fewer than } l-k+1 \text{ times for all } (k-1)\text{-subsets } J \subseteq \{1, \dots, n\}. \quad (1) $$

By a certain algorithm (see Theorem 2.7) we can construct a generic perturbation $W$ of $V \in Gr_{k,n}$ such that the vectors in $V$ change sign fewer than $l$ times iff (1) holds for $V' = W$.

The algorithm involves perturbing one coordinate of $V$ by an adjacent coordinate at most $2(n-1)(n-k)$ times; see Theorem 2.7 for the details.

The natural framework in which to consider sign patterns of vectors in $V$, and signs of the $\Delta_I(V)$, is that of *oriented matroids*. Our results hold in this context, suitably interpreted in the language of oriented matroids (see Section 4), and are more general because while every subspace gives rise to an oriented matroid, not every oriented matroid comes from a subspace.

We now describe our second main result. For each totally nonnegative $V \in Gr_{k,n}$, we define the *positroid* of $V$ as the set of $k$-subsets $I$ of $\{1, \dots, n\}$ such that $\Delta_I(V)$ is nonzero. The stratification of the totally nonnegative Grassmannian by positroids is a cell decomposition [Rie99, Pos]. We also define the *Grassmann necklace* of $V$ as the $n$-tuple $(I_1, \dots, I_n)$ of $k$-subsets of $\{1, \dots, n\}$, where $I_j$ is the lexicographically minimal $I$ such that $\Delta_I(V) \neq 0$, with respect to the total order $\leq_j$ on $\{1, \dots, n\}$ given by $j <_j j+1 <_j \dots <_j n <_j 1 <_j \dots <_j j-1$. Postnikov [Pos] showed that the positroid of $V$ is uniquely determined by its Grassmann necklace.

How can we determine the positroid of $V$, or equivalently its Grassmann necklace, from the sign patterns of vectors in $V$? Given a subset $I \subseteq \{1, \dots, n\}$ and a sign vector $\omega \in \{+, -\}^I$, we say that $V$ realizes $\omega$ if there exists a vector in $V$ whose restriction to $I$ has signs given by $\omega$. For example, if $(2, 3, -2, -1) \in V$, then $V$ realizes $(+, -, -)$ on $\{1, 3, 4\}$. It is not difficult to show that for all $V \in Gr_{k,n}$, we have $\Delta_I(V) \neq 0$ iff $V$ realizes all $2^k$ sign vectors in $\{+, -\}^I$. Furthermore, we potentially have to check all of the $2^k$ sign vectors, since given any $\omega \in \{+, -\}^I$ (and assuming $n > k$), there exists a $V \in Gr_{k,n}$ which realizes all $2^k$ sign vectors in $\{+, -\}^I$ except for $\pm\omega$. However, in the case that $V$ is totally nonnegative, we show that we need only check $2^k$ particular sign vectors in $\{+, -\}^I$ to verify that $\Delta_I(V) \neq 0$, and moreover that we can use these sign vectors to pick out the Grassmann necklace of $V$.

**Theorem 1.5.** Suppose that $V \in Gr_{k,n}$ is totally nonnegative.

(i) (Positroid criterion) Let $J$ be a $k$-subset of $\{1, \dots, n\}$. Then $\Delta_J(V) \neq 0$ iff $V$ realizes all $2^k$ sign vectors in $\{+, -\}^J$ which alternate between every pair of consecutive components, with at most one exceptional pair. (For example, if $k=5$ these sign vectors are $(+, -, +, -, +), (+, +, -, +, -), (+, -, -, +, -), (+, -, +, +, -), (+, -, +, -, -)$, and their negations.)

(ii) (Grassmann necklace criterion) Let $(I_1, \dots, I_n)$ be the Grassmann necklace of $V$. Then $I_j$ is the $j$-Gale minimum among all $k$-subsets $J$ of $\{1, \dots, n\}$ such that $V$ realizes a sign vector on $J$ which alternates except precisely from component $\max(\{i \in J : i < j\})$ to component $\min(\{i \in J : i \ge j\})$
(if both components exist). (For example, if $J = \{1, 4, 6, 8, 9\}$ and $j = 7$, then such a sign vector is $(+, -, +, +, -)$ or its negation. The $j$-Gale order is given by $\{i_1 <_j \cdots <_j i_k\} \le_{j-\text{Gale}} \{i'_1 <_j \cdots <_j i'_k\}$ iff $i_1 \le_j i'_1, \cdots, i_k \le_j i'_k$.)

Neither (i) nor (ii) hold for all $V \in \text{Gr}_{k,n}$; see Example 3.8 and Example 3.3. For further details on Theorem 1.5 see Section 3, specifically Corollary 3.6 and Corollary 3.4.

**Example 1.6.** Let $V \in \text{Gr}_{3,5}$ be the row span of the matrix
$$
\begin{bmatrix}
2 & 1 & 0 & 0 & 3 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1
\end{bmatrix}
$$
, which is totally non-negative. Part (i) of Theorem 1.5 states that for 3-subsets $I$ of $\{1, 2, 3, 4, 5\}$, we have $\Delta_I(V) \neq 0$ iff the 3 sign vectors $(+, -, +), (+, +, -), (+, -, -)$ on $I$ are realized by $V$. For $I = \{1, 3, 5\}$, the vectors $(2, 1, -1, 0, 3)$, $(2, 1, 1, -4, -1)$, $(2, 1, -1, -4, -1)$ in $V$ realize the sign vectors $(+, -, +), (+, +, -), (+, -, -)$ on $I$, so $\Delta_{\{1,3,5\}}(V) \neq 0$. (We do not need to check that $(+, +, +)$, the remaining sign vector on $I$ up to sign, is realized.) For $I = \{1, 4, 5\}$, the vectors $(2, 1, 0, -1, 2)$ and $(2, 1, 0, -4, -1)$ in $V$ realize the sign vectors $(+, -, +)$ and $(+, -, -)$ on $I$, but no vector in $V$ realizes the sign vector $(+, +, -)$ on $I$, so $\Delta_{\{1,4,5\}}(V) = 0$. Part (ii) of Theorem 1.5 for $j = 1$ states that the lexicographic minimum $I_1 = \{1, 3, 4\}$ of the positroid of $V$ is also the Gale minimum of $\{\{1, 3, 4\}, \{1, 3, 5\}, \{1, 4, 5\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}\}$, the set of 3-subsets of $\{1, 2, 3, 4, 5\}$ on which $V$ realizes the alternating sign vector $(+, -, +)$.
$\diamond$

**Acknowledgements.** I thank Lauren Williams, my advisor, for many helpful conversations and suggestions. I also thank Sylvie Corteel and the Laboratoire d'Informatique Algorithmique: Fondements et Applications at Université Paris Diderot for hosting me while I conducted this work.

## 2 Sign changes and the Grassmannian

In this section we characterize the maximum number of times a vector in $V$ changes sign, in terms of the Plücker coordinates of $V$. In the case that $V$ is generic, we give a direct criterion (Theorem 2.1); otherwise, we show how to perturb $V$ into a generic subspace, whence we may apply the same criterion to the perturbation (Theorem 2.7).

We introduce some terminology. Let $\text{Gr}_{k,n}$ denote the *Grassmannian* of $k$-dimensional subspaces of $\mathbb{R}^n$. Given $V \in \text{Gr}_{k,n}$, take a $k \times n$ matrix $A$ whose rows span $V$. For $I \in \binom{[n]}{k}$, we define the *Plücker coordinate* $\Delta_I(V)$ as the minor of $A$ which uses the columns in $I$ (where $\binom{[n]}{k}$ denotes the set of $k$-subsets of $[n] := \{1, \cdots, n\}$). Note that if $A'$ is another $k \times n$ matrix whose rows span $V$, then the corresponding minors of $A$ and $A'$ are equal up to multiplication by a global nonzero constant. Hence $\Delta_I(V)$ is well-defined in the projective space $\mathbb{P}(n)_k^{-1}$. Also, for $v \in \mathbb{R}^n$ and $I \subseteq [n]$, we say that $v$ *alternates on* $I$ if the components of $v$ alternate sign on $I$, i.e. $I = \{i_1, \cdots, i_k\}$ ($i_1 < \cdots < i_k$) and $v_{i_1}v_{i_2}, v_{i_2}v_{i_3}, \cdots, v_{i_{k-1}}v_{i_k}$ are all negative. For example, $(3, 1, -2)$ alternates on $\{1, 3\}$ and $\{2, 3\}$, but not on $\{1, 2\}$. The number of sign changes of $v \in \mathbb{R}^n$ is one less than the maximum size of a subset $I \subseteq [n]$ on which $v$ is alternating. For example, $(3, 1, -2)$ changes sign once.

We say that $V \in \text{Gr}_{k,n}$ is *generic* if $\Delta_I(V) \neq 0$ for all $I \in \binom{[n]}{k}$. We have the following criterion for when the vectors in a generic $V$ change sign fewer than $l$ times.

**Theorem 2.1.** (i) If the vectors in $V \in \text{Gr}_{k,n}$ change sign fewer than $l$ times, then $(\Delta_{J \cup \{i\}}(V))_{i \notin J}$ changes sign fewer than $l - k + 1$ times for all $J \in \binom{[n]}{k-1}$.
(ii) If $V \in \text{Gr}_{k,n}$ is generic and $(\Delta_{J \cup \{i\}}(V))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $J \in \binom{[n]}{k}$, then the vectors in $V$ change sign fewer than $l$ times.

We give an example which shows that part (ii) above does not hold for all $V \in \text{Gr}_{k,n}$.

**Example 2.2.** Let $V \in \text{Gr}_{2,4}$ be the row span of the matrix $\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{bmatrix}$. Note that the 4 sequences of Plücker coordinates

$$ 
\begin{aligned}
(\Delta_{\{1,2\}}(V) : \Delta_{\{1,3\}}(V) : \Delta_{\{1,4\}}(V)) &= (1 : 0 : 1), \\
(\Delta_{\{1,2\}}(V) : \Delta_{\{2,3\}}(V) : \Delta_{\{2,4\}}(V)) &= (1 : -1 : 0), \\
(\Delta_{\{1,3\}}(V) : \Delta_{\{2,3\}}(V) : \Delta_{\{3,4\}}(V)) &= (0 : -1 : 1), \\
(\Delta_{\{1,4\}}(V) : \Delta_{\{2,4\}}(V) : \Delta_{\{3,4\}}(V)) &= (1 : 0 : 1)
\end{aligned}
$$

each change sign fewer than $l-k+1=2$ times (where we take $l:=3$), but the vector $(1, -1, 1, -1) \in V$ changes sign $l=3$ times. Note that if we were forced to pick a sign for $\Delta_{\{1,3\}}(V)$, then either the first or third sequence above would change sign twice. This motivates the introduction of perturbations below. ♦

Given $V, V' \in \text{Gr}_{k,n}$, we say that $V'$ is a perturbation of $V$ if for all $I \in \binom{[n]}{k}$ with $\Delta_I(V)$ nonzero, $\Delta_I(V')$ is also nonzero and has the same sign as $\Delta_I(V)$. It is not hard (using the theory of oriented matroids; see Definition 4.3) to show that if the vectors in $V'$ change sign fewer than $l$ times, then so do the vectors in $V$. Conversely, however, if the vectors in $V$ change sign fewer than $l$ times, it is not obvious that there exists a nontrivial perturbation $V'$ of $V$ whose vectors also change sign fewer than $l$ times. This is what we now show, leading up to a generalization of Theorem 2.1 to such non-generic $V$ (Theorem 2.7). We build our perturbations using sequences of elementary perturbations called $i \to_{\epsilon} j$-perturbations.

**Definition 2.3 (i $\to \epsilon$ j-perturbation).** Let $i, j \in [n]$ be distinct and $\epsilon \in \{+, -\}$. Given $V \in \text{Gr}_{k,n}$, take a $k \times n$ matrix $A = [x^{(1)}|\cdots|x^{(n)}]$ whose rows span $V$, where $x^{(1)}, \cdots, x^{(n)} \in \mathbb{R}^k$ are column vectors. For $\alpha \in \mathbb{R}$, let $V' \in \text{Gr}_{k,n}$ be the row span of the $k \times n$ matrix $A' := [x^{(1)}|\cdots|x^{(j-1)}|x^{(j)} + \alpha x^{(i)}|x^{(j+1)}|\cdots|x^{(n)}]$. (Note that $V'$ depends only on $\alpha$, not on our choice of $A$.) We say that $V'$ is an $i \to \epsilon$ j-perturbation of $V$ if $\alpha$ is nonzero, has the same sign as $\epsilon$, and is sufficiently small that if $I \in \binom{[n]}{k}$ indexes a nonzero minor of $A$, then the $I$-minor of $A'$ is also nonzero with the same sign.

The possible values of $\alpha$ form an open interval between 0 and some number, or $\pm\infty$, with sign $\epsilon$.

**Example 2.4.** Let $V \in \text{Gr}_{2,4}$ be the row span of the matrix $A := \begin{bmatrix} 1 & 0 & 2 & 0 \\ 0 & 3 & -1 & 4 \end{bmatrix}$, and for $\alpha < 0$ let $V' \in \text{Gr}_{2,4}$ be the row span of the perturbed matrix $A' := \begin{bmatrix} 1 & 0 & 2 & \alpha \\ 0 & 3 & -1 & 4 \end{bmatrix}$. Note that the $\{3,4\}$-minor of $A$ equals 8, and the $\{3,4\}$-minor of $A'$ equals $8+\alpha$, so we should pick $\alpha > -8$ so that these minors agree in sign. In fact, for any $\alpha \in (-8, 0)$ the $I$-minors of $A$ and $A'$ have the same sign whenever the $I$-minor of $A$ is nonzero (for $I \in \binom{[4]}{2}$), whence $V'$ is a $1 \to_-$ 4-perturbation of $V$. ♦

If the vectors in $V \in \text{Gr}_{k,n}$ change sign fewer than $l$ times, then certain $i \to_{\epsilon} j$-perturbations preserve this property, and are in fact sufficient to perturb $V$ into a generic subspace.
**Lemma 2.5.** (i) If the vectors in $V \in \text{Gr}_{k,n}$ change sign fewer than $l$ times, then so do the vectors in any $(i+1) \to_+ i$, $i \to_+ (i+1)^-$, $1 \to_{(-1)^{l-1}} n^-$, or $n \to_{(-1)^{l-1}} 1$-perturbation of $V$ (for any $i \in [n-1]$).

(ii) Applying the sequence of perturbations

$$2 \to 1, 3 \to 2, \dots, n \to (n-1), 1 \to n, 2 \to 1, 3 \to 2, \dots, (n-1) \to (n-2)$$

in order from left to right $n-k$ times to any $V \in \text{Gr}_{k,n}$ gives a generic subspace. (Here an $i \to j$-perturbation denotes either of the $i \to_\epsilon j$-perturbations for $\epsilon \in \{+, -\}$; the sign of $\epsilon$ is not important.) Similarly, applying the sequence of perturbations

$$2 \to 1, 3 \to 2, \dots, n \to (n-1), (n-1) \to n, (n-2) \to (n-1), \dots, 1 \to 2$$

in order from left to right $n-k$ times to any $V \in \text{Gr}_{k,n}$ gives a generic subspace.

Note that part (i) above follows in general from the specific case of $2 \to_+ 1$-perturbations, by the following symmetries: if the vectors in the row span of the matrix $[x^{(1)}|\dots|x^{(n)}]$ change sign fewer than $l$ times, then so do the vectors in the row span of the cyclic shift $[x^{(2)}|\dots|x^{(n)}|(-1)^{l-1}x^{(1)}]$ and the reversal $[x^{(n)}|\dots|x^{(1)}]$. Also note that part (ii) above gives two specific algorithms for constructing a generic perturbation of any $V \in \text{Gr}_{k,n}$ in $2(n-1)(n-k) < 2n^2$ steps.

**Example 2.6.** Let $V \in \text{Gr}_{2,3}$ be the row span of the matrix $\begin{bmatrix} 0 & 1 & 3 \\ 1 & 0 & 0 \end{bmatrix}$, whose vectors change sign fewer than $l := 2$ times. Then $V$ is not generic, but we can get a generic subspace by applying a $1 \to_- 3$-perturbation, which gives the row span of $\begin{bmatrix} 0 & 1 & 3 \\ 1 & 0 & \alpha \end{bmatrix}$ ($\alpha < 0$), or by applying a $1 \to_+ 2$-perturbation, which gives the row span of $\begin{bmatrix} 0 & 1 & 3 \\ 1 & \beta & 0 \end{bmatrix}$ ($\beta > 0$). The vectors in these two subspaces change sign fewer than $l = 2$ times.

Note that we cannot make $V$ generic by applying only $2 \to 1$- and $3 \to 2$-perturbations. Also note that, for example, applying a $1 \to_- 2$-perturbation gives the row span of $\begin{bmatrix} 0 & 1 & 3 \\ 1 & \gamma & 0 \end{bmatrix}$ ($\gamma < 0$), which has a vector (e.g. $(-\frac{2}{\gamma}, -1, 3)$) that changes sign twice. $\diamond$

**Theorem 2.7.** The vectors in $V \in \text{Gr}_{k,n}$ change sign fewer than $l$ times iff there exists a generic perturbation $V'$ of $V$ such that $(\Delta_{J \cup \{i\}}(V'))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $J \in \binom{[n]}{k-1}$.

Explicitly, let $W$ be obtained from $V \in \text{Gr}_{k,n}$ by applying the sequence of perturbations

$$2 \to_+ 1, 3 \to_+ 2, \dots, n \to_+ (n-1), 1 \to_{(-1)^{l-1}} n, 2 \to_+ 1, 3 \to_+ 2, \dots, (n-1) \to_+ (n-2)$$

in order from left to right $n-k$ times, or by applying the sequence of perturbations

$$2 \to_+ 1, 3 \to_+ 2, \dots, n \to_+ (n-1), (n-1) \to_+ n, (n-2) \to_+ (n-1), \dots, 1 \to_+ 2$$

in order from left to right $n-k$ times, so that $W$ is a generic perturbation of $V$. Then the following are equivalent:

(i) the vectors in $V$ change sign fewer than $l$ times;

(ii) the vectors in $W$ change sign fewer than $l$ times; and

(iii) $(\Delta_{J \cup \{i\}}(W))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $J \in \binom{[n]}{k-1}$.
In principle the results in this section are about components of vectors in subspaces, and their Plücker coordinates, only up to sign (zero, positive, or negative). There is an object $\mathcal{M}(V)$ which, given $V \in \text{Gr}_{k,n}$, records precisely the vectors of $V$ up to sign, or equivalently the Plücker coordinates $\Delta(V)$ up to sign; it is called the *oriented matroid* associated to $V$. There is a general notion of an *oriented matroid*, among which those of the form $\mathcal{M}(V)$ comprise the strict subset of *realizable* oriented matroids. All the results in this section generalize naturally to oriented matroids, using the following dictionary:

<table><thead><tr><th>subspaces</th><th>oriented matroids</th></tr></thead><tbody><tr><td>sign vectors of vectors in V</td><td>covectors of $\mathcal{M}(V)$</td></tr><tr><td>$\Delta(V)$, up to sign</td><td>the chirotope $\chi_{\mathcal{M}(V)}$</td></tr><tr><td>V is generic</td><td>$\mathcal{M}(V)$ is uniform</td></tr><tr><td>$V'$ is a perturbation of V</td><td>$\mathcal{M}(V) \le \mathcal{M}(V')$</td></tr></tbody></table>

We also generalize $i \to_e j$-perturbation to oriented matroids. We give precise statements in Section 4.

## 3 Positroids from sign patterns

We say that $V \in \text{Gr}_{k,n}$ is *totally nonnegative* if $\Delta_I(V) \ge 0$ for all $I \in \binom{[n]}{k}$ (or equivalently, $\Delta_I(V) \le 0$ for all $I \in \binom{[n]}{k}$), since $\Delta(V)$ is defined in projective space). Let $\text{Gr}_{k,n}^{\ge 0}$ be the subset of $\text{Gr}_{k,n}$ of totally nonnegative elements, called the *totally nonnegative Grassmannian*. The goal of this section is to describe several ways to recover the *positroid cell* of a given $V \in \text{Gr}_{k,n}^{\ge 0}$ from the sign patterns of vectors in $V$.

For $V \in \text{Gr}_{k,n}$, let $M(V) := \{I \in \binom{[n]}{k} : \Delta_I(V) \ne 0\}$ be the *matroid* of $V$. In the case that $V$ is totally nonnegative, we call $M(V)$ a *positroid*. Postnikov [Pos] showed that the positroid stratification of $\text{Gr}_{k,n}^{\ge 0}$ (i.e. its partition into equivalence classes, where $V \sim W$ iff $M(V) = M(W)$) is a cell decomposition, which coincides with the one earlier conjectured by Lusztig [Lus94] and proven by Rietsch [Rie99] in the more general context of total positivity in partial flag varieties $G/P$. Postnikov constructed in particular, for each stratum, a homeomorphism between $\mathbb{R}_{>0}^d$ and the stratum using a certain bicolored planar graph

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** A homeomorphism from $\mathbb{R}_{>0}^4$ to the cell of $\text{Gr}_{2,4}^{\ge 0}$ labeled by the positroid $M = \binom{[4]}{2}$.</figcaption></figure>

drawn inside a disk. He also showed that for $V \in \text{Gr}_{k,n}^{\ge 0}$, the positroid $M(V)$ is uniquely determined by its *Grassmann necklace* $(I_1, \dots, I_n) \in \binom{[n]}{k}^n$, where $I_j$ (for $j \in [n]$) is the lexicographic minimum of $M(V)$ with respect to the total order $\le_j$ on $[n]$ given by $j <_j j + 1 <_j \dots <_j n <_j 1 <_j \dots <_j j - 1$. For example, the Grassmann necklace of the positroid $M = \binom{[4]}{2}$ is $(\{1, 2\}, \{2, 3\}, \{3, 4\}, \{4, 1\})$.

Given $V \in \text{Gr}_{k,n}^{\ge 0}$, how can we determine the positroid $M(V)$, or equivalently its Grassmann necklace, from the sign vectors of $V$, i.e. those $\omega \in \{0, +, -\}^n$ such that some vector in $V$ has signs given by $\omega$? It follows from the theory of oriented matroids (see Section 4) that for any $V \in \text{Gr}_{k,n}$, given the signs (either $0$, $+$, or $-$) of all Plücker coordinates $\Delta_I(V)$, we can determine the sign vectors of $V$, and vice versa. Hence we can recover $M(V)$ from the sign vectors of $V$. We now focus on criteria for $V \in \text{Gr}_{k,n}^{\ge 0}$ which take advantage of the special properties of the totally nonnegative Grassmannian.
We begin by examining the *Schubert cell* of V, which is labeled by $I_1$, the lexicographic minimum of $M(V)$. We use the *Gale partial order* $\leq_{\text{Gale}}$, which is the partial order of $\binom{[n]}{k}$ given by

$$I \leq_{\text{Gale}} J \iff i_1 \leq j_1, i_2 \leq j_2, \dots, i_k \leq j_k$$

for subsets $I = \{i_1, \dots, i_k\}$ ($i_1 < \dots < i_k$), $J = \{j_1, \dots, j_k\}$ ($j_1 < \dots < j_k$) of $[n]$.

**Proposition 3.1.** Suppose that $V \in \text{Gr}_{k,n}^{\geq 0}$ and $I \in \binom{[n]}{k}$ is the lexicographic minimum of $M(V)$.

(i) For all $J \in M(V)$, there exists a vector in $V$ which alternates on $J$.

(ii) If some vector in $V$ alternates on $J \in \binom{[n]}{k}$, then $I \leq_{\text{Gale}} J$.

Thus $I$ is the Gale-minimal element of $\binom{[n]}{k}$ on which some vector in $V$ alternates.

**Example 3.2.** Let $V \in \text{Gr}_{2,4}^{\geq 0}$ be the row span of the matrix $\begin{bmatrix} 1 & 2 & 0 & -1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$. Then no vector in $V$ alternates on $\{1, 2\}$, and $(1, 2, -1, -1) \in V$ alternates on $\{1, 3\}$, so $\{1, 3\}$ is the lexicographic minimum of $M(V)$. Note that the vector $(1, 2, 0, -1) \in V$ alternates on $\{1, 4\} \notin M(V)$, so the converse to part (i) above does not necessarily hold. $\diamond$

Part (i) of Proposition 3.1 holds for all $V \in \text{Gr}_{k,n}$ (since $J \in M(V)$ iff $V|_J = \mathbb{R}^J$, where $V|_J$ denotes the restriction of $V$ to the coordinates in $J$), but not part (ii), as the next example shows.

**Example 3.3.** Let $V \in \text{Gr}_{3,6}$ be the row span of the matrix $\begin{bmatrix} 1 & 0 & -1 & -1 & 1 & 0 \\ 0 & 1 & 1 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$. Then the vector $(1, -1, -2, -3, 1, 0) \in V$ alternates on $\{1, 2, 5\}$, and $(3, 2, -1, 1, 3, 0) \in V$ alternates on $\{1, 3, 4\}$, but no vector in $V$ alternates on $\{1, 2, 3\}$ or $\{1, 2, 4\}$. Hence $\{J \in \binom{[6]}{3} : \text{some vector in } V \text{ alternates on } J\}$ has no Gale minimum. $\diamond$

We can generalize Proposition 3.1 to the entire Grassmann necklace, as follows. Let $V \in \text{Gr}_{k,n}$ and $(I_1, \dots, I_n) \in \binom{[n]}{k}$ be the Grassmann necklace of $V$. For $j \in [n]$, we define the $j$-cyclic shift $V_j$ of $V$ as follows: take a $k \times n$ matrix $[x^{(1)}|\dots|x^{(n)}]$ whose rows span $V$, and let $V_j$ be the row span of $[x^{(j)}|x^{(j+1)}|\dots|x^{(n)}|(-1)^{k-1}x^{(1)}|\dots|(-1)^{k-1}x^{(j-1)}]$, with columns labeled $j, j+1, \dots, n, 1, \dots, j-1$. Note that $V_j$ does not depend on our choice of matrix, and if $V$ is totally nonnegative then so is $V_j$ (which explains why we have the signs $(-1)^{k-1}$). Then $I_j$ is the lexicographically minimal index of a nonzero Plücker coordinate of $V_j$ (given our labeling of the columns), and $v \in V_j$ alternates on $J \in \binom{[n]}{k}$ (with respect to the total order $\leq_j$) iff $v \in V$ alternates on $J$ except precisely from component $\max(J \cap [1, j))$ to component $\min(J \cap [j, n))$ (if both components exist). For example, if $J = \{1, 3, 4\}$ and $j = 3$, then $v = (1, 1, 1, -1)$ satisfies this condition, but not $v = (1, 1, -1, 1)$. Applying Proposition 3.1 to $V_j$ gives the following corollary, where $\leq_{j-\text{Gale}}$ is the Gale order on $\binom{[n]}{k}$ induced by the total order $\leq_j$ on $[n]$.

**Corollary 3.4.** Suppose that $V \in \text{Gr}_{k,n}^{\geq 0}$ has Grassmann necklace $(I_1, \dots, I_n) \in \binom{[n]}{k}$, and $j \in [n]$.

(i) For all $J \in M(V)$, there exists a vector in $V$ which alternates on $J$ except precisely from component $\max(J \cap [1, j))$ to component $\min(J \cap [j, n))$ (if both components exist).

(ii) If some vector in $V$ alternates on $J \in \binom{[n]}{k}$ except precisely from component $\max(J \cap [1, j))$ to component $\min(J \cap [j, n))$ (if both components exist), then $I_j \leq_{j-\text{Gale}} J$.

Thus $I_j$ is the $j$-Gale-minimal element of $\binom{[n]}{k}$ on which some vector in $V$ alternates except precisely from component $\max(J \cap [1, j))$ to component $\min(J \cap [j, n))$ (if both components exist).
Oh [Oh11] explicitly described a positroid in terms of its Grassmann necklace. With Corollary 3.4, we immediately get a characterization of the positroid of $V \in \mathrm{Gr}_{k,n}^{\ge 0}$ in terms of sign patterns of vectors in $V$. Given $I \subseteq [n]$ and a sign vector $\omega \in \{+, -\}^I$, we say that $V$ realizes $\omega$ if there exists a vector in $V$ whose restriction to $I$ has signs given by $\omega$.

**Theorem 3.5 (Theorem 6 of [Oh11]).** Suppose that $M$ is a set of $k$-subsets of $[n]$ which is a matroid with Grassmann necklace $(I_1, \dots, I_n) \in \binom{[n]}{k}^n$. Then $M$ is a positroid iff $M = \{J \in \binom{[n]}{k} : I_j \le j$-Gale $J$ for $j \in [n]\}$.

**Corollary 3.6.** For all $V \in \mathrm{Gr}_{k,n}^{\ge 0}$ and $I \in \binom{[n]}{k}$, we have $I \in M(V)$ iff $V$ realizes all $2k$ sign vectors in $\{+, -\}^I$ which alternate between every pair of consecutive components, with at most one exceptional pair.

We remark that we can also prove Corollary 3.6 directly from Theorem 1.1, as follows. If $I \in M(V)$ then $V|_I = \mathbb{R}^I$, and so $V$ realizes all sign vectors on $I$. Conversely, if $I \notin M(V)$, then we take $j \in [n] \setminus I$ such that $V|_{I \cup \{j\}}$ has rank greater than that of $V|_I$, i.e. there exists a vector $v \in V$ with $v|_I = 0$ and $v_j \ne 0$. Using $v$, we can extend any sign vector which $V$ realizes on $I$ to a sign vector which $V$ realizes on $I \cup \{j\}$, with our choice of sign in component $j$. Since no vector in $V$ alternates on $I \cup \{j\}$, there is no vector in $V$ which alternates on $I$ except precisely from component $\max(I \cap [1, j))$ to component $\min(I \cap [j, n))$ (if both components exist).

By way of contrast to Corollary 3.6, we offer a similar criterion for general $V \in \mathrm{Gr}_{k,n}$, which is not difficult to prove using the fact that $I \in M(V)$ iff $V|_I = \mathbb{R}^I$.

**Proposition 3.7.** For $V \in \mathrm{Gr}_{k,n}$ and $I \in \binom{[n]}{k}$, we have $I \in M(V)$ iff $V$ realizes all $2^k$ sign vectors in $\{+, -\}^I$.

Moreover, given $\omega \in \{+, -\}^I$, we can construct $V \in \mathrm{Gr}_{k,n}$ (assuming $n > k$) such that $V$ realizes all $2^k$ sign vectors in $\{+, -\}^I$ except for $\pm\omega$, by taking $v \in \mathbb{R}^I$ with sign vector $\omega$ and letting $V|_I$ be the hyperplane in $\mathbb{R}^I$ perpendicular to $v$. Thus for general $V \in \mathrm{Gr}_{k,n}$, we potentially need to check (up to sign) that $2^{k-1}$ sign vectors on $I$ are realized, whereas if $V$ is totally nonnegative then we need only check $k$ by Corollary 3.6. We give an explicit example of this phenomenon.

**Example 3.8.** Let $V \in \mathrm{Gr}_{3,4}$ be the row span of the matrix $$ \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$ which is not totally non-negative, and let $I := \{1, 2, 3\}$. Then the vectors $(1, -2, 1, 0)$, $(1, 1, -2, 0)$, $(2, -1, -1, 0)$ in $V$ realize the sign vectors $(+, -, +)$, $(+, -, -)$, $(+, -, -)$ on $I$, but $I \notin M(V)$. $\diamond$

The results in this section also hold for oriented matroids, but this gives no new information: by a recent result of Ardila, Rincón, and Williams [ARW], all oriented matroids which are totally nonnegative (called positively oriented matroids) come from totally nonnegative subspaces.

# 4 Results generalized to oriented matroids

In this section we generalize the results of Section 2 to oriented matroids. A comprehensive account of the theory of oriented matroids, and our reference throughout, is [BLVS+99]. We begin by describing oriented matroids coming from subspaces of $\mathbb{R}^n$ (called realizable oriented matroids), which can serve as a reference point for our results. For $\alpha \in \mathbb{R}$ we let $\mathrm{sign}(\alpha) \in \{0, +, -\}$ be the sign of $\alpha$, and for $v \in \mathbb{R}^E$
we define the sign vector $\operatorname{sign}(v) \in \{0, +, -\}^E$ by $\operatorname{sign}(v)_e := \operatorname{sign}(v_e)$ for $e \in E$. The *support* of a sign vector $X \in \{0, +, -\}^E$ is the subset of $E$ which indexes the nonzero components of $X$. For example, $\operatorname{sign}(5, 0, -1, 2) = (+, 0, -, +)$ has support $\{1, 3, 4\}$.

**Definition 4.1 (realizable oriented matroids; 1.2 of [BLVS+99]).** Let $V \in \operatorname{Gr}_{k,n}$. The (realizable) oriented matroid $\mathcal{M}(V)$ is uniquely determined by $[n]$ (the ground set of $\mathcal{M}(V)$) and any one of the following three objects:

• the set $\mathcal{V}^* := \{\operatorname{sign}(v) : v \in V\}$, called the covectors of $\mathcal{M}(V)$; or

• the set $\mathcal{C}^* := \{X \in \mathcal{V}^* : X \text{ has minimal nonempty support}\}$, called the cocircuits of $\mathcal{M}(V)$; or

• the function $\chi : (\begin{bmatrix} n \\ k \end{bmatrix}) \to \{0, +, -\}$ (up to multiplication by $\pm 1$), called the chirotope of $\mathcal{M}(V)$, where $\chi(I) := \operatorname{sign}(\Delta_I(V))$ for $I \in (\begin{bmatrix} n \\ k \end{bmatrix})$.

The rank of $\mathcal{M}(V)$ is $k$.

A general oriented matroid $\mathcal{M}$ is determined by its ground set $E$ (where $E$ is a totally ordered finite set), and any one of the three objects $\mathcal{V}^*(\mathcal{M}) \subseteq 2^{\{0,+,,-\}^E}$ (the covectors), $\mathcal{C}^*(\mathcal{M}) \subseteq 2^{\{0,+,,-\}^E}$ (the cocircuits), or $\chi_{\mathcal{M}} : (\begin{bmatrix} E \\ k \end{bmatrix}) \to \{0, +, -\}$ up to multiplication by $\pm 1$ (the chirotope), where $k$ is the rank of $\mathcal{M}$. (Usually one does not require that $E$ is totally ordered, but it will be essential for us here.) The bases of $\mathcal{M}$ are those $I \in (\begin{bmatrix} E \\ k \end{bmatrix})$ such that $\chi_{\mathcal{M}}(I) \neq 0$, so $\chi_{\mathcal{M}}$ assigns an orientation (either $+$ or $-$) to every basis of $\mathcal{M}$. The objects $\mathcal{V}^*(\mathcal{M})$, $\mathcal{C}^*(\mathcal{M})$, and $\chi_{\mathcal{M}}$ are characterized by certain axioms, and each can be determined from any other; see chapter 3 of [BLVS+99].

We can now begin translating the results of Section 2 to the more general framework of oriented matroids. We say that an oriented matroid of rank $k$ is *uniform* if every $k$-subset of its ground set is a basis, so that $V \in \operatorname{Gr}_{k,n}$ is generic iff $\mathcal{M}(V)$ is uniform.

**Theorem 4.2.** Suppose that $\mathcal{M}$ is an oriented matroid of rank $k$ with ground set $[n]$, and $l \ge k$.

(i) If the covectors of $\mathcal{M}$ change sign fewer than $l$ times, then $(\chi_{\mathcal{M}}(J \cup \{i\}))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $J \in (\begin{bmatrix} n \\ k-1 \end{bmatrix})$.

(ii) If $\mathcal{M}$ is uniform and $(\chi_{\mathcal{M}}(J \cup \{i\}))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $J \in (\begin{bmatrix} n \\ k \end{bmatrix})$, then the covectors of $\mathcal{M}$ change sign fewer than $l$ times.

We now describe a partial order on oriented matroids with a fixed ground set, coming from what are called *weak maps* in the literature. We use the partial order on sign vectors given by $X \leq Y$ iff $X_e = Y_e$ for all $e \in E$ such that $X_e \neq 0$ (for $X, Y \in \{0, +, -\}^E$). This also defines a partial order on chirotopes, regarded as sign vectors in $\{0, +, -\}^{\begin{bmatrix} E \\ k \end{bmatrix}}$.

**Definition 4.3 (partial order on oriented matroids; 7.7.5 of [BLVS+99]).** Let $\mathcal{M}$ and $\mathcal{N}$ be oriented matroids with ground set $E$. We say that $\mathcal{M} \leq \mathcal{N}$ if for every covector $X$ of $\mathcal{M}$, there exists a covector $Y$ of $\mathcal{N}$ with $X \leq Y$. Then $\leq$ is a partial order on oriented matroids with ground set $E$. If $\mathcal{M}$ and $\mathcal{N}$ have the same rank, then $\mathcal{M} \leq \mathcal{N}$ iff $\chi_{\mathcal{M}} \leq \pm \chi_{\mathcal{N}}$.

Note that for $V, V' \in \operatorname{Gr}_{k,n}$, we have $\mathcal{M}(V) \leq \mathcal{M}(V')$ iff $V'$ is a perturbation of $V$.

We now generalize $i \to_e j$-perturbation of subspaces to oriented matroids. Let $\mathcal{M}$ be an oriented matroid with ground set $E$. A single element extension of $\mathcal{M}$ at $a$ is an oriented matroid $\tilde{\mathcal{M}}$ with ground set $E \cup \{a\}$ and the same rank as $\mathcal{M}$, such that the covectors of $\mathcal{M}$ are precisely the restriction of covectors of $\tilde{\mathcal{M}}$ to $E$. Las Vergnas [LV78] studied single element extensions; we refer to his results as given in [BLVS+99]. For a sign vector $X \in \{0, +, -\}^E$ and $y \in \{0, +, -\}$, we let $(X, y)_a \in \{0, +, -\}^{E \cup \{a\}}$
denote the sign vector whose restriction to E is X and whose a th component is y. By 7.1.4 of [BLVS<sup>+</sup>99], there exists a unique function σ : C<sup>*</sup>(M) → {0, +, −} such that (C, σ(C))<sub>a</sub> is a cocircuit of M̄ for all cocircuits C of M. In this case, we say that M̄ is the single element extension of M at a by σ. (In general, not all functions σ : C<sup>*</sup>(M) → {0, +, −} give rise to single element extensions.)

**Definition 4.4** ($i \to \epsilon$ j-perturbation). Let $i, j \in [n]$ be distinct and $\epsilon \in \{+, -\}$. Given an oriented matroid $\mathcal{M}$ with ground set $[n]$, we define the $i \to \epsilon$ j-perturbation of $\mathcal{M}$ as the oriented matroid $\mathcal{N}$ with rank $k$ and ground set $[n]$ as follows. If $j$ is in every basis of $\mathcal{M}$, then we define $\mathcal{N} := \mathcal{M}$. Otherwise, we write $\mathcal{M}$ as the single element extension of $\mathcal{M}'$ (with ground set $[n] \setminus \{j\}$) at $j$ by $\sigma : C^*(\mathcal{M}') \to \{0, +, -\}$, and let $\mathcal{N}$ be the single element extension of $\mathcal{M}'$ at $j$ by $\sigma \circ \tau$, where $\tau : C^*(\mathcal{M}') \to \{0, +, -\}$ is given by $\tau(C) := \epsilon C_i$ for $C \in C^*(\mathcal{M}')$. (Here $(\sigma \circ \tau)(C)$ equals $\sigma(C)$ if $\sigma(C) \neq 0$, and $\tau(C)$ otherwise.) Then $\mathcal{N}$ is well-defined by 7.2.2 of [BLVS<sup>+</sup>99], and $\mathcal{M} \le \mathcal{N}$ by 7.7.8 of [BLVS<sup>+</sup>99].

We have the same desirable properties of $i \to \epsilon$ j-perturbation of oriented matroids as for subspaces.

**Lemma 4.5.** Suppose that $\mathcal{M}$ is an oriented matroid of rank $k$ with ground set $[n]$.

(i) If the covectors of $\mathcal{M}$ change sign fewer than $l$ times, then so do the covectors of the $(i+1) \to_+ i$-, $i \to_+ (i+1)$-, $1 \to_{(-1)^{l-1}} n$-, and $n \to_{(-1)^{l-1}} 1$-perturbations of $\mathcal{M}$ (for $i \in [n-1]$).

(ii) Applying the sequence of perturbations

$$2 \to 1, 3 \to 2, \dots, n \to (n-1), 1 \to n, 2 \to 1, 3 \to 2, \dots, (n-1) \to (n-2)$$

in order from left to right $n-k$ times to $\mathcal{M}$ gives a uniform oriented matroid. (Here an $i \to j$-perturbation denotes either of the $i \to \epsilon$ j-perturbations for $\epsilon \in \{+, -\}$; the sign of $\epsilon$ is not important.) Similarly, applying the sequence of perturbations

$$2 \to 1, 3 \to 2, \dots, n \to (n-1), (n-1) \to n, (n-2) \to (n-1), \dots, 1 \to 2$$

in order from left to right $n-k$ times to $\mathcal{M}$ gives a uniform oriented matroid.

(iii) If $V'$ is an $i \to \epsilon$ j-perturbation of $V \in \text{Gr}_{k,n}$, then $\mathcal{M}(V')$ is the $i \to \epsilon$ j-perturbation of $\mathcal{M}(V)$.

**Theorem 4.6.** Suppose that $\mathcal{M}$ is an oriented matroid of rank $k$ with ground set $[n]$. The covectors of $\mathcal{M}$ change sign fewer than $l$ times iff there exists a uniform $\mathcal{M}' \ge \mathcal{M}$ of rank $k$ with ground set $[n]$ such that $(\chi_{\mathcal{M}'}(J \cup \{i\}))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $J \in \binom{[n]}{k-1}$.

Explicitly, let $\mathcal{N}$ be obtained from $\mathcal{M}$ by applying the sequence of perturbations

$$2 \to_+ 1, 3 \to_+ 2, \dots, n \to_+ (n-1), 1 \to_{(-1)^{l-1}} n, 2 \to_+ 1, 3 \to_+ 2, \dots, (n-1) \to_+ (n-2)$$

in order from left to right $n-k$ times, or by applying the sequence of perturbations

$$2 \to_+ 1, 3 \to_+ 2, \dots, n \to_+ (n-1), (n-1) \to_+ n, (n-2) \to_+ (n-1), \dots, 1 \to_+ 2$$

in order from left to right $n-k$ times, so that $\mathcal{N} \ge \mathcal{M}$ is uniform. Then the following are equivalent:

(i) the covectors of $\mathcal{M}$ change sign fewer than $l$ times;

(ii) the covectors of $\mathcal{N}$ change sign fewer than $l$ times; and

(iii) $(\chi_{\mathcal{N}}(J \cup \{i\}))_{i \notin J}$ changes sign fewer than $l-k+1$ times for all $J \in \binom{[n]}{k-1}$.
Finally, we explain how to obtain the generalization of Theorem 1.1 to oriented matroids, as a consequence of these results for $l = k$. Let $\mathcal{M}$ be an oriented matroid of rank $k$ with ground set $[n]$. We say that $\mathcal{M}$ is positively oriented if every basis of $\mathcal{M}$ has the same orientation. If $\mathcal{M}$ is positively oriented, we let $\mathcal{N}$ be the uniform positively oriented matroid of rank $k$ with ground set $[n]$; then $\mathcal{N} \ge \mathcal{M}$, so the covectors of $\mathcal{M}$ change sign fewer than $k$ times by Theorem 4.6. Conversely, if the covectors of $\mathcal{M}$ change sign fewer than $k$ times, then by Theorem 4.2(i) any two bases of $\mathcal{M}$ with $k-1$ elements in common have the same orientation; it follows from the *basis exchange property* for (oriented) matroids that all bases of $\mathcal{M}$ have the same orientation. Hence we have the following corollary.

**Corollary 4.7.** An oriented matroid of rank $k$ is positively oriented iff its covectors change sign fewer than $k$ times.

We remark that since all positively oriented matroids are realizable [ARW], the forward direction follows from [ARW] and Theorem 1.1.

## References

[ARW] Federico Ardila, Felipe Rincón, and Lauren Williams. Positively oriented matroids are realizable. Preprint, http://arxiv.org/abs/1310.4159.

[BLVS$^{+99}$] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. *Oriented matroids*, volume 46 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, second edition, 1999.

[GK50] F. R. Gantmakher and M. G. Krein. *Ostsillyatsionnye matritsy i yadra i malye kolebaniya mekhanicheskikh sistem*. Gosudarstvennoye Izdatel'stvo Tekhniko-Teoreticheskoy Literatury, Moscow-Leningrad, second edition, 1950.

[Lus94] G. Lusztig. Total positivity in reductive groups. In *Lie theory and geometry*, volume 123 of *Progr. Math.*, pages 531–568. Birkhäuser Boston, Boston, MA, 1994.

[LV78] Michel Las Vergnas. Extensions ponctuelles d'une géométrie combinatoire orientée. In *Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976)*, volume 260 of *Colloq. Internat. CNRS*, pages 265–270. CNRS, Paris, 1978.

[Oh11] Suho Oh. Positroids and Schubert matroids. *J. Combin. Theory Ser. A*, 118(8):2426–2435, 2011.

[Pos] Alexander Postnikov. Total positivity, Grassmannians, and networks. Preprint, http://math.mit.edu/~apost/papers/tpgrass.pdf.

[Rie99] Konstanze Rietsch. An algebraic cell decomposition of the nonnegative part of a flag variety. *J. Algebra*, 213(1):144–154, 1999.

[SW51] I. J. Schoenberg and Anne Whitney. A theorem on polygons in $n$ dimensions with applications to variation-diminishing and cyclic variation-diminishing linear transformations. *Compositio Math.*, 9:141–160, 1951.