# Generalizing Krawtchouk Polynomials Using Hadamard Matrices

Authors: Peter S. Chami; Bernd Sing; Norris Sookoo
Journal: ISRN Applied Mathematics
 (2014)

---

## Abstract

We investigate polynomials, calledm-polynomials, whose generator polynomial has coefficients that can be arranged in a square matrix; in particular, the case where this matrix is a Hadamard matrix is considered. Orthogonality relations and recurrence relations are established, and coefficients for the expansion of any polynomial in terms of m-polynomials are obtained. We conclude this paper by an implementation of m-polynomials and some of the results obtained for them in Mathematica.


---

## Body

## 1. Introduction

Matrices have been the subject of much study, and large bodies of results have been obtained about them. We study the interplay between the theory of matrices and the theory of orthogonal polynomials. For Krawtchouk polynomials, introduced in [1], interesting results have been obtained in [2–4]; also see the review article [5] and compare [6] for generalized Krawtchouk polynomials. More recently, conditions for the existence of integral zeros of binary Krawtchouk polynomials have been obtained in [7], while properties for generalized Krawtchouk polynomials can be found in [8]. Other generalizations of binary Krawtchouk polynomials have also been considered; for example, some properties of binary Krawtchouk polynomials have been generalised to q-Krawtchouk polynomials in [9]. Orthogonality relations for quantum and q-Krawtchouk polynomials have been derived in [10], and it has been shown that affine q-Krawtchouk polynomials are dual to quantum q-Krawtchouk polynomials. In this paper, we define and study generalizations of Krawtchouk polynomials, namely, m-polynomials.The Krawtchouk polynomialK
k
(
x
) is given by
(1)
K
k
(
x
)
=
∑
j
=
0
k
‍
(
-
1
)
j
(
x
j
)
(
n
-
x
k
-
j
)
,
where n is a natural number and x
∈
{
0,1
,
…
,
n
}. The generator polynomial is
(2)
(
1
+
z
)
n
-
x
(
1
-
z
)
x
=
∑
k
=
0
n
‍
K
k
(
x
)
z
k
.
The generalized Krawtchouk polynomial K
p
(
s
) is obtained by generalizing the above generator polynomial as follows:
(3)
∏
l
=
0
q
-
1
‍
(
∑
i
=
0
q
-
1
‍
χ
(
ω
¯
i
ω
¯
l
)
z
i
)
s
i
=
∑
p
∈
V
(
n
,
q
)
‍
K
p
(
s
)
z
p
,
where ∑
‍
s
i
=
∑
‍
p
i
=
n, q is a prime power, the z
i are indeterminate, the field G
F
(
q
) with q elements is {
0
,
ω
¯
1
,
ω
¯
2
,
…
,
ω
¯
q
-
1
}, and χ is a character.The above information about Krawtchouk polynomials and generalized Krawtchouk polynomials was taken from [6].If we replace theχ
(
ω
¯
i
ω
¯
l
) by arbitrary scalars in the last equation, we obtain the generator polynomial of m-polynomials M
G
(
p
,
s
); see Definition 2 below. These m-polynomials are the subject of study in this paper.In Section2, we present relevant notations and definitions. In Section 3, we introduce the generator polynomial. The associated matrix of coefficients G can be any square matrix, and so the question that immediately arises is how the properties of the m-polynomials are related to the properties of G. We will establish that, if G is a generalized Hadamard matrix, then the associated m-polynomials satisfy orthogonality conditions. In Section 4, we establish recurrence relations for m-polynomials. Afterwards, we obtain coefficients for the expansion of a polynomial in terms of m-polynomials in Section 5. Finally, in Section 6, we implement the results obtained here in Mathematica, so the reader may easily derive and explore m-polynomials for any matrix G.


## 2. Definitions and Notations

