Determinants of generalized binary band matrices

Under binary matrices we mean matrices whose elements can take only two values. Matrices of this kind arise in different mathematical questions. For example, this type includes popular objects in mathematics and its applications such as matrices over the field GF (2) [1]. The Hadamard’s problem of finding the maximal determinant of ( - 1 , 1) -matrices, i.e. matrices consisting from 1 and - 1 , is well known [2]. Further, (0 , 1) -matrices are one of the favorite objects of the enumerative combinatorics [3-6]. Also one can use binary (1 ,x ) -matrices for enumerative problems [6]. These examples can be extended.

One of the basic notion of the matrix theory is the notion of determinant. There exist effective algorithms for the determinant calculation, for example, the modified method of Gaussian elimination, which run in polynomial time. Nevertheless, in cases of some kinds of matrices it is possible to obtain good explicit formulae for the de- terminant expression. On the one hand, these formulae allow to draw certain conclusions about properties of matrices. On the other hand, they give even greater gain in the speed of the determinant calculation.

Our paper is motivated to some extent by the recent work [7] in which the explicit formula for the determinant of some binary circulant matrices has been obtained. In the present paper we get explicit formulae for determinants of some kinds of binary Toeplitz matrices. Considered matrices are close in their structure to band matrices, therefore we call them generalized band matrices. For our purpose we use quite elementary methods. Applying the Laplace expansion we obtain recurrent formulae leading to the required result.

In the second section we give and prove the formulae, which allow to efficiently calculate determinants of generalized binary band matrices in an explicit form. In the third section we give a few examples of the application of the determinant of such matrices for the enumeration of even and odd permutations of different types.

1. The main part

Let n, k, l be integers, 1 < l < k < n . Consider a binary Toeplitz matrix A = ( a ij ) of order n with the following elements:

^a ij ⁼

b, if — l < j — i < k ; a, otherwise,

where a and b ( a = b ) belong to a commutative associative ring with a unit. In the case a = 0 we get a so-called band matrix ( [8], p.16). So we can say that we consider generalized binary band matrices . Our purpose is to get explicit formulae for calculating the determinant of the matrix A . We will divide this problem into two cases. Case 1 . Let l = 1 . In other words, let the first row of the matrix A have the form:

Proof. Subtracting the penultimate row from the last row and expanding the determinant along the last row, we get that f _n = ( b — a ) f _{n -} 1 . Using the given formula consecutively to f _{n -} 1 , f _{n -}2 and so on, we get (4). □

Suppose that k = n , i.e. consider the matrix of order n of the form:

/ b b b ... b \ b b ... b b

a

b

n

and the ( i + 1) -st row is obtained from the first row by the removal of i elements on the right and addition of i elements a on the left:

ba

.. b

b

b

.

.

.

b

Theorem 1. Let n = p (mod k ) , where 0 < p < k .

Then the determinant of the matrix (1) is equal to:

det A = ( b — a ) n- ¹

(b + n-pa)-

For the proof of Theorem 1 one can apply the method given in [7] for the proof of explicit formulae of the determinants of circulant matrices (using the formula of the determinant of a 2 x 2 block matrix). But in this case another method will be more convenient. First let us formulate some auxiliary statements. Consider a square matrix of order n of the form:

b

b

b

• •

b

a

b

b

^a a a

.

.

.

.

. b

.

.

.

.

b

.

.

.

a

a

.

.

.

aa a

• •   •

a

•   • •

.

.

. b

a

.

.

.

a

a

The given matrix is obtained from the matrix (1) of order ( n — 1) by addition of one more (the last) row and one more (the last) column, consisting entirely of elements a . Let f n denote the determinant of such matrix.

Lemma 1. The determinant of the matrix (3) is equal to:

f n = ( b — a ) n- ¹ a.                (4)

By g n denote the determinant of such matrix.

Lemma 2. One can calculate the determinant of the matrix (5) by the formula:

g n = ( b — a ) ^{n - 1} b.                (6)

Proof. Similarly to the proof of the previous lemma. □

Consider the matrix (1) of order n with k < n . Let d n denote the determinant of such matrix.

Lemma 3. The following equality holds:

dn = f (b — a)kdn-k + (b — a)n 1 a, k< n;

I ( b — a ) ^{n -} 1 ( b + a ) ,             k >  n . ^V)

Proof. Let k <  ⁿ ₂ , i.e. the number of elements b in the first row of the matrix (1) is less than the number of elements a . Let us subtract the penultimate row of the matrix from the last row and expand the determinant along the last row. Performing this procedure consecutively k times, we come to the equality:

