Schur elementary-coordinate substitutions

Replacing one elementary symmetric function $e_r$ by $e_r+t$ in the dual Jacobi–Trudi determinant of a skew Schur function, evaluated at a nonnegative alphabet, gives a polynomial in $t$ with only real zeros. A parity condition on the positions where $e_r$ occurs decides whether the zeros are negative or positive.

Results

For a finite alphabet $\alpha$ let $e_m(\alpha)$ be the coefficient of $x^m$ in $\prod_i(1+\alpha_i x)$, with $e_m=0$ for $m<0$. For weakly decreasing column heights $h=\lambda'$ and $k=\mu'$ (the shorter list padded with zeros to a common length $n$), set $a_i=h_i-i$, $b_j=k_j-j$, and for $r\in\mathbb Z$ $$ M_{ij}=e_{a_i-b_j}(\alpha),\qquad V_{ij}=\mathbf 1_{a_i=b_j+r},\qquad \Phi_{\lambda/\mu,r}(t;\alpha)=\det(M+tV), $$ with indices from $0$. Here $\det M=s_{\lambda/\mu}(\alpha)$ in dual Jacobi–Trudi form, and $\Phi$ replaces $e_r$ by $e_r+t$ in every position with $a_i=b_j+r$, also when $r$ exceeds the number of letters.

Theorem. Let $\alpha$ be a finite alphabet of nonnegative reals with $p$ positive letters, let $h,k$ be weakly decreasing with $k_i\le h_i\le k_i+p$, and let $r\in\mathbb Z$. Then $M$ is totally nonnegative and $\det M>0$. If $i+j$ is even whenever $a_i=b_j+r$, then $\Phi_{\lambda/\mu,r}$ is a nonzero Pólya frequency polynomial with only real, strictly negative zeros (constants and empty shapes included). If $i+j$ is odd whenever $a_i=b_j+r$, then $\Phi_{\lambda/\mu,r}$ is nonzero and real-rooted with only strictly positive zeros.

Theorem (consecutive shapes). Under the hypotheses above with $n+1$ columns and even parity, the shape $(\lambda/\mu)^-$ with its first column removed satisfies $\Phi_{(\lambda/\mu)^-,r}\ll\Phi_{\lambda/\mu,r}$.

Theorem (rectangles). Let $\alpha$ have at least $r$ positive letters, let $j\ge0$, and put $$ F_n(t)=\det\Bigl(e_{r-u+v}(\alpha)+(-1)^{r+j}\,t\,\mathbf 1_{r-u+v=j}\Bigr)_{u,v=0}^{n-1}, \qquad F_0=1. $$ Then every $F_n$ is nonzero and real-rooted with strictly negative zeros, and $F_n\ll F_{n+1}$ for all $n\ge0$, with no parity condition on $r$ or $j$.

Further consequences: let $\lambda^{(m)}/\mu^{(m)}$ repeat each column $m$ times, with $r\in\mathbb N$. If $h_i+k_j+r$ is even for all $i,j$, every $\Phi_{\lambda^{(m)}/\mu^{(m)},r}$ is nonzero and real-rooted with strictly negative zeros, and if it is odd for all $i,j$, with strictly positive zeros. If $h_i=k_i+r$ for all $i$ and $r\le p$, then $\Phi=\det(M+tI)$ and all stretches have strictly negative real zeros with no parity condition. If $k_i\le h_i$ and $2h_i\le 2k_i+p$, doubling both height lists gives nonzero real-rooted polynomials with strictly negative zeros for the moving coordinate $2r$, for every $r,m\ge0$.

