SOLUTIONS OF TWO PROBLEMS OF D. Ž. DJOKOVIĆ

Ice B. Risteski and Kostadin G. Trencevski

Abstract. In this paper, solutions of two old problems of D. Ž. Djoković are given. One solution of the first problem is given by O. P. Lossers [2] in implicit form and the other solution by another method is given in explicit form. The second problem is solved here for the first time.

1. The First Problem. D. Ž. Djoković formulated the following problem in [1].

Find the eigenvalues and eigenvectors of the two–diagonal matrix A = (a_{ij}), where a_{ij} = 0 if | i − j |≠ 1 and a_{i,i+1} = a_{n+2−i,n+1−i} = i, (1 ≤ i ≤ n).

\underline{Comment on the Problem}. O. P. Lossers [2] has proven that if λ is an eigenvalue and (q_{1}, ⋯, q_{n+1}) is the corresponding eigenvector, then the possible values of λ are n − 2k for (0 ≤ k ≤ n) and the coordinates q_{i} of the corresponding eigenvector for λ = n − 2k are given by the coefficients of the polynomial Q(x) = q_{1} + q_{2}x + ⋯ + q_{n+1}x^{n}, where Q(x) = (1 + x)^{n−k}(1 − x)^{k}, (0 ≤ k ≤ n) is a generating polynomial. Since he found n+1 eigenvalues which have multiplicity 1 and their corresponding eigenvectors, these are the required eigenvalues and eigenvectors.

Apart from the solution [2], we give another explicit solution of the problem by a different method. We obtain our solution without any information about the Lossers’ solution.

D. S. Mitrinović [3] cites this problem two times as an unsolved problem (after publishing the solution [2]) in order to emphasize the difficulty of the problem. D. Ž. Djoković probably formulated this problem based on Problem 2.29 in the book by D. S. Mitrinović and R. B. Potts [4]. The determinant of the matrix A is well–known and found in [5, 6].

\underline{Solution of the problem}. The characteristic polynomial of A is

D_{n+1}(−λ) = det(A − λI) = | \begin{matrix}−λ & 1 & 0 & ⋯ & 0 & 0 & 0 \\ n & −λ & 2 & ⋯ & 0 & 0 & 0 \\ 0 & n − 1 & −λ & ⋯ & 0 & 0 & 0 \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ 0 & 0 & 0 & ⋯ & −λ & n − 1 & 0 \\ 0 & 0 & 0 & ⋯ & 2 & −λ & n \\ 0 & 0 & 0 & ⋯ & 0 & 1 & −λ \end{matrix} | .

If to each row of the determinant we add all the following rows, we obtain

D_{n+1}(−λ) = | \begin{matrix}n − λ & n − λ & n − λ & ⋯ & n − λ & n − λ & n − λ \\ n & n − λ − 1 & n − λ & ⋯ & n − λ & n − λ & n − λ \\ 0 & n − 1 & n − λ − 2 & ⋯ & n − λ & n − λ & n − λ \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ 0 & 0 & 0 & ⋯ & 2 − λ & n − λ & n − λ \\ 0 & 0 & 0 & ⋯ & 2 & 1 − λ & n − λ \\ 0 & 0 & 0 & ⋯ & 0 & 1 & −λ \end{matrix} | .

If from each column we subtract the previous column, it follows that

D_{n+1}(−λ) = (n−λ) | \begin{matrix}−λ − 1 & 1 & 0 & ⋯ & 0 & 0 & 0 \\ n − 1 & −λ − 1 & 2 & ⋯ & 0 & 0 & 0 \\ 0 & n − 2 & −λ − 1 & ⋯ & 0 & 0 & 0 \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ 0 & 0 & 0 & ⋯ & −λ − 1 & n − 2 & 0 \\ 0 & 0 & 0 & ⋯ & 2 & −λ − 1 & n − 1 \\ 0 & 0 & 0 & ⋯ & 0 & 1 & −λ − 1 \end{matrix} | ,