d n = ( b — a ) ^k d n-k + ( b — a ) ^k f n-k .

Substituting here the formula (4), we get the first row of the equality (7).

Let n < k , i.e. the number of elements b in the first row of the matrix (1) is more or equal to the number of elements a , but less than n . Executing the same k consecutive expansions along the last row as in the first case, we come to the equality:

d n = ( b — a ) ^k ( f n-k + g n-k ) .

Substituting here the formulae (4) and (6), we get the second row of (7).                                 □

Proof. (of the Theorem 1) . Suppose that n = p (mod k ) , where 0 < p < k , i.e. n = km + p , where m is a non-negative integer. Assume that k < n . Then m >  0 and, using the first row of the formula (7) recurrently m — 1 times, we obtain the equality:

d n = ( b — a ) ^{n - k - p}d k + p + ( m — 1)( b — a ) ^{n - 1} a.

Since k +2 p < k , then applying the second row of the formula (7) to d k + p and performing obvious transformations, we get (2).

If k = n , i.e. the first row of the matrix (1) entirely consists from elements b , then p = n and the formula (2) gives us d _n = ( b — a ) ^{n - 1} b , which corresponds to the statement of the Lemma 2.                     □

Case 2. Let 1 >  1 . In other words, let the i -th row of the matrix A , i = 1 ,... ,1 , have the form:

and second rows differ also only in the ( k + 1) -st column. Performing this procedure 1 - 1 times, we obtain that det A = ( - 1)^{( k - 1)( l -} 1) ( b - a ) ^{l - 1} det A ’ , where

k + i- 1

n

and the ( 1 + j ) -th row is obtained from the 1 -th one by the removal of j elements on the right and addition of j elements a on the left:

b

.

.

.

A = ^b

a

b             a \

A ^′′

/ b ... b

..

..

..

ab

a

a b

b

b

.

.

.

b

b ... ba

...

...

...

b               ...'-.

...

..

...

..

a               b...b

The matrix A is not symmetric in general, but it is per-symmetric (i.e. symmetric with respect of the secondary diagonal) like all Toeplitz matrices.

Lemma 4. In the matrix (8) exactly max ( k + 1 - n, 0) rows consist entirely from elements b .

Proof. First note that each row of the matrix A contains no more than k + 1 - 1 elements b by definition. Let k + 1 - n <  0 . Hence k + 1 - 1 < n , i.e. there is at least one element a in each row and there are no rows, consisting entirely from elements b . Let now k + 1-n >  0 or, alternatively, k + 1 - 1 > n .If n = k + i - 1 , 1 < i < 1 , then the number of rows, that consist entirely from elements b , will be equal to 1 - i + 1 = k + 1 - n . □

The part of the matrix A ^′′ that is located above the horizontal line consists from k rows, and in the first row there are exactly k elements b . In the lower right corner of the matrix A ^′′ there is a submatrix, which is formed by intersection of the last n - k -1 + 1 rows and columns of A . The given submatrix, in turn, also has the form (8).

The algorithm can be repeated s times with an obvious shift at each step in the k rows down and in the k columns to the right. Thus in the second step we subtract the (k + 1)-st row of the matrix A’ from the (k + 2)-nd one and expand the determinant along the (k + 2)-nd row, and repeat this procedure 1 -1 times and so on. As a result we will get that det A = (-1)(k-1)(l- 1)s(b - a)(l- 1)s det A’’, (10)

where

Theorem 2. Let 1 < 1 < k < n and n = p (mod k + 1 - 1) , 0 < p < k + 1 - 1 . Then the determinant of the matrix (8) is equal to:

f ( - 1) . ( b + .' a ) , p = 0 , det A =? ( - 1) ⁵ ( ^{n -} У ^(b + n- ¹ a), p =1 , (9)

I 0, " p> 1, where

5 = ⁽ k - 2/⁽ l - 1) , » =( b - a ) n— ¹ , ° = k + l - 1 . k + l- 1

Proof. By the theorem condition n >  2 . Let n = p (mod k + 1 - 1) , 0 < p < k + 1 - 1 . This is equivalent to n = ( k + 1 - 1) s + p , where s is a non-negative integer.

First consider the case when s = 0 , i.e. when p = n and, respectively, n < k + 1 - 1 . By lemma 4 at least 2 rows of the matrix A will consist entirely from elements b in this case, therefore the determinant of the matrix A will be equal to 0 , that corresponds to the formula (9).

Now assume that s > 1. The first row of the matrix A differs from the second one only by an element in the (k + 1)-st column. Let us subtract the first row from the second one and expand the determinant along the second row. We will get that det A = (-1)k- 1(b - a) det A’, where A’ is a matrix, whose first b ... b a

