Monotone column permanent theorem

If the columns of a real matrix $A$ are monotone, then $\operatorname{per}(zJ+A)$ is real-rooted with leading coefficient $n!$, and the multivariate column permanent is real stable.

Results

Let $A=(a_{ij})$ be a real $n\times n$ matrix and $J_n$ the all-ones matrix. The columns of $A$ are weakly decreasing if $a_{kj}\le a_{ij}$ for $i\le k$, and weakly increasing if $a_{ij}\le a_{kj}$ for $i\le k$. The column permanent of $A$ is $$ \operatorname{per}(z_j+a_{ij}) =\operatorname{per}\bigl(J_n\operatorname{diag}(z_1,\dots,z_n)+A\bigr). $$

Theorem (monotone column permanent). If the columns of $A$ are weakly decreasing or weakly increasing, then $\operatorname{per}(z_j+a_{ij})$ is real stable: it has no zero with every $z_j$ in the open upper half-plane. Consequently $\operatorname{per}(zJ_n+A)$ is nonzero and splits over $\mathbb R$. Its coefficient of $z^n$ is $n!$ for every $A$.

The decreasing case is [BHVW11]; the increasing case is the convention of the conjecture of Haglund, Ono and Wagner [HOW99], to which the decreasing case reduces by reversing the rows.

Proposition (Ferrers matrices). A Ferrers matrix is a zero-one matrix with weakly decreasing columns and weakly increasing rows. For such $A$ the two-alphabet permanent $$ \operatorname{per}\bigl(a_{ij}y_j+(1-a_{ij})x_i\bigr) $$ is real stable. If $A$ is a Ferrers matrix of size $n+1$ with $a_{n+1,n+1}=0$, this polynomial satisfies a deletion recurrence in terms of the polynomials of smaller Ferrers matrices.

Proof

Decreasing columns reduce to zero-one columns, which sort into a Ferrers matrix. Real stability of the Ferrers permanents follows by induction using the deletion recurrence. A specialization of the $x_i$ and a fractional substitution give the multivariate theorem.

References

