Problem Solving Answers to Problem Set 7

10 July 2012

1. Let n ≥ 2 be an integer. What is the minimal and maximal possible rank of an n × n matrix whose n^{2} entries are precisely the numbers 1, 2, …, n^{2} ? Answer: Let the first column of A contain the numbers 1, 2, …, n in that order, let the second column contain n + 1, n + 2, …, 2n and so on. Subtracting the first row from each of the others (this will not affect the rank), we obtain the matrix with 1, 2, …, n in the first row, n, n, …, n in the second row, and jn, jn, …, jn is row j + 1. Subtracting j times the second row from row j + 2 for j = 1, 2, …, n − 2 we obtain a matrix with zeros everywhere after the first 2 rows. Hence the minimal rank is ≤ 2. There is no such matrix of rank 1. For consider the row with 1 in it. If the matrix was of rank 1, all the other rows would have to be different multiples of this one. So one would have to be multiplied by n at least. This implies that the elements of the first row must be ≤ n, ie it must contain 1, 2, …, n. But then we could not have twice this row, since this would give an additional 1. So one multiple would have to be by more than n, and so would contain an element > n^{2}. [Or, by a lemma of Erdos, there is a prime p in the range n^{2}/2 ≤ p ≤ n^{2}. But the row containing this element could not be a multiple of any other, nor could any row be a multiple of this one.] So the minimal rank is 2. To see that the maximal rank is n, let us work modulo 2. Let us put the even numbers 2, 4, …, n(n − 1) in the triangle above the diagonal; let us put the odd numbers 1, 3, …, 2n − 1 along the diagonal; and let the remaining numbers be arranged in any way in the triangle below the diagonal. Then modulo 2 we have a lower triangular matrix with 1’s along the diagonal, having determinant 1. It follows that the matrix of integers has determinant an odd integer, so non-zero.

2. Show that every rational number p/q ∈ (0, 1) with q ≥ 1 can be represented uniquely in the form

\frac{p}{q} = \frac{a_{1}}{1!} + \frac{a_{2}}{2!} + ⋯ + \frac{a_{k}}{k!} ,

with 0 ≤ a_{i} < i. Answer: Set

x = x_{0} = p/q,
a_{1} = [x_{0}],
x_{1} = x_{0} − a_{1},
a_{2} = [2x_{1}],
x_{2} = 2x_{1} − a_{2},
… a_{n} = [nx_{n−1}],
x_{n} = nx_{n−1} − a_{n},
…

Then

0 ≤ x_{n} < 1,
0 ≤ a_{n} < n,

while

x_{0} = a_{1} + x_{1}

= a_{1} + \frac{a_{2} + x_{2}}{2!}

= a_{1} + \frac{a_{2}}{2!} + \frac{a_{3} + x_{3}}{3!}

= a_{1} + \frac{a_{2}}{2!} + \frac{a_{3}}{3!} + \frac{x_{3}}{3!}

…  = a_{1} + \frac{a_{2}}{2!} + ⋯ + \frac{a_{n}}{n!} + \frac{x_{n}}{n!}.

Thus

n!x_{0} = n!a_{1} + \frac{n!}{2!}a_{2} + ⋯ + a_{n} + x_{n}
= s_{n} + x_{n},

where s_{n} ∈ ℕ, 0 ≤ x_{n} < 1. If x_{0} = p/q then n!x_{0} ∈ ℕ if q | n!, and in particular if n ≥ q. It follows that x_{n} = 0, and so

0 = a_{n+1} = a_{n+2} = ⋯,

ie the series terminates after n terms. To see that this expression is unique, suppose we have two series of this form,

x_{0} = a_{1} + \frac{a_{2}}{2!} + ⋯

= b_{1} + \frac{b_{2}}{2!} + · · · .

Suppose

a_{i} = b_{i}

for i ≤ n. Then as we have seen

n!x_{0} = n!a_{1} + \frac{n!}{2!}a_{2} + ⋯ + a_{n} + x_{n}

= n!a_{1} + \frac{n!}{2!}a_{2} + ⋯ + a_{n} + y_{n}.

It follows that

x_{n} = y_{n}

and so

a_{n+1} = [(n + 1)x_{n}] = [(n + 1)y_{n}] = b_{n+1}.