which gives the recurrence formula D_{n+1}(−λ) = (n − λ)D_{n}(−λ − 1).

Continuing this process, we obtain

D_{n+1}(−λ) = (n − λ)(n − λ − 2)D_{n−1}(−λ − 2) = (n − λ)(n − λ − 2)(n − λ − 4)D_{n−2}(−λ − 3) = ⋯ = (n − λ)(n − λ − 2)(n − λ − 4) ⋯ [n − λ − 2(n − 1)]D_{1}(−λ − n) = (n − λ)(n − λ − 2)(n − λ − 4) ⋯ [n − λ − 2(n − 1)](−λ − n)

= ∏_{k=1}^{n+1}[n − λ − 2(k − 1)].

Hence, the eigenvalues are

λ_{k} = n − 2(k − 1), (1 ≤ k ≤ n + 1).

The eigenvectors X_{k}(1 ≤ k ≤ n+1) of A, are determined from the matrix equation

(A − λ_{k}I)X_{k} = O,

where X_{k} = [x_{1k}, x_{2k}, …, x_{n+1,k}]^{T} is a non–zero vector determined up to a scalar multiplier. In our case we obtain the following system

− λ_{k}x_{1k} + x_{2k} = 0
nx_{1k} − λ_{k}x_{2k} + 2x_{3k} = 0
(n − 1)x_{2k} − λ_{k}x_{3k} + 3x_{4k} = 0

⋮
3x_{n−2,k} − λ_{k}x_{n−1,k} + (n − 1)x_{nk} = 0
2x_{n−1,k} − λ_{k}x_{nk} + nx_{n+1,k} = 0
x_{nk} − λ_{k}x_{n+1,k} = 0,

i.e.,

(n + 2 − i)x_{i−1,k} − λ_{k}x_{ik} + ix_{i+1,k} = 0,  (1 ≤ i, k ≤ n + 1)  (1.1)

where we have put x_{0k} = x_{n+2,k} = 0. We will prove that

x_{ik} = ∑_{j=0}^{i−1}(−1)^{i−1−j}\binom{k − 1}{i − 1 − j}\binom{n + 1 − k}{j},  (1 ≤ i, k ≤ n + 1).  (1.2)

If k = n + 1, from (1.1) we obtain

(n + 2 − i)x_{i−1,n+1} + nx_{i,n+1} + ix_{i+1,n+1} = 0.  (1.3)

It is easy to verify that y_{i} = \binom{n}{i−1} satisfies

(n + 2 − i)y_{i−1} − ny_{i} + iy_{i+1} = 0.

Hence, x_{i,n+1} = (−1)^{i−1}y_{i} = (−1)^{i−1}\binom{n}{i−1} is a solution of (1.3), and (1.2) is satisfied for k = n + 1.

The eigenvectors for k = n, n − 1, …, 1, can be determined as follows. By adding the first i (1 ≤ i ≤ n + 1) equations in (1.1), we obtain

(2k − 2)(x_{1k} + ⋯ + x_{i−1,k}) + x_{ik}(i + 2k − n − 3) + ix_{i+1,k} = 0.

Let A_{s} = x_{1k} + … + x_{sk} (1 ≤ s ≤ n + 1). Then

(2k − 2)A_{i−1} + (A_{i} − A_{i−1})(i + 2k − n − 3) + i(A_{i+1} − A_{i}) = 0,
(n + 1 − i)A_{i−1} − (n + 3 − 2k)A_{i} + iA_{i+1} = 0,
(n′ + 2 − i)A_{i−1} − (n′ + 2 − 2k′)A_{i} + iA_{i+1} = 0,  (1.4)

where n′ = n − 1 and k′ = k − 1. Now comparing (1.1) and (1.4) we note that the vector [A_{1}, A_{2}, …, A_{n+1}]^{T} satisfies a system of the form (1.1) where n and k are decreased for 1. This fact enables us to determine the eigenvectors for k = n, n − 1, …, 1. We do this by using the following combinatorial identity.

