Toeplitz matrix determinants broken down by simpler band factors
Toeplitz multiplication and graded factorization of determinant recurrences
Symbolic Computation
Summary
Toeplitz matrices have a special pattern where numbers along each diagonal stay the same. When these matrices have only a few diagonals with numbers, their determinants follow a pattern that repeats according to a fixed formula. The authors show that for complicated matrices, this repeating pattern can actually be built up from simpler patterns of smaller matrices multiplied together. They explain how shifting these smaller matrices changes where the pattern breaks, and how to combine these shifts to get the full formula for the big matrix. This gives a way to find the repeating formula more efficiently without complex calculations.
What this means in practice
- •For numerical linear algebra developers: Create efficient algorithms to compute determinant recurrences for large banded Toeplitz matrices by assembling simpler factors.
- •For signal processing engineers: Improve the analysis of filters modeled by banded Toeplitz matrices through modular determinant recurrence construction.
Authors
Max A. Alekseyev, Dmitry I. Khomovsky
Abstract
Toeplitz matrices are matrices whose entries are constant along each diagonal. When only finitely many diagonals are nonzero, the determinants of successively larger matrices obey a fixed linear recurrence: each new determinant is a fixed linear combination of finitely many preceding ones. We ask whether the recurrence for a complicated band can be built from recurrences for simpler factors, and show that it can. Multiplying two finite banded Toeplitz matrices reproduces the expected product throughout the interior, with discrepancies only near two opposite corners. Shifting the factors relative to the main diagonal redistributes these boundary discrepancies, and the different shifts account exactly for the pieces from which the full determinant recurrence is assembled. For several factors, all allowed shifts are described by a finite system of linear inequalities, giving a systematic decomposition of the recurrence. This viewpoint also leads to a recursive construction that works directly with polynomial coefficients, without solving for their roots. When a factorization into bounded-degree pieces is supplied, a valid recurrence can be constructed using essentially a linear number of arithmetic operations in the number of coefficients that must be output. A five-diagonal example shows how a sixth-order recurrence is assembled from two tridiagonal Toeplitz factors together with two boundary contributions.