Combinatorial formulas for -coordinates in a totally
nonnegative Grassmannian, extended abstract, extended
abstract

Kelli Talaska

► To cite this version:

Kelli Talaska. Combinatorial formulas for -coordinates in a totally nonnegative Grassmannian, extended abstract, extended abstract. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.825-832, 10.46298/dmtcs.2706 . hal-01185398

HAL Id: hal-01185398

https://inria.hal.science/hal-01185398

Submitted on 20 Aug 2015

**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
Combinatorial formulas for $\mathcal{I}$-coordinates
in a totally nonnegative Grassmannian,
extended abstract

Kelli Talaska

Department of Mathematics, University of Michigan, Ann Arbor, MI 48109, USA

Postnikov constructed a decomposition of a totally nonnegative Grassmannian $(Gr_{kn})_{\ge 0}$ into positroid cells. We provide combinatorial formulas that allow one to decide which cell a given point in $(Gr_{kn})_{\ge 0}$ belongs to and to determine affine coordinates of the point within this cell. This simplifies Postnikov's description of the inverse boundary measurement map and generalizes formulas for the top cell given by Speyer and Williams. In addition, we identify a particular subset of Plücker coordinates as a totally positive base for the set of non-vanishing Plücker coordinates for a given positroid cell.

**Keywords:** positroid, totally nonnegative Grassmannian, Le-diagram

Postnikov [4] has described a cell decomposition of a totally nonnegative Grassmannian into positroid cells, which are indexed by $\mathcal{I}$-diagrams; this decomposition is analogous to the matroid stratification of a real Grassmannian given by Gel'fand, Goresky, MacPherson, and Serganova [2]. Postnikov also introduced a parametrization of each positroid cell using a collection of parameters which we call $\mathcal{I}$-coordinates.

In this extended abstract, we give an informal description of the main results of [8], in which the reader will find rigorous formulations and proofs. Specifically, we give an explicit criterion for determining which positroid cell contains a given point in a totally nonnegative Grassmannian and explicit combinatorial formulas for the $\mathcal{I}$-coordinates of a point. This generalizes the formulas of Speyer and Williams given for the top dimensional positroid cell [5], and provides a simpler description of Postnikov's inverse boundary measurement map, which was given recursively in [4]. For a fixed positroid cell, our formulas are written in terms of a minimal set of Plücker coordinates, and this minimal set forms a totally positive base (in the sense of Fomin and Zelevinsky [1]) for the set of Plücker coordinates which do not vanish on the specified cell.

# 1 Positroid stratification and the boundary measurement map

In this section, we review Postnikov's positroid stratification of a totally nonnegative Grassmannian and boundary measurement map.

Let $Gr_{kn}$ denote the Grassmannian of $k$-dimensional subspaces of $\mathbb{R}^n$. A point $x \in Gr_{kn}$ can be described by a collection of (projective) Plücker coordinates $(P_J(x))$, indexed by the $k$-element subsets
$J \subset [n]$. The totally nonnegative Grassmannian $(\mathrm{Gr}_{kn})_{\ge 0}$ is the subset of points $x \in \mathrm{Gr}_{kn}$ such that all Plücker coordinates $P_J(x)$ can be chosen to be simultaneously nonnegative.

In [2], the authors gave a decomposition of the Grassmannian $\mathrm{Gr}_{kn}$ into *matroid strata*. More precisely, for a matroid $\mathcal{M} \subseteq \binom{[n]}{k}$, let $S_{\mathcal{M}}$ denote the subset of points $x \in \mathrm{Gr}_{kn}$ such that $P_J(x) \neq 0$ if and only if $J \in \mathcal{M}$. In particular, each possible vanishing pattern of Plücker coordinates is given by a unique (realizable) matroid $\mathcal{M}$. In [4], Postnikov studies a natural analogue of the matroid stratification for the totally nonnegative Grassmannian, a decomposition into disjoint *positroid cells* taking the form $(S_{\mathcal{M}})_{\ge 0} = S_{\mathcal{M}} \cap (\mathrm{Gr}_{kn})_{\ge 0}$.