∑_{j=0}^{r}(−1)^{j}\binom{t}{j} = (−1)^{r}\binom{t − 1}{r},  (1.5)

which is easy to prove by induction of r. Hence, (1.2) can be obtained. Indeed, (1.2) can be proven by regressive induction of k, using the identity (1.5). This completes the solution of the problem. Finally, we note that the eigenvector for k = 1 is

[\binom{n}{0}, \binom{n}{1}, ⋯, \binom{n}{n}]^{T} .

2. The Second Problem. In [7, 8] the following problem is stated.

Prove the identity

∑_{k=0}^{n} P_{k}(x)P_{n−k}(x) = ∑_{k=n−[n/2]}^{n}(−1)^{n−k}\binom{k}{n − k}(2x)^{2k−n},  (2.1)

where P_{n}(x) is Legendre’s polynomial.

\underline{First Solution}. The above may be rewritten in the following form,

∑_{k=0}^{n} P_{k}(x)P_{n−k}(x) = ∑_{k=0}^{[n/2]}(−1)^{k}\binom{n − k}{k}(2x)^{n−2k} = C_{n}^{1}(x),  (2.2)

where C_{n}^{1}(x) is Gegenbauer’s polynomial.

By squaring

(1 − 2xt + t^{2})^{−1/2} = ∑_{ν=0}^{∞} P_{ν}(x)t^{ν},

we obtain

(1 − 2xt + t^{2})^{−1} = ∑_{ν=0}^{∞} a_{ν}(x)t^{ν},  a_{ν}(x) = ∑_{k=0}^{ν} P_{k}(x)P_{ν−k}(x).  (2.3)

Next, differentiating (2.3) n-times with respect to t, we obtain

\frac{∂^{n}[(1 − 2xt + t^{2})^{−1}]}{∂t^{n}} |_{t=0}= n!C_{n}^{1}(x) = n! ∑_{k=0}^{n} P_{k}(x)P_{n−k}(x).  (2.4)

The proof follows immediately from (2.2) and (2.4).

\underline{Second Solution}. Using

P_{k}(x) = ∑_{i=0}^{[k/2]}(−1)^{i} \frac{1}{2^{k}} \binom{2k − 2i}{k − i}\binom{k − i}{i}x^{k−2i}

it is sufficient to prove that the coefficients of x^{i} of the left and the right side of (2.1) are equal. By convention, all indices are non–negative integers, such as the indices of the binomial coefficient \binom{n}{k}, 0 ≤ k ≤ n, unless otherwise specified. According to this convention, we must prove that

\begin{matrix}∑_{k} ∑_{i+j=s}(−1)^{i+j} \frac{1}{2^{n}} \binom{2k − 2i}{k − i}\binom{k − i}{i}\binom{2n − 2k − 2j}{n − k − j}\binom{n − k − j}{j} \\ = (−1)^{s}\binom{n − s}{s}2^{n−2s} \end{matrix}

for s ∈ {0, 1, ⋯, [n/2]}, i.e.,

∑_{k} ∑_{i} \frac{1}{2^{n}} \binom{2k − 2i}{k − i}\binom{k − i}{i}\binom{2n − 2k − 2s + 2i}{n − k − s + i}\binom{n − k − s + i}{s − i}

= \binom{n − s}{s}2^{n−2s}.  (2.5)

In order to transform the left side L of (2.5) into the right side R, we will use the following two identities.

∑_{i+j=s} \binom{a}{i}\binom{b}{j} = \binom{a + b}{s}  (2.6)

and

∑_{k=0}^{n} \binom{2k}{k}\binom{2n − 2k}{n − k} = 4^{n}.  (2.7)

Identity (2.6) is well–known. In order to prove (2.7), we note that

\frac{1}{2^{k}} \binom{2k}{k} = \binom{k − \frac{1}{2}}{k},

and (2.4) is equivalent to

∑_{k=0}^{n} \binom{k − \frac{1}{2}}{k}\binom{n − k − \frac{1}{2}}{n − k} = 1.  (2.8)

