Lindström–Gessel–Viennot lemma and total positivity
Path matrices of networks with nonnegative weights are totally nonnegative whenever the Lindström–Gessel–Viennot cancellation works with sources and sinks in order. Applied to Toeplitz minors, this gives Pólya frequency sequences, for instance from networks of lower-bidiagonal chips.
Results
The path matrix of a finite network with weighted paths has as $(s,t)$ entry the total weight of the paths from $s$ to $t$. The Lindström–Gessel–Viennot lemma writes a minor of the path matrix, with sources $s_1<\dots<s_n$ and sinks $t_1<\dots<t_n$, as a signed sum over path families. We say the minor cancels in order if there is a notion of disjointness for pairs of paths such that two paths from $s_i$ to $t_k$ and from $s_j$ to $t_l$ with $s_i<s_j$ and $t_l<t_k$ are never disjoint, together with a weight-negating involution on the signed path families that are not pairwise disjoint, fixing only families of weight zero. Vertex-disjointness in a planar network with sources and sinks in order along the boundary is the classical example.
Theorem (total nonnegativity). Let $N$ be a finite path network over an ordered ring with nonnegative path weights. If every minor with strictly increasing row and column selections cancels in order, then the path matrix of $N$ is totally nonnegative.
Theorem (Pólya frequency sequences). Let $a=(a_k)$ be a real sequence. If each Toeplitz submatrix of $a$ with strictly increasing rows and columns is the path matrix of a network with nonnegative weights whose determinant cancels in order, then $a$ is a Pólya frequency sequence.
Theorem (chip networks). A chip is a lower-bidiagonal matrix on levels $0,\dots,N$. Let $G,K$ be words of chips with nonnegative weights such that the product matrix of $K$ is strictly lower triangular. Then the repeated-chip kernel sequence of $(G,K)$ is a Pólya frequency sequence, and the kernel row of Brändén and Saud Leite at the last level is a PF polynomial.
For a weighted quiver with finitely many vertices, the total weight of the paths of length $n$ from $a$ to $b$ is the $(a,b)$ entry of the $n$-th power of the edge-sum matrix.
Proof
The involution cancels the families that are not pairwise disjoint. A pairwise disjoint family cannot contain two paths in opposite order, so it connects $s_i$ to $t_i$ for every $i$ and contributes its nonnegative weight with sign $+1$.
References
- [Lin73] On the Vector Representations of Induced Matroids. Bulletin of the London Mathematical Society, 5(1), 85-90, 1973.
BibTeX
@article{Lindstrom1973, title = {On the Vector Representations of Induced Matroids}, volume = {5}, ISSN = {0024-6093}, url = {http://dx.doi.org/10.1112/blms/5.1.85}, DOI = {10.1112/blms/5.1.85}, number = {1}, journal = {Bulletin of the London Mathematical Society}, publisher = {Wiley}, author = {Lindstr\"{o}m, Bernt}, year = {1973}, month = mar, pages = {85–90} } - [GV85] Binomial determinants, paths, and hook length formulae. Advances in Mathematics, 58(3), 300-321, 1985.
BibTeX
@article{GesselViennot1985, doi = {10.1016/0001-8708(85)90121-5}, url2 = {https://doi.org/10.1016/0001-8708(85)90121-5}, year = {1985}, month = dec, publisher = {Elsevier {BV}}, volume = {58}, number = {3}, pages = {300--321}, author = {Ira Gessel and G{\'{e}}rard Viennot}, title = {Binomial determinants, paths, and hook length formulae}, journal = {Advances in Mathematics} }