**Definition 1.1.** A $\mathcal{J}$-diagram is a partition $\lambda$ together with a filling of the boxes of the Young diagram of $\lambda$ with entries 0 and + satisfying the $\mathcal{J}$-property: there is no 0 which has a + above it (in the same column) and a + to its left (in the same row).

Replacing the boxes labeled + in a $\mathcal{J}$-diagram with positive real numbers, called $\mathcal{J}$-coordinates, we obtain a $\mathcal{J}$-tableau. Let $\mathcal{T}_L$ denote the set of $\mathcal{J}$-tableaux whose vanishing pattern is determined by the $\mathcal{J}$-diagram $L$. Note that $\mathcal{T}_L$ is an affine space whose dimension is equal to the number of “+” entries in $L$, which we denote by $|L|$.

For a box $B$ in $\lambda$, we let $L_B$ and $T_B$ denote the labels of the box $B$ in the $\mathcal{J}$-diagram $L$ and the $\mathcal{J}$-tableau $T$, respectively.

In the positroid cell decomposition of $(\mathrm{Gr}_{kn})_{\ge 0}$ given in [4], the positroid cells are indexed by $\mathcal{J}$-diagrams $L$ which fit inside a $k \times (n-k)$ rectangle. Further, the positroid corresponding to a fixed $\mathcal{J}$-diagram $L$ is parametrized by the $\mathcal{J}$-tableaux $T \in \mathcal{T}_L$, i.e., those with vanishing pattern given by $L$.

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** The $\mathcal{J}$-tableau $T$ and $\Gamma$-network $N_T$ for a point in $(Gr_{5,12})_{\ge 0}$. We have shape $\lambda = (7, 7, 7, 6, 4)$ and boundary sources $I = \{1, 2, 3, 5, 8\}$.</figcaption></figure>

The parametrization described below is a special case of Postnikov's boundary measurement map. To give a formula for this parametrization, we need to introduce certain planar networks, called $\Gamma$-networks, which are in bijection with $\mathcal{J}$-tableaux. As shown in Figure 1, given a $\mathcal{J}$-tableau $T$, we start with a boundary disk of shape $\lambda$, draw a hook for each positive entry $L_B$, and give the resulting face under that
hook the weight $L_B$. Further, if $T$ has an empty row or column, we place an isolated vertex on the east or south boundary of the disk. All edges are directed from east to west or north to south. We now have one *boundary source* for each row of $\lambda$ and one *boundary sink* for each column of lambda. Let $I$ denote the set of boundary sources.

In the special case of $\Gamma$-networks, the definition of Postnikov's map given in [4] can be viewed as an instance of the classical formula of Lindström [3]. This formula is usually given in terms of weights of edges; we apply Postnikov's transformation from edge weights to face weights [4] to obtain the following restatement of his definition.

**Definition 1.2.** For each $\mathbb{J}$-diagram $L$ which fits in a $k \times (n-k)$ rectangle, the *boundary measurement map* $\text{Meas}_L : \mathbb{T}_L \to (\text{Gr}_{kn})_{\ge 0}$ is defined by

$$P_J(\text{Meas}_L(T)) = \sum_{A \in \mathcal{A}_J(N_T)} \text{wt}(A), \text{ where}$$

* $N_T$ is the $\Gamma$-network corresponding to the $\mathbb{J}$-tableau $T$, and its boundary source set is labeled by $I$,

* $\mathcal{A}_J(N_T)$ is the collection of non-intersecting path families $A = \{A_i\}_{i \in I}$ in $N_T$ from the boundary sources $I$ to the boundary destinations $J$,

* $\text{wt}(A) = \prod_{i \in I} \text{wt}(A_i)$, and

* the weight $\text{wt}(A_i)$ of a path $A_i$ in the family $A$ is the product of the weights of the faces of $N_T$ which lie southeast of $A_i$.

For a $\mathbb{J}$-diagram $L$, let $G_L$ be the corresponding $\Gamma$-graph. Let us define the set $M_L \subseteq \binom{[n]}{k}$ by the condition that $J \in M_L$ if and only if there exists a non-intersecting path collection in $G_L$ with sources $I$ and destinations $J$. It can be shown that $M_L$ has the structure of a matroid, but this is not necessary for our purposes. Further, it is easily verified that for distinct $\mathbb{J}$-diagrams $L$ and $L^*$, we have $M_L \neq M_{L^*}$.

