Karp, Steven N. - Sign variation, the Grassmannian, and total positivity

dmtcs:2518 - Discrete Mathematics & Theoretical Computer Science, January 1, 2015, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Sign variation, the Grassmannian, and total positivity

Authors: Karp, Steven N.

The <i>totally nonnegative Grassmannian</i> is the set of $k$-dimensional subspaces $V$ of &#8477;<sup>$n$</sup> 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 <i>generic perturbation</i> of $V$ change sign fewer than $l &minus; k &plus; 1$ times. We give an algorithm which constructs such a generic perturbation. Also, we determine the <i>positroid cell</i> of each totally nonnegative $V$ from sign patterns of vectors in $V$. These results generalize to oriented matroids.


Source : oai:HAL:hal-01337834v1
Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Section: Proceedings
Published on: January 1, 2015
Submitted on: November 21, 2016
Keywords: sign variation,totally nonnegative Grassmannian,oriented matroid,positroid,Grassmann necklace,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 14 times.
This article's PDF has been downloaded 29 times.