a

a

...

M

The part of the matrix A ^′′′ that is located above the horizontal line consists from ks rows, and in the first row there are exactly k elements b . In the lower right corner of the matrix A ^′′′ there is a submatrix M , which is formed by intersection of the last n - ( k + 1 - 1) s = p rows and columns of the matrix A .

It is not hard to see that if 1 < p < k + 1 - 1 then M contains two identical rows, hence the matrix A ^′′′ also contains two identical rows, and therefore its determinant and the determinant of the matrix A are equal to 0 .

If p = 0 then the matrix A ’’ is the matrix of the form (1) of order ks . Then by Theorem 1 we get:

det A ’’ = ( b - a ) ^{ks - 1}

ks - k

(^{b +}— a ) =

= ( b - a ) ^{ks 1} [ b + ( s - 1) a ] .

Then, substituting the given formula in (10) and taking into account that n = (k + l - 1)s, we finally obtain:

det A =

= ( - 1)^{( k — 1)(} l^- 1) s ( b - a )^{( k +} l^- 1) ^{s — 1} [ b + ( s - 1) a ] =

^{( k - 1)(} l ^- 1) ⁿ nn — 1(1 n — k — l + 1 A

= ^{( -} 1)   k ⁺ l ^{- 1}   ( b-a )     ^b +— k + 1 - 1 ay

If p = 1 then the matrix A ’’ will be the matrix of the form (1) of order ks + 1 . Then from Theorem 1 we get:

det A ’’ = ( b - a ) ^ks bb +

ks + 1 - 1

^“ J =

= ( b - a ) ^ks ( b + sa ) .

Then, substituting the given formula in (10) and taking into account that n = ( k + 1 - 1) s + 1 , we finally obtain:

Such matrices arise in the variation of the famous mé-nage problem , where not a round table, but one side of a rectangular table is considered ( [5], ch. 8).

Ifwe denote the permanent of such matrix by p n , then the sequence of permanents will satisfy the following recurrence relation:

( n - 1) P n = ( n ² - n - 1) p n — 1 + np n — 2 + 2( - 1) ^{n +1} , P 1 = P 2 = 0 .

One can also calculate these permanents by the following explicit formula:

2n - k pn = z2 ( k   )(n - k)!(- 1)k.

k =0

Let d n denote the determinant of the matrix A n .

Substituting b = 0 , a = 1 , k = 2 to the formula (2), we get

det A = ( - 1)^{( k — 1)( l —} 1) ^s ( b - a )^{( k + 1 —} 1) ^s ( b + sa ) = , ч x ⁽ k ^{- 1)(} l ^{- 1)(} n ^- 1) /1 x _{n —} 1    1 n — 1    \

= ^{( -} 1)      ^{k +} l ^{- 1      ( b - a} )      (^{b +} k + i - 1 a) •

□

d _n = ( - 1) ^{n 1} — 2”, n — p (mod 2) , 0 < p <  2 .

One can also rewrite this equality in the following form:

d n = ( - 1) ^{n - 1}

n- 1

n- 1

-

2 V n- 2

if n -odd ;

if n – even .

2. The application of determinants of binary matrices to the enumeration of permutations

As mentioned in the Introduction, the binary matrices are one of the favorite objects of the enumerative combinatorics. In particular, they are applied for enumeration of permutations with restricted positions. Following [6] let us describe briefly this mechanism.

Let A = ( a ij ) be a (0 , 1) -matrix of order n . Each of such matrices defines a class B ( A ) of restricted permutations. Namely a permutation p belongs to B ( A ) if and only if the inequality M p ≤ A holds for its incidence matrix M p , i.e. each element of the matrix M p is not more than the corresponding element of the matrix A . The matrix A is called the characteristic matrix of the class B ( A ) . It is not hard to see that the number of permutations in the class B ( A ) is equal to the permanent of the matrix A : |B ( A ) | = per A . By E A and O A denote the number of even and odd permutations from the class B ( A ) , respectively. It is obvious that E A + O A = per A . It is easy to see also that E A -O A = det A . This implies the following formulae for calculating the total number of even and odd permutations from the class B ( A ) :

Applying formulae (11), we obtain sequences of the number of even ( e n ) and odd ( o n ) permutations of the given type depending on the permutation order:

n	1	2	3	4	5	6	7	8	...
p n	0	0	1	3	16	96	675	5413	...
d n	0	0	1	- 1	2	- 2	3	- 3	...
e n	0	0	1	1	9	47	339	2705	...
o n	0	0	0	2	7	49	336	2708	...

