Son of Symmetric Krawtchouk

1. Factorization

Throughout N is even. Begin by recalling the subspaces V₊₊, V_+-,V_-+,V_--. The dimensions depend on the parity of M =N/2. When N ≡ 2 (mod 4) we have

dim V₊₊	=	(N+2)/4
dim V_+-	=	(N+2)/4
dim V_-+	=	(N+2)/4
dim V_--	=	N/4

When N ≡ 0 (mod 4) we have

dim V₊₊	=	(N/4)+1
dim V_+-	=	N/4
dim V_-+	=	N/4
dim V_--	=	N/4

Pick the usual basis for each subspace. When N ≡ 2 (mod 4) the basis vectors v_i are

0 ≤ i ≤ (N-2)/4		v_i =e_2i+e_N-2i
(N+2)/4 ≤ i ≤ N/4		v_i =e_2s+e_N-2s where s=i-(N+2)/4
(N/2)+1 ≤ i ≤ (3N-2)/4		v_i =e_2s+1+e_N-2s-1 where s=i-(N/2)-1
i=(3N+2)/4		v_i=e_N/2
(3N+6)/4 ≤ i ≤ N		v_i =e_2s+1+e_N-2s-1 where s=i-(3N+6)/4

The other case is similar. Let P have this basis as its columns. Let S denote the Nth symmetric Krawtchouk matrix.

Lemma 1 P ^-1SP has the form

A	0	0	0
0	0	B	0
0	C	0	0
0	0	0	D

Proof. Previously shown that S fixes V₊₊ and V_-- and interchanges the other two.

Let cp(A) denote the characteristic polynomial of A. The next lemma is presumably well-known.

Lemma 2 For the matrix M

()

0 B
C 0

we have cp(M)(x)=cp(BC)(x²).

Proof. We have by direct computation

) =det ()

det (

xI -B
-C xI

xI -B
0 -x^-1CB+xI

which gives xⁿdet(xI-x^-1CB)=det(x²I-CB)=cp(BC)(x²). QED

Corollary 3 cp(S) =(x-trS)cp(D)(x)cp(D)(-x)cp(BC)(x²).

Proof. T sends eigenvectors in V_-- to eigenvectors (with value -λ) in V₊₊, missing only the eigenvector for tr S. So sp(A)(x)=(x-trS)cp(D)(-x).QED

I guess, but cannot prove, that cp(D) and cp(BC) are irreducible (over Q) and that they are distinct. This would prove that S has simple eigenvalues.

2.Non-negativity

The idea here is that R=2^2NP^-1S^-2P is non-negative which allows estimates on small eigenvalues of S. There is one binomial coefficient result that I am unable to prove (as always). See subsection B.

A. Entries of R

First note that P^-1S²P is block diagonal and hence so is R. Call the blocks D₁, D₂, D₃, D₄. Let SS denote 2^2NS^-2.

Lemma 4 Let E be the diagonal matrix with diagonal entries (1,1,1,..,1,2,1,..1), where the 2 is in the (3N+2)/4 spot if N ≡ 2 (mod 4) and in the N/4 spot if N ≡ 0 (mod 4). Then P^-1 =(1/2)EP^t. Proof. The columns of P are orthogonal and each has length 2 except the (3N+2)/4 column (in the first case), which has length 1. QED

We will use the double symmetry of SS, namely that SS_ij=SS_ji=SS_N-i,N-j.

Proposition 5 When N ≡ 2 (mod 4) we have (writing M for N/2)

a. The entries of D₁ are SS_2i,2j +SS_2i,N-2j, where 0 ≤ i,j ≤ (N-2)/4.

b. The entries of D₂ are SS_2s,2t -SS_2s,N-2t, where 0 ≤ s,t ≤ (N-2)/4.

c. The entries of D₃ are SS_2s+1,2t+1 +SS_2s+1,N-2t-1, where 0 ≤ s,t < (N-2)/4. The last column is SS_2s+1,M while the last row (except the last column entry) is 2SS_2t+1,M

d. The entries of D₄ are SS_2s+1,2t+1 -SS_2s+1,N-2t-1, where 0 ≤ s,t ≤ (N-2)/4.

Proof. Let e_i be the standard basis. The entries of D₁ are e_i^t Re_j, over the given range of i and j. From our computation of P^-1 we get

e_i^t Re_j	=	(1/2)e_i^tP^tSSPe_j
	=	(1/2)(e_2i +e_N-2i)^tSS (e_2j+e_N-2j)
	=	(1/2)(2SS_2i,2j +2SS_2i,N-2j)

which gives the result. The other computations are similar except for the last row and column of D₃. For the last row (excluding the last column) we want e_i^tRe_j for (N/2) < i < (3N+2)/4 and j=(3N+2)/4. Set s=i-(N/2)-1 and t=j-(N/2)-1. Note that 2t+1=M. We obtain

(1/2)(e_2s+1 +e_N-2s-1)^tSSe_M =SS_2s+1,M

When i=(3N+2)/4 and (N/2) < j < (3N+2)/4 we obtain

e_M^tSS(e_2t+1+e_N-2t-1) = 2SS_2t+1,M

. QED

We make a few comments. D₁, D₂ and D₄ are symmetric but D₃ is not. But only the last row and column fail. To prove R is non-negative it is enough to show D₂ and D₄ are positive since the other two are clearly positive (entries are sums of entries in SS). For this it suffices to show

SS_ij-SS_i,N-i > 0

for i+j even and i+j ≤ N.

Binomial coefficient inequality

Lemma 6 Fix b and k with b ≥ 2k. Suppose k ≤ a ≤ b-k. As a function of a

(

a
k

)

(

b-a
k

)

is unimodal with maximum at a=b/2 ( or (b-1)/2, (b+1)/2). In particular,

(

a
k

)

(

b-a
k

)

≥

(

c
k

)

(

b-c
k

)

Comments: Webmaster