**Theorem 1.3.** [4] For each $\mathbb{J}$-diagram $L$ which fits in a $k \times (n-k)$ rectangle, the map $\text{Meas}_L : \mathbb{T}_L \to (\text{Gr}_{kn})_{\ge 0}$ is injective, and the image $\text{Meas}_L(\mathbb{T}_L)$ is exactly the positroid cell $(S_{M_L})_{\ge 0}$.

These positroid cells are pairwise disjoint, and the union $\cup_L (S_{M_L})_{\ge 0}$, taken over all $\mathbb{J}$-diagrams $L$ which fit inside the $k \times (n-k)$ rectangle, is the entire totally nonnegative Grassmannian $(\text{Gr}_{kn})_{\ge 0}$. Each positroid cell $(S_{M_L})_{\ge 0}$ is a topological cell; that is, $(S_{M_L})_{\ge 0}$ is isomorphic to $\mathbb{R}^{|L|}$, where $|L|$ is the number of “+” entries in $L$. Thus, the positroid cells form a cell decomposition of $(\text{Gr}_{kn})_{\ge 0}$.

In Postnikov's work [4], this result is proved by giving a recursive algorithm for finding the $\mathbb{J}$-tableau $T$ corresponding to a given point in $(\text{Gr}_{kn})_{\ge 0}$. In [8], we obtain explicit combinatorial formulas solving the same problem. This is done in two stages. First, we give an explicit rule for determining which positroid cell contains a given point. Next, we give two combinatorial formulas for the inverse of each particular map $\text{Meas}_L$ (i.e., formulas for the corresponding $\mathbb{J}$-coordinates) in terms of the relevant Plücker coordinates.
## 2 Determining the positroid cell of a point in $(\mathrm{Gr}_{kn})_{\ge 0}$

In this section, we give an explicit formula for the $\mathbb{I}$-tableau $L(x)$ that determines which positroid cell $(S_{\mathcal{M}_L})_{\ge 0}$ a given point $x \in (\mathrm{Gr}_{kn})_{\ge 0}$ belongs to. Let $x \in (\mathrm{Gr}_{kn})_{\ge 0}$ be given by its Plücker coordinates

$$ (P_J(x) : J \in \binom{[n]}{k}). $$

Order the $k$-subsets of $[n]$ lexicographically. That is, a $k$-subset $A = \{a_1 < a_2 < \cdots < a_k\}$ is less than or equal to a $k$-subset $B = \{b_1 < b_2 < \cdots < b_k\}$ if at the smallest index $m$ for which $a_m \neq b_m$, we have $a_m < b_m$.

Set $\mathcal{M}(x) = \{J \in \binom{[n]}{k} : P_J(x) \neq 0\}$. Let $I = \{i_1 < i_2 < \cdots < i_k\}$ be the lexicographically minimum set in $\mathcal{M}(x)$. Let $\lambda(x)$ be the partition in the $k \times (n-k)$ rectangle whose southeastern border is given by the path from the northeast corner of the $k \times (n-k)$ rectangle to its southwest corner which has edges to the south in positions $I$ and edges to the west in positions $[n] \setminus I$. Then $\lambda(x)$ is the shape of the $\mathbb{I}$-diagram corresponding to $x$.

Next, let $A_{r,c} = \{1, 2, \dots, i_r\} \cup \{j_c, j_c + 1, \dots, n\}$. As an intermediate step, we set $M'(B) = \text{lexmax}\{J \in \mathcal{M}(x) : J \cap A_{r,c} = I \cap A_{r,c}\}$. In plain language, this says that we are taking the maximum over sets $J$ which contain all of the sources outside the open interval from $i_r$ to $j_c$ and none of the sinks, i.e., those sets whose interesting behavior happens inside the interval. This lexicographically maximal set gives the destinations of the non-intersecting path collection which is nested as far northwest as possible (strictly) under the hook along row $r$ and column $c$.

