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.
- The weighted rook polynomial of $A$ is a weighted matching polynomial of the complete bipartite graph on the rows and columns of $A$.
- It is a Pólya frequency polynomial, so it is real-rooted with nonpositive roots.
- In Nijenhuis's signed normalization $p(-x)$ the roots are nonnegative.
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.
- [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
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
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
def nijenhuisRookPolynomial [Fintype Row] [Fintype Column]
(A : Row → Column → ℝ) : ℝ[X] :=
(weightedRookPolynomial A).comp (-X)
Rook polynomial of a finite board
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
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
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
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
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
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
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.