In this paper,ℕ
0 denotes {
0,1
,
2,3
,
…
}. We use the convention that if p
∈
ℕ
0
q, then p has components (
p
0
,
p
1
,
…
,
p
q
-
1
). So, if r
(
i
)
∈
ℕ
0
q then r
(
i
) denotes (
r
i
,
0
,
r
i
,
1
,
…
,
r
i
,
q
-
1
). We will also use the q  elementary unit vectors  e
0
=
(
1,0
,
0
,
…
,
0
), e
1
=
(
0,1
,
0
,
…
,
0
)
,
…
,
e
q
-
1
=
(
0,0
,
…
,
0,1
).We use theℓ
1-norm (the “taxicab-metric”) to measure the length  |
p
| of p
∈
ℕ
0
q, that is, |
p
|
=
∑
i
=
0
q
-
1
p
i. We define the set of weak compositions of
n
into
q
numbers by V
(
n
,
q
)
=
{
p
∈
ℕ
0
q
:
|
p
|
=
n
}; in other words, V
(
n
,
q
) is the subset of q-dimensional nonnegative vectors of length n. We note that the set V
(
n
,
q
) has cardinality (
n
+
q
-
1
q
-
1
). For p
∈
ℕ
0
q, we use the multi-index notation p
!
=
∏
i
=
0
q
-
1
p
i
!. Similarly, for a variable z
=
(
z
0
,
z
1
,
…
,
z
q
-
1
)
∈
ℂ
q and p
∈
ℕ
0
q, we write z
p
=
∏
j
=
0
q
-
1
‍
z
j
p
i (where the convention 0
0
=
1 is used). We note that the multinomial theorem reads
(4)
(
∑
i
=
0
q
-
1
‍
z
i
)
n
=
∑
p
∈
V
(
n
,
q
)
‍
(
n
p
)
·
z
p
=
∑
p
∈
V
(
n
,
q
)
‍
n
!
p
0
!
⋯
p
q
-
1
!
·
z
0
p
0
⋯
z
q
-
1
p
q
-
1
.In the following,G denotes an arbitrary q
×
q matrix. We use the following convention to refer to the entries of a q
×
q matrix [11]. The entry in the ith row and jth column is called the (
i
-
1
,
j
-
1
)  entry, where i
,
j
=
1,2
,
…
,
q. Thus, the (
i
,
j
) entry of G is denoted by g
i
j, where i
,
j
=
0,1
,
…
,
q
-
1. Given a matrix G, the matrix that remains when the first row and the first column of G are removed is called the core of G.The next definition is well known.Definition 1.
For an integerq greater than one, a q
×
q matrix H is called a generalized Hadamard matrix if H
H
¯
T
=
q
I
q, where H
¯
T is the complex conjugate transpose of H and I
q is the q
×
q identity matrix.
We now define them-polynomial with respect to a matrix G.Definition 2.
Lets
=
(
s
0
,
s
1
,
,
…
,
s
q
-
1
) and p
=
(
p
0
,
p
1
,
…
,
p
q
-
1
) be elements of V
(
n
,
q
). The  m
-polynomial in
s
with respect to
G
having parameter
p is denoted by  M
G
(
p
;
s
) or M
G
(
p
0
,
p
1
,
…
,
p
q
-
1
;
s
0
,
s
1
,
…
,
s
q
-
1
) and given by
(5)
M
G
(
p
;
s
)
=
∑
r
i
,
j
‍
s
!
∏
i
,
j
r
i
,
j
!
∏
a
=
0
q
-
1
‍
∏
b
=
0
q
-
1
‍
g
a
b
r
a
,
b
=
s
!
∑
r
i
,
j
‍
∏
a
=
0
q
-
1
‍
∏
b
=
0
q
-
1
‍
g
a
b
r
a
,
b
r
a
,
b
!
,
where the summation is taken over all sets of nonnegative integers r
i
,
j (with i
,
j
=
0,1
,
…
,
q
-
1) satisfying
(6)
∑
j
=
0
q
-
1
‍
r
i
,
j
=
s
i
,
i
=
0,1
,
…
,
q
-
1
,
∑
i
=
0
q
-
1
‍
r
i
,
j
=
p
j
,
j
=
0,1
,
…
,
q
-
1
.


## 3. The Generator Polynomial and Orthogonality Relations

