Constructive recurrences for determinants and permanents of banded Toeplitz matrices
Abstract
For fixed nonnegative integers m1,m2, let An=(aj−i)i,j=1n be the leading n× n section of a Toeplitz matrix with lower and upper semibandwidths m1 and m2. We give two constructive Laplace-expansion methods for scalar recurrences of det An and perm An. The increasing-rows method eliminates a fixed family of boundary cofactors and gives recurrence order at most d=binomm1+m2m1 for both sequences. The row-column method closes normalized boundary minors recursively and packages them in a sparse transfer matrix. Its reachable states are classified exactly: level j is indexed by a pair of j-subsets of [m1] and [m2]. Hence the transfer dimension is d, and we obtain an explicit formula for the number of nonzero transitions. For determinants, the complementary cofactors of the increasing-rows construction are coordinates of the classical compound companion representation. The independently constructed row-column transfer has the Widom characteristic polynomial and is generically similar to the compound transfer. Thus the order d recurrence is generically minimal for the unrestricted fixed-band determinant family. For permanents the same state graph gives the binomial upper bound, without a general minimality claim. The pentadiagonal case recovers Sweet's order-six determinant recurrence and its permanent analogue, while the one-superdiagonal family gives closed scalar recurrences and rational generating functions. Position-dependent band weights preserve the finite state graph but replace the constant transfer by a cocycle. For cyclic determinants, Fourier diagonalization produces all subset products of the symbol roots and a generically minimal annihilator of degree 2m1+m2, corresponding to the passage from one exterior degree to the full exterior algebra.
Related
- Symmetry reductions and recurrence degrees for banded Toeplitz determinants and permanents
- Toeplitz multiplication and graded factorization of determinant recurrences
- Hankel, Toeplitz, Hermitian--Toeplitz Determinants and the Zalcman Functional for a Class of Biholomorphic Mappings on Complex Banach Spaces
- A proof of Karp's conjecture on the zeros of Toeplitz determinants of rising factorial series
- Eigenvalues of Hermitian Toeplitz matrices with Fisher--Hartwig symbols
BibTeX
@misc{alekseyev2026constructive,
title = {{Constructive recurrences for determinants and permanents of banded Toeplitz matrices}},
author = {Max A. Alekseyev and Dmitry I. Khomovsky},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13674},
eprint = {2609.13674},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13674},
}
RIS
TY - UNPB
TI - Constructive recurrences for determinants and permanents of banded Toeplitz matrices
AU - Max A. Alekseyev
AU - Dmitry I. Khomovsky
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.13674
UR - https://arxiv.org/abs/2609.13674
AB - For fixed nonnegative integers m_1,m_2, let A_n=(a_j−i)_i,j=1^n be the leading n× n section of a Toeplitz matrix with lower and upper semibandwidths m_1 and m_2. We give two constructive Laplace-expansion methods for scalar recurrences of det A_n and perm A_n. The increasing-rows method eliminates a fixed family of boundary cofactors and gives recurrence order at most d=binomm_1+m_2m_1 for both sequences. The row-column method closes normalized boundary minors recursively and packages them in a sparse transfer matrix. Its reachable states are classified exactly: level j is indexed by a pair of j-subsets of [m_1] and [m_2]. Hence the transfer dimension is d, and we obtain an explicit formula for the number of nonzero transitions. For determinants, the complementary cofactors of the increasing-rows construction are coordinates of the classical compound companion representation. The independently constructed row-column transfer has the Widom characteristic polynomial and is generically similar to the compound transfer. Thus the order d recurrence is generically minimal for the unrestricted fixed-band determinant family. For permanents the same state graph gives the binomial upper bound, without a general minimality claim. The pentadiagonal case recovers Sweet's order-six determinant recurrence and its permanent analogue, while the one-superdiagonal family gives closed scalar recurrences and rational generating functions. Position-dependent band weights preserve the finite state graph but replace the constant transfer by a cocycle. For cyclic determinants, Fourier diagonalization produces all subset products of the symbol roots and a generically minimal annihilator of degree 2^m_1+m_2, corresponding to the passage from one exterior degree to the full exterior algebra.
ER -