Toeplitz–Hessenberg determinants

TheoremTrudi's formula for Toeplitz–Hessenberg determinants, general case#✓fully proved

Let \(R\) be a commutative ring, let \(n \ge 0\), and let \(a_0, a_1, a_2, \dots\) be any elements of \(R\). Let \(A_n\) be the \(n \times n\) matrix whose entry in row \(i\) and column \(j\) (\(0 \le i, j < n\)) is \(a_{i+1-j}\) if \(j \le i + 1\) and \(0\) otherwise; for \(n = 0\) it is the empty matrix, whose determinant is \(1\). Then

\[\det A_n = \sum_{c} (-a_0)^{n - \ell(c)} \, a_{c_1} a_{c_2} \cdots a_{c_{\ell(c)}},\]

where \(c = (c_1, \dots, c_{\ell(c)})\) runs over the compositions of \(n\), that is, the finite sequences of positive integers with sum \(n\), and \(\ell(c)\) is the number of parts of \(c\).

No hypothesis \(n \ge 1\) or \(a_0 \ne 0\) is needed.

theorem Matrix.det_toeplitzHessenberg_eq_sum_compositions_general {R : Type*}
    [CommRing R] (n : Nat) (a : Nat → R) :
    Matrix.det (fun i j : Fin n =>
      if (j : Nat) ≤ (i : Nat) + 1 then a ((i : Nat) + 1 - (j : Nat)) else 0) =
    Finset.univ.sum (fun c : Composition n =>
      (-a 0) ^ (n - c.length) *
        Finset.univ.prod (fun r : Fin c.length => a (c.blocksFun r)))

Used by 2

Used byTrudi's formula for Toeplitz–Hessenberg determinants · Trudi's formula in composition form

TheoremTrudi's formula for Toeplitz–Hessenberg determinants#✓fully proved

Let \(R\) be a commutative ring, let \(n \ge 1\), and let \(a_0, a_1, a_2, \dots\) be elements of \(R\) with \(a_0 \ne 0\). Let \(A_n\) be the \(n \times n\) matrix whose entry in row \(i\) and column \(j\) (\(0 \le i, j < n\)) is \(a_{i+1-j}\) if \(j \le i + 1\) and \(0\) otherwise. Then

\[\det A_n = \sum_{c} (-a_0)^{n - \ell(c)} \, a_{c_1} a_{c_2} \cdots a_{c_{\ell(c)}},\]

where \(c = (c_1, \dots, c_{\ell(c)})\) runs over the compositions of \(n\), that is, the finite sequences of positive integers with sum \(n\), and \(\ell(c)\) is the number of parts of \(c\).

theorem Matrix.det_toeplitzHessenberg_eq_sum_compositions {R : Type*}
    [CommRing R] (n : Nat) (hn : 0 < n) (a : Nat → R) (ha0 : a 0 ≠ 0) :
    Matrix.det (fun i j : Fin n =>
      if (j : Nat) ≤ (i : Nat) + 1 then a ((i : Nat) + 1 - (j : Nat)) else 0) =
    Finset.univ.sum (fun c : Composition n =>
      (-a 0) ^ (n - c.length) *
        Finset.univ.prod (fun r : Fin c.length => a (c.blocksFun r)))

Sources

• Taras Goy and Mark Shattuck, Determinants of Some Hessenberg-Toeplitz Matrices with Motzkin Number Entries, Journal of Integer Sequences 26 (2023), Article 23.3.4, matrix display DetHess lines 146–155, Lemma lem1 lines 157–166 with equation Trudi at lines 159–161 and the equivalent composition sum at lines 163–165, https://cs.uwaterloo.ca/journals/JIS/VOL26/Shattuck/sh36.tex.

Uses 1

Proof usesTrudi's formula for Toeplitz–Hessenberg determinants, general case

DefinitionToeplitz–Hessenberg determinant#✓fully proved