The values of them-polynomial with respect to a matrix G can be derived from a generator polynomial.Theorem 3 (generator polynomial).
Lets
=
(
s
0
,
s
1
,
…
,
s
q
-
1
)
∈
V
(
n
,
q
) and let G
=
(
g
i
j
) be a q
×
q matrix. Then,
(7)
∏
i
=
1
q
-
1
‍
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
=
∑
p
∈
V
(
n
,
q
)
‍
M
G
(
p
;
s
)
z
p
,
where p
=
(
p
0
,
p
1
,
…
,
p
q
-
1
).Proof.
This is an application of the multinomial theorem (recall that forr
(
i
)
∈
ℕ
0
q, we have r
(
i
)
=
(
r
i
,
0
,
r
i
,
1
,
…
,
r
i
,
q
-
1
)):
(8)
∏
i
=
0
q
-
1
‍
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
=
∏
i
=
0
q
-
1
‍
{
∑
r
(
i
)
∈
V
(
s
i
,
q
)
‍
s
i
!
r
(
i
)
!
[
∏
j
=
0
q
-
1
‍
(
g
i
j
z
j
)
r
i
,
j
]
}
=
∑
r
(
i
)
∈
V
(
s
i
,
q
)
,
i
=
0,1
,
…
,
q
-
1
‍
s
!
∏
i
,
j
r
i
,
j
!
(
∏
a
=
1
q
-
1
‍
∏
b
=
0
q
-
1
‍
g
a
b
r
a
,
b
)
×
∏
k
=
0
q
-
1
‍
z
k
r
0
,
k
+
r
1
,
k
+
⋯
+
r
q
-
1
,
k
=
∑
p
∈
V
(
n
,
q
)
‍
M
G
(
p
;
s
)
z
p
,
where p
k
=
r
0
,
k
+
r
1
,
k
+
⋯
+
r
q
-
1
,
k.As an immediate consequence, we can recover the entriesg
i
j of the matrix G as the m-polynomials of minimum order.Corollary 4.
We haveM
G
(
e
ℓ
;
e
k
)
=
g
k
ℓ.Proof.
Fors
=
e
k, the left-hand side of (7) becomes
(9)
g
k
,
0
z
0
+
g
k
,
1
z
1
+
⋯
+
g
k
,
q
-
1
z
q
-
1
,
and since p
∈
V
(
1
,
q
) and thus runs through e
0
,
…
,
e
q
-
1 in this case, the rest follows by comparing coefficients of z
j.Remark 5.
Theorem3 can also be used for summation results of m-polynomials over V
(
n
,
q
): using z
=
(
1
,
…
,
1
), we obtain
(10)
∑
p
∈
V
(
n
,
q
)
‍
M
G
(
p
;
s
)
=
∏
i
=
0
q
-
1
‍
(
∑
j
=
0
q
-
1
‍
g
i
j
)
s
i
,
that is, the product of the s
ith power of the ith column sum of G.
As an immediate result of this remark, we can establish the following corollary.Corollary 6.
If∑
j
=
0
q
-
1
g
i
j
=
0 for one 0
≤
i
≤
q
-
1 (i.e., one of the row-sums of the matrix G is zero), then ∑
p
∈
V
(
n
,
q
)
M
G
(
p
;
s
)
=
0.For a generalized Hadamard matrixG, the multinomial theorem yields the following orthogonality relation for the corresponding m-polynomials.Theorem 7 (orthogonality relation).
IfG is a generalized Hadamard matrix, then the m-polynomials M
G
(
p
,
s
), with p
,
s
∈
V
(
n
,
q
), satisfy the orthogonality relations
(11)
∑
s
∈
V
(
n
,
q
)
‍
1
s
!
M
G
(
p
;
s
)
M
G
(
t
;
s
)
¯
=
q
n
p
!
δ
p
,
t
,
where
(12)
s
=
(
s
0
,
s
1
,
…
,
s
q
-
1
)
,
p
=
(
p
0
,
p
1
,
…
,
p
q
-
1
)
,
t
=
(
t
0
,
t
1
,
…
,
t
q
-
1
)
,
δ
p
,
t
=
∏
i
=
0
q
-
1
‍
δ
p
i
,
t
i
=
{
1
,
i
f
p
i
=
t
i
∀
i
,
0
,
o
t
h
e
r
w
i
s
e
,
denotes Kronecker’s delta.Proof.
Letz
=
(
z
0
,
z
1
,
…
,
z
q
-
1
), y
=
(
y
0
,
y
1
,
…
,
y
q
-
1
)
∈
ℂ
q, and define
(13)
J
=
∑
i
=
0
q
-
1
‍
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
(
∑
k
=
0
q
-
1
‍
g
i
k
¯
y
k
)
=
∑
i
=
0
q
-
1
‍
∑
j
=
0
q
-
1
‍
∑
k
=
0
q
-
1
‍
g
i
j
g
i
k
¯
z
j
y
k
.
Then, on the one hand, we have
(14)
J
=
q
∑
j
=
0
q
-
1
‍
z
j
y
j
since G is a generalized Hadamard matrix. Consequently,
(15)
J
n
=
q
n
{
∑
s
∈
V
(
n
,
q
)
‍
n
!
s
!
(
z
0
y
0
)
s
0
(
z
1
y
1
)
s
1
⋯
(
z
q
-
1
y
q
-
1
)
s
q
-
1
}
.
On the other hand, the multinomial theorem yields
(16)
J
n
=
∑
s
∈
V
(
n
,
q
)
‍
n
!
s
!
∏
i
=
0
q
-
1
‍
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
(
∑
k
=
0
q
-
1
‍
g
i
k
¯
y
k
)
s
i
=
∑
s
∈
V
(
n
,
q
)
‍
n
!
s
!
[
∑
p
∈
V
(
n
,
q
)
‍
M
G
(
p
;
s
)
z
p
]
×
[
∑
t
∈
V
(
n
,
q
)
‍
M
G
(
t
;
s
)
¯
y
t
]
.
Equating coefficients ofz
p
y
t in the two above expressions for J
n, we obtain the desired result.IfG is a generalized Hadamard matrix and also satisfies certain additional conditions, then it is possible to establish that the corresponding m-polynomials satisfy additional orthogonality conditions. We use the following three results in proving this.Lemma 8.
IfG is symmetric, that is, G
=
G
T, then M
G
(
s
;
p
)
=
(
p
!
/
s
!
)
M
G
(
p
;
s
).Proof.
By Definition2, we have (where ∑
j
=
0
q
-
1
h
i
,
j
=
p
i and ∑
i
=
0
q
-
1
h
i
,
j
=
s
j)
(17)
M
G
(
s
;
p
)
=
p
!
∑
h
i
,
j
‍
∏
a
=
0
q
-
1
‍
∏
b
=
0
q
-
1
‍
g
a
b
h
a
,
b
h
a
,
b
!
=
p
!
s
!
s
!
∑
h
i
,
j
‍
∏
a
=
0
q
-
1
‍
∏
b
=
0
q
-
1
‍
g
b
a
h
a
,
b
h
a
,
b
!
=
p
!
s
!
s
!
∑
r
i
,
j
‍
∏
b
=
0
q
-
1
‍
∏
a
=
0
q
-
1
‍
g
b
a
r
b
,
a
r
b
,
a
!
=
p
!
s
!
M
G
(
p
;
s
)
,
where we define r
i
,
j
=
h
j
,
i (and thus ∑
j
=
0
q
-
1
r
i
,
j
=
s
i and ∑
i
=
0
q
-
1
r
i
,
j
=
p
j), and since G is symmetric (i.e., g
a
b
=
g
b
a).The following results can be obtained in a similar manner to Lemma8.Lemma 9.
IfG has a symmetric core, g
0
,
j
=
1 for j
=
0
,
…
,
q
-
1 and g
i
,
0
=
-
1 for i
=
1
,
…
,
q
-
1, then M
G
(
s
;
p
)
=
(
-
1
)
s
0
+
p
0
(
p
!
/
s
!
)
M
G
(
p
;
s
).Such symmetry relations yield additional orthogonality relations.Theorem 10 (additional orthogonality relation).
LetG be a generalized Hadamard matrix. (i)
If in addition
G
is symmetric, then
(18)
∑
s
∈
V
(
n
,
q
)
‍
M
G
(
p
;
s
)
M
G
(
s
;
t
)
¯
=
q
n
δ
p
,
t
.
(ii)
If in addition
G
has a symmetric core,
g
0
,
j
=
1
for
j
=
0
,
…
,
q
-
1
and
g
i
,
0
=
-
1
for
i
=
1
,
…
,
q
-
1
, then
(19)
∑
s
∈
V
(
n
,
q
)
(
-
1
)
s
0
M
G
(
p
;
s
)
M
G
(
s
;
t
)
¯
=
(
-
1
)
t
0
q
n
δ
p
,
t
.Proof.
This follows immediately from Theorem7 and Lemmas 8 and 9.Remark 11.
It turns out that a slight modification of the abovem-polynomials has already been considered in [12, 13]. For a matrix G and p
,
s
∈
V
(
n
,
q
), [13, Equation (2.3)] defines polynomials L
p
,
s
(
G
) by L
p
,
s
(
G
)
=
(
1
/
s
!
)
M
G
(
p
;
s
) in our notation. For these polynomials, the following multiplication property is proved (see [13, Theorem 3.2]):
(20)
L
p
,
t
(
G
1
G
2
)
=
∑
s
∈
V
(
n
,
q
)
‍
s
!
L
p
,
s
(
G
1
)
L
s
,
t
(
G
2
)
,
for q
×
q matrices G
1, G
2. With G
1
=
G, G
2
=
G
¯
T and thus G
1
G
2
=
G
G
¯
T
=
q
I
q, Theorem 7 becomes a special case of this equation by noting that L
s
,
t
(
G
T
)
=
L
t
,
s
(
G
) (see [13, Equation (4.5)]) and L
p
,
t
(
q
I
q
)
=
(
q
n
/
p
!
)
δ
p
,
t (using the notation of Definition 2, the polynomial on the left can only be nonzero if r
i
,
j
=
0 whenever i
≠
j and p
i
=
r
i
,
i
=
t
i otherwise).


## 4. Recurrence Relations and Summation of Certain Polynomials

We use Theorem3 to derive a recurrence relation for m-polynomials in s having parameter p where both s
,
p
∈
V
(
n
,
q
) by a sum of m-polynomials where both s
,
p
∈
V
(
n
-
1
,
q
).Theorem 12 (recurrence relations I).
Letp
,
s
∈
V
(
n
,
q
) with s
i
>
0 for one i
∈
{
0
,
…
,
q
-
1
}. Then,
(21)
M
G
(
p
;
s
)
=
∑
k
=
0
,
p
k
>
0
q
-
1
‍
g
i
k
M
G
(
p
-
e
k
;
s
-
e
i
)
,
where the sum on the right is taken over all k such that the kth component p
k of p
∈
V
(
n
,
q
) is positive.Proof.
Using (7) twice, we obtain (if s
i
>
0)
(22)
∑
p
∈
V
(
n
,
q
)
‍
M
G
(
p
;
s
)
z
p
=
∏
i
=
1
q
-
1
‍
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
=
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
(
∑
j
=
0
q
-
1
‍
g
0
j
z
j
)
s
0
⋯
(
∑
j
=
0
q
-
1
‍
g
i
-
1
,
j
z
j
)
s
i
-
1
,
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
-
1
(
∑
j
=
0
q
-
1
‍
g
i
+
1
,
j
z
j
)
s
i
+
1
⋯
(
∑
j
=
0
q
-
1
‍
g
q
-
1
,
j
z
j
)
s
q
-
1
=
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
∑
p
~
∈
V
(
n
-
1
,
q
)
‍
M
G
(
p
~
;
s
-
e
i
)
z
p
~
.
Multiplying the right-hand side out and equating coefficients of z
p establish the claim.Theorem 13 (recurrence relations II).
Letp
,
s
∈
V
(
n
,
q
) with p
k
>
0 for one k
∈
{
0
,
…
,
q
-
1
}. Then,
(23)
M
G
(
p
;
s
)
=
∑
i
=
0
,
s
i
>
0
q
-
1
s
i
p
k
g
i
k
M
G
(
p
-
e
k
;
s
-
e
i
)
,
where the sum on the right is taken over all i such that the ith component s
i of s
∈
V
(
n
,
q
) is positive.Proof.
We note that we have(24)
∂
∂
z
k
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
=
{
s
i
g
i
k
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
-
1
,
if
s
i
>
0
,
0
,
if
s
i
=
0
.
Thus, on the one hand, the derivative of the left-hand side of (7) with respect to z
k is
(25)
∑
m
=
0
,
s
m
>
0
q
-
1
‍
[
s
m
g
m
k
(
∑
ℓ
=
0
q
-
1
‍
g
m
ℓ
z
ℓ
)
s
m
-
1
∏
i
=
0
,
i
≠
m
q
-
1
‍
(
∑
j
=
0
q
-
1
‍
g
i
j
z
j
)
s
i
]
.
Using (7), this is equal to
(26)
∑
m
=
0
,
s
m
>
0
q
-
1
‍
[
s
m
g
m
k
∑
p
~
∈
V
(
n
-
1
,
q
)
‍
M
G
(
p
~
;
s
-
e
m
)
z
p
~
]
.
On the other hand, the derivative of the right-hand side of (7) with respect to z
k is
(27)
∑
p
∈
V
(
n
,
q
)
,
p
k
>
0
‍
p
k
M
G
(
p
;
s
)
z
p
-
e
k
.
Equating the last two expressions and interchanging the order of summation yield
(28)
∑
p
~
∈
V
(
n
-
1
,
q
)
‍
[
∑
m
=
0
,
s
m
>
0
q
-
1
‍
s
m
g
m
k
M
G
(
p
~
;
s
-
e
m
)
z
p
~
]
=
∑
p
∈
V
(
n
,
q
)
,
p
k
>
0
‍
p
k
M
G
(
p
;
s
)
z
p
-
e
k
;
by comparing coefficients, we must have p
~
=
p
-
e
k, and therefore (noting that p
k
>
0)
(29)
M
G
(
p
;
s
)
=
∑
m
=
0
,
s
m
>
0
q
-
1
‍
s
m
p
k
g
m
k
M
G
(
p
-
e
k
;
s
-
e
m
)
.We note that (21) and (23) can be rewritten as
(30)
M
G
(
p
;
s
)
=
∑
r
∈
V
(
1
,
q
)
,
s
.
t
.
p
-
r
∈
V
(
n
-
1
,
q
)
‍
g
i
0
r
0
g
i
1
r
1
⋯
g
i
,
q
-
1
r
q
-
1
gggggggggggggggggggggg
×
M
G
(
p
-
r
;
s
-
e
i
)
,
M
G
(
p
;
s
)
=
∑
r
∈
V
(
1
,
q
)
,
s
.
t
.
s
-
r
∈
V
(
n
-
1
,
q
)
‍
s
0
r
0
s
1
r
1
⋯
s
q
-
1
r
q
-
1
p
k
g
0
k
r
0
g
1
k
r
1
⋯
g
q
-
1
,
k
r
q
-
1
g
g
g
g
g
g
g
g
g
g
g
×
M
G
(
p
-
e
k
;
s
-
r
)
,
respectively.In particular, Theorem12 can be easily iterated to obtain the following statements.Proposition 14.
Letp
,
s
∈
V
(
n
,
q
) with s
i
≥
m
≥
0 for one i
∈
{
0
,
…
,
q
-
1
}. Then,
(31)
M
G
(
p
;
s
)
=
∑
r
∈
V
(
m
,
q
)
,
s.t.
p
-
r
∈
V
(
n
-
m
,
q
)
‍
(
m
r
)
g
i
0
r
0
g
i
1
r
1
⋯
g
i
,
q
-
1
r
q
-
1
g
g
g
g
g
g
g
g
g
g
×
M
G
(
p
-
r
;
s
-
m
e
i
)
,
where the sum on the right is taken over all r
∈
V
(
m
,
q
) such that p
-
r is in V
(
n
-
m
,
q
).Proof.
This follows by repeatedly applying (21) in Theorem 12. The multinomial coefficient (
m
r
) arises as the number of ways p can be changed to p
-
r step-by-step.Corollary 15.
Letp
,
s
∈
V
(
n
,
q
) with s
i
≥
m
i
≥
0 for all i
∈
{
0
,
…
,
q
-
1
}. Then,
(32)
M
G
(
p
;
s
)
=
∑
r
(
i
)
∈
V
(
m
i
,
q
)
,
s.t.
p
-
∑
i
=
0
q
-
1
r
∈
V
(
n
-
|
m
|
,
q
)
‍
[
∏
i
=
0
q
-
1
‍
(
m
i
r
(
i
)
)
]
×
[
∏
i
=
0
q
-
1
‍
∏
j
=
0
q
-
1
‍
g
i
j
r
i
j
]
M
G
(
p
-
∑
i
=
0
q
-
1
‍
r
(
i
)
;
s
-
m
)
,
where the sum on the right is taken over all the q
-
1 vectors r
(
i
)
∈
V
(
m
i
,
q
) such that p
-
∑
i
=
0
q
-
1
r
∈
V
(
n
-
|
m
|
,
q
).Proof.
This follows from repeatedly applying Proposition14, by subtracting m
0 from s
0, m
1 from s
1, and so on.We note that takingm
=
s in the previous corollary yields the statement of Definition 2 (since, by definition, M
G
(
0
;
0
)
=
1).Combining the recurrence relation in Theorem12 with Theorem 7 yields the following summation formula for m-polynomials.Proposition 16 (summation formula).
LetG be a generalized Hadamard matrix and p
,
s
∈
V
(
n
,
q
). Then, for any pair of fixed, arbitrary elements i
,
j
∈
{
0
,
…
,
q
-
1
}, one has
(33)
∑
s
∈
V
(
n
,
q
)
‍
1
s
!
M
G
(
p
+
e
j
;
s
+
e
i
)
M
G
(
p
;
s
)
¯
=
g
i
j
q
n
p
!
.


## 5. Expansion of a Polynomial

The coefficients for the expansion of a polynomial in terms of Krawtchouk polynomials have been obtained (cf. [6]). We obtain a similar result for m-polynomials defined in terms of a generalized Hadamard matrix, using orthogonality properties.Theorem 17 (polynomial expansion).
LetG be a generalized Hadamard matrix, and let x
=
(
x
0
,
x
1
,
…
,
x
q
-
1
) be a variable element of V
(
n
,
q
). (i)
IfG is symmetric and the expansion of a polynomial γ
(
x
) in terms of m-polynomials defined with respect to G is (with coefficients α
s
∈
ℂ)
(34)
γ
(
x
)
=
∑
s
∈
V
(
n
,
q
)
‍
α
s
·
M
G
(
x
;
s
)
,
then, for all ℓ
∈
V
(
n
,
q
),
(35)
α
ℓ
=
q
-
n
∑
i
∈
V
(
n
,
q
)
‍
γ
(
i
)
·
M
G
(
ℓ
,
i
)
¯
.
Similarly, if the expansion of a polynomial γ
(
x
) in terms of m-polynomials is (with coefficients β
s
∈
ℂ)
(36)
γ
(
x
)
=
∑
s
∈
V
(
n
,
q
)
‍
β
s
·
M
G
(
s
;
x
)
,
then, for all ℓ
∈
V
(
n
,
q
),
(37)
β
ℓ
=
q
-
n
∑
i
∈
V
(
n
,
q
)
‍
γ
(
i
)
·
M
G
(
i
,
ℓ
)
¯
.
(ii)
IfG has a symmetric core, g
0
,
j
=
1 for j
=
0
,
…
,
q
-
1 and g
i
,
0
=
-
1 for i
=
1
,
…
,
q
-
1, then the corresponding coefficients can be calculated for all ℓ
∈
V
(
n
,
q
) by
(38)
α
ℓ
=
(
-
1
)
ℓ
0
q
-
n
∑
i
∈
V
(
n
,
q
)
‍
(
-
1
)
i
0
γ
(
i
)
·
M
G
(
ℓ
,
i
)
¯
,
respectively,
(39)
β
ℓ
=
(
-
1
)
ℓ
0
q
-
n
∑
i
∈
V
(
n
,
q
)
‍
(
-
1
)
i
0
γ
(
i
)
·
M
G
(
i
,
ℓ
)
¯
.Proof.
Letx
=
i. Multiplying both sides of (34) by M
G
(
ℓ
,
i
)
¯ and summing each side over all elements of V
(
n
,
q
) yield
(40)
∑
i
∈
V
(
n
,
q
)
‍
γ
(
i
)
M
G
(
ℓ
,
i
)
¯
=
∑
i
∈
V
(
n
,
q
)
‍
∑
s
∈
V
(
n
,
q
)
‍
α
s
M
G
(
ℓ
,
i
)
¯
M
G
(
i
,
s
)
=
∑
s
∈
V
(
n
,
q
)
‍
α
s
∑
i
∈
V
(
n
,
q
)
‍
M
G
(
l
,
i
)
¯
M
G
(
i
,
s
)
=
∑
s
∈
V
(
n
,
q
)
‍
α
s
∑
i
∈
V
(
n
,
q
)
‍
M
G
(
l
,
i
)
M
G
(
i
,
s
)
¯
¯
=
(
⋆
)
∑
s
∈
V
(
n
,
q
)
‍
α
s
·
q
n
·
δ
ℓ
,
s
=
α
ℓ
q
n
,
where step (
⋆
) uses Theorem 10; the first result in (i) follows. The other results are proved similarly.


## 6. Mathematica Code

Here, we present Mathematica code to obtainm-polynomials. First, we specify the matrix G and the length n:> g = {{1, 1}, {1, −1}}
> n = 6From this we can calculate q, the set V
(
n
,
q
) and initialize the variable z: > q = Union[Dimensions[g]][[1]]
> pall = Sort[Flatten[Map[Permutations,
IntegerPartitions[n, {q},
Range[0, n]]], 1]]
> z = Table[f[i], {i, q}]Using Theorem 3, we obtain the m-polynomial via its generator: > generator[s_]:= Expand[Product[
(Sum[g[[i, j]] z[[j]],
{j, 1, q}])^(s[[i]]), {i, 1, q}]]
> mg[p_, s_]:= Coefficient[generator[s],
Inner[Power, z, p, Times]]The values of the m-polynomial can be shown using the following command: > TableForm[Table[mg[pall[[i]],
pall[[j]]], {i, Length[pall]},
{j, Length[pall]}], TableHeadings ->
{pall, pall}, TableDepth -> 2]For the above chosen matrixG and length n, the output for M
G
(
p
;
s
) looks as follows (p denotes the row and s the column; e.g., M
G
(
(
2,4
)
;
(
3,3
)
)
=
3):
(41)
{
0,6
}
{
1,5
}
{
2,4
}
{
3,3
}
{
4,2
}
{
5,1
}
{
6,0
}
{
0,6
}
1
-
1
1
-
1
1
-
1
1
{
1,5
}
-
6
4
-
2
0
2
-
4
6
{
2,4
}
15
-
5
-
1
3
-
1
-
5
15
{
3,3
}
-
20
0
4
0
-
4
0
20
{
4,2
}
15
5
-
1
-
3
-
1
5
15
{
5,1
}
-
6
-
4
-
2
0
2
4
6
{
6,0
}
1
1
1
1
1
1
1
Thus, we are able to evaluate the m-polynomial M
G
(
p
;
s
) for any p
,
s
∈
V
(
n
,
q
) (and thus check orthogonality and recurrence relations). With the help of the Mathematica function Fit, we can express the m-polynomials as univariant polynomials in (
s
0
-
s
1
) as follows (we also recall that |
(
s
0
,
s
1
)
|
=
s
0
+
s
1
=
6 here):
(42)
M
G
(
(
0,6
)
;
(
s
0
,
s
1
)
)
=
1
720
(
s
0
-
s
1
)
6
-
5
72
(
s
0
-
s
1
)
4
+
34
45
(
s
0
-
s
1
)
2
-
1
,
M
G
(
(
1,5
)
;
(
s
0
,
s
1
)
)
=
1
120
(
s
0
-
s
1
)
5
-
1
3
(
s
0
-
s
1
)
3
+
11
5
(
s
0
-
s
1
)
,
M
G
(
(
2,4
)
;
(
s
0
,
s
1
)
)
=
1
24
(
s
0
-
s
1
)
4
-
7
6
(
s
0
-
s
1
)
2
+
3
,
M
G
(
(
3,3
)
;
(
s
0
,
s
1
)
)
=
1
6
(
s
0
-
s
1
)
3
-
8
3
(
s
0
-
s
1
)
,
M
G
(
(
4,2
)
;
(
s
0
,
s
1
)
)
=
1
2
(
s
0
-
s
1
)
2
-
3
,
M
G
(
(
5,1
)
;
(
s
0
,
s
1
)
)
=
(
s
0
-
s
1
)
,
M
G
(
(
6,0
)
;
(
s
0
,
s
1
)
)
=
1
.
Similarly, we may express the m-polynomials as univariant polynomials in (
p
0
-
p
1
) as follows:
(43)
M
G
(
(
p
0
,
p
1
)
;
(
0,6
)
)
=
77
3840
(
p
0
-
p
1
)
6
-
203
192
(
p
0
-
p
1
)
4
+
1519
120
(
p
0
-
p
1
)
2
-
20
,
M
G
(
(
p
0
,
p
1
)
;
(
1,5
)
)
=
7
640
(
p
0
-
p
1
)
5
-
49
96
(
p
0
-
p
1
)
3
+
131
30
(
p
0
-
p
1
)
,
M
G
(
(
p
0
,
p
1
)
;
(
2,4
)
)
=
-
7
3840
(
p
0
-
p
1
)
6
+
7
64
(
p
0
-
p
1
)
4
-
199
120
(
p
0
-
p
1
)
2
+
4
,
M
G
(
(
p
0
,
p
1
)
;
(
3,3
)
)
=
-
7
1920
(
p
0
-
p
1
)
5
+
19
96
(
p
0
-
p
1
)
3
-
67
30
(
p
0
-
p
1
)
,
M
G
(
(
p
0
,
p
1
)
;
(
4,2
)
)
=
7
11520
(
p
0
-
p
1
)
6
-
25
576
(
p
0
-
p
1
)
4
+
329
360
(
p
0
-
p
1
)
2
-
4
,
M
G
(
(
p
0
,
p
1
)
;
(
5,1
)
)
=
1
384
(
p
0
-
p
1
)
5
-
17
96
(
p
0
-
p
1
)
3
+
19
6
(
p
0
-
p
1
)
,
M
G
(
(
p
0
,
p
1
)
;
(
6,0
)
)
=
-
1
2304
(
p
0
-
p
1
)
6
+
23
576
(
p
0
-
p
1
)
4
-
101
72
(
p
0
-
p
1
)
2
+
20
.
By Theorem 17, we can express any polynomial γ
(
x
)
=
γ
(
x
0
,
…
,
x
q
-
1
) in terms of m-polynomials. Using Mathematica to find the corresponding coefficients α
s and β
s in the expansion in terms of m-polynomials, for example, for the polynomial p
(
x
0
,
x
1
)
=
x
0
x
1, is achieved as follows: > p[{x0_, x1_}]:= x0 x1
> Table[1/q^n Total[Table[p[pall[[i]]]
Conjugate[mg[pall[[j]], pall[[i]]]],
{i, Length[pall]}]], {j, Length[pall]}]
> Table[1/q^n Total[Table[p[pall[[i]]]
Conjugate[mg[pall[[i]], pall[[j]]]],
{i, Length[pall]}]], {j, Length[pall]}]The output of the later two lines is(44)
{
-
3
64
,
0
,
-
39
64
,
0
,
7
64
,
0
,
35
64
}
,
{
0,0
,
0,0
,
-
1
2
,
0
,
15
2
}
,
giving the list of coefficients α
s, respectively, β
s for s
∈
V
(
n
,
q
). That is, the expansion in terms of m-polynomials here reads as follows:
(45)
x
0
x
1
=
-
3
64
M
G
(
(
x
0
,
x
1
)
;
(
0,6
)
)
-
39
64
M
G
(
(
x
0
,
x
1
)
;
(
2,4
)
)
+
7
64
M
G
(
(
x
0
,
x
1
)
;
(
4,2
)
)
+
35
64
M
G
(
(
x
0
,
x
1
)
;
(
6,0
)
)
,
x
0
x
1
=
-
1
2
M
G
(
(
4,2
)
;
(
x
0
,
x
1
)
)
+
15
2
M
G
(
(
6,0
)
;
(
x
0
,
x
1
)
)
.
As a check, we have (recall that x
0
+
x
1
=
6)
(46)
-
1
2
M
G
(
(
4,2
)
;
(
x
0
,
x
1
)
)
+
15
2
M
G
(
(
6,0
)
;
(
x
0
,
x
1
)
)
=
-
1
2
·
(
1
2
(
x
0
-
x
1
)
2
-
3
)
+
15
2
·
1
=
x
0
(
6
-
x
0
)
=
x
0
x
1
.For a generalized Hadamard matrix with symmetric core,g
0
,
j
=
1 for j
=
0
,
…
,
q
-
1 and g
i
,
0
=
-
1 for i
=
1
,
…
,
q
-
1; for example,
(47)
G
=
(
1
1
1
-
1
1
-
3
2
1
+
3
2
-
1
1
+
3
2
1
-
3
2
)
.
The above mathematica code using Theorem 17 has to be modified as follows: > Table[1/q^n Total [Table
[(-1)^(pall[[i, 1]] + pall[[j, 1]])
p[pall[[i]]] Conjugate[mg[pall[[j]],
pall[[i]]]],
{i, Length[pall]}]], {j, Length[pall]}]
> Table[1/q^n Total[
Table[(-1)^(pall[[i, 1]] + pall[[j, 1]])
p[pall[[i]]] Conjugate[mg[pall[[i]],
pall[[j]]]],
{i, Length[pall]}]], {j, Length[pall]}]


## 7. Outlook

Krawtchouk polynomials and their generalisation appear in many areas of Mathematics, see [5]: harmonic analysis [1, 2, 4], statistics [3], combinatorics and coding theory [6, 7, 9, 11, 14, 15], probability theory [5], representation theory (e.g., of quantum groups) [10, 12, 13], difference equations [16], and pattern recognition [17] (a website called the “Krawtchouk Polynomials Home Page” by V. Zelenkov at http://orthpol.narod.ru/eng/index.html collecting material about M. Krawtchouk and the polynomials that bear his name has, unfortunately, not been updated in a while). However, our motivation in this paper was primarily driven by generalising the results obtained in [8]—and thus shedding more light on the qualitative structure of (generalisations of) Krawtchouk polynomials—and not yet with a specific application in mind. By providing the Mathematica code to obtain m-polynomials, we also hope that other researchers are encouraged to explore them and see if they can be used in their research.



---

*Source: 498135-2014-03-04.xml*