Consider the function (1 − x)^{− \frac{1}{2}} for |x| < 1. By squaring

(1 − x)^{− \frac{1}{2}} = 1 − \frac{\frac{−1}{2}}{1!} x + \frac{\frac{−1}{2} \frac{−3}{2}}{2!} x^{2} − \frac{\frac{−1}{2} \frac{−3}{2} \frac{−5}{2}}{3!} x^{3} + ⋯

= 1 + \binom{\frac{1}{2}}{1}x + \binom{\frac{3}{2}}{2}x^{2} + \binom{\frac{5}{2}}{3}x^{3} + ⋯,

and comparing the coefficients of x^{n} in

(1 − x)^{−1} = 1 + x + x^{2} + x^{3} + ⋯

and

[1 + \binom{\frac{1}{2}}{1}x + \binom{\frac{3}{2}}{2}x^{2} + \binom{\frac{5}{2}}{3}x^{3} + ⋯][1 + \binom{\frac{1}{2}}{1}x + \binom{\frac{3}{2}}{2}x^{2} + \binom{\frac{5}{2}}{3}x^{3} + ⋯]

we obtain (2.8).

Replacing k in k ≥ i by the non–negative integer variable t = k − i and using (2.6) and (2.7), we obtain

L = ∑_{t} ∑_{i} \frac{1}{2^{n}} \binom{2t}{t}\binom{t}{i}\binom{2n − 2s − 2t}{n − s − t}\binom{n − s − t}{s − i}

= ∑_{t} \frac{1}{2^{n}} [∑_{i} \binom{t}{i}\binom{n − s − t}{s − i}]\binom{2t}{t}\binom{2n − 2s − 2t}{n − s − t}

= ∑_{t} \frac{1}{2^{n}} \binom{n − s}{s}\binom{2t}{t}\binom{2n − 2s − 2t}{n − s − t}

= \frac{1}{2^{n}} \binom{n − s}{s} ∑_{t} \binom{2t}{t}\binom{2n − 2s − 2t}{n − s − t}

= \frac{1}{2^{n}} \binom{n − s}{s}4^{n−s} = \binom{n − s}{s}2^{n−2s} = R.

\underline{References}

1. D. Ž. Djoković, “Problem 251,” Canad. Math. Bull., 19 (1976), 249.

2. O. P. Lossers, “Solutions of Problem 251,” Canad. Math. Bull., 20 (1977), 522.

3. D. S. Mitrinović and G. V. Kalajdžić, Matrice i Determinante i Vektorski Prostori, Zbornik, Zadataka i Problema, peto izdanje, Nauc̆na knjiga, Beograd 1989, p. 121, problem 6.64 and p. 150, problem 8.51.

4. D. S. Mitrinović and R. B. Potts, Elementary Matrices, Tutorial Text No. 3, Wolters–Noordhoff Publ., Groningen 1965, p. 41, problem 2.29.

5. D. K. Fadeev and I. S. Sominskii, Problems in Higher Algebra, Freeman 1965, problem 330.

6. I. V. Proskuryakov, Problems in Linear Algebra, Mir Publ., Moscow 1978, p. 61, problem 399.

7. D. S. Mitrinović et al., Zbornik Matematic̆kih Problema I, treće izmenjeno izdanje, Zavod za izdavanje udžbenika NRS, Beograd 1962, problem 142, s. 434.

8. D. S. Mitrinović et al., Specijalne Funkcije – Zbornik Zadataka i Problema, treće dopunjeno izdanje, Nauc̆na knjiga, Beograd, 1986, problem 2.2.27, s. 18.

Ice B. Risteski 2 Milepost Place #606 Toronto M4H 1C7, Canada email: iceristeski@hotmail.com

Kostadin G. Trencevski St. Cyril and Methodius University Institute of Mathematics P.O. Box 162, 1000 Skopje, Macedonia email: kostatre@iunona.pmf.ukim.edu.mk