See [HOW99]; [BHVW11].

  1. [HOW99] James Haglund, Ken Ono, & David G. Wagner. Theorems and Conjectures Involving Rook Polynomials with Only Real Zeros. Topics in number theory, 207-221, 1999.
    BibTeX
    @incollection{HaglundOnoWagner1999,
      doi = {10.1007/978-1-4613-0305-3_13},
      url = {https://doi.org/10.1007/978-1-4613-0305-3_13},
      year = {1999},
      publisher = {Springer {US}},
      pages = {207--221},
      author = {James Haglund and Ken Ono and David G. Wagner},
      title = {Theorems and Conjectures Involving Rook Polynomials with Only Real Zeros},
      booktitle = {Topics in Number Theory}
    }
  2. [BHVW11] Petter Brändén, James Haglund, Mirkó Visontai, & David G. Wagner. Proof of the monotone column permanent conjecture. Notions of positivity and the geometry of polynomials, 63-78, 2011.
    BibTeX
    @incollection{BrandenHaglundVisontaiWagner2011,
      doi = {10.1007/978-3-0348-0142-3_5},
      url2 = {https://doi.org/10.1007/978-3-0348-0142-3_5},
      year = {2011},
      publisher = {Springer Basel},
      pages = {63--78},
      author = {Petter Br{\"{a}}nd{\'{e}}n and James Haglund and Mirk{\'{o}} Visontai and David G. Wagner},
      title = {Proof of the Monotone Column Permanent Conjecture},
      booktitle = {Notions of Positivity and the Geometry of Polynomials}
    }

Definitions

  • Weakly decreasing matrix columns

    Matrix.HasWeaklyDecreasingColumnssource
    def HasWeaklyDecreasingColumns {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ) : Prop :=
      ∀ j i k, i ≤ k → A k j ≤ A i j
  • Weakly increasing matrix columns

    Matrix.HasWeaklyIncreasingColumnssource
    def HasWeaklyIncreasingColumns {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ) : Prop :=
      ∀ j i k, i ≤ k → A i j ≤ A k j
  • Multivariate column permanent

    RealRooted.Permanent.columnPermanentsource
    def columnPermanent {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) :
        MvPolynomial (Fin n) ℝ :=
      Matrix.permanent fun i j => MvPolynomial.X j + MvPolynomial.C (A i j)
  • Univariate diagonal permanent

    RealRooted.Permanent.diagonalPermanentsource
    def diagonalPermanent {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) :
        Polynomial ℝ :=
      Matrix.permanent fun i j => Polynomial.X + Polynomial.C (A i j)
  • Ferrers matrix

    Matrix.IsFerrerssource
    def IsFerrers {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) : Prop :=
      IsZeroOne A ∧ HasWeaklyDecreasingColumns A ∧
        HasWeaklyIncreasingRows A
  • Two-alphabet Ferrers permanent

    RealRooted.Permanent.ferrersPermanentsource
    def ferrersPermanent {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) :
        MvPolynomial (Sum (Fin n) (Fin n)) ℝ :=
      Matrix.permanent fun i j =>
        MvPolynomial.C (A i j) * MvPolynomial.X (Sum.inr j) +
          MvPolynomial.C (1 - A i j) * MvPolynomial.X (Sum.inl i)

Theorems

  • Ferrers deletion recurrence

    RealRooted.Permanent.ferrersPermanent_eq_recurrenceRhssource
    theorem ferrersPermanent_eq_recurrenceRhs {n : ℕ}
        {A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
        (hA : Matrix.IsFerrers A)
        (hcorner : A (Fin.last n) (Fin.last n) = 0) :
        ferrersPermanent A = ferrersRecurrenceRhs A
  • Ferrers permanents are real stable

    RealRooted.Permanent.ferrersPermanent_mvRealStablesource
    theorem ferrersPermanent_mvRealStable {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ) (hA : Matrix.IsFerrers A) :
        MvRealStable (ferrersPermanent A)
  • Decreasing-column permanent is real stableMain result

    RealRooted.Permanent.columnPermanent_mvRealStable_of_decreasingColumnssource
    theorem columnPermanent_mvRealStable_of_decreasingColumns {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ)
        (hcols : Matrix.HasWeaklyDecreasingColumns A) :
        MvRealStable (columnPermanent A)
  • Increasing-column permanent is real stable

    RealRooted.Permanent.columnPermanent_mvRealStable_of_increasingColumnssource
    theorem columnPermanent_mvRealStable_of_increasingColumns {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ)
        (hcols : Matrix.HasWeaklyIncreasingColumns A) :
        MvRealStable (columnPermanent A)
  • Decreasing-column univariate permanent is real-rooted

    RealRooted.Permanent.diagonalPermanent_ne_zero_and_splits_of_decreasingColumnssource
    theorem diagonalPermanent_ne_zero_and_splits_of_decreasingColumns {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ)
        (hcols : Matrix.HasWeaklyDecreasingColumns A) :
        diagonalPermanent A ≠ 0 ∧ (diagonalPermanent A).Splits
  • Monotone column permanent theorem

    RealRooted.Permanent.diagonalPermanent_ne_zero_and_splits_of_increasingColumnssource
    theorem diagonalPermanent_ne_zero_and_splits_of_increasingColumns {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ)
        (hcols : Matrix.HasWeaklyIncreasingColumns A) :
        diagonalPermanent A ≠ 0 ∧ (diagonalPermanent A).Splits
  • The leading coefficient of per(zJ + A) is n!

    RealRooted.Permanent.diagonalPermanent_coeff_cardsource
    theorem diagonalPermanent_coeff_card {n : ℕ}
        (A : Matrix (Fin n) (Fin n) ℝ) :
        (diagonalPermanent A).coeff n = n.factorial

Lean source RealRooted/Challenges/Matrices/MonotoneColumnPermanent.lean at revision d6670742. Formalized 2026-10-13.