TAOCP 5.1.4 Exercise 33

Section 5.1.4: Tableaux and Involutions

Exercise 33. [M25] (O. H. Mitchell, 1881.) True or false: $\Delta(a_1, a_2, \ldots, a_m)/\Delta(1, 2, \ldots, m)$ is an integer when $a_1, a_2, \ldots, a_m$ are integers.

Verified: yes
Solve time: 19m22s

Solution

The statement is true. For any integers (a_1, a_2, \dots, a_m), the ratio [ \frac{\Delta(a_1, a_2, \dots, a_m)}{\Delta(1, 2, \dots, m)} ] is an integer.

Proof. Recall the Vandermonde determinant [ \Delta(x_1, x_2, \dots, x_m) = \prod_{1\le i<j\le m} (x_j - x_i). ] For (x_i = i) we have [ \Delta(1, 2, \dots, m) = \prod_{1\le i<j\le m} (j-i) = \prod_{k=1}^{m-1} k!. ]

Consider the (m\times m) matrix (A) with entries (A_{ij} = a_i^{j-1}) ((i,j=1,\dots,m)). Its determinant is exactly (\Delta(a_1,\dots,a_m)). We transform (A) by using the basis of falling factorials [ x^{\underline{k}} = x(x-1)\cdots(x-k+1) \qquad (x^{\underline{0}}=1). ] Since (x^{j-1}) is a monic polynomial of degree (j-1) in (x), it can be expressed as [ x^{j-1} = x^{\underline{j-1}} + \text{integer linear combination of } x^{\underline{0}},\dots,x^{\underline{j-2}}. ] Thus there exists an upper‑triangular matrix (U) with integer entries and (1)s on the diagonal such that (A = B U), where (B) has entries (B_{ij} = a_i^{\underline{j-1}}). Consequently [ \det A = \det B. ]

Now (a_i^{\underline{j-1}} = (j-1)! \binom{a_i}{j-1}). Let (C) be the matrix with entries (C_{ij} = \binom{a_i}{j-1}) and let (D) be the diagonal matrix with (D_{jj} = (j-1)!). Then (B = C D) and [ \det B = \det C \cdot \prod_{j=1}^m (j-1)! = \det C \cdot \prod_{k=1}^{m-1} k! = \det C \cdot \Delta(1,2,\dots,m). ] Because each (\binom{a_i}{j-1}) is an integer, (C) is an integer matrix; therefore (\det C) is an integer. Combining the equalities, [ \Delta(a_1,\dots,a_m) = \det A = \det B = \det C \cdot \Delta(1,2,\dots,m), ] so the ratio equals (\det C), an integer.

If the integers (a_1,\dots,a_m) are not all distinct, (\Delta(a_1,\dots,a_m)=0) and the ratio is (0), which is also an integer.

Thus in all cases the ratio is an integer. ∎

Answer: \boxed{\text{True}}