Let \(R\) be a commutative ring, let \(a_0, a_1, a_2, \dots\) be elements of \(R\) and let \(n \ge 0\). The Toeplitz–Hessenberg determinant \(\det A_n\) is the determinant of the \(n \times n\) matrix \(A_n = A_n(a_0; a_1, \dots, a_n)\) whose entry in row \(i\) and column \(j\) (\(0 \le i, j < n\)) is \(a_{i+1-j}\) if \(j \le i + 1\) and \(0\) otherwise. Thus \(a_0\) fills the superdiagonal, \(a_1\) the diagonal, and every entry above the superdiagonal is \(0\). For \(n = 0\) the determinant is \(1\).

def toeplitzHessenbergDet {R : Type*} [CommRing R] (a : ℕ → R) (n : ℕ) : R :=
  (Matrix.of fun i j : Fin n =>
    if (j : ℕ) ≤ (i : ℕ) + 1 then a ((i : ℕ) + 1 - (j : ℕ)) else 0).det

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Section 2, display (1) and the notation D_±.

Used by 10

Used byToeplitz–Hessenberg determinants with Catalan entries · Toeplitz–Hessenberg determinants of Fuss–Catalan numbers · Special Toeplitz–Hessenberg determinants of Fuss–Catalan numbers · Generating function of Toeplitz–Hessenberg determinants · Toeplitz–Hessenberg determinants of ternary Fuss–Catalan numbers · Brioschi's formula: the case \(a_0 = 1\) of Trudi's formula · Trudi's formula in composition form · Trudi's formula when \(a_0 = -1\) · The \(1 \times 1\) Toeplitz–Hessenberg determinant · The \(2 \times 2\) Toeplitz–Hessenberg determinant

TheoremThe \(1 \times 1\) Toeplitz–Hessenberg determinant#✓fully proved

For every commutative ring \(R\) and every sequence \(a_0, a_1, a_2, \dots\) in \(R\), the Toeplitz–Hessenberg determinant of size \(1\) built from \(a\) is \(\det A_1 = a_1\).

theorem toeplitzHessenbergDet_one {R : Type*} [CommRing R] (a : ℕ → R) :
    toeplitzHessenbergDet a 1 = a 1

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Section 2, display (1).

Uses 1

Statement usesToeplitz–Hessenberg determinant

TheoremThe \(2 \times 2\) Toeplitz–Hessenberg determinant#✓fully proved

For every commutative ring \(R\) and every sequence \(a_0, a_1, a_2, \dots\) in \(R\), the Toeplitz–Hessenberg determinant of size \(2\) built from \(a\) is \(\det A_2 = a_1^2 - a_0 a_2\).

theorem toeplitzHessenbergDet_two {R : Type*} [CommRing R] (a : ℕ → R) :
    toeplitzHessenbergDet a 2 = a 1 ^ 2 - a 0 * a 2

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Section 2, display (1).

Uses 1

Statement usesToeplitz–Hessenberg determinant

TheoremTrudi's formula in composition form#✓fully proved

Let \(R\) be a commutative ring, let \(a_0, a_1, a_2, \dots\) be elements of \(R\) and let \(n \ge 0\). The Toeplitz–Hessenberg determinant \(\det A_n\) of size \(n\) built from \(a\) satisfies

\[\det A_n = \sum_{c} (-a_0)^{n - \ell(c)} \, a_{c_1} a_{c_2} \cdots a_{c_{\ell(c)}},\]

where \(c = (c_1, \dots, c_{\ell(c)})\) runs over the compositions of \(n\), that is, the finite sequences of positive integers with sum \(n\), and \(\ell(c)\) is the number of parts of \(c\).

theorem toeplitzHessenbergDet_eq_sum_compositions {R : Type*} [CommRing R] (a : ℕ → R)
    (n : ℕ) :
    toeplitzHessenbergDet a n =
      ∑ c : Composition n, (-a 0) ^ (n - c.length) * ∏ r : Fin c.length, a (c.blocksFun r)

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Lemma 1 and Section 3 (the composition form of the determinant).

Uses 2 · Used by 2

Statement usesToeplitz–Hessenberg determinant

Proof usesTrudi's formula for Toeplitz–Hessenberg determinants, general case

Used byBrioschi's formula: the case \(a_0 = 1\) of Trudi's formula · Trudi's formula when \(a_0 = -1\)

DefinitionTrudi's partition sum#✓fully proved

