Determinant of Three-Layer Toeplitz Matrices

Dmitry Efimov Institute of Physics and Mathematics Komi Science Centre UrD RAS Kommunisticheskaya Street 24 167000 Syktyvkar Russia

                        dmefim@mail.ru

Abstract We obtain an explicit and efficient formula for the determinant of a three-layer Toeplitz matrix. We show that many well-known sequences, such as Jacobsthal numbers, generalized Fibonacci numbers, and k-Fibonacci numbers, can be represented as sequences of determinants of three-layer Toeplitz matrices. Further, we evaluate the spectrum for one of these matrices using the obtained formulae and, as a consequence, discover some interesting factorizations of certain integer sequences in terms of products of complex numbers, the imaginary parts of which are expressed using the tangent function.

1 Introduction

Owing to the Gaussian elimination method, no computational difficulty is encountered when calculating the determinant of an arbitrary matrix. However, the problem of deriving new formulae for the determinants of various classes of matrices is yet to be solved; such formulae for determinants can increase the speed of calculations, enable us to study the properties of the corresponding matrices more deeply, and expand the application potential. Herein, we obtain explicit and efficient formulae for the determinants of three-layer Toeplitz matrices T = (t_{ij}). Such matrices are given by

t_{ij} = \{ \begin{matrix}a, & if j − i ≥ k; \\ b, & if − l < j − i < k; \\ c, & if j − i ≤ −l, \end{matrix}

where k, l ∈ ℤ^{+} and a, b, and c are elements of some field. As the name suggests, one can clearly distinguish three diagonal layers in such matrices; each of these layers consists of the same elements. The middle layer contains the main diagonal. If the elements of the side layers are the same, then we have a special case considered earlier in [1]. Herein, we use fairly elementary methods, namely Laplace expansion and combinations of various recurrence relations.

This paper is organized as follows. In the next section, we obtain explicit and efficient formulae for the determinants of three-layer Toeplitz matrices. In the third section, we consider in detail the special case of such matrices wherein the middle layer coincides with the main diagonal. We show that many of the sequences in [4] can be viewed as sequences of determinants of such matrices. Several such sequences are combined in the table presented at the end of the paper. As an application of the obtained formulae, we calculate the spectrum for the three-layer Toeplitz matrices of a special type. We also obtain interesting ratios that express elements of some integer sequences in terms of products of complex numbers, the imaginary parts of which are expressed in terms of the tangent function.

2 General formulae

Let n, k ∈ ℤ^{+}. Consider a Toeplitz matrix A = (a_{ij}) of order n with entries

a_{ij} = \{ \begin{matrix}a, & if j − i ≥ k; \\ b, & if − 1 < j − i < k; \\ c, & if j − i ≤ −1, \end{matrix}

where a, b, and c are elements of some field.

A = ( \begin{matrix}^{k} b & … & b & a & … & a \\ c & ... & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & a \\ ⋮ & ... & ... & b \\ ⋮ & ... & ... & ⋮ \\ c & … & … & … & c & b \end{matrix} ) .  (1)

Theorem 1. Let s be the quotient and p the remainder when n is divided by k. Then,

det A = \begin{cases}(b − c)^{n−s−sgn(p)} \frac{a(b − c)^{s+sgn(p)} − c(b − a)^{s+sgn(p)}}{a − c}, & a ≠ c; \\ (b − c)^{n−1}[b + (s + sgn(p) − 1)c], & a = c, \end{cases}  (2)

where sgn(p) is the sign function (i.e., sgn(p) = 0 if p = 0 and sgn(p) = 1 if p > 0).

Proof. Let d_{n} denote the determinant of a matrix A of order n. If k ≥ n, then A has the following form:

( \begin{matrix}b & … & … & … & b \\ c & ... & & & ⋮ \\ ⋮ & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ⋮ \\ c & … & … & c & b \end{matrix} ) .

Subtracting the penultimate row from the last one and expanding the determinant along the last row, we have d_{n} = (b − c)d_{n−1}. Applying this formula recursively, we obtain

d_{n} = (b − c)^{n−1}b  (3)

in this case. If k = n, then s = 1 and p = 0. If k > n, then s = 0 and p = n. In both the cases, (3) is consistent with the first and second lines of (2).

Consider a complementary matrix of order n of the following form:

( \begin{matrix}b & & & & & a \\ c & ... & & T & & ⋮ \\ ⋮ & ... & ... & & & ⋮ \\ ⋮ & & ... & ... & & ⋮ \\ c & … & … & c & b & a \\ c & … & … & … & c & a \end{matrix} ) .

Here, the triangular area below the main diagonal is completely filled with elements c, the last column entirely consists of a, and triangular area T consists of arbitrary elements. Let f_{n} denote the determinant of such a matrix. For n = 1, we assume that the matrix consists of one element a and that f_{1} = a. If n ≥ 2, then subtracting the penultimate row from the last one and expanding the determinant along the last row, we obtain f_{n} = (b − c)f_{n−1}. Applying this formula recursively, we obtain

f_{n} = (b − c)^{n−1}a.  (4)

Let k < n. Then, subtracting the penultimate row of A from the last one, expanding the determinant along the last row, and repeating this procedure k times, we obtain

d_{n} = (b − c)^{k}f_{n−k} + (b − c)^{k−1}(b − a)d_{n−k}.  (5)

By assumption, n = ks + p, 0 ≤ p < k. Applying (5) recursively s + sgn(p) − 1 times, we obtain

d_{n} = (b − c)^{(s+sgn(p)−1)(k−1)}(b − a)^{s+sgn(p)−1}d_{k(1−sgn(p))+p} + a ∑_{i=1}^{s+sgn(p)−1}(b − c)^{n−i}(b − a)^{i−1}.

Because k ≥ k(1 − sgn(p)) + p, applying (3) to d_{k(1−sgn(p))+p} yields

d_{n} = ∑_{i=1}^{s+sgn(p)} (⌊\frac{i}{s + sgn(p)}⌋ (b − a) + a) (b − c)^{n−i}(b − a)^{i−1}.  (6)

Using the formula for the sum of a geometric progression, we find that (6) is equivalent to (2).

Let n, k, l ∈ ℤ^{+}, 1 < l ≤ k. Consider a Toeplitz matrix B = (b_{ij}) of order n with entries

b_{ij} = \{ \begin{matrix}a, & if j − i ≥ k; \\ b, & if − l < j − i < k; \\ c, & if j − i ≤ −l, \end{matrix}

where a, b, c are elements of an arbitrary field:

B =l \{( \begin{matrix}^{k} b & … & b & a & … & a \\ ⋮ & ... & ... & ... & ⋮ \\ b & ... & ... & a \\ c & ... & ... & b \\ ⋮ & ... & ... & ... & ⋮ \\ c & … & c & b & … & b \end{matrix} ) .  (7)

Theorem 2. Let s be the quotient and p the remainder when n is divided by k +l −1. Then,

det B = \begin{cases}(b − a)^{(l−1)s}(b − c)^{(k−1)s} \frac{a(b − c)^{s+p} − c(b − a)^{s+p}}{(−1)^{(k−1)(l−1)s}(a − c)}, & p ≤ 1, a ≠ c; \\ (−1)^{(k−1)(l−1)s}(b − c)^{n−1}[b + (s + p − 1)c], & p ≤ 1, a = c; \\ 0, & p > 1. \end{cases}  (8)

Proof. It is clear that if k ≥ n, then matrix B has at least two rows consisting entirely of elements b, and its determinant equals 0. In this case, s = 0 and p = n, and the result is consistent with (8).

Let k < n. Subtracting the first row from the second one and expanding the determinant along the second row, we obtain

det B = (−1)^{k−1}(b − a) det B′,

where B′ is the matrix in which the first and second rows only differ in the (k+1)-th column. Repeating this procedure recursively (l − 1) times, we obtain

det B = (−1)^{(k−1)(l−1)}(b − a)^{l−1} det B′′,

where

B′′ =k \{( \begin{matrix}b & … & b \\ & ... & ⋮ & ... & & & a \\ c & & b & … & b \\ & & & b & … & b & & & a \\ & & & ⋮ & ... & & ... \\ & c & & b & & ... & & ... \\ & & & & ... & & ... & & b \\ & & & & & ... & & ... & ⋮ \\ & & & c & & & b & … & b \end{matrix} ) .

A part of matrix B′′ located above the horizontal line contains k rows, and the first row contains exactly k b’s. The lower right part of the matrix is formed by the n − k − l + 1 last rows and columns of the initial matrix and clearly has the same form as that of the initial matrix.

One can implement the algorithm recursively s times with a shift of k rows each time; i.e., at the next step, the (k + 1)-th row of matrix B′′ is subtracted from the (k + 2)-th row, and the determinant is expanded along the (k + 2)-th row; this procedure is continued recursively (l − 1) times. As a result, we have

det B = (−1)^{(k−1)(l−1)s}(b − a)^{(l−1)s} det B′′′,  (9)

where

B′′′ = ( \begin{matrix}b & … & b & & a \\ & ... & & ... & & a \\ & & ... & & b \\ & c & & ... & ⋮ & ... \\ & & & & b & … \\ & & c & & & M \end{matrix} ) .

The part of matrix B′′′ located above the horizontal axis consists of ks rows. The number of elements b in the first row is k. Submatrix M is formed by the intersection of the last p = n − (k + l − 1)s rows and columns of matrix B. It is clear that if p > 1, then matrix M contains at least two rows consisting entirely of elements b. Therefore, matrix B′′′ also has two identical rows, and its determinant equals 0. Accordingly, the determinant of matrix B in this case also equals 0.

If p = 0, then B′′′ is a matrix of the form (1) and order ks. By Theorem 1, we have

det B′′′ = \begin{cases}(b − c)^{(k−1)s} \frac{a(b − c)^{s} − c(b − a)^{s}}{a − c}, & a ≠ c; \\ (b − c)^{ks−1}(b + (s − 1)c), & a = c, \end{cases}

which in combination with (9) agrees with (8).

If p = 1, then B′′′ is a matrix of the form (1) and order ks + 1; therefore, by Theorem 1, we have

det B′′′ = \begin{cases}(b − c)^{(k−1)s} \frac{a(b − c)^{s+1} − c(b − a)^{s+1}}{a − c}, & a ≠ c; \\ (b − c)^{ks}(b + sc), & a = c, \end{cases}

which in combination with (9) also agrees with (8).

Remark 3. Theorems 1 and 2 allow us to compute determinants of matrices (1) and (7) of order n in O(n) time.

3 Special case

Consider in more detail a three-layer Toeplitz matrix of order n of the form

C = ( \begin{matrix}b & a & … & … & a \\ c & ... & ... & & ⋮ \\ ⋮ & ... & ... & ... & ⋮ \\ ⋮ & & ... & ... & a \\ c & … & … & c & b \end{matrix} ) .  (10)

Here k = l = 1. By Theorem 1, we have

det C = \begin{cases}\frac{a(b − c)^{n} − c(b − a)^{n}}{a − c}, & a ≠ c; \\ (b − c)^{n−1}(b + (n − 1)c), & a = c. \end{cases}

Let g_{n} denote the determinant of matrix C of order n. It is clear that the ordinary generating function of (g_{n}) has the following form:

G(x) = \frac{(a + c − b)x + 1}{(b − a)(b − c)x^{2} + (a + c − 2b)x + 1}.

Accordingly, the following recurrence relation holds for sequence (g_{n}):

g_{n} = (2b − a − c)g_{n−1} − (b − a)(b − c)g_{n−2}; g_{0} = 1, g_{1} = b.  (11)

Many sequences presented in [4] correspond to recurrence relation (11) up to a shift by one or two elements. For example, consider the so-called metallic mean [3] of the following form:

σ_{k} = \frac{k + \sqrt{k^{2} + 4}}{2}, k ∈ ℤ^{+}.

For k = 1, we obtain the well-known golden ratio; for k = 2, we obtain the silver ratio, and so on. Now, we consider the following values as parameters a, b, and c:

a = σ_{k} − k, b = 0, c = −σ_{k}.

Substituting these values into (11), we obtain the following recurrence relation:

g_{n} = kg_{n−1} + g_{n−2}; g_{0} = 1, g_{1} = 0,

which defines a sequence of the so-called k-Fibonacci numbers [2] shifted by one element to the right. For k = 1, we obtain the Fibonacci sequence; for k = 2, we obtain the sequence of Pell numbers, and so on. Let F_{k,n} denote the n-th member of the k-Fibonacci sequence. Thus the following proposition holds.

Proposition 4.

F_{k,n} = | \begin{matrix}0 & σ_{k} − k & … & … & σ_{k} − k \\ −σ_{k} & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & ⋮ \\ ⋮ & ... & ... & σ_{k} − k \\ _{n+1} − σ_{k} & … & … & −σ_{k} & 0 \end{matrix} | .

Some examples of other sequences from the On-Line Encyclopedia of Integer Sequences (OEIS), which can also be considered sequences of determinants of matrices of the form (10), are presented in Table 1.

Now, assume that c = −a; i.e., consider the matrices of the form

D = ( \begin{matrix}b & a & … & … & a \\ −a & ... & ... & & ⋮ \\ ⋮ & ... & ... & ... & ⋮ \\ ⋮ & & ... & ... & a \\ −a & … & … & −a & b \end{matrix} ) .

By Theorem 1, the determinant of matrix D of order n is given by

det D = \frac{(b + a)^{n} + (b − a)^{n}}{2}.  (12)

Theorem 5. If a, b ∈ ℝ, then the spectrum of matrix D of order n has the following form:

σ(D) = \begin{cases}\{b + ia tan \frac{πk}{2m + 1}, −m ≤ k ≤ m\} , & n = 2m + 1; \\ \{b + ia tan \frac{π(2k + 1)}{4m}, −m ≤ k ≤ m − 1\} , & n = 2m. \end{cases}  (13)

Proof. Without loss of generality, we may assume that a > 0. First, we find the spectrum of matrix D for b = 0. Considering (12), the characteristic equation det(D − λI) = 0 in this case takes the following form:

(a + λ)^{n} = (−1)^{n+1}(a − λ)^{n}.

The numbers a + λ and a − λ must have the same modulus. This is only possible when λ is a purely imaginary number. Let λ = pi, p ∈ ℝ; i.e., consider the equation

(a + pi)^{n} = (−1)^{n+1}(a − pi)^{n}.  (14)

We denote the argument of a + pi by ϕ. Because a > 0, ϕ ∈ (−π/2, π/2). Let n = 2m + 1. Equating arguments of the numbers on the right and left sides of equation (14), we obtain ϕ = πk/n, where k takes integer values in the range [−m, m]. Because tan ϕ = p/a, eigenvalues of D in this case have the following form:

ia tan \frac{πk}{2m + 1}, −m ≤ k ≤ m.

Similarly, if n = 2m, then equating the arguments of the numbers on the right and left sides of equation (14), we obtain ϕ = π(2k + 1)/2n, k ∈ [−m, m − 1], and accordingly, the eigenvalues of matrix D have the following form:

ia tan \frac{π(2k + 1)}{4m}, −m ≤ k ≤ m − 1.

Clearly, for an arbitrary b, the spectrum of matrix D has the form (13).

As a consequence of (12) and Theorem 5, we obtain the following interesting relation.

Corollary 6. Let a, b ∈ ℝ. Then,

\frac{(b + a)^{n} + (b − a)^{n}}{2} = \begin{cases}∏_{k=−m}^{m} (b + ia tan \frac{πk}{2m + 1}) , & n = 2m + 1; \\ ∏_{k=−m}^{m−1} (b + ia tan \frac{π(2k + 1)}{4m}) , & n = 2m. \end{cases}

Example 7 (The sequence \underline{A007051}). Let a = 1, b = 2. Then, by Corollary 6, we have

\frac{3^{n} + 1}{2} = \begin{cases}∏_{k=−m}^{m} (2 + i tan \frac{πk}{2m + 1}) , & n = 2m + 1; \\ ∏_{k=−m}^{m−1} (2 + i tan \frac{π(2k + 1)}{4m}) , & n = 2m. \end{cases}

For example,

5 = (2 − i tan \frac{π}{4} ) · (2 + i tan \frac{π}{4} ),
14 = 2 · (2 − i tan \frac{π}{3} ) · (2 + i tan \frac{π}{3} ),
41 = (2 − i tan \frac{3π}{8} ) · (2 − i tan \frac{π}{8} ) · (2 + i tan \frac{π}{8} ) · (2 + i tan \frac{3π}{8} ),
122 = 2 · (2 − i tan \frac{2π}{5} ) · (2 − i tan \frac{π}{5} ) · (2 + i tan \frac{π}{5} ) · (2 + i tan \frac{2π}{5} ),

and so on.

a b c k l  A-number in the OEIS
1 0 −2 1 1 \underline{A078008} (Expansion of (1 − x)/((1 + x)(1 − 2x)))
1 0 −3 1 1 \underline{A054878} (Number of closed walks of length n ...)
1 2 −1 1 1 \underline{A007051} (a_{n} = (3^{n} + 1)/2)
2 0 −3 1 1 \underline{A102901} (a_{n} = a_{n−1} + 6a_{n−2}, a_{0} = 1, a_{1} = 0)
2 1 −1 1 1 \underline{A001045} (Jacobsthal numbers)
2 1 −2 1 1 \underline{A046717} (a_{n} = 2a_{n−1} + 3a_{n−2}, a_{0} = a_{1} = 1)
3 1 −2 1 1 \underline{A015441} (Generalized Fibonacci numbers)
3 1 −3 1 1 \underline{A003665} (a_{n} = 2^{n−1}(2^{n} + (−1)^{n}))
3 1 −4 1 1 \underline{A320469} (a_{n} = 3a_{n−1} + 10a_{n−2}, a_{0} = 1, a_{1} = 1)

Table 1: Correspondence of sequences of determinants of three-layer Toeplitz matrices to sequences from the OEIS

4 Acknowledgments

The author would like to thank the anonymous referee for careful reading of the paper and helpful comments.

References

[1] D. B. Efimov, Determinants of generalized binary band matrices, Proceedings Komi Science Centre UrD RAS 4 (28) (2016), 5–10.

[2] S. Falcón and Á. Plaza, On the Fibonacci k-numbers, Chaos Solitons Fractals 32 (2007), 1615–1624.

[3] V. W. de Spinadel, The metallic means family and renormalization group techniques, Proc. Steklov Inst. Math. 6 (2000), 173–189.

[4] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

   at https://oeis.org.

2010 Mathematics Subject Classification: Primary 15A15, Secondary 15B05, 15A18. Keywords: determinant, Toeplitz matrix, spectrum.

(Concerned with sequences \underline{A000045}, \underline{A000129}, \underline{A001045}, \underline{A003665}, \underline{A007051}, \underline{A015441}, \underline{A046717}, \underline{A054878}, \underline{A078008}, \underline{A102901}, and \underline{A320469}.)

Received June 10 2021; revised version received August 20 2021. Published in Journal of Integer Sequences, October 25 2021.

Return to Journal of Integer Sequences home page.