A family of doubly stochastic matrices involving Chebyshev polynomials
A doubly stochastic matrix is a square matrix A = (aij) of non-negative real numbers such that ∑i aij =∑j aij =1. The Chebyshev polynomial of the first kind is defined by the recurrence relation T₀ (x) = 1, T₁ (x) = x, and Tn+1(x) = 2xTn(x) − Tn−1(x). In this paper, we show a 2ᵏ ×2ᵏ (for each intege...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2019 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2019
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/188430 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | A family of doubly stochastic matrices involving Chebyshev polynomials / T. Ahmed, J.M.R. Caballero // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 155–164. — Бібліогр.: 2 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-188430 |
|---|---|
| record_format |
dspace |
| spelling |
Ahmed, T. Caballero, J.M.R. 2023-03-01T15:26:38Z 2023-03-01T15:26:38Z 2019 A family of doubly stochastic matrices involving Chebyshev polynomials / T. Ahmed, J.M.R. Caballero // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 155–164. — Бібліогр.: 2 назв. — англ. 1726-3255 2010 MSC: Primary 05D10. https://nasplib.isofts.kiev.ua/handle/123456789/188430 A doubly stochastic matrix is a square matrix A = (aij) of non-negative real numbers such that ∑i aij =∑j aij =1. The Chebyshev polynomial of the first kind is defined by the recurrence relation T₀ (x) = 1, T₁ (x) = x, and Tn+1(x) = 2xTn(x) − Tn−1(x). In this paper, we show a 2ᵏ ×2ᵏ (for each integer k > 1) doubly stochastic matrix whose characteristic polynomial is x² − 1 times a product of irreducible Chebyshev polynomials of the first kind (upto rescaling by rational numbers). en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics A family of doubly stochastic matrices involving Chebyshev polynomials Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
A family of doubly stochastic matrices involving Chebyshev polynomials |
| spellingShingle |
A family of doubly stochastic matrices involving Chebyshev polynomials Ahmed, T. Caballero, J.M.R. |
| title_short |
A family of doubly stochastic matrices involving Chebyshev polynomials |
| title_full |
A family of doubly stochastic matrices involving Chebyshev polynomials |
| title_fullStr |
A family of doubly stochastic matrices involving Chebyshev polynomials |
| title_full_unstemmed |
A family of doubly stochastic matrices involving Chebyshev polynomials |
| title_sort |
family of doubly stochastic matrices involving chebyshev polynomials |
| author |
Ahmed, T. Caballero, J.M.R. |
| author_facet |
Ahmed, T. Caballero, J.M.R. |
| publishDate |
2019 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
A doubly stochastic matrix is a square matrix A = (aij) of non-negative real numbers such that ∑i aij =∑j aij =1. The Chebyshev polynomial of the first kind is defined by the recurrence relation T₀ (x) = 1, T₁ (x) = x, and Tn+1(x) = 2xTn(x) − Tn−1(x). In this paper, we show a 2ᵏ ×2ᵏ (for each integer k > 1) doubly stochastic matrix whose characteristic polynomial is x² − 1 times a product of irreducible Chebyshev polynomials of the first kind (upto rescaling by rational numbers).
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/188430 |
| citation_txt |
A family of doubly stochastic matrices involving Chebyshev polynomials / T. Ahmed, J.M.R. Caballero // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 155–164. — Бібліогр.: 2 назв. — англ. |
| work_keys_str_mv |
AT ahmedt afamilyofdoublystochasticmatricesinvolvingchebyshevpolynomials AT caballerojmr afamilyofdoublystochasticmatricesinvolvingchebyshevpolynomials AT ahmedt familyofdoublystochasticmatricesinvolvingchebyshevpolynomials AT caballerojmr familyofdoublystochasticmatricesinvolvingchebyshevpolynomials |
| first_indexed |
2025-11-27T03:40:09Z |
| last_indexed |
2025-11-27T03:40:09Z |
| _version_ |
1850797163568693248 |
| fulltext |
“adm-n2” — 2019/7/14 — 21:27 — page 155 — #5
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 27 (2019). Number 2, pp. 155–164
c© Journal “Algebra and Discrete Mathematics”
A family of doubly stochastic matrices
involving Chebyshev polynomials
Tanbir Ahmed and José M. R. Caballero
Communicated by V. A. Artamonov
Abstract. A doubly stochastic matrix is a square matrix
A = (aij) of non-negative real numbers such that
∑
i aij=
∑
j aij=1.
The Chebyshev polynomial of the first kind is defined by the recur-
rence relation T0(x) = 1, T1(x) = x, and
Tn+1(x) = 2xTn(x)− Tn−1(x).
In this paper, we show a 2k × 2k (for each integer k > 1) doubly
stochastic matrix whose characteristic polynomial is x2 − 1 times
a product of irreducible Chebyshev polynomials of the first kind
(upto rescaling by rational numbers).
1. Introduction
Chebyshev polynomial of the first kind is defined by
Tn(x) = cos (n · arccos (x)) .
The fact that roots of T2k(x) are cos
(
2j−1
2k+1 π
)
, for 1 6 j 6 2k together
with the trigonometric identity 2 + 2 cos
(
θ
2k+1
)
= 2 ±
√
2 + 2 cos
(
θ
2k
)
make T2k(x) a remarkable subsequence. For example, Kimberling [2] used
2010 MSC: Primary 05D10.
Key words and phrases: doubly stochastic matrices, Chebyshev polynomials.
“adm-n2” — 2019/7/14 — 21:27 — page 156 — #6
156 Doubly stochastic matrices
these facts in order to obtain a Gray code by means of the numbers
2 + c1
√
√
√
√
2 + c2
√
2 + c3
√
2 + c4
√
· · ·+ cn
√
2,
where each cj ∈ {−1, 1} and generalized this result to a wider class of
polynomials. Another reason why Tn(x) indexed by powers of 2 are special
is that, as a consequence of Esenstein’s irreducibility criterion, Tn(x) is
irreducible overQ[x] if and only if n is a power of 2. A normalized Chebyshev
polynomial is a Chebyshev polynomial divided by the coefficient of its
leading term. So, the leading term of a normalized Chebyshev polynomial
is always 1.
We represent the matrix in context as a self-similar structure. A
self-similar algebra (see Bartholdi [1]) (A, ψ) is an associative algebra A
endowed with a morphism of algebras ψ : A −→ Md (A), where Md (A)
is the set of d × d matrices with coefficients from A. Given s ∈ A and
integers a > 0 and b > 0, the 2× 2 matrix ψa,b(s) is obtained using the
mapping x 7→
(
0 xa
ya 0
)
, y 7→
(
0 xb
yb 0
)
. We write ψ1,0(s) as ψ(s).
Given a self-similar algebra (A, ψ), with ψ : A −→ M2 (A), we define
(
A, ψ(k)
)
(for k > 0) with ψ(k) : A −→ M2k (A) given by ψ(0)(s) := s
and ψ(k+1)(s) :=
(
ψ(k)(si,j)
)
06i,j62k−1
, where ψ(s) = (si,j)06i,j62k−1. For
k > 1, we consider the following doubly stochastic matrix
Mk(a, b) := ψ
(k)
a,b
(
1
2
x+
1
2
y
)∣
∣
∣
∣
(x,y)=(1,1)
∈M2k (Q) .
We show that the characteristic polynomial of Mk(1, 0) is x2 − 1 times
a product of irreducible Chebyshev polynomials of the first kind (upto
rescaling by rational numbers).
2. Preliminaries
In this section, we discuss some preliminaries from linear algebra. We
use Newton identities for the characteristic polynomial of a matrix.
Lemma 2.1. Let M and N be two k×k square matrices. For each integer
n > 1,
tr
[(
M M
N N
)n]
= tr
[(
N M
N M
)n]
= tr [(M +N)n] .
“adm-n2” — 2019/7/14 — 21:27 — page 157 — #7
T. Ahmed, J. M. R. Caballero 157
Proof. The following identity can be checked by complete induction,
(
M M
N N
)n
=
(
M(M +N)n−1 M(M +N)n−1
N(M +N)n−1 N(M +N)n−1
)
.
Using the properties of the trace, we conclude that
tr
[(
M M
N N
)n]
= tr
[
M(M +N)n−1
]
+ tr
[
N(M +N)n−1
]
= tr [(M +N)n] .
The proof of tr
[(
N M
N M
)n]
= tr [(M +N)n] is analogous.
Lemma 2.2. Let M and N be two k × k square matrices. The charac-
teristic polynomials of
(
M M
N N
)
and
(
N M
N M
)
are the same.
Proof. By Lemma 2.1, for all n > 1,
tr
[(
M M
N N
)n]
= tr
[(
N M
N M
)n]
.
Using Newton identities and the fact that both matrices have the same
dimensions, we derive that both matrices have the same characteristic
polynomials.
Lemma 2.3. Let M and N be k × k square matrices. Let p(x) and q(x)
be the characteristic polynomials of
(
M M
N N
)
and M +N , respectively.
Then p(x) = xkq(x).
Proof. By Lemma 2.1, for all n > 1, tr
[(
M M
N N
)n]
= tr [(M +N)n].
Using Newton identities, we derive that the coefficients of p(x) and q(x)
coincide but the degree of p(x) exceeds the degree of q(x) by k. Hence,
p(x) = xkq(x).
Lemma 2.4. Let M be a k × k square matrix. Let p(x) and q(x) be the
characteristic polynomials of M and −M , respectively. If tr(Mn) = 0 for
each odd non-negative integer n, then p(x) and q(x) coincide.
“adm-n2” — 2019/7/14 — 21:27 — page 158 — #8
158 Doubly stochastic matrices
Proof. For each even integer n > 0, it follows that tr (Mn) = tr ((−M)n).
On the other hand, for any odd integer n > 0, we have tr (Mn) =
tr ((−M)n) = 0, by hypothesis. So tr (Mn) = tr ((−M)n) for any in-
teger n > 0 regardless of its parity. Using Newton identities, we conclude
that p(x) is the same as q(x).
Lemma 2.5. Let M be a k × k square matrix. Let p(x) and q(x) be the
characteristic polynomials of M and M2, respectively. If tr(Mn) = 0 for
each odd non-negative integer n, then (p(x))2 = q(x2).
Proof. By hypothesis and by Lemma 2.4, we have |xI −M | = |xI +M |,
where I is the k × k identity matrix. Then,
|xI −M |2 = |(xI −M)(xI +M)| = |x2I −M2|,
and hence (p(x))2 = q(x2).
3. Eigenvalues of Mk(a, b)
Proposition 3.1. For all a ≡ b (mod 2), if λ ∈ C is an eigenvalue of the
matrix Mk(a, b) then either λ = −1 or λ = 1.
Proof. We shall consider the following cases.
(i) If a ≡ b ≡ 1 (mod 2) then Mk(a, b) is the exchange matrix, i.e. the
matrix J = (Ji,j)06i,j62k−1, where
Ji,j =
{
1 if j = 2k − 1− i,
0 if j 6= 2k − 1− i.
(ii) If a ≡ b ≡ 0 (mod 2) then Mk(a, b) is the block matrix
(
I2k−1 02k−1
02k−1 I2k−1
)
. where In and 0n are the n× n identity matrix and
the n× n zero matrix respectively.
In both cases, all the eigenvalues belong to the set {−1, 1}.
4. The characteristic polynomial of Mk(1, 0)
We study the structure of Mk(1, 0), which is less trivial than in the
previous examples. Denote
Ak := ψ(k)(x)
∣
∣
∣
(x,y)=(1,1)
, and Bk := ψ(k)(y)
∣
∣
∣
(x,y)=(1,1)
,
“adm-n2” — 2019/7/14 — 21:27 — page 159 — #9
T. Ahmed, J. M. R. Caballero 159
such that Mk(1, 0) = 1
2 [A2k +B2k ]. Note that the pair of matrices
(A2k , B2k) can be defined equivalently using the following recursion:
A1 = B1 = (1)1×1 , A2k+1 =
(
02k A2k
B2k 02k
)
2k+1
×2k+1
,
B2k+1 =
(
02k I2k
I2k 02k
)
2k+1
×2k+1
,
where 02k and I2k are respectively the 2k × 2k zero and identity matrices.
Lemma 4.1. For each integer k > 2, Mk(1, 0)
2 =
(
P2k−1 02k−1
02k−1 Q2k−1
)
,
where
P2k−1 =
1
4
(
A2k−2 + I2k−2 A2k−2 + I2k−2
B2k−2 + I2k−2 B2k−2 + I2k−2
)
,
Q2k−1 =
1
4
(
B2k−2 + I2k−2 A2k−2 + I2k−2
B2k−2 + I2k−2 A2k−2 + I2k−2
)
Proof. It follows from the identity:
[Mk(1, 0)]
2
=
(
02k−1
1
2
(A2k−1 + I2k−1)
1
2
(B2k−1 + I2k−1) 02k−1
)2
=
1
4
(
(A2k−1 + I2k−1) (B2k−1 + I2k−1) 02k−1
02k−1 (B2k−1 + I2k−1) (A2k−1 + I2k−1)
)
=
1
4
A2k−2 + I2k−2 A2k−2 + I2k−2 02k−2 02k−2
B2k−2 + I2k−2 B2k−2 + I2k−2 02k−2 02k−2
02k−2 02k−2 B2k−2 + I2k−2 A2k−2 + I2k−2
02k−2 02k−2 B2k−2 + I2k−2 A2k−2 + I2k−2
.
Lemma 4.2. Given positive integer k > 2, let p(x) and q(x) be the
characteristics polynomials of
[
1
2
(A2k +B2k)
]2
and
1
4
(A2k−2 +B2k−2 + 2I2k−2) ,
respectively. Then p(x) =
(
x2
k−2
q(x)
)2
.
Proof. By Lemma 4.1, the characteristics polynomial of [Mk(1, 0)]
2 is
the product of the characteristic polynomials of P2k−1 and Q2k−1 . By
Lemma 2.2, P2k−1 and Q2k−1 have the same characteristic polynomials.
By Lemma 2.3, the characteristic polynomial of P2k−1 is x2
k−2
times the
“adm-n2” — 2019/7/14 — 21:27 — page 160 — #10
160 Doubly stochastic matrices
characteristic polynomial of 1
4 (A2k−2 +B2k−2 + 2I2k−2). Hence, p(x) =
(
x2
k−2
q(x)
)2
.
Let the characteristic polynomial of Mk(1, 0) be denoted by Ck(x) such
that
Ck(x) := |xI2k −Mk(1, 0)|
Lemma 4.3. Given positive integer k > 2, the polynomial Ck(x) satisfies
the following recurrence relation
Ck(x) =
x2
k−1
22k−2
Ck−2
(
2x2 − 1
)
.
Proof. We have
[Ck(x)]2 = |xI2k − [Mk(1, 0)]|2
=
∣
∣
∣
x2I2k − [Mk(1, 0)]
2
∣
∣
∣
, (by Lemma 2.5)
=
(
(x2)2
k−2
∣
∣
∣
∣
x2I2k−2 − 1
4
(A2k−2 +B2k−2 + 2I2k−2)
∣
∣
∣
∣
)2
,
(by Lemma 4.2)
=
(
x2
k−1
∣
∣
∣
∣
1
2
(
2x2I2k−2 − 1
2
(A2k−2 +B2k−2 + 2I2k−2)
)∣
∣
∣
∣
)2
,
=
(
x2
k−1
22k−2
∣
∣
∣
∣
(
2x2 − 1
)
I2k−2 − 1
2
(A2k−2 +B2k−2)
∣
∣
∣
∣
)2
,
Using the fact that the characteristic polynomial has leading coefficient 1
in our definition, we conclude that
|xI2k − [Mk(1, 0)]| =
x2
k−1
22k−2
∣
∣
∣
∣
(
2x2 − 1
)
I2k−2 − 1
2
(A2k−2 +B2k−2)
∣
∣
∣
∣
.
Therefore, Ck(x) = x2
k−1
22
k−2 Ck−2
(
2x2 − 1
)
.
Example 4.1. The matrices M1(1, 0), M2(1, 0), and M3(1, 0) are
M1(1, 0) =
(
0 1
1 0
)
,M2(1, 0) =
0 0 1
2
1
2
0 0 1
2
1
2
1
2
1
2 0 0
1
2
1
2 0 0
,
“adm-n2” — 2019/7/14 — 21:27 — page 161 — #11
T. Ahmed, J. M. R. Caballero 161
M3(1, 0) =
0 0 0 0 1
2 0 0 1
2
0 0 0 0 0 1
2
1
2 0
0 0 0 0 0 1
2
1
2 0
0 0 0 0 1
2 0 0 1
2
1
2 0 1
2 0 0 0 0 0
0 1
2 0 1
2 0 0 0 0
1
2 0 1
2 0 0 0 0 0
0 1
2 0 1
2 0 0 0 0
.
Example 4.2. The first values of Ck(λ) are
C2 (λ) =
(
λ2 − 1
)
· λ2,
C3 (λ) =
(
λ2 − 1
)
· λ6,
C4 (λ) =
(
λ2 − 1
)
· λ10 ·
(
λ2 − 1
2
)2
,
C5 (λ) =
(
λ2 − 1
)
· λ18 ·
(
λ2 − 1
2
)6
,
C6 (λ) =
(
λ2 − 1
)
· λ34 ·
(
λ2 − 1
2
)10
·
(
λ4 − x2 +
1
8
)2
,
C7 (λ) =
(
λ2 − 1
)
· λ66 ·
(
λ2 − 1
2
)18
·
(
λ4 − λ2 +
1
8
)6
,
C8 (λ) =
(
λ2 − 1
)
· λ130 ·
(
λ2 − 1
2
)34
·
(
λ4 − λ2 +
1
8
)10
·
(
λ8 − 2λ6 +
5
4
λ4 − 1
4
λ2 +
1
128
)2
.
5. A monoid generated by the irreducible Chebyshev
polynomials of the first kind
The commutative monoid, generated by T2(x) = 2x2 − 1 with com-
position (superposition) of polynomials as the binary operation, will
be denoted by T◦ ⊆ Q[x]. We will use the notation T1(x) = x and
T2r+1(x) = T2r (T2(x)) for the elements of T◦. Let T ⊆ Q[x] be the com-
mutative monoid generated by the rational numbers and the elements
from T◦, with the ordinary polynomial product as binary operation. For
each T2r(x) ∈ T◦, the application T → T given by p(x) 7→ p (T2r(x)) is a
well-defined commutative monoid morphism.
“adm-n2” — 2019/7/14 — 21:27 — page 162 — #12
162 Doubly stochastic matrices
Theorem 5.1. Given positive integer k, the characteristic polynomial of
Mk(1, 0) is equal to x2 − 1 times an element from T.
Proof. We proceed by induction on k > 1. The result is true for k = 1
and k = 2 by direct computation,
C1(x) = x2 − 1, C2(x) = (x2 − 1) (T1(x))
2 .
Let k = m for some m > 3. Suppose that Cm−2(x) = (x2 − 1)p(x) for
some p(x) ∈ T. By Lemma 4.3,
Cm(x) =
x2
m−1
22m−2
Cm−2(2x
2 − 1),
which implies
Cm(x) =
(T1(x))
2m−1
22m−2
(
(
2x2 − 1
)2 − 1
)
p(2x2 − 1).
Using p(2x2−1) = p(T2(x)) ∈ T and
(
(
2x2−1
)2−1
)
= 4 (T1(x))
2 (x2−1),
we conclude Cm(x)/(x2 − 1) ∈ T. Therefore, the result is true for all k > 1
by induction.
Corollary 5.1. For k > 0, the matrix 2Mk(1, 0) is nilpotent mod 2, i.e.
for some integer N > 0, all the entries of (2Mk(1, 0))
N are even integers.
Proof. By Theorem 5.1, we have
|xI2k −Mk(1, 0)| = ρ · (x2 − 1)T2r1 (x)T2r2 (x)T2r3 (x) · · ·T2rh (x),
where r1, r2, . . . , rh are some nonnegative integer and ρ is a positive
rational number. Substituting x by x/2 in the above equation, we obtain
|xI2k − 2Mk(1, 0)| =
22
k
−h−2ρ · (x2 − 4)T2r1
(x
2
)
T2r2
(x
2
)
T2r3
(x
2
)
· · ·T2rh
(x
2
)
.
Each polynomial 2T2rj for j = 1, 2, . . . , h has leading coefficient 1 and
the characteristic polynomial of 2Mk(1, 0) has leading coefficient 1 too.
Hence, 22
k
−h−2ρ = 1.
We claim that the non-leading coefficients in T2rj for j = 1, 2, . . . , h
are even integers. Indeed, 2T20
(
x
2
)
= x satisfies this claim. If 2T2r
(
x
2
)
satisfies the claim, then
2T2r+1
(x
2
)
= 2T2r
(
T2
(x
2
))
= 2T2r
(
2
(x
2
)2
− 1
)
= 2T2r
(
x2 − 2
2
)
also satisfies the claim. The claim follows by induction.
“adm-n2” — 2019/7/14 — 21:27 — page 163 — #13
T. Ahmed, J. M. R. Caballero 163
After reducing the entries of 2Mk(1, 0) to Z/2Z, we obtain that its
characteristic polynomial is x2
k
. Therefore, the matrix 2Mk(1, 0) is nilpo-
tent in F2.
Example 5.1. The 15th power of 2M10(a, b) for (a, b) = (1, 0) and
(a, b) = (1, 2) are represented1 in Figure 1 and Figure 2, respectively. The
odd entries correspond to the black points and the even entries, to the
white points.
Figure 1. Representation of (2M10(1, 0))
15
.
Figure 2. Representation of (2M10(1, 2))
15
.
1These pictures were obtained in SageMath using a program created by the authors.
“adm-n2” — 2019/7/14 — 21:27 — page 164 — #14
164 Doubly stochastic matrices
The following common property seem to be true because of the empir-
ical evidences.
Conjecture 5.1. For a > 0, b > 0, and k > 0, the matrix 2Mk(a, b) is
nilpotent mod 2, i.e. for some integerN > 0, all the entries of (2Mk(a, b))
N
are even integers.
References
[1] Bartholdi, L. (2010). Self-similar lie algebras. arXiv preprint arXiv:1003.1125.
[2] Kimberling C., Polynomials defined by a second order recurrence, interlacing zeros,
and gray codes, Fibonacci Quarterly, 48 (3) (2010).
Contact information
T. Ahmed,
J. M. R. Caballero
LaCIM, UQÁM, Montréal, Canada
E-Mail(s): tanbir@gmail.com,
josephcmac@gmail.com
Web-page(s): www.lacim.quam.ca/∼tanbir
Received by the editors: 25.10.2017
and in final form 29.12.2017.
|