Let \(R\) be a commutative semiring, let \(s \in R\), let \(n\) be a natural number, and let \(a : \mathbb{N} \to R\) (only \(a_1, \dots, a_n\) enter). Trudi's partition sum is

\[ \sum_{\alpha} s^{|\alpha|} \, m_n(\alpha) \, a_1^{\alpha_1} a_2^{\alpha_2} \cdots a_n^{\alpha_n}, \]

where \(\alpha = (\alpha_1, \dots, \alpha_n)\) runs over the tuples of natural numbers with \(\alpha_1 + 2\alpha_2 + \cdots + n\alpha_n = n\), \(|\alpha| = \alpha_1 + \cdots + \alpha_n\), and \(m_n(\alpha) = |\alpha|! / (\alpha_1! \cdots \alpha_n!)\) is the multinomial coefficient, taken in \(R\). Such a tuple records a partition of \(n\) with \(\alpha_i\) parts equal to \(i\). For \(n = 0\) the sum has the single empty term and equals \(1\).

def trudiPartitionSum {R : Type*} [CommSemiring R] (s : R) (a : ℕ → R) (n : ℕ) : R :=
  ∑ α ∈ (Fintype.piFinset fun _ : Fin n => Finset.range (n + 1)).filter
      (fun α => ∑ i : Fin n, ((i : ℕ) + 1) * α i = n),
    s ^ (∑ i : Fin n, α i) * (Nat.multinomial Finset.univ α : R) *
      ∏ i : Fin n, a ((i : ℕ) + 1) ^ α i

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Lemma 1 (notation α̃, |α|, m_n(α)).

Used by 5

Used byTrudi multi-sums of Fuss–Catalan numbers · Brioschi's formula: the case \(a_0 = 1\) of Trudi's formula · Trudi's formula when \(a_0 = -1\) · Trudi's partition sum as a sum over compositions · Two values of Trudi's partition sum

TheoremTrudi's partition sum as a sum over compositions#✓fully proved

Let \(R\) be a commutative semiring, let \(s \in R\), let \(a_0, a_1, a_2, \dots\) be elements of \(R\) and let \(n \ge 0\). Trudi's partition sum

\[\sum_\alpha s^{|\alpha|} m_n(\alpha) \, a_1^{\alpha_1} a_2^{\alpha_2} \cdots a_n^{\alpha_n},\]

taken over the tuples \(\alpha = (\alpha_1, \dots, \alpha_n)\) of nonnegative integers with \(\alpha_1 + 2\alpha_2 + \dots + n\alpha_n = n\), where \(|\alpha| = \alpha_1 + \dots + \alpha_n\) and \(m_n(\alpha) = |\alpha|! / (\alpha_1! \cdots \alpha_n!)\), equals

\[\sum_c s^{\ell(c)} \, a_{c_1} a_{c_2} \cdots a_{c_{\ell(c)}},\]

where \(c = (c_1, \dots, c_{\ell(c)})\) runs over the compositions of \(n\), that is, the finite sequences of positive integers with sum \(n\), and \(\ell(c)\) is the number of parts of \(c\).

The multinomial coefficient \(m_n(\alpha)\) counts the compositions of \(n\) in which each part \(i\) occurs \(\alpha_i\) times.

theorem trudiPartitionSum_eq_sum_compositions {R : Type*} [CommSemiring R] (s : R) (a : ℕ → R) (n : ℕ) :
    trudiPartitionSum s a n =
      ∑ c : Composition n, s ^ c.length * ∏ r : Fin c.length, a (c.blocksFun r)

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Lemma 1 and the composition reading of det(A_n) in Section 3.

Uses 5 · Used by 2

Statement usesTrudi's partition sum

Proof usesWords with prescribed content · Words of given content are counted by the multinomial coefficient · The content of a word sums to its length · Content of a word

Used byBrioschi's formula: the case \(a_0 = 1\) of Trudi's formula · Trudi's formula when \(a_0 = -1\)

TheoremBrioschi's formula: the case \(a_0 = 1\) of Trudi's formula#✓fully proved

Let \(R\) be a commutative ring and let \(a_0, a_1, a_2, \dots\) be elements of \(R\) with \(a_0 = 1\). For every \(n \ge 0\), the Toeplitz–Hessenberg determinant \(\det A_n\) of size \(n\) built from \(a\) satisfies

