Weighted rook polynomials

Weighted rook polynomials of finite matrices with nonnegative entries are Pólya frequency polynomials, hence real-rooted with nonpositive roots.

A rook placement in a finite array is a set of cells, no two of which share a row or a column. For a matrix $A=(a_{rc})$, the weighted rook polynomial is $$ \sum_P \prod_{(r,c)\in P} a_{rc}\,x^{|P|}, $$ summed over rook placements $P$, the empty placement included. For a board $B$, that is, a set of cells, the ordinary rook polynomial $\sum_k r_k(B)x^k$ is the case of the $0/1$ indicator matrix of $B$.

Results

Theorem (Nijenhuis). Let $A$ be a finite matrix with nonnegative entries.

In particular, the rook polynomial of every finite board is a real-rooted Pólya frequency polynomial.

References

See [Nij76] and the rook-polynomial overview on symmetricfunctions.com.

  1. [Nij76] Albert Nijenhuis. On permanents and the zeros of rook polynomials. Journal of Combinatorial Theory, Series A, 21(2), 240-244, 1976.
    BibTeX
    @article{Nijenhuis1976,
      doi = {10.1016/0097-3165(76)90068-6},
      url2 = {https://doi.org/10.1016/0097-3165(76)90068-6},
      year = {1976},
      month = sep,
      publisher = {Elsevier {BV}},
      volume = {21},
      number = {2},
      pages = {240--244},
      author = {Albert Nijenhuis},
      title = {On permanents and the zeros of rook polynomials},
      journal = {Journal of Combinatorial Theory,  Series A}
    }

Definitions

  • Rook placement

    RealRooted.Rook.IsRookPlacementsource
    def IsRookPlacement (P : Finset (Row × Column)) : Prop :=
      ∀ ⦃x⦄, x ∈ P → ∀ ⦃y⦄, y ∈ P → x ≠ y →
        x.1 ≠ y.1 ∧ x.2 ≠ y.2
  • Weighted rook polynomial

    RealRooted.Rook.weightedRookPolynomialsource
    def weightedRookPolynomial [Fintype Row] [Fintype Column]
        (A : Row → Column → ℝ) : ℝ[X] := by
      classical
      exact ∑ P ∈ (Finset.univ.filter fun P : Finset (Row × Column) ↦
          IsRookPlacement P),
        (∏ x ∈ P, C (A x.1 x.2)) * X ^ P.card
  • Nijenhuis's signed rook polynomial

    RealRooted.Rook.nijenhuisRookPolynomialsource
    def nijenhuisRookPolynomial [Fintype Row] [Fintype Column]
        (A : Row → Column → ℝ) : ℝ[X] :=
      (weightedRookPolynomial A).comp (-X)
  • Rook polynomial of a finite board

    RealRooted.Rook.rookPolynomialsource
    def rookPolynomial [Fintype Row] [Fintype Column]
        [DecidableEq Row] [DecidableEq Column]
        (B : Finset (Row × Column)) : ℝ[X] :=
      weightedRookPolynomial fun r c ↦ if (r, c) ∈ B then 1 else 0

Theorems

  • Rook polynomials are bipartite matching polynomials

    RealRooted.Rook.weightedRookPolynomial_eq_weightedMatchingPolynomialByEdgessource
    theorem weightedRookPolynomial_eq_weightedMatchingPolynomialByEdges
        [Fintype Row] [Fintype Column]
        (A : Row → Column → ℝ) :
        weightedRookPolynomial A =
          Graph.weightedMatchingPolynomialByEdges
            (_root_.completeBipartiteGraph Row Column) (matrixEdgeWeight A)
  • Weighted rook polynomials are real-rootedMain result

    RealRooted.Rook.weightedRookPolynomial_splitssource
    theorem weightedRookPolynomial_splits [Fintype Row] [Fintype Column]
        (A : Row → Column → ℝ) (hA : ∀ r c, 0 ≤ A r c) :
        (weightedRookPolynomial A).Splits
  • The signed rook polynomial has nonnegative roots

    RealRooted.Rook.nijenhuisRookPolynomial_roots_nonnegsource
    theorem nijenhuisRookPolynomial_roots_nonneg
        [Fintype Row] [Fintype Column]
        (A : Row → Column → ℝ) (hA : ∀ r c, 0 ≤ A r c) :
        ∀ z ∈ (nijenhuisRookPolynomial A).roots, 0 ≤ z
  • Rook polynomials of boards are real-rooted

    RealRooted.Rook.rookPolynomial_splitssource
    theorem rookPolynomial_splits [Fintype Row] [Fintype Column]
        [DecidableEq Row] [DecidableEq Column]
        (B : Finset (Row × Column)) :
        (rookPolynomial B).Splits
  • Nonnegative weighted rook polynomials are Pólya frequency

    RealRooted.Rook.weightedRookPolynomial_isPFPolynomialsource
    theorem weightedRookPolynomial_isPFPolynomial [Fintype Row] [Fintype Column]
        (A : Row → Column → ℝ) (hA : ∀ r c, 0 ≤ A r c) :
        IsPFPolynomial (weightedRookPolynomial A)
  • Rook polynomials of finite boards are Pólya frequency

    RealRooted.Rook.rookPolynomial_isPFPolynomialsource
    theorem rookPolynomial_isPFPolynomial [Fintype Row] [Fintype Column]
        [DecidableEq Row] [DecidableEq Column]
        (B : Finset (Row × Column)) :
        IsPFPolynomial (rookPolynomial B)

Lean source RealRooted/Challenges/PolyaFrequency/Nijenhuis.lean at revision d6670742. Formalized 2026-09-26.