Let $M(B) = (M'(B) \setminus \{i_r\}) \cup \{j_c\}$. This corresponds to adding the hook along row $r$ and column $c$ to the path collection above.

**Theorem 2.1.** For $x \in (\mathrm{Gr}_{kn})_{\ge 0}$. Then the filling of $\lambda(\mathcal{M}(x))$ given by

$$ L(x)_B = \begin{cases} 0 & \text{if } P_{M(B)}(x) = 0; \\ + & \text{if } P_{M(B)}(x) \neq 0. \end{cases} $$

is a $\mathbb{I}$-diagram, and $x$ lies in the positroid cell $(S_{\mathcal{M}_L})_{\ge 0}$.

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** The $\Gamma$-graph of an example in $(\mathrm{Gr}_{5,12})_{\ge 0}$ and the path families corresponding to $M'((2, 6), \mathcal{M}_L)$ and $M((2, 6), \mathcal{M}_L)$.</figcaption></figure>
**Example 2.2.** On the left in Figure 2, we have the $\Gamma$-graph of the example in Figure 1. We see that $M'((2, 6), \mathcal{M}_L) = \{1, 2, 7, 9, 10\}$, corresponding to the solid path collection on the right in Figure 2. Adding in the potential (dotted) hook from $i_2 = 2$ to $j_6 = 11$, we have $M((2, 6), \mathcal{M}_L) = \{1, 7, 9, 10, 11\}$. Since this hook does not occur in the $\Gamma$-graph, we must have $P_{M((2,6),\mathcal{M}_L)}(x) = 0$ for this point.

### 3 The $\mathbb{J}$-tableau associated with a point in $(S_{\mathcal{M}_L})_{\ge 0}$

In Postnikov’s original work, the map from $(\mathrm{Gr}_{kn})_{\ge 0}$ to $\bigcup_L \mathbf{T}_L$ is given recursively. In this section, we provide an explicit description of that map. More precisely, given a point $x \in (S_{\mathcal{M}_L})_{\ge 0}$, we give combinatorial formulas for the entries of the parametrizing $\mathbb{J}$-tableau, which we call $\mathbb{J}$-coordinates for $x$.

Informally, for a directed path $W$ in a $\Gamma$-graph, we let $\mathcal{OC}(W)$ index the boxes where $W$ turns to the south, and $\mathcal{IC}(W)$ index the boxes where $W$ turns to the west, as in Figure 3. We call these boxes outer corners and inner corners, respectively.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Finding the outer corners (marked “oc”) and the inner corners (marked “ic”) of the two paths in bold.</figcaption></figure>

For a face $F = F(B)$ with the box $B$ in its northwest corner, let $U_F$ be the unique hook which determines the northwest boundary of $F$, and let $D_F$ be the unique path which has the same endpoints as $U_F$ and determines the southeast boundary of $F$. (If $F$ touches the boundary of the disk, $D_F$ may consist of a union of non-intersecting paths.)

**Definition 3.1.** For any two faces $F_1 = F(B_1)$ and $F_2 = F(B_2)$ of $G_L$, we have

$$ \mu_L(F_1, F_2) = \begin{cases} 1 & \text{if } F_1 = F_2 \text{ or } B_2 \in \mathcal{IC}(D_{F_1}) \\ -1 & \text{if } B_2 \in \mathcal{OC}(D_{F_1}) \\ 0 & \text{otherwise.} \end{cases} $$

**Theorem 3.2.** Suppose $x \in (S_{\mathcal{M}_L})_{\ge 0}$. Then the $\mathbb{J}$-coordinates of $x$ are the entries of the $\mathbb{J}$-tableau $T(x) \in \mathbf{T}_L$ defined below. That is, $\mathrm{Meas}_L(T(x)) = x$, and $T(x)$ is the unique $\mathbb{J}$-tableau whose image under $\mathrm{Meas}_L$ is $x$.

$$ T(x)_B = \begin{cases} 0 & \text{if } P_{M(B)}(x) = 0; \\ \prod_{L_C = +} \left( \frac{P_{M(C)}(x)}{P_{M'(C)}(x)} \right)^{\mu(B,C)} & \text{if } P_{M(B)}(x) \neq 0. \end{cases} $$
## 4 J-coordinates of a positroid cell in terms of a minimal set of Plücker coordinates

By Theorem 1.3, the dimension of a positroid cell $(S_{M_L})_{\ge 0}$ is $|L|$, the number of “+” entries in the corresponding J-diagram $L$. However, finding the J-coordinates of a point $x \in (S_{M_L})_{\ge 0}$ via equation (4.1) may require roughly twice this many Plücker variables. In this section, we give a formula for the map from $(S_{M_L})_{\ge 0}$ to $T_L$, using precisely $|L|$ Plücker variables. This formula is, of course, equivalent to our first formula modulo Plücker relations, but we now use exactly the desired number of parameters.

Suppose $x \in (S_{M_L})_{\ge 0}$ and $\mathrm{Meas}_L(T) = x$. As in the previous section, let $U_F$ and $D_F$ denote paths determining the upper and lower boundaries of the face $F$. Let $U'_F$ and $D'_F$ be the northwest-most paths lying strictly southeast of $U_F$ and $D_F$, respectively. (Again, it is possible that these are unions of disjoint paths.)

For a path $W$ in a $\Gamma$-network $N$ and a box $B$ in $\lambda$, we set

$$ \varepsilon_W(B) = \begin{cases} 1 & \text{if } B \in \mathcal{OC}(W); \\ -1 & \text{if } B \in \mathcal{IC}(W); \\ 0 & \text{otherwise.} \end{cases} $$

**Theorem 4.1.** Suppose $x \in (S_{M_L})_{\ge 0}$ and $\mathrm{Meas}_L(T) = x$. Then the J-coordinates of $x$ may be written in the alternate form

$$ T_B = \begin{cases} 0 & \text{if } P_{M(B)}(x) = 0; \\ \prod_{L_C=+} (P_{M(C)}(x))^{\varepsilon(C)} & \text{if } P_{M(B)}(x) \neq 0, \end{cases} $$

$$ \text{where } \varepsilon(C) = [\varepsilon_{U_F}(C) - \varepsilon_{U'_F}(C)] - [\varepsilon_{D_F}(C) - \varepsilon_{D'_F}(C)]. $$

While this formula may look complicated, it is very easy to use in practice: we simply trace out four easily defined paths, keeping track of where they turn.

The following corollary uses the *totally positive bases* of [1].

**Corollary 4.2.** *The set of Plücker coordinates*

$$ \mathcal{P}_L = \{P_{M(B)} : L_B = +\} $$

forms a totally positive base for the non-vanishing Plücker coordinates $\{P_J : J \in M_L\}$ of the positroid cell $(S_{M_L})_{\ge 0}$. That is, every Plücker coordinate $P_J$ with $J \in M_L$ can be written as a subtraction-free rational expression (i.e., a ratio of two polynomials with nonnegative integer coefficients) in the elements of $\mathcal{P}_L$, and $\mathcal{P}_L$ is a minimal set (with respect to inclusion) with this property. Further, each $P_J$ with $J \in M_L$ is a *Laurent polynomial* in the elements of $\mathcal{P}_L$, with nonnegative coefficients.

## Acknowledgements

The author was supported by NSF Grants DMS-0502170 and DMS-0555880. The author would like to thank Sergey Fomin and Lauren Williams for many helpful conversations and an anonymous FPSAC reviewer for useful comments on an early version of the manuscript.
References

[1] S. Fomin and A. Zelevinsky, Double Bruhat cells and total positivity, J. Amer. Math. Soc. 12 (1999), no. 2, 335-380.

[2] I. M. Gel'fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. in Math. 63 (1987), no. 3, 301-316.

[3] B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85-90.

[4] A. Postnikov, Total positivity, Grassmannians, and networks, version of October 17, 2007, http://math.mit.edu/~apost/papers.html.

[5] D. Speyer and L. Williams, The tropical totally positive Grassmannian, J. Algebraic Combin. 22 (2005), no. 2, 189-210.

[6] R. Stanley, *Enumerative Combinatorics, Volume I*, Cambridge University Press, 1997.

[7] K. Talaska, A formula for Plücker coordinates associated with a planar network, Int. Math. Res. Not. IMRN, (2008), article ID rnn081.

[8] K. Talaska, Combinatorial formulas for I-coordinates in a totally nonnegative Grassmannian, arXiv:0812.0640v2.

[9] L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005), no. 2, 319-342.