Theory of paradeterminants and its applications
We consider elements of linear algebra based on triangular tables with entries in some number field and their functions, analogical to the classical notions of a matrix, determinant and permanent. Some properties are investigated and applications in various areas of mathematics are given.
Збережено в:
| Дата: | 2007 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2007
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/157344 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Theory of paradeterminants and its applications / R.A. Zatorsky // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 1. — С. 108–137. — Бібліогр.: 26 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157344 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1573442019-06-21T01:29:32Z Theory of paradeterminants and its applications Zatorsky, R.A. We consider elements of linear algebra based on triangular tables with entries in some number field and their functions, analogical to the classical notions of a matrix, determinant and permanent. Some properties are investigated and applications in various areas of mathematics are given. 2007 Article Theory of paradeterminants and its applications / R.A. Zatorsky // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 1. — С. 108–137. — Бібліогр.: 26 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 15A15. http://dspace.nbuv.gov.ua/handle/123456789/157344 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We consider elements of linear algebra based on
triangular tables with entries in some number field and their functions, analogical to the classical notions of a matrix, determinant
and permanent. Some properties are investigated and applications
in various areas of mathematics are given. |
| format |
Article |
| author |
Zatorsky, R.A. |
| spellingShingle |
Zatorsky, R.A. Theory of paradeterminants and its applications Algebra and Discrete Mathematics |
| author_facet |
Zatorsky, R.A. |
| author_sort |
Zatorsky, R.A. |
| title |
Theory of paradeterminants and its applications |
| title_short |
Theory of paradeterminants and its applications |
| title_full |
Theory of paradeterminants and its applications |
| title_fullStr |
Theory of paradeterminants and its applications |
| title_full_unstemmed |
Theory of paradeterminants and its applications |
| title_sort |
theory of paradeterminants and its applications |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2007 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157344 |
| citation_txt |
Theory of paradeterminants and its applications / R.A. Zatorsky // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 1. — С. 108–137. — Бібліогр.: 26 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT zatorskyra theoryofparadeterminantsanditsapplications |
| first_indexed |
2025-07-14T09:47:21Z |
| last_indexed |
2025-07-14T09:47:21Z |
| _version_ |
1837615223385620480 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2007). pp. 108 – 137
c© Journal “Algebra and Discrete Mathematics”
Theory of paradeterminants and its applications
Roman A. Zatorsky
Communicated by V. V. Kirichenko
Abstract. We consider elements of linear algebra based on
triangular tables with entries in some number field and their func-
tions, analogical to the classical notions of a matrix, determinant
and permanent. Some properties are investigated and applications
in various areas of mathematics are given.
Introduction
In the past decades the process of implementing of the notions and meth-
ods of linear algebra into combinatorial analysis has been intensified. In
particular, there is a well-known monograph by Babai and Frankl [1], and
also monographs by V.E. Tarakanov [16] and I.V.Protasov, O.M.Khromu-
lyak [2], which discuss this topic.
The present paper is a continuation of this process. The functions
of triangular tables analogical to classical functions of determinant and
permanent are considered. While the idea of a determinant is mainly
based on the notions of a permutation and a transversal (tuple of elements
of a square matrix taken one at a time from each row and each column),
the idea of paradeterminant is based on the notions of an ordered partition
of a positive integer [6] and a monotransversal (tuple of elements of a
triangular matrix taken by one from each column). Mainly due to the
implementation of the notion of ordered partition in the construction
of functions of triangular tables, the latter gained many applications in
combinatorial analysis (see [20]–[22], [24]).
2000 Mathematics Subject Classification: 15A15.
Key words and phrases: paradeterminant, parapermanent, triangular matrix.
R. Zatorsky 109
The author was led to the idea of paradeterminants by the combi-
natorial problem of computing the number P (n1, n2, . . . , nr) of shortest
paths in Ferrer graphs. Originally the following formula was obtained
P (n1, n2, . . . , nr) =
=
∑
{s
k1
1 ,...,s
kl
l
}∈Ξ(r)
(−1)r−(λ1+...+λp)
Πl
j=1Π
kj−1
i=0 (nsj
− kj + i + 2)
Πl
i=1ki!
,
where Ξ(r) is the set of multisets A = {sk1
1 , . . . , s
kl
l } defined on page 112,
and {λ1, λ2, . . . , λp} is a secondary specification [17] of a multiset A. This
result was obtained in 1985. Later on, around 2000, while simplifying this
formula author came to the idea of some functions of triangular tables of
elements, which are called here paradeterminants and parapermanents of
triangular matrices, after a suggestion by A.G. Ganyushkin.
The main notions of the theory of paradeterminants were exposed
by the author in 2002 (see [21],[19],[18]). Later, A.G. Ganyushkin [25]
proved theorem 2, which happened to be useful in applications of pa-
radeterminants to partition polynomials and formal power series. Since
paradeterminants have found their applications in several areas of mathe-
matics, the problem of construction of convenient algorithms for comput-
ing these functions of triangular matrices naturally arose. This problem
was formulated by I.V. Protasov and successfully solved (see theorem 4)
by I.I. Lischinsky [25]. In 2003 I.I. Lishchinsky found the connection be-
tween paradeterminants and some class of determinants (see theorem 18).
Approximately at the same time, during discussion related to some prob-
lem about F–determinants, it was noticed by the author and N.M.Dyakiv
[26] that F–determinants [21] are a special case of paradeterminants.
Since 2002, all the efforts of the author have been devoted to finding
applications of paradeterminants and parapermanents. As a result, their
applications were found in number theory and the theory of continued
fractions. They appeared to be useful in solving linear recurrent equa-
tions, for partition polynomials, operations with formal power series and
also in solving combinatorial and some other problems.
It should be noted here that the theory of paradeterminants is being
developed under a constant communication between the author and the
two Ukrainian mathematicians R.I. Grigorchuk and A.G. Ganyushkin.
1. Definition of a paradeterminant and parapermanent
Let K be a fixed number field.
110 Theory of Paradeterminants and its Applications
Definition 1. A triangular table of numbers from some field K
A =
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
n
(1.1)
is called a triangular matrix, and the number n is called its order.
Note that a triangular matrix in the definition is not a matrix in
the usual sense because it is triangular rather than rectangular table of
numbers.
Definition 2. A matrix of the form
A =
M1
0 M2
...
...
. . .
0 0 · · · Ms
n
, (1.2)
where Mi, i = 1, . . . , s are some triangular matrices and 0’s denote some
rectangular zero matrices, is called a triangular block–diagonal matrix
To every element aij of the matrix (1.1) we correspond the (i− j +1)
elements aik, k = j, . . . , i, which are called the derived elements of the
matrix generated by the key element aij .
The product of all derived elements generated by the element aij is
denoted by {aij} and called the factorial product of the key element aij ,
i.e.
{aij} =
i
∏
k=j
aik.
Definition 3. A tuple of key elements of the matrix (1.1) is called a
normal tuple of this matrix if the derived elements of these key elements
form a monotransversal, i.e. they form a set of elements of cardinality n,
no two of which belong to the same column in the matrix.
Let P(n) be the set of all ordered partitions (compositions) (see [5],
[6], p. 67) of a positive integer n into positive integer summands. It is
known that
|P(n)| =
n
∑
r=1
(
n − 1
r − 1
)
= 2n−1. (1.3)
It is easy to see that there is a 1 − 1 correspondence between normal
tuples of key elements of matrix (1.1) and compositions of a positive
integer n.
R. Zatorsky 111
We associate a sign (−1)ε(a) to every normal tuple a of key elements,
where ε(a) is the sum of all the indices of the key elements of this tuple.
Definition 4. The paradeterminant of a triangular matrix (1.1) is the
number
ddet(A) =
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
=
=
∑
(α1,α2,...,αr)∈P(n)
(−1)ε(a)
r
∏
s=1
{ai(s),j(s)},
where ai(s),j(s) is the key element corresponding to the s-th component
of the partition α = (α1, α2, . . . , αr), and the symbol ε(a) is the sign of
the normal tuple a of key elements.
In analogy to the notion of paradeterminant of a matrix (1.1) we
introduce the notion of a parapermanent of a triangular matrix.
Definition 5. The paradeterminant of a triangular matrix (1.1) is the
number
pper(A) =
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
=
∑
(α1,α2,...,αr)∈P(n)
r
∏
s=1
{ai(s),j(s)},
where ai(s),j(s) is the key element corresponding to the s-th component
of the partition α = (α1, α2, . . . , αr).
Remark 1. According to (1.3) the paradeterminant and the paraperma-
nent of a matrix of order n consist of 2n−1 summands.
Example 1. The parapermanent of a 3-rd order matrix is equal to:
a11
a21 a22
a31 a32 a33
= a11a22a33 − a21a22a33 − a11a32a33 + a31a32a33.
Definition 6. (see [13], [3]) A multiset A is any unordered tuple of
elements of some set [A], which is called a basis of this multiset.
The number k of times an element a of a set [A] occurs in a multiset
A is called the multiplicity of a in A and is denoted as ak ∈ A. Multisets
are mostly written in their canonical form as A = {ak1
1 , . . . , akn
n }.
112 Theory of Paradeterminants and its Applications
Definition 7. Ξ(n)-set is the set of all ordered multisets
ξ = {ξ(1), ξ(2), . . . , ξ(n)}
satisfying the following conditions:
1) ξ(j) satisfies inequality j ≤ ξ(j) ≤ n, j = 1, 2, . . . , n;
2)for each j = 1, 2, . . . , n the following equality holds: ξ(j) = ξ(j +
1) = . . . = ξ(ξ(j)).
Remark 2. If j = n then inequality 1) implies ξ(n) = n.
Proposition 1. (i) The set Ξ(n) contains 2n−1 elements, and Ξ(1) =
{{1}}.
(ii) If Ξ(k) is already constructed, then the elements of Ξ(k + 1) can be
obtained in the following way: 2k−1 elements are obtained by adding k+1
at the (k + 1)-st place in each k–multiset from Ξ(k), and the other 2k−1
elements are obtained by replacing k with k + 1 and adding k + 1 at the
(k + 1)-st place in each k-multiset from Ξ(k).
Theorem 1. If A is a triangular matrix (1.1) then the following equalities
hold:
ddet(A) =
∑
ξ∈Ξ(n)
(−1)n−r · aξ(1),1aξ(2),2 · . . . · aξ(n),n,
pper(A) =
∑
ξ∈Ξ(n)
aξ(1),1aξ(2),2 · . . . · aξ(n),n,
where r is the number of elements in the basis of the multiset ξ, i.e.
number of its distinct elements.
Theorem 2. (Ganyushkin O.G.) If A is a triangular matrix (1.1), then
the following equalities hold:
ddet(A) =
n
∑
r=1
∑
α1+...+αr=n
(−1)n−r
r
∏
s=1
{aα1+...+αs,α1+...+αs−1+1}, (1.4)
pper(A) =
n
∑
r=1
∑
α1+...+αr=n
r
∏
s=1
{aα1+...+αs,α1+...+αs−1+1}, (1.5)
where the summation is over the set of positive integer solutions of the
equation α1 + . . . + αr = n.
Let us define product of a vector (b1, b2, . . . , bn) with a matrix parade-
terminant (1.1), using equality (1.4) by
(b1, b2, . . . , bn) · ddet(A)
def
= (1.6)
R. Zatorsky 113
=
n
∑
r=1
br ·
∑
α1+...+αr=n
(−1)n−r
r
∏
s=1
{
aα1+...+αs,α1+...+αs−1+1
}
.
Analogously define product of a vector (b1, b2, . . . , bn) with a matrix
parapermanent using equality (1.5) by
(b1, b2, . . . , bn) · pper(A)
def
= (1.7)
=
n
∑
r=1
br ·
∑
α1+...+αr=n
r
∏
s=1
{
aα1+...+αs,α1+...+αs−1+1
}
.
To each element aij of a triangular matrix (1.1) we associate the
triangular table of elements of this matrix that has aij in the bottom left
corner. We call this table a corner of the matrix and denote it by Rij .
Obviously, the corner Rij is a triangular matrix of order (i − j + 1), and
it contains only elements ars of matrix (1.1) whose indices satisfy the
inequalities j ≤ s ≤ r ≤ i.
In the sequel we will assume that
ddet(R01) = pper(R01) = ddet(Rn,n+1) = pper(Rn,n+1) = 1.
Definition 8. A rectangular table, denoted T (i), i = 1, 2, . . . , n, of ele-
ments of a triangular matrix (1.1) is inscribed in this matrix if one of its
vertices coincides with the element an1, and the opposite one coincides
with the element aii. We will denote this table by T (i).
Remark 3. According to definition 8, T (1) is the fist column and T (n)
is the last row of the matrix.
In order to compute paradeterminants and parapermanents it is con-
venient to use algebraic complements.
Definition 9. The numbers
Dij = (−1)i+j · ddet(Rj−1,1) · ddet(Rn,i+1),
Pij = pper(Rj−1,1) · pper(Rn,i+1),
where Rj−1,1 and Rn,i+1 are corners, are called the algebraic complements
to the factorial product {aij} of the key element aij of the triangular
matrix (1.1).
More detailed information about the notions in the first section can
be found in [18].
114 Theory of Paradeterminants and its Applications
2. Properties of paradeterminants and parapermanents of
triangular matrices
Although the definitions of paradeterminants and parapermanents sig-
nificantly differ from the classical definitions of determinants and perma-
nents, their properties are similar in many ways.
Proposition 2. [18] Let each elements ari, r = i, i + 1, . . . , n of the
i-th column of the triangular matrix (1.1) be a sum of two elements
bri + cri. Then the paradeterminant of this matrix equals the sum of two
paradeterminants corresponding to matrices whose elements are equal to
the elements in A, except for the elements in the i-th column, which are
equal to bri and cri, r = i, i + 1, . . . , n, respectively.
Analogous statement is true for parapermanents.
Proposition 3. [18] For a block-diagonal triangular matrix (1.2) the
following is true:
ddet(A) = ddet(M1) · ddet(M2) · . . . · ddet(Ms)
pper(A) = pper(M1) · pper(M2) · . . . · pper(Ms)
A proposition on differentiation of paradeterminants and paraperma-
nents analogous to the one for determinants and permanents of a square
matrix holds.
Theorem 3. [18] ( Decomposition of paradeterminant and paraperma-
nent by elements of an inscribed rectangular table) Let A be triangular
matrix (1.1) and T (i) be some inscribed rectangular table. Then the
following equalities hold:
ddet(A) =
i
∑
s=1
n
∑
r=i
{ars} · Drs, (2.1)
pper(A) =
i
∑
s=1
n
∑
r=i
{ars} · Prs, (2.2)
where Drs and Prs are the algebraic complements to the factorial product
of the key element ars, which belongs to the inscribed rectangular table
T (i).
R. Zatorsky 115
Corollary 1. For i = 1 by formulae (2.1)–(2.2) and 3, obtain the de-
composition of paradeterminant and parapermanent by elements of their
first column
ddet(A) =
n
∑
r=1
(−1)r+1 · {ar1} · ddet(Rn,r+1),
pper(A) =
n
∑
r=1
{ar1} · pper(Rn,r+1).
For i = n obtain the respective decompositions by elements of last row
ddet(A) =
n
∑
s=1
(−1)n+s · {ans} · ddet(Rs−1,1),
pper(A) =
n
∑
s=1
{ans} · pper(Rs−1,1).
It is known that the question of Polia ”Does there exist a way to assign
+ and − sign to each element of a square matrix of order n, n ≥ 3, in
such a way that its permanent would be equal the determinant?” doesn’t
have a positive answer. Moreover, Markus and Minc proved [9] that for
n ≥ 3 there is no linear transformation T on the set of all matrices of
order n such that per(T (A)) = det(A).
But this is not the case for paradeterminants and parapermanents.
Proposition.[18] If A is a triangular matrix (1.1), then the following
equality holds
ddet((−1)δij+1 · aij)1≤j≤i≤n = pper(aij)1≤j≤i≤n. (2.3)
Remark 4. Using multiplication of vectors by paradeterminants (see
(1.6), p. 112), equality (2.3) can be written as
((−1)n−1, (−1)n−2, · · · , (−1)0) ·
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
=
=
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
.
116 Theory of Paradeterminants and its Applications
The following theorem provides a convenient way of computing pa-
radeterminants and parapermanents.
Theorem 4. (Lishchinsky I.I.) The following equalities hold:
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
= (−1) ·
(a21 − a11) · a22
(a31 − a11) · a32 a33
...
...
. . .
(an1 − a11) · an2 an3 · · · ann
,
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
n
=
(a21 + a11) · a22
(a31 + a11) · a32 a33
...
...
. . .
(an1 + a11) · an2 an3 · · · ann
n−1
.
Remark 5. To find the value of a paradeterminant (parapermanent)
it is enough to perform n·(n−1)
2 multiplications and the same number
of additions. Since a triangular matrix contains n·(n+1)
2 entries and all
of them affect the value, the proposed algorithm cannot be essentially
improved.
Note that we listed only a few established paradeterminant and para-
permanent properties. Other properties can be found in the paper [18].
3. Applications of parapermanents in the investigation of
linear recurrent sequences of k-th order
Parapermanents of triangular matrices are convenient tools for investi-
gation of linear recurrent sequences. They can be used to solve linear
recurrent equations of k-th order, and to establish some important func-
tional relations between the terms of sequences generated by recurrent
equations. Also they are used to define an important class of so called
normal initial conditions in linear recurrent equations.
Theorem 5. [18] Consider a linear equation of k-th order
un = a1 ·un−1 + . . .+ak ·un−k, a1 6= 0, 1 ≤ k ≤ n, n = k+1, k+2, . . . ,
(3.1)
with initial conditions
ui = a
(0)
i , a
(0)
i ∈ R, i = 1, . . . , k. (3.2)
R. Zatorsky 117
Then the following equality holds
un =
a1x1x2
a2
a1
x1 a1x3
· · · · · ·
. . .
ak−1
ak−2
x1
ak−2
ak−3
· · · a1xk
ak
ak−1
x1
ak−1
ak−2
· · · a2
a1
a1
0 ak
ak−1
· · · a3
a2
a2
a1
a1
· · · · · · · · · · · · · · · · · ·
. . .
0 0 · · · 0 ak
ak−1
· · · a2
a1
a1
n−1
, (3.3)
u1 = x1, n = k + 1, k + 2, · · · ,
where the corrections xi are defined by the equalities
x1 = a
(0)
1 , xi =
a
(0)
i
a1a
(0)
i−1 + a2a
(0)
i−2 + · · · + ai−2a
(0)
2 + ai−1a
(0)
1
, i = 2, . . . , k,
The following is also true
a
(0)
1 + a
(0)
2 · (1 − 1
x2
) · x1 + . . . + a
(0)
k · (1 − 1
xk
) · xk−1
1 − a1x − . . . − akxk
=
∞
∑
i=1
uix
i−1.
(3.4)
Remark 6. For k = 1 equality (3.3) is of the form
un =
a1x1
0 a1
· · · · · ·
. . .
0 0 · · · a1
n−1
.
Remark 7. If some coefficient ai, i = 2, . . . , k− 1 in the recurrent equa-
tion (3.1) equals zero, then the zeros cancel out in the evaluation of
paradeterminants or parapermanents and the indefiniteness disappears.
Let us denote
ui = a1a
(0)
i−1 + a2a
(0)
i−2 + . . . + ai−1a
(0)
i , i = 2, . . . , k.
The differences ui − ui will be called defects. The equality (3.4) can then
be written as
u1 +
∑k
i=2(ui − ui) · x
i−1
1 − a1x − . . . − akxk
=
∞
∑
i=1
uix
i−1 (3.5)
118 Theory of Paradeterminants and its Applications
Definition 10. Let us call initial conditions
u1 = 1, ui =
a1
a2
a1
a1
· · · · · ·
. . .
ai−1
ai−2
ai−2
ai−3
· · · a1
i−1
, i = 2, . . . , k (3.6)
of the recurrent equation (3.1) normal initial conditions.
Remark 8. If initial conditions in the equation (3.1) are normal, then
all corrections xi, i = 1, . . . , k, in the equality (3.3) are equal to one, and
all defects in the equality (3.5) are equal to zero. Then equality (3.5)
may be written as
1
1 − a1x − . . . − akxk
=
∞
∑
i=1
uix
i−1.
As noted before, it is easy to establish general functional relations
between terms of sequences generated by linear recurrent equations of
k-th order by using parapermanents, which are relatively hard to prove
even in the case k = 2.
Theorem 6. If sequences {u∗
n}
∞
n=1, {un}
∞
n=1 satisfy the recurrent equa-
tion (3.1) of k-th order with initial conditions (3.2) and (3.6) respectively,
and k < r, then
u∗
r+s =
k
∑
i=1
ai
r
∑
j=r−i+1
u∗
jur+s−i−j+1
. (3.7)
Corollary 2. If a sequence {un}
∞
n=1 satisfies the recurrent equation (3.1)
with normal initial conditions (3.6), then
ur+s =
k
∑
i=1
ai
r
∑
j=r−i+1
ujur+s−i−j+1
. (3.8)
To establish relation (3.8) it is enough to decompose the paraperma-
nent which is the solution of equation (3.1) with normal initial conditions,
by elements of some inscribed rectangular table.
The next two theorems illustrate application of parapermanents in in-
vestigating number-theoretic properties of sequences generated by linear
recurrent equation of second order.
We essentially use relations (3.7), (3.8) for k = 2.
R. Zatorsky 119
Theorem 7. Let the sequence {uk}
∞
k=1 satisfy the recurrent equation of
second order
un+2 = a1un+1 + a2un (3.9)
with integer non-zero coefficients and normal initial conditions
u1 = 1, u2 = a1.
Then
1) the following equalities hold:
ur+s = ur+1us + a2urus−1, r = 1, 2, . . . ; s = 2, 3, . . . ,
usr ≡ 0(mod ur), s, r = 1, 2, . . . ;
2) if the coefficients in (3.9) are relatively prime, i.e. (a1, a2) = 1,
then
(us, ur) = u(s,r).
Corollary 3. If the sequence {uk}
∞
k=1 satisfies the conditions of theorem
7 and uk 6= 1, 2 ≤ k, then us is a prime if and only if s is a prime.
Corollary 4. Let the sequence {uk}
∞
k=1 satisfy conditions of theorem 7
and p be a prime. Then up is relatively prime with all previous terms of
this sequence.
Corollary 5. Let the sequence {uk}
∞
k=1 satisfy the conditions of theorem
7. If a2 = b2, where b is an integer, then each term u2m+1, 1 < m of this
sequence can be represented as a sum of squares of two natural numbers
u2m+1 = u2
m+1 + (bum)2.
Corollary 6. For each natural number m > 0 the following holds:
m
∑
i=0
(−1)i
(
2m − i
i
)
a2(m−i)b2i =
=
[m/2]
∑
i=0
(−1)i
(
m − i
i
)
am−2ib2i −
−
[(m−1)/2]
∑
i=0
(−1)i
(
m − i − 1
i
)
am−2i−1b2i+1
×
×
[m/2]
∑
i=0
(−1)i
(
m − i
i
)
am−2ib2i +
+
[(m−1)/2]
∑
i=0
(−1)i
(
m − i − 1
i
)
am−2i−1b2i+1
120 Theory of Paradeterminants and its Applications
Example 2. For m = 7 and m = 11 identity (2) can be written as:
a6 − 5a4b2 + 6a2b4 − b6 = (a3 − 2ab2 − a2b + b3) · (a3 − 2ab2 + a2b − b3),
a10 − 9a8b2 + 28a6b4 − 35a4b6 + 15a2b8 − b10 =
= (a5 − a4b − 4a3b2 + 3a2b3 + 3ab4 − b5)·
·(a5 + a4b − 4a3b2 − 3a2b3 + 3ab4 + b5).
Remark 9. Since the recurrent equation un+2 = un+1 + un generates
the Fibonacci sequence, theorem 7 can be considered as generalization of
some relations between Fibonacci numbers (see [7], p. 325-327).
Theorem 8. Let the sequences {un}
∞
n=1 and {u∗
n}
∞
n=1 satisfy a recurrent
equation of second order
un+2 = a1un+1 + a2un
with initial conditions
u1 = 1, u2 = a1; u∗
1 = k, u∗
2 = a1,
respectively. Then:
(1)for each n, n ≥ 3, the following holds
u∗
n = un + (k − 1)a2un−2;
(2) If
k = a2 = s2 + 1,
and 0 < a1, then for each n, n ≥ 3, the number u∗
2n−1 is a sum of three
squares:
u∗
2n−1 = (un)2 + ((s2 + 1) · un−1)
2 + ((s3 + s) · un−2)
2; (3.10)
(3) If
k = s2 + 1, a2 = b2,
then for each n, 2 ≤ n the number u∗
2n+1 is a sum of four squares:
u∗
2n+1 = u2
n+1 + (bun)2 + (sbun)2 + (sb2un−1)
2. (3.11)
Example 3. Let a1 = 4, s = 2 in theorem 8 . Then u1 = a2 = k = 5,
u∗
n =
1
2
· (3 · 5n−1 + 7 · (−1)n−1), un =
1
6
· (5n + (−1)n−1)
R. Zatorsky 121
and equality (3.10) can be written as
1
2
· (3 · 52n−2 + 7) ==
(
1
6
· (5n + (−1)n−1)
)2
+
(
5
6
· (5n−1 + (−1)n−2)
)2
+
(
5
3
· (5n−2 + (−1)n−3)
)2
.
In particular, for n = 13 the last equality provides a decomposition of
the prime number 89406967163085941 into sum of three squares:
89406967163085941 = 2034505212 + 2034505202 + 813802102.
Example 4. If in theorem 8, (3) we put a1 = 3, a2 = b = 2, s = 1,
then u∗
n = 4n−1 + (−1)n−1, un = 1
5 · (4n + (−1)n−1) and equality (3.11)
transforms to
24m + 1 =
(
4m+1 + (−1)m
5
)2
+
(
22m+1 + (−1)m−1 · 2
5
)2
+
+
(
22m+1 + (−1)m−1 · 2
5
)2
+
(
22m + (−1)m−2 · 4
5
)2
.
Since Fermat numbers Fn = 22n
+ 1 can be written as 24m + 1 for
all n ≥ 2, they can be decomposed into sum of four squares of positive
integers for all n ≥ 3.
4. Applications of parapermanents to the study of contin-
ued fractions
Suppose we are given some continued periodic fraction
δ = a0 +
b1
a1 +
b2
a2 +···+
bn
an +···
= a0 +
∞
K
i=1
(
bi
ai
)
,
where
ask+m = am > 0; bsk+m = bm > 0; m = 1, . . . , k; s = 0, 1, . . . ; k ≥ 2
and its n-th approaching fraction
δn ==
Pn
Qn
= a0 +
b1
a1 +
b2
a2 +···+
bn
an
= a0 +
n
K
i=1
(
bi
ai
)
,
where
Pn = anPn−1 + bnPn−2, P−2 = 0, P−1 = 1,
122 Theory of Paradeterminants and its Applications
Qn = anQn−1 + bnQn−2, Q−2 = 1, P−1 = 0, b0 = 1.
It is easy to see that
Pn =
a0
b1
a1
a1
0 b2
a2
a2
· · · · · · · · ·
. . .
0 . . . 0 bn
an
an
, n = 0, 1, . . . ;
Qn =
a1
b2
a2
a2
0 b3
a3
a3
· · · · · · · · ·
. . .
0 . . . 0 bn
an
an
, n = 1, 2, . . .
Theorem 9. [23] The sequence
δr = a0 + b1 ·
Br−1
Ar
,
where
Ar = b1 · α · Br−2 + β · Ar−1, Br−1 = b1 · γ · Br−2 + λ · Ar−1,
α =
a1
b2
a2
a2
0 b3
a3
a3
· · · · · · · · ·
. . .
0 . . . 0
bk−1
ak−1
ak−1
, β = A1 =
a1
b2
a2
a2
0 b3
a3
a3
· · · · · · · · ·
. . .
0 . . . 0 bk
ak
ak
,
γ =
a2
b3
a3
a3
0 b4
a4
a4
· · · · · · · · ·
. . .
0 . . . 0
bk−1
ak−1
ak−1
, λ = B0 =
a2
b3
a3
a3
0 b4
a4
a4
· · · · · · · · ·
. . .
0 . . . 0 bk
ak
ak
,
such that the following inequality is satisfied
ω =
b1
β2
· |βγ − αλ| < 1,
converges to δ, and moreover there is an error bound of the form
|δ − δr| < σ ·
ωr
1 − ω
,
R. Zatorsky 123
where
σ =
b1λβ
b1λα + β2
.
Remark 10. When k = 2 we assume γ = 1.
Analogous theorem on combined continued fractions is proved in [23].
5. Paradeterminants and partition polynomials
The notion of partition polynomials introduced by Bell [8] has wide range
of applications in discrete mathematics. They appear in differentiation
of composite functions [10], [12], in number theory [11], algebra, etc. In
this section identities between some important partition polynomials and
paradeterminants of triangular matrices are established.
Consider a triangular matrix of the form
A =
k11 · x1
k21 ·
x2
x1
k22 · x1
· · · · · · · · · · · · · · · · · · · · · · · ·
kn1 ·
xn
xn−1
kn2 ·
xn−1
xn−2
· · · knn · x1
n
=
(
kij ·
xi−j+1
xi−j
)
1≤j≤i≤n
,
(5.1)
x0 = 1, where kij is some rational function of i and j.
Let M be a fixed multiset with primary specification of Sachkov [17]
of the form
[
1λ1 , 2λ2 , . . . , nλn
]
.
If the exponents of the primary specification of a multiset M satisfy
the equation λ1 + 2λ2 + . . . + nλn = n then such a multiset is called an
unordered partition of the positive integer n and is denoted by π(n).
The sum of all elements of the primary specification of a partition
π(n) is denoted by λ(π), i.e.
λ(π) = λ1 + λ2 + . . . + λn.
Note that λ(π) has certain combinatorial sense, namely it is the number
of components of the partition π(n).
Let Π(n) be the set of all multisets π(n), and Πk(n) be the set of
all multisets π(n) such that the exponents of their primary specifications
satisfy the equality λ(π) = k.
Definition 11. Partition polynomials are polynomials of the form
P (x1, . . . , xn) =
n
∑
k=1
yk ·
∑
π(n)∈Πk(n)
c(n; λ1, . . . λn) · xλ1
1 · . . . · xλn
n , (5.2)
where yk, c(n; λ1, . . . , λn) are some rational numbers.
124 Theory of Paradeterminants and its Applications
Remark 11. If all yk in the equality (5.2) are equal to 1, then it can be
transformed to the following form
P (x1, . . . , xn) =
n
∑
k=1
∑
π(n)∈Πk(n)
c(n; λ1, . . . , λn) · xλ1
1 · . . . · xλn
n =
=
∑
π(n)∈Π(n)
c(n; λ1, . . . λn) · xλ1
1 · . . . · xλn
n . (5.3)
Polynomials of the form (5.3) are called primary partition polynomials.
Theorem 10. Paradeterminants and parapermanents of triangular ma-
trices of the form (5.1) are primary partition polynomials, i.e. the equal-
ities
pper(A) =
∑
π(n)∈Π(n)
c(n; λ1, . . . , λn) · xλ1
1 · . . . · xλn
n , (5.4)
ddet(A) =
∑
π(n)∈Π(n)
(−1)n−λ(π) · c(n; λ1, . . . , λn) · xλ1
1 · . . . · xλn
n . (5.5)
are satisfied.
If the equalities (5.4)-(5.5) are satisfied, then the partition polynomi-
als
n
∑
k=1
yk ·
∑
π(n)∈Πk(n)
c(n; λ1, . . . , λn) · xλ1
1 · . . . · xλn
n
, (5.6)
n
∑
k=1
yk ·
∑
π(n)∈Πk(n)
(−1)n−k · c(n; λ1, . . . , λn) · xλ1
1 · . . . · xλn
n
,
according to the definition (1.6) of a product of a vector and a parade-
terminant and the definition (1.7) of a product of a vector and a parap-
ermanent, may be written in the form of products:
(y1, . . . , yn) ·
τ11 · x1
τ21 ·
x2
x1
τ22 · x1
... · · ·
. . .
τn1 ·
xn
xn−1
τn2 ·
xn−1
xn−2
· · · τnn · x1
(y1, . . . , yn) ·
τ11 · x1
τ21 ·
x2
x1
τ22 · x1
· · · · · · · · · · · · · · · · · · · · ·
τn1 ·
xn
xn−1
τn2 ·
xn−1
xn−2
· · · τnn · x1
R. Zatorsky 125
Definition 12. A triangular matrix of the form
Bn(a1, a2, . . . , an) =
=
a1
1
1 · a2
a1
a1
1
2 · a3
a2
2
1 · a2
a1
a1
... · · · · · ·
. . .
1
n−2 · an−1
an−2
2
n−3 · an−2
an−3
3
n−4 · an−3
an−4
· · · a1
1
n−1 · an
an−1
2
n−2 · an−1
an−2
3
n−3 · an−2
an−3
· · · n−1
1 · a2
a1
a1
n
=
=
(
j
i − j + j · δij
·
ai−j+1
ai−j
)
is called a triangular Bell matrix.
Proposition 4. The right part of the Faa di Bruno formula
dn
dxn
f(g(x)) =
n
∑
m=1
dm
dgm
f(g(x))
∑
π(n)∈Πm(n)
n!
λ1! · . . . · λn! · (1!)λ1 · . . . · (n!)λn
×
×(g′(x))λ1 · . . . · (g(n)(x))λn
is a partition polynomial and the formula can be expressed in the form
dn
dxn
f(g(x)) = (f
′
g, f
′′
g , . . . , f (n)
g ) · pper(B(g
′
x, g
′′
x , . . . , g(n)
x ).
Proposition 5. For a triangular matrix of the form
Z (x1, x2, . . . , xn) =
x1
x2
x1
x1
· · · · · · · · ·
xn
xn−1
xn−1
xn−2
· · · x2
x1
x1
n
=
(
xi−j+1
xi−j
)
1≤j≤i≤n
(5.7)
the next identities hold:
pper (Z(x1, . . . , xn)) =
∑
π(n)∈Π(n)
(λ1 + . . . + λn)!
λ1! · . . . · λn!
· xλ1
1 · . . . · xλn
n , (5.8)
ddet (Z(x1, . . . , xn)) = (5.9)
=
∑
π(n)∈Π(n)
(−1)n−(λ1+...+λn) ·
(λ1 + . . . + λn)!
λ1! · . . . · λn!
· xλ1
1 · . . . · xλn
n .
126 Theory of Paradeterminants and its Applications
By replacing xi, i = 1, . . . , n,, in identities (5.8), (5.9) by yi
i and yi
i! ,
respectively, we obtain new important identities:
pper
(
Z
(y1
1
,
y2
2
, . . . ,
yn
n
))
=
[
i − j + δij
i − j + 1
·
yi−j+1
yi−j
]
1≤j≤i≤n
=
=
∑
Π(n)
(λ1 + . . . + λn)!
1λ1λ1! · . . . · nλnλn!
· yλ1
1 · . . . · yλn
n ,
pper
(
Z
(y1
1!
,
y2
2!
, . . . ,
yn
n!
))
=
[
1
i − j + 1
·
yi−j+1
yi−j
]
1≤j≤i≤n
=
=
∑
Π(n)
(λ1 + . . . + λn)!
(1!)λ1λ1! · . . . · (n!)λnλn!
· yλ1
1 · . . . · yλn
n ,
ddet
(
Z
(y1
1
,
y2
2
, . . . ,
yn
n
))
=
〈
i − j + δij
i − j + 1
·
yi−j+1
yi−j
〉
1≤j≤i≤n
=
=
∑
Π(n)
(−1)n−(λ1+...+λn) ·
(λ1 + . . . + λn)!
1λ1λ1! · . . . · nλnλn!
· yλ1
1 · . . . · yλn
n ,
ddet
(
Z
(y1
1!
,
y2
2!
, . . . ,
yn
n!
))
=
〈
1
i − j + 1
·
yi−j+1
yi−j
〉
1≤j≤i≤n
=
=
∑
Π(n)
(−1)n−(λ1+...+λn)·
(λ1 + . . . + λn)!
(1!)λ1λ1! · . . . · (n!)λnλn!
· yλ1
1 · . . . · yλn
n .
Consider one more example of a primitive partition polynomial.
Proposition 6. If
C =
(
j
i − j + 1
·
xi−j+1
xi−j
)
1≤j≤i≤n
,
then the following identities hold:
pper(C) =
∑
π(n)∈Π(n)
n! · (λ(π))!
λ1! · . . . · λn! · (1!)λ1 · . . . · (n!)λn
· xλ1
1 · . . . · xλn
n ,
ddet(C) =
=
∑
π(n)∈Π(n)
(−1)n−λ(π) ·
n! · (λ(π))!
λ1! · . . . · λn! · (1!)λ1 · . . . · (n!)λn
· xλ1
1 · . . . · xλn
n .
The following propositions also hold.
R. Zatorsky 127
Proposition 7.
a)
[
j
i − j + j · δij
]
1≤j≤i≤n
=
=
∑
π(n)∈Π(n)
n!
λ1! · . . . · λn! · (1!)λ1 · . . . · (n!)λn
=
=
n
∑
k=1
∑
π(n)∈Πk(n)
n!
λ1! · . . . · λn! · (1!)λ1 · . . . · (n!)λn
=
n
∑
k=1
S(n, k) ;
b)
〈
j
i − j + j · δij
〉
1≤j≤i≤n
=
=
∑
π(n)∈Π(n)
(−1)n−λ(π) ·
n!
λ1! · . . . · λn! · (1!)λ1 · . . . · (n!)λn
=
=
n
∑
k=1
∑
π(n)∈Πk(n)
(−1)n−k ·
n!
λ1! · . . . · λn! · (1!)λ1 · . . . · (n!)λn
=
=
n
∑
k=1
(−1)n−kS(n, k) ,
where S(n, k) denote Stirling numbers of the second kind.
Proposition 8.
a) [j − (j − 1) · δij ]1≤j≤i≤n =
∑
π(n)∈Π(n)
n!
λ1! · . . . · λn! · 1λ1 · . . . · nλn
=
=
n
∑
k=1
(−1)n−k · s(n, k) = n!,
b) 〈(j − (j − 1) · δij)〉1≤j≤i≤n =
=
∑
π(n)∈Π(n)
(−1)n−(λ1+...+λn) n!
λ1! . . . · λn! · 1λ1 . . . · nλn
=
=
n
∑
k=1
s(n, k) =
{
1 , n = 1,
0 , n > 1.
where s(n, k) denote Stirling numbers of the first kind.
Some results of this section were announced by the author in [22] and
an extended version of the content is accepted for publication.
128 Theory of Paradeterminants and its Applications
6. Paradeterminants and formal operations with formal
power series
One of the central methods of combinatorial analysis is the method of
generating functions [4], which uses formal operations with power se-
ries. However operations such as inversion, composition of series and
some other operations with formal series, as it is well known, present
some difficulties. In this section, using techniques of paradeterminants
and parapermanents of triangular matrices, we construct some recurrent
algorithms for formal operations with series.
Some results of this section were announced by the author in [24] and
an extended version of the content is accepted to print.
We consider formal power series with nonzero constant term.
Theorem 11. Let A(x) =
∑∞
i=0 aix
i, a0 = 1, be some formal power
series. Then the following equalities hold:
(A(x))n = 1 +
∞
∑
k=1
(−1)k
〈
(i − j + 1)n − (j − 1)
(i − j)n − j
·
ai−j+1
ai−j
〉
1≤j≤i≤k
· xk,
(A(x))−n = 1 +
∞
∑
k=1
(−1)k
〈
(i − j + 1)n + (j − 1)
(i − j)n + j
·
ai−j+1
ai−j
〉
1≤j≤i≤k
· xk,
(A(x))
1
n = 1 +
∞
∑
k=1
(−1)k
〈
−(i − j + 1) + (j − 1)n
−(i − j) + jn
·
ai−j+1
ai−j
〉
1≤j≤i≤k
· xk,
(A(x))−
1
n = 1 +
∞
∑
k=1
(−1)k
〈
(i − j + 1) + (j − 1)n
(i − j) + jn
·
ai−j+1
ai−j
〉
1≤j≤i≤k
· xk.
Theorem 12. Let A(x) = 1+
∑∞
i=1 aix
i, B(x) = 1+
∑∞
i=1 bix
i, C(x) =
1 +
∑∞
i=1 cix
i be some formal power series such that
C(x) =
A(x)
B(x)
.
Then
ci =
i−1
∑
j=0
(ai−j − bi−j) ·
〈
bs−r+1
bs−r
〉
1≤r≤s≤j
, i = 1, 2, . . . .
We assume that
〈
bs−r+1
bs−r
〉
1≤r≤s≤0
= 1.
R. Zatorsky 129
Corollary 7. If A(x) is the formal power series from Theorem 12 then
1
A(x)
= 1 − 〈a1〉 · x
1 + a1
a2
a1
a1
· x2 − . . .+
+(−1)i
a1
a2
a1
a1
... · · ·
. . .
ai
ai−1
ai−1
ai−2
· · · a1
· xi + . . .
Theorem 13. Let f(x) and g(x) be two infinitely differentiable functions
such that
gi
x(0) = ai, f i
x(a0) = bi, i = 0, 1, 2, . . . .
Then
f(g(x)) = b0+
1
1!
pper(B1(a1)·(b1)·x+
1
2!
pper(B2(a1, a2))·(b1, b2)·x
2+. . . ,
where Bn(a1, a2, . . . , an) is a triangular Bell matrix.
Corollary 8. If the function f(x) is infinitely differentiable and g(x) can
be presented as a series
g(x) = a0 + a1x + a2x
2 + . . . ,
such that equalities f(a0) = b0, f
(i)
x (a0) = bi, i = 1, 2, . . . , hold, then
f(g(x)) = b0+pper(Z1(a1)·
(
b1
1!
)
·x+pper(Z2(a1, a2))·
(
b1
1!
,
b2
2!
)
·x2+. . . ,
where Zn(a1, a2, . . . , an) is a triangular matrix of the form (5.7).
We consider now formal operations with formal power series with zero
constant term.
Theorem 14. (Theorem on composition of series) If formal power series
c(x) =
∑∞
i=1 cix
i is a composition of formal power series b(x) =
∑∞
i=1 bix
i
and a(x) =
∑∞
i=1 aix
i, i.e. c(x) = b(a(x)) =
∑∞
i=1 bia
i(x), then
ci = (b1, b2, . . . , bi) ·
a1
a2
a1
a1
...
...
. . .
ai
ai−1
ai−1
ai−2
· · · a1
i
.
130 Theory of Paradeterminants and its Applications
Theorem 15. (Theorem on inversion of a series) Let a(x) =
∑∞
i=1 aix
i
and b(x) =
∑∞
i=1 bix
i be some formal series such that
b(a(x)) = 1 · x + 0 · x2 + 0 · x3 + . . . .
Then the following equalities hold
bi =
(−1)i−1
ai
1
·
(
(i + 1)0
1!
,
(i + 1)1
2!
, . . . ,
(i + 1)i−2
(i − 1)!
)
× (6.1)
×
a2
a1
a3
a2
a2
a1
...
...
. . .
ai
ai−1
ai−1
ai−2
· · · a2
a1
, i = 1, 2, . . . .
Theorem 16. Let a(x) =
∑∞
i=1 aix
i и c(x) =
∑∞
i=1 cix
i be some formal
series and ω(x) =
∑∞
i=1 ωi · x
i. Then the equalities
ω(a(x)) = c(x) and a(ω(x)) = c(x)
imply the equalities
ωn = pper(Z(b1, . . . , bn)) · (c1, . . . , cn)
and
ωn = pper(Z(c1, . . . , cn)) · (b1, . . . , bn),
where bi, i = 1, 2, . . . , n, are defined by equalities (6.1).
7. Application of paradeterminants to the solution of
problems on paths in skew diagrams and Ferrer graphs
Let λ = (λ1, λ2, . . . , λr) be some disordered partition of a number n.
A partition µ = (µ1, µ2, . . . , µr) is called a subpartition of λ (denoted
µ � λ), if the inequalities µi ≤ λi, i = 1, . . . , r hold. To any pair of such
partitions one can associate some skew diagram ([14], 12–15).
diagr(λ, µ) =
(
λ1, . . . , λn−1, λn
µ1, . . . , µn−1, 0
)
(7.1)
Distance between two points on the diagram is the shortest distance
between these points. A path in a skew diagram between the lowest right
point A and the upper left point B is a shortest path between these
points. Furthermore, we will move only in two directions: up and left.
R. Zatorsky 131
Theorem 17. [21] The number of the shortest paths between the lowest
right point and the upper left point on the skew diagram (7.1) is equal
to
ddet
(
(
1 − δij
i − j + 1
+ δij
)
·
(λi − µj + j − i + 1)i−j+1
(λi − µj+1 + j − i + 2)i−j
)
1≤j≤i≤n
(7.2)
where δij is the Kronecker symbol.
Remark 12. If in the paradeterminant (7.2) we have the inequality λi−
µj +j−i+1 ≤ 0, then the corresponding element of this paradeterminant
is assumed to be zero. Moreover, the value of the expression (λi −µj+1 +
j − i + 2)i−j for i = j = n is assumed to be 1.
Corollary 9. Suppose the diagram (7.1) has the form
diagr(λ, 0) =
(
λ1, . . . , λn−1, λn
0, . . . , 0, 0
)
,
i.e. it is a Ferrer graph. Then the number of shortest paths in the Ferrer
graph, or the number of standard tableaux of this graph can be found by
the formula
(−1)
n(n−1)
2 ·
N !
∏n
i=1(λi + n − i)!
· det((λi − i)j−1)i,j=1,...,n, (7.3)
where N is the weight of the Ferrer graph.
Remark 13. Thus the Frame-Robinson-Thrall hook rule [15] giving the
number of standard Young tableaux on Ferrer deagrams can be repre-
sented using formula (7.3) and Vandermonde determinant.
The reader can find an extended version of this material in [21].
8. A connection between determinants and paradetermi-
nants
The existing analogy between the properties of determinants and parade-
terminants can be explained mostly by the close connections between
them. In some sense determinants can be reduced to paradeterminants.
Replacement of determinants by paradeterminants could essentially sim-
plify calculations in many cases since the latter can be calculated faster.
132 Theory of Paradeterminants and its Applications
Consider a matrix
B =
b11 1 0 . . . 0 0
b21 b22 1 . . . 0 0
b31 b32 b33 . . . 0 0
. . . . . . . . . . . . . . . . . .
bn−1,1 bn−1,2 bn−1,3 . . . bn−1,n−1 1
bn1 bn2 bn3 . . . bn,n−1 bnn
, (8.1)
which we will call lower quasi-triangular.
Theorem 18. (Lischinski I.I.) For any triangular matrix (1.1)
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
=
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
b11 1 0 . . . 0 0
b21 b22 1 . . . 0 0
b33 b32 b33 . . . 0 0
· · · · · · · · · · · · · · · · · ·
bn−1,1 bn−1,2 bn−1,3 . . . bn−1,n−1 1
bn1 bn2 bn3 . . . bn,n−1 bnn
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
,
a11
a21 a22
...
...
. . .
an1 an2 · · · ann
=
b11 1 0 . . . 0 0
b21 b22 1 . . . 0 0
b33 b32 b33 . . . 0 0
· · · · · · · · · · · · · · · · · ·
bn−1,1 bn−1,2 bn−1,3 . . . bn−1,n−1 1
bn1 bn2 bn3 . . . bn,n−1 bnn
,
where
bij = {aij} =
i
∏
k=j
aik, 1 ≤ j ≤ i ≤ n. (8.2)
Corollary 10. For any lower triangular matrix (8.1)
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
b11 1 0 . . . 0 0
b21 b22 1 . . . 0 0
b31 b32 b33 . . . 0 0
. . . . . . . . . . . . . . . . . .
bn−1,1 bn−1,2 bn−1,3 . . . bn−1,n−1 1
bn1 bn2 bn3 . . . bn,n−1 bnn
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
=
=
b11
b21
b22
b22
b31
b32
b32
b33
b33
...
...
...
. . .
bn1
bn2
bn2
bn3
bn3
bn4
· · · bnn
.
R. Zatorsky 133
Observe that the elements bij , 1 ≤ j ≤ i ≤ n in equality (??) can
take values from a numeric field, as follows from Remark 7.
Theorem 19. Let A be a square matrix of order n
A =
α11 α12 · · · α1n
α21 α22 · · · α2n
· · · · · · · · · · · ·
αn1 αn2 · · · αnn
,
such that the minors of A satisfy the inequalities:
A
(
1
2
)
6= 0, A
(
1 2
2 3
)
6= 0, . . . , A
(
1 2 . . . n − 2 n − 1
2 3 . . . n − 1 n
)
6= 0.
Then the following identity holds
det(A) = a12a
(1)
23 a
(2)
34 · . . . · a
(n−2)
n−1,n · ddet
〈
a
(j−2)
ij
a
(j−1)
i,j+1
〉
1≤j≤i≤n
,
where
a
(p−2)
i,p =
A
(
1 2 ... p−2 i
2 3 ...p−1 p
)
A
(
1 2 ... p−2
2 3... p−1
) , p = 3, 4, . . . , n, i = p − 1, p, . . . , n,
a
(p−2)
ip = aip , p = 1, 2, an−1
n,n+1 = 1.
Proposition 9. For any matrix (19) and n = 3, 4, . . ., the following
identity holds
det(A) · A
(
1 2···n−2
2 3···n−1
)
= A
(
1 2···n−1
1 2···n−1
)
A
(
1 2···n−2 n
2 3···n−1 n
)
−
−A
(
1 2···n−2 n−1
2 3···n−1 n
)
A
(
1 2···n−2 n
1 2···n−2 n−1
)
.
Thus, by virtue of the proposition cited above, the determinant of the
matrix (19), for any n = 3, 4, . . ., can be expressed through four minors
of order n − 1 and one minor of order (n − 2).
9. Principles of calculus for triangular matrices
We define the basic operations on triangular matrices: addition of tri-
angular matrices, multiplication of a triangular matrix by a number and
multiplication of triangular matrices.
Let A = (aij)1≤j≤i≤n, B = (bij)1≤j≤i≤n and C = (cij)1≤j≤i≤n be
some triangular matrices of order n.
134 Theory of Paradeterminants and its Applications
Definition 13. Sum of two triangular matrices A and B is the matrix
C, whose elements are equal to the sum of the corresponding elements in
A and B, i.e. cij = aij + bij , 1 ≤ j ≤ i ≤ n.
It follows directly from the definition that the addition operation is
commutative and associative.
Definition 14. Product of a triangular matrix A by a number α from
some numeric field is the matrix C with elements cij = α · aij , 1 ≤ j ≤
i ≤ n.
Obviously:
α(A + B) = αA + αB, (α + β)A = αA + βA, (αβ)A = α(βA).
To define the product of two triangular matrices we give some pre-
liminary definitions:
Definition 15. An element ξ1 ∈ Ξ(n) is not related to an element ξ2 ∈
Ξ(n) if [ξ1]
⋂
[ξ2] = {n}, where [·] denotes the basis of the corresponding
multiset (see definition 6). Otherwise these elements are called related.
The set of all elements of Ξ(n) not related to an element ξ is denoted
by Ξξ(n).
Proposition 10. There are 3n−1 pairs (ξ1, ξ2) in the Cartesian product
Ξ(n) × Ξ(n) whose components are not related.
Two summands aξ1(1),1aξ1(2),2·. . .·aξ1(n),n and bξ2(1),1bξ2(2),2·. . .·bξ2(n),n
in the paradeterminant (parapermanent) of the triangular matrices A and
B are not related, if the elements ξ1 = {ξ1(1), ξ1(2), . . . , ξ1(n)}, ξ2 =
{ξ2(1), ξ2(2), . . . , ξ2(n)}, which belong to Ξ(n), are not related.
Definition 16. Incomplete product of the paradeterminants of matrices
A and B is the sum of products of all pairwise not related components
of these paradeterminants taken with appropriate signs, i.e.
ddet(A) ◦ ddet(B) =
=
∑
(ξ1,ξ2)∈Ξ(n)×Ξ(n)
(−1)ε(ξ1)+ε(ξ2)·k(ξ1, ξ2)·aξ1(1),1·. . .·aξ1(n),n·bξ2(1),1·. . .·bξ2(n),n,
where ε(ξ1) and ε(ξ2) are the numbers of different elements in the multiset
ξ1 and ξ2, respectively, and k(ξ1, ξ2) is defined by the equality
k(ξ1, ξ2) =
{
1, if [ξ1] ∩ [ξ2] = {n},
0, if [ξ1] ∩ [ξ2] 6= {n}.
R. Zatorsky 135
Example 5. The incomplete product of paradeterminants of matrices A
and B of order 3 is given by
ddet(A) ◦ ddet(B) =
= a11a22a33b31b32b33 + a21a22a33b11b32b33 − a21a22a33b31b32b33 +
+ a11a32a33b21b22b33 − a11a32a33b31b32b33 + a31a32a33b11b22b33 −
− a31a32a33b21b22b33 − a31a32a33b11b32b33 + a31a32a33b31b32b33
Incomplete product of parapermanents is defined in the same way,
except that the sing (−1)ε(ξ)+ε(ξ). is disregarded.
Definition 17. The paradeterminant (parapermanent) product of two
triangular matrices A and B of order n is the matrix C = A · B of the
same order with elements:
cij(A, B) = (−1)δij+1 ·
dij(A, B)
di,j+1(A, B)
(
cij(A, B) =
pij(A, B)
pi,j+1(A, B)
)
,
where δij is the Kronecker symbol, and dij(A, B), pij(A, B) — incomplete
product of paradeterminants (parapermanents) of the corners Rij of the
triangular matrices A and B, i.e.
dij(A, B) = ddet(Rij(A)) ◦ ddet(Rij(B))
(pij(A, B) = pper(Rij(A)) ◦ pper(Rij(B))) ,
where 1 ≤ j ≤ i ≤ n.
Proposition 11. The following equalities hold: AB = BA, (AB)C =
A(BC), A(B + C) = AB + AC, ddet(AB) = ddet(A) · ddet(B),
pper(AB) = pper(A) · pper(B).
Identity matrix is the matrix of the form
E =
1
0 1
...
...
. . .
0 0 · · · 1
References
136 Theory of Paradeterminants and its Applications
[1] Babai L., Frankl P. Linear algebra methods in combinatories with Applications to
Geometry and Computer Science p. 234.
[2] Protasov I.V., Khromulyak O.M. Methods of Linear Algebra in Combinatorics.
Kyiv, 1997, 40 p (in Ukrainian).
[3] Stechkin B.S.Tuples and their usage in combinatorial schemes (on one combina-
torial formalization) // Sb. "Comb. and asympt. analysis", Kras. GU, 1977., p.
44-54 (in Russian).
[4] Doubilet P., Rota G.-C., Stanley R. On the foundations of combinatorial the-
ory. VI. The idea of generating function. Proceedings of the Sixth Berkeley Sym-
posium on Mathematical Statistics and Probability (Univ. California, Berkeley,
Calif., 1970/1971), Vol. II: Probability theory, pp. 267–318. Univ. California
Press, Berkeley, Calif., 1972.
[5] Stanley R. Enumerative combinatorics: Translation from English — Moscow: Mir,
1990. — 440 p.
[6] Andrews G. The theory of partitions. Encyclopedia of Mathematics and its
Applications, Vol. 2. Addison-Wesley Publishing Co., Reading, Mass.-London-
Amsterdam, 1976. xiv+255 pp.
[7] Graham R.L., Knuth D.E., Patashnik O. Concrete mathematics. A foundation for
computer science. Second edition. Addison-Wesley Publishing Company, Reading,
MA, 1994. xiv+657 pp.
[8] Bell E.T. Partition polynomials. — Ann. Math. 29, 1927, p. 38 – 46.
[9] M.Marcus, H.Minc. On the relation between the determinant and the permanent,
Illinois J. Math. 5 (1961), 376-381.
[10] Riordan J. An Introduction to Combinatorial Analysis, Wiley, New York, 1958.
[11] Fine N.J. Sums over partitions.— Report of the Institute in the Theory of Num-
bers, Boulder, 1959, p. 86-94.
[12] Riordan J. Kombinatornye tozhdestva. (Russian) [Combinatorial identities] Trans-
lated from the English by A. E. Zhukov. “Nauka”, Moscow, 1982. 256 pp.
[13] Aı̆gner M. Kombinatornaya teoriya. (Russian) [Combinatorial theory] Translated
from the English by V. V. Ermakov and V. N. Lyamin. Translation edited and
with a preface by G. P. Gavrilov. “Mir”, Moscow, 1982. 558 pp.
[14] Macdonald I.G. Simmetricheskie funktsii i mnogochleny Kholla. (Russian) [Sym-
metric functions and Hall polynomials] Translated and with a preface by
A.V. Zelevinskĭı. “Mir”, Moscow, 1985. 224 pp.
[15] Frame J.S., Robinson G. de B., Thrall R.M. The hook graphs of Sn. // Canad. J.
Math. 6, 1954, p. 316-324.
[16] Tarakanov V.E. Kombinatornye zadachi i (0, 1)-matritsy. (Russian) [Combinato-
rial problems and (0, 1)-matrices] Problemy Nauki i Tekhnicheskogo Progressa.
[Problems of Science and Technological Progress] “Nauka”, Moscow, 1985. 192 pp.
[17] Sachkov V.N. Vvedenie v kombinatornye metody diskretnŏımatematiki. (Rus-
sian) [Introduction to combinatorial methods of discrete mathematics] “Nauka”,
Moscow, 1982. 384 pp.
[18] Zatorsky R.A. On paradeterminants and parapermanents of triangular matrices.
(Ukrainian) Mat. Stud. 17 (2002), no. 1, 3–17.
R. Zatorsky 137
[19] Zatorsky R.A. Paradeterminants and parapermanents of triangular matrices.
(Ukrainian) Dopov. Nats. Akad. Nauk Ukr. Mat. Prirodozn. Tekh. Nauki 2002,
no. 8, 21–28.
[20] ZatorskĭıR.A. Parapermanents and linear recurrent relations. In the Proceedings
of Internation Algebraic conference in memory of D.Grave, Kyiv University, Kyiv,
Ukraine, June, 2002., p. 138.
[21] Zatorsky R.A. Determinants of triangular matrices and trajectories on Ferrers
diagrams. (Russian) Mat. Zametki 72 (2002), no. 6, 834–852; translation in Math.
Notes 72 (2002), no. 5-6, 768–783.
[22] Zatorsky R.A. On partition polynomials and their paradeterminants and parap-
ermanents. In the Proceedings of X Kravchuk International Conference, Kyiv:
NTUU (KPI). - 2004. - p. 383.
[23] Zatorsky R.A. Continued fractions, K-polynomials and parapermanents.
(Ukrainian) Mat. Metodi Fiz.-Mekh. Polya 44 (2001), no. 4, 12–21.
[24] R.Zatorsky. Paradeterminants and formal operations on series // 4th Interna-
tional Algebraic Conference in Ukraine, Lviv, 2003., 242.
[25] Ganyushkin O.G.,Zatorsky R.A., Lishcinski I.I. On paradeterminants and para-
permanents of triangular matrices (Ukrainian) Bull. Kyiv Univ. Ser. Phys. and
Math. (2005) no. 1, 40–45.
[26] Dyakiv N.M., Zatorsky R.A.On F−paradeterminants and F−parapermanents of
triangular matrices (Ukrainian) Mat. Metodi Fiz.-Mekh. Polya (2005), no. 1, 21–
24.
Contact information
R. Zatorsky Precarpathian University, 57 Shevchenko
Str., Ivano-Frankivsk, Ukraine
E-Mail: romazz@rambler.ru
Received by the editors: 15.03.2007
and in final form 24.05.2007.
|