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]; [GV85].

  1. [Lin73] Bernt Lindström. 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}
    }
  2. [GV85] Ira Gessel & Gérard Viennot. 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}
    }

Definitions

  • Index set of a Toeplitz minor

    RealRooted.StrictToeplitzMinorIndexsource
    structure StrictToeplitzMinorIndex (n : ℕ) where
      /-- The strictly increasing source rows. -/
      sourceRow : Fin n → ℕ
      /-- The strictly increasing sink columns. -/
      sinkColumn : Fin n → ℕ
      sourceRow_strictMono : StrictMono sourceRow
      sinkColumn_strictMono : StrictMono sinkColumn
  • Lower-bidiagonal chip

    RealRooted.LGV.ChipNetwork.Chipsource
    structure Chip (R : Type*) (N : ℕ) where
      /-- The weights of the diagonal transfers, indexed by the levels `0, ..., N`. -/
      diagonal : Fin (N + 1) → R
      /-- The weights of the subdiagonal transfers, indexed by `Fin N`. -/
      subdiagonal : Fin N → R
  • Matrix of a word of chips

    RealRooted.LGV.ChipNetwork.wordMatrixsource
    def wordMatrix {R : Type*} [Semiring R] (word : List (Chip R N)) :
        Matrix (Fin (N + 1)) (Fin (N + 1)) R :=
      (word.map Chip.matrix).prod
  • Repeated-chip kernel sequence

    RealRooted.LGV.RepeatedChip.kernelSequencesource
    def kernelSequence (G K : List (Chip ℝ N)) (q : ℕ) : ℝ :=
      (wordMatrix G * (wordMatrix K * wordMatrix G) ^ q) (Fin.last N) 0

Theorems

  • Path networks give totally nonnegative matricesMain result

    LGV.FinitePathNetwork.matrix_isTotallyNonneg_of_orderedCertificatessource
    theorem matrix_isTotallyNonneg_of_orderedCertificates
        {R : Type u} {ι : Type v}
        [CommRing R] [LinearOrder R] [IsStrictOrderedRing R] [PartialOrder ι]
        (N : LGV.FinitePathNetwork R ι)
        (certificate : ∀ {n : ℕ} {rows cols : Fin n → ι},
          StrictMono rows → StrictMono cols →
            OrderedCancellationCertificate (N.reindex rows cols))
        (hweight : ∀ {s t : ι} (p : N.Path s t), 0 ≤ N.weight p) :
        N.matrix.IsTotallyNonneg
  • Path networks give Pólya frequency sequences

    RealRooted.isPolyaFreqSeq_of_minorOrderedCertificatessource
    theorem isPolyaFreqSeq_of_minorOrderedCertificates
        {a : ℕ → ℝ}
        (network : ∀ {n : ℕ}, StrictToeplitzMinorIndex n →
          LGV.FinitePathNetwork ℝ (Fin n))
        (hmatrix : ∀ {n : ℕ} (I : StrictToeplitzMinorIndex n),
          (network I).matrix = I.toeplitzSubmatrix a)
        (certificate : ∀ {n : ℕ} (I : StrictToeplitzMinorIndex n),
          LGV.FinitePathNetwork.OrderedCancellationCertificate (network I))
        (hweight : ∀ {n : ℕ} (I : StrictToeplitzMinorIndex n)
          {s t : Fin n} (p : (network I).Path s t),
          0 ≤ (network I).weight p) :
        IsPolyaFreqSeq a
  • Repeated-chip kernel sequences are PF

    RealRooted.LGV.RepeatedChip.kernelSequence_isPolyaFreqSeqsource
    theorem kernelSequence_isPolyaFreqSeq
        (G K : List (Chip ℝ N))
        (hG : ∀ c ∈ G, c.IsNonnegative)
        (hK : ∀ c ∈ K, c.IsNonnegative)
        (hKstrict : ∀ i j, i.val ≤ j.val → wordMatrix K i j = 0) :
        IsPolyaFreqSeq (kernelSequence G K)
  • Repeated-chip kernel rows are PF polynomials

    RealRooted.LGV.RepeatedChip.kernelRow_isPFPolynomialsource
    theorem kernelRow_isPFPolynomial
        (G K : List (Chip ℝ N))
        (hG : ∀ c ∈ G, c.IsNonnegative)
        (hK : ∀ c ∈ K, c.IsNonnegative)
        (hKstrict : ∀ i j, i.val ≤ j.val → wordMatrix K i j = 0) :
        IsPFPolynomial
          (BrandenLeite.kernelRow (wordMatrix G) (wordMatrix K) (Fin.last N))
  • Paths of length n and powers of the edge matrix

    Quiver.Path.sum_weight_exactLength_eq_edgeSumMatrix_powsource
    theorem sum_weight_exactLength_eq_edgeSumMatrix_pow
        [Semiring R] [Fintype V] [DecidableEq V] [∀ a b : V, Fintype (a ⟶ b)]
        (w : ∀ {a b : V}, (a ⟶ b) → R) (a b : V) (n : ℕ) :
        ∑ p : ExactLength a b n, p.1.weight w = (edgeSumMatrix w ^ n) a b

Lean source RealRooted/Challenges/Matrices/LGV.lean at revision d6670742. Formalized 2026-09-17.