Theorem (pencils). Let $A,B$ be totally nonnegative matrices of size $n+1$ with $\det A>0$, and let $\mathrm{cb}(B)_{ij}=(-1)^{i+j}B_{ij}$. Let $A',B'$ be obtained by removing the first row and column and suppose $\det A'>0$. Then $$ \det(A'+t\,\mathrm{cb}(B'))\ll\det(A+t\,\mathrm{cb}(B)). $$ The same holds when the last row and column are removed instead, if the resulting section of $A$ has positive determinant; $B$ need be neither triangular nor invertible. Consequently, if $a_i,b_j$ are strictly decreasing, $M$ is totally nonnegative with $\det M>0$ and $i+j$ is even whenever $a_i=b_j+r$, then $\det(M+tV)$ is a Pólya frequency polynomial.

Proof

The matrix $V$ is an ordered submatrix of the identity, hence totally nonnegative, and even parity makes it invariant under the checkerboard sign change, so the pencil theorem applies. Positivity of $\det M$ follows because, for $a_i>0$, every minor of the Toeplitz matrix of $\prod_i(x+a_i)$ with strictly increasing rows and columns inside its band is strictly positive. For odd parity we reflect $t\mapsto-t$.

References

C.-K. Li and R. Mathias, Interlacing Inequalities for Totally Nonnegative Matrices.

Definitions

  • Positions affected by an elementary-coordinate substitution

    RealRooted.Schur.activeMatrixsource
    def activeMatrix {n : ℕ} (a b : Fin n → ℤ) (r : ℤ) :
        Matrix (Fin n) (Fin n) ℝ :=
      fun i j ↦ if a i = b j + r then 1 else 0
  • Elementary-coordinate specialization defined by a determinant

    RealRooted.Schur.elementarySubstitutionsource
    noncomputable def elementarySubstitution {ι : Type*} {n : ℕ}
        (s : Finset ι) (α : ι → ℝ) (h k : Fin n → ℕ) (r : ℤ) : ℝ[X] :=
      det ((elementaryMatrix s α h k).map C + (X : ℝ[X]) •
        (activeMatrix (fun i => (columnIndex h i : ℤ))
          (fun j => (columnIndex k j : ℤ)) r).map C)
  • Signed rectangular elementary-coordinate deformation

    RealRooted.Schur.rectangularElementarySubstitutionsource
    noncomputable def rectangularElementarySubstitution {ι : Type*} (s : Finset ι)
        (a : ι → ℝ) (r j n : ℕ) : ℝ[X] :=
      checkerboardPencil (elementaryMatrix s a (fun _ : Fin n => r) (fun _ => 0))
        (activeMatrix (fun i => (columnIndex (fun _ : Fin n => r) i : ℤ))
          (fun i => (columnIndex (fun _ : Fin n => 0) i : ℤ)) j)
  • Horizontal stretching by repetition of column heights

    RealRooted.Schur.repeatColumnssource
    def repeatColumns {n : ℕ} (h : Fin n → ℕ) (m : ℕ) : Fin (n * m) → ℕ :=
      h ∘ unstretchColumn m

Theorems

  • Elementary skew Jacobi–Trudi matrices are totally nonnegativeRealRooted original

    RealRooted.Schur.elementaryMatrix_isTotallyNonnegsource
    theorem elementaryMatrix_isTotallyNonneg {ι : Type*} {n : ℕ}
        (s : Finset ι) (α : ι → ℝ) (hα : ∀ i ∈ s, 0 ≤ α i)
        {h k : Fin n → ℕ} (hh : Antitone h) (hk : Antitone k) :
        (elementaryMatrix s α h k).IsTotallyNonneg
  • Parity-compatible specialization assuming positive constant determinantRealRooted original

    RealRooted.Schur.elementarySubstitution_isPFPolynomialsource
    theorem elementarySubstitution_isPFPolynomial {ι : Type*} {n : ℕ}
        (s : Finset ι) (α : ι → ℝ) (hα : ∀ i ∈ s, 0 ≤ α i)
        {h k : Fin n → ℕ} (hh : Antitone h) (hk : Antitone k) (r : ℤ)
        (hdet : 0 < (elementaryMatrix s α h k).det)
        (hpar : ∀ i j, (columnIndex h i : ℤ) = columnIndex k j + r →
          Even (i.val + j.val)) :
        IsPFPolynomial (elementarySubstitution s α h k r)
  • Corner-section interlacing for general totally nonnegative pencilsRealRooted original

    Matrix.IsTotallyNonneg.strictInterl_checkerboardPencil_succsource
    theorem IsTotallyNonneg.strictInterl_checkerboardPencil_succ {n : ℕ}
        {A B : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
        (hA : A.IsTotallyNonneg) (hB : B.IsTotallyNonneg) (hdet : 0 < A.det)
        (hminor : 0 < (A.submatrix Fin.succ Fin.succ).det) :
        RealRooted.StrictInterl
          (checkerboardPencil (A.submatrix Fin.succ Fin.succ)
            (B.submatrix Fin.succ Fin.succ)) (checkerboardPencil A B)
  • Conditional parity criterion for a totally nonnegative determinant pencilRealRooted original

    RealRooted.Schur.isPFPolynomial_det_activesource
    theorem isPFPolynomial_det_active {n : ℕ} {M : Matrix (Fin n) (Fin n) ℝ}
        {a b : Fin n → ℤ} {r : ℤ} (hM : M.IsTotallyNonneg) (hdet : 0 < M.det)
        (ha : StrictAnti a) (hb : StrictAnti b)
        (hpar : ∀ i j, a i = b j + r → Even (i.val + j.val)) :
        RealRooted.IsPFPolynomial
          (Matrix.det (M.map C + (X : ℝ[X]) • (activeMatrix a b r).map C))
  • Positive constant determinant from the number of positive lettersRealRooted original

    RealRooted.Schur.det_elementaryMatrix_pos_of_nonnegsource
    theorem det_elementaryMatrix_pos_of_nonneg {ι : Type*} {n : ℕ} (s : Finset ι)
        (a : ι → ℝ) (ha : ∀ i ∈ s, 0 ≤ a i)
        {h k : Fin n → ℕ} (hh : Antitone h) (hk : Antitone k)
        (hkh : ∀ i, k i ≤ h i)
        (hsize : ∀ i, h i ≤ k i + (s.filter fun j => 0 < a j).card) :
        0 < (elementaryMatrix s a h k).det
  • Real-rooted dual Jacobi–Trudi specialization under alphabet-size and parity hypothesesMain resultRealRooted original

    RealRooted.Schur.elementarySubstitution_isRealRootedsource
    theorem elementarySubstitution_isRealRooted :
        elementarySubstitution s a h k r ≠ 0 ∧ (elementarySubstitution s a h k r).Splits
  • All roots of the parity-compatible specialization are strictly negativeRealRooted original

    RealRooted.Schur.roots_elementarySubstitution_negsource
    theorem roots_elementarySubstitution_neg :
        ∀ x ∈ (elementarySubstitution s a h k r).roots, x < 0
  • Consecutive leading sections of general TN pencils interlaceRealRooted original

    Matrix.IsTotallyNonneg.strictInterl_checkerboardPencil_castSuccsource
    theorem IsTotallyNonneg.strictInterl_checkerboardPencil_castSucc {n : ℕ}
        {A B : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
        (hA : A.IsTotallyNonneg) (hB : B.IsTotallyNonneg) (hdet : 0 < A.det)
        (hminor : 0 < (A.submatrix Fin.castSucc Fin.castSucc).det) :
        RealRooted.StrictInterl
          (checkerboardPencil (A.submatrix Fin.castSucc Fin.castSucc)
            (B.submatrix Fin.castSucc Fin.castSucc)) (checkerboardPencil A B)
  • Real-rootedness under odd active-position parityRealRooted original

    RealRooted.Schur.elementarySubstitution_isRealRooted_of_oddsource
    theorem elementarySubstitution_isRealRooted_of_odd :
        elementarySubstitution s a h k r ≠ 0 ∧ (elementarySubstitution s a h k r).Splits
  • Strictly positive roots under odd active-position parityRealRooted original

    RealRooted.Schur.roots_elementarySubstitution_pos_of_oddsource
    theorem roots_elementarySubstitution_pos_of_odd :
        ∀ x ∈ (elementarySubstitution s a h k r).roots, 0 < x
  • Every horizontal stretch is real-rooted under even boundary parityRealRooted original

    RealRooted.Schur.repeatColumns_isRealRootedsource
    theorem repeatColumns_isRealRooted (hpar : ∀ i j, Even (h i + k j + r)) (m : ℕ) :
        elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r ≠ 0 ∧
          (elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r).Splits
  • Strictly negative roots under all horizontal stretchesRealRooted original

    RealRooted.Schur.roots_repeatColumns_negsource
    theorem roots_repeatColumns_neg (hpar : ∀ i j, Even (h i + k j + r)) (m : ℕ) :
        ∀ x ∈ (elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r).roots,
          x < 0
  • Every horizontal stretch is real-rooted under odd boundary parityRealRooted original

    RealRooted.Schur.repeatColumns_isRealRooted_of_oddsource
    theorem repeatColumns_isRealRooted_of_odd (hpar : ∀ i j, Odd (h i + k j + r)) (m : ℕ) :
        elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r ≠ 0 ∧
          (elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r).Splits
  • Strictly positive roots for odd-parity horizontal stretchesRealRooted original

    RealRooted.Schur.roots_repeatColumns_possource
    theorem roots_repeatColumns_pos (hpar : ∀ i j, Odd (h i + k j + r)) (m : ℕ) :
        ∀ x ∈ (elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r).roots,
          0 < x
  • Constant skew column height gives det(M+tI)RealRooted original

    RealRooted.Schur.elementarySubstitution_eq_det_add_X_onesource
    theorem elementarySubstitution_eq_det_add_X_one {ι : Type*} {n : ℕ}
        (s : Finset ι) (a : ι → ℝ) {h k : Fin n → ℕ}
        (hk : Antitone k) (r : ℕ) (hheight : ∀ i, h i = k i + r) :
        elementarySubstitution s a h k r =
          det ((elementaryMatrix s a h k).map C + (X : ℝ[X]) • 1)
  • All constant-column-height stretches are real-rootedRealRooted original

    RealRooted.Schur.repeatColumns_isRealRooted_of_constant_heightsource
    theorem repeatColumns_isRealRooted_of_constant_height {ι : Type*} {n : ℕ}
        (s : Finset ι) (a : ι → ℝ) (ha : ∀ i ∈ s, 0 ≤ a i)
        {h k : Fin n → ℕ} (hh : Antitone h) (hk : Antitone k)
        (r : ℕ) (hheight : ∀ i, h i = k i + r)
        (hsize : r ≤ (s.filter fun i => 0 < a i).card) (m : ℕ) :
        elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r ≠ 0 ∧
          (elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r).Splits
  • Constant-column-height stretches have negative rootsRealRooted original

    RealRooted.Schur.roots_repeatColumns_neg_of_constant_heightsource
    theorem roots_repeatColumns_neg_of_constant_height {ι : Type*} {n : ℕ}
        (s : Finset ι) (a : ι → ℝ) (ha : ∀ i ∈ s, 0 ≤ a i)
        {h k : Fin n → ℕ} (hh : Antitone h) (hk : Antitone k)
        (r : ℕ) (hheight : ∀ i, h i = k i + r)
        (hsize : r ≤ (s.filter fun i => 0 < a i).card) (m : ℕ) :
        ∀ x ∈ (elementarySubstitution s a (repeatColumns h m) (repeatColumns k m) r).roots,
          x < 0
  • Duplicating rows gives real-rooted families for every even moving coordinateRealRooted original

    RealRooted.Schur.repeatColumns_double_isRealRootedsource
    theorem repeatColumns_double_isRealRooted {ι : Type*} {n : ℕ}
        (s : Finset ι) (a : ι → ℝ) (ha : ∀ i ∈ s, 0 ≤ a i)
        {h k : Fin n → ℕ} (hh : Antitone h) (hk : Antitone k) (hkh : ∀ i, k i ≤ h i)
        (hsize : ∀ i, 2 * h i ≤ 2 * k i + (s.filter fun j => 0 < a j).card)
        (r m : ℕ) :
        elementarySubstitution s a (repeatColumns (fun i => 2 * h i) m)
          (repeatColumns (fun i => 2 * k i) m) (2 * r) ≠ 0 ∧
        (elementarySubstitution s a (repeatColumns (fun i => 2 * h i) m)
          (repeatColumns (fun i => 2 * k i) m) (2 * r)).Splits
  • Duplicated-row families have negative roots under all stretchesRealRooted original

    RealRooted.Schur.roots_repeatColumns_double_negsource
    theorem roots_repeatColumns_double_neg {ι : Type*} {n : ℕ}
        (s : Finset ι) (a : ι → ℝ) (ha : ∀ i ∈ s, 0 ≤ a i)
        {h k : Fin n → ℕ} (hh : Antitone h) (hk : Antitone k) (hkh : ∀ i, k i ≤ h i)
        (hsize : ∀ i, 2 * h i ≤ 2 * k i + (s.filter fun j => 0 < a j).card)
        (r m : ℕ) :
        ∀ x ∈ (elementarySubstitution s a (repeatColumns (fun i => 2 * h i) m)
          (repeatColumns (fun i => 2 * k i) m) (2 * r)).roots, x < 0
  • Consecutive compatible skew suffixes interlaceRealRooted original

    RealRooted.Schur.strictInterl_elementarySubstitution_succsource
    theorem strictInterl_elementarySubstitution_succ {ι : Type*} {n : ℕ}
        (s : Finset ι) (a : ι → ℝ) (ha : ∀ i ∈ s, 0 ≤ a i)
        {h k : Fin (n + 1) → ℕ} (hh : Antitone h) (hk : Antitone k)
        (hkh : ∀ i, k i ≤ h i)
        (hsize : ∀ i, h i ≤ k i + (s.filter fun j => 0 < a j).card)
        (r : ℤ) (hpar : ∀ i j, (columnIndex h i : ℤ) = columnIndex k j + r →
          Even (i.val + j.val)) :
        StrictInterl (elementarySubstitution s a (h ∘ Fin.succ) (k ∘ Fin.succ) r)
          (elementarySubstitution s a h k r)
  • The rectangular definition equals the signed elementary substitutionRealRooted original

    RealRooted.Schur.rectangularElementarySubstitution_eq_detsource
    theorem rectangularElementarySubstitution_eq_det {ι : Type*} (s : Finset ι)
        (a : ι → ℝ) (r j n : ℕ) :
        rectangularElementarySubstitution s a r j n =
          det ((elementaryMatrix s a (fun _ : Fin n => r) (fun _ => 0)).map C +
            (X : ℝ[X]) • ((-1 : ℝ) ^ (r + j) • activeMatrix
              (fun i => (columnIndex (fun _ : Fin n => r) i : ℤ))
              (fun i => (columnIndex (fun _ : Fin n => 0) i : ℤ)) j).map C)
  • Every signed rectangular specialization is real-rootedRealRooted original

    RealRooted.Schur.rectangularElementarySubstitution_isRealRootedsource
    theorem rectangularElementarySubstitution_isRealRooted (n : ℕ) :
        rectangularElementarySubstitution s a r j n ≠ 0 ∧
          (rectangularElementarySubstitution s a r j n).Splits
  • Every signed rectangular specialization has negative rootsRealRooted original

    RealRooted.Schur.roots_rectangularElementarySubstitution_negsource
    theorem roots_rectangularElementarySubstitution_neg (n : ℕ) :
        ∀ x ∈ (rectangularElementarySubstitution s a r j n).roots, x < 0
  • Consecutive rectangular widths interlace for every moving coordinateRealRooted original

    RealRooted.Schur.strictInterl_rectangularElementarySubstitutionsource
    theorem strictInterl_rectangularElementarySubstitution (n : ℕ) :
        StrictInterl (rectangularElementarySubstitution s a r j n)
          (rectangularElementarySubstitution s a r j (n + 1))
  • Supported minors of Toeplitz matrices of positive linear-factor products are positiveRealRooted original

    RealRooted.Schur.det_toeplitz_prod_linear_possource
    theorem det_toeplitz_prod_linear_pos {ι : Type*} (s : Finset ι) (a : ι → ℝ)
        (ha : ∀ i ∈ s, 0 < a i) {n : ℕ}
        (rows cols : Fin n → ℕ) (hrows : StrictMono rows) (hcols : StrictMono cols)
        (hlo : ∀ i, cols i ≤ rows i) (hhi : ∀ i, rows i ≤ cols i + s.card) :
        0 < ((toeplitz (∏ i ∈ s, (X - C (-a i))).coeff).submatrix rows cols).det
  • Supported minors of a bidiagonal Toeplitz matrix are strictly positiveRealRooted original

    RealRooted.Schur.det_bidiagonal_submatrix_possource
    theorem det_bidiagonal_submatrix_pos {a : ℝ} (ha : 0 < a) {n : ℕ}
        {rows cols : Fin n → ℕ} (hrows : StrictMono rows) (hcols : StrictMono cols)
        (hlo : ∀ i, cols i ≤ rows i) (hhi : ∀ i, rows i ≤ cols i + 1) :
        0 < ((bidiagonal a).submatrix rows cols).det

Lean source RealRooted/Challenges/Combinatorial/SchurElementarySubstitution.lean at revision d6670742. Formalized 2026-11-07.