As a second example, we will calculate the number of even and odd permutations π ∈ S n such that |n ( i ) - i| >  1 , i = 1 ,... ,n . The characteristic matrix of the given class of permutations is the matrix of order n B n whose main diagonal and its neighboring diagonals are zero, and all other elements are equal to 1 :

B n

0 0 0

.

..

0   0 0

E per A + det A O per A - det A (Ц)

As an example we calculate the number of even and odd permutations n e S _n such that n ( i ) = i, i + 1 for i = 1 ,.. .n - 1 and n ( n ) = n . The characteristic matrix of this class of permutations is the following (0 , 1) -matrix A n of order n :

A n

00 1

..

..

1        0 0

This example is linked with another variation of the mé-nage problem, where a rectangular table is considered and additional restriction on the placement of men is imposed. The explicit formula of the total number of such permutations of order n or, alternatively, of the value of the permanent of B n was found by V.S. Shevelev (see the review [6]). Here we will not give it, but indicate only that the sequence {p ^′ _n } of such numbers has the id-number A 001883 in [9]. Let d ‘ _n denote the determinant of the matrix B _n . Substituting b = 0 , a = 1 , k = l = 2 to the formula (9), we get

3 —n

3, n — 1

0 ,

,

,

if p = 0;

if p = 1;

if p = 2 ,

where n ≡ p (mod 3) . Applying formulae (11), we obtain sequences of the number of even ( e ^′ _n ) and odd ( o ^′ _n ) permutations of the given type depending on the permutation order:

n	1	2	3	4	5	6	7	8	...
p ′ n	0	0	0	1	4	29	206	1708	...
d ′′ n	0	0	0	1	0	- 1	2	0	...
e ′ n	0	0	0	1	2	14	104	854	...
o n	0	0	0	0	2	15	102	854	...

Another version of the application of binary matrices to enumeration of permutations has been described also in [6]. It consists in the following. Let us consider a binary matrix A of order n in which some elements are equal to the variable b , and other elements are equal to 1 . It is easy to see that the coefficient on b^k in the permanent per A will be equal to the number of permutations π ∈ S n whose incidence matrices have exactly k units in the positions, in which there are elements b in the matrix A . Respectively, the coefficient on b^k in the determinant det A will be equal to the difference between the number of even and odd permutations of such type. Then calculating in expressions ¹ ₂ (det A± per A ) the coefficient on b^k , we get the number of even and odd permutations of such kind.

Let us give an example of the application of this scheme. Let π be a permutation. Recall that a number i for which π ( i ) ≥ i is called a weak excedance of π ( [10], p. 40). Let us find the number of even and odd permutations of order n with exactly k weak excedances. Consider a binary matrix of order n C n whose elements on the main diagonal and above it are equal to b , and other elements are equal to 1 :

bbb b b

b

b

.

.

.

b

It is well known ( [10], p. 39–40) that the permanent of this matrix is equal to the Eulerian polynomial of order n , and, respectively, the coefficient on b^k is equal to the Eulerian number T ( n, k ) (A008292 in [9]). By the formula (2) we get that det C n = ( b - 1) ^{n - 1} b . It follows that the coefficient on b^k in det C n is equal to:

c ( n, k ) = ( - 1) ^{n - k n} _{k -} ^- ₁ ¹ .

Hence the number of even and odd permutations of order n with exactly k weak excedances is equal to:

enk =2 (T (n,k) + (-1)n-k (n-;)), onk=1, (T (n,k)—(—1) n—k(k- ^y

Let, for example, k = 2. Then en 2= 12 (T (n, 2) + (-1)n(n - 1)), on 2= 12 (T (n, 2) - (-1)n(n - 1))

and we get the following table:

n	1	2	3	4	5	6	7	8	...
T ( n, 2)	0	1	4	11	26	57	120	247	...
c ( n, 2)	0	1	- 2	3	- 4	5	- 6	7	...
e n 2	0	1	1	7	11	31	57	127	...
o n 2	0	0	3	4	15	26	63	120	...

Let us write out all permutations of order 4 with 2 weak excedances: 14 23 , 2 1 4 3 , 24 13 , 3 12 4 , 3 1 4 2 , 34 12 , 34 21 , 4 1 3 2 , 42 13 , 43 12 , 43 21 — total 7 even and 4 odd permutations (weak excedances are in bold, even permutations are underlined).

The study is supported by Program of UD RAS, project 15-16-1-3.

Acknowledgment. The author is grateful to V.S. Shevelev for useful pointers to the literature and comments.