\[\det A_n = (-1)^n \sum_\alpha (-1)^{|\alpha|} m_n(\alpha) a_1^{\alpha_1} \cdots a_n^{\alpha_n},\]

where the sum, Trudi's partition sum with weight \(-1\) per part, runs over the tuples \(\alpha = (\alpha_1, \dots, \alpha_n)\) of nonnegative integers with \(\alpha_1 + 2\alpha_2 + \dots + n\alpha_n = n\), with \(|\alpha| = \alpha_1 + \dots + \alpha_n\) and \(m_n(\alpha) = |\alpha|! / (\alpha_1! \cdots \alpha_n!)\).

theorem toeplitzHessenbergDet_eq_neg_one_pow_mul_trudiPartitionSum {R : Type*} [CommRing R]
    (a : ℕ → R) (ha : a 0 = 1) (n : ℕ) :
    toeplitzHessenbergDet a n = (-1) ^ n * trudiPartitionSum (-1) a n

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Lemma 1 with a_0 = 1 (the sign D_+).

Uses 4

Statement usesToeplitz–Hessenberg determinant · Trudi's partition sum

Proof usesTrudi's formula in composition form · Trudi's partition sum as a sum over compositions

TheoremTrudi's formula when \(a_0 = -1\)#✓fully proved

Let \(R\) be a commutative ring and let \(a_0, a_1, a_2, \dots\) be elements of \(R\) with \(a_0 = -1\). For every \(n \ge 0\), the Toeplitz–Hessenberg determinant \(\det A_n\) of size \(n\) built from \(a\) satisfies

\[\det A_n = \sum_\alpha m_n(\alpha) \, a_1^{\alpha_1} a_2^{\alpha_2} \cdots a_n^{\alpha_n},\]

where the sum, Trudi's partition sum with weight \(1\) per part, runs over the tuples \(\alpha = (\alpha_1, \dots, \alpha_n)\) of nonnegative integers with \(\alpha_1 + 2\alpha_2 + \dots + n\alpha_n = n\), with \(|\alpha| = \alpha_1 + \dots + \alpha_n\) and \(m_n(\alpha) = |\alpha|! / (\alpha_1! \cdots \alpha_n!)\).

theorem toeplitzHessenbergDet_eq_trudiPartitionSum_one {R : Type*} [CommRing R] (a : ℕ → R)
    (ha : a 0 = -1) (n : ℕ) :
    toeplitzHessenbergDet a n = trudiPartitionSum 1 a n

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Lemma 1 with a_0 = -1 (the sign D_-).

Uses 4

Statement usesToeplitz–Hessenberg determinant · Trudi's partition sum

Proof usesTrudi's formula in composition form · Trudi's partition sum as a sum over compositions

TheoremTwo values of Trudi's partition sum#✓fully proved

For an integer \(s\), integers \(a_1, a_2, \dots\) and \(n \ge 0\), write \(T_n(s; a) = \sum_\alpha s^{|\alpha|} m_n(\alpha) \, a_1^{\alpha_1} \cdots a_n^{\alpha_n}\) for Trudi's partition sum, where \(\alpha = (\alpha_1, \dots, \alpha_n)\) runs over the tuples of nonnegative integers with \(\alpha_1 + 2\alpha_2 + \dots + n\alpha_n = n\), with \(|\alpha| = \alpha_1 + \dots + \alpha_n\) and \(m_n(\alpha) = |\alpha|! / (\alpha_1! \cdots \alpha_n!)\). Then \(T_4(1; a) = 8\), the number of compositions of \(4\), when \(a_i = 1\) for all \(i\); and \(T_3(-1; a) = -1 + 4 - 3 = 0\) when \(a_i = i\) for all \(i\).

theorem trudiPartitionSum_examples :
    trudiPartitionSum (1 : ℤ) (fun _ => 1) 4 = 8 ∧
      trudiPartitionSum (-1 : ℤ) (fun i => i) 3 = 0

Sources

• Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Fuss-Catalan Entries, Journal of Integer Sequences 29 (2026), Article 26.1.2, Lemma 1.

Uses 1

Statement usesTrudi's partition sum

11 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.