Problem Solving Set 2

05 July 2012

1. (a) Let A be a n × n, n ≥ 2, symmetric, invertible matrix with real positive elements. Show that z_{n} ≤ n^{2} − 2n, where z_{n} is the number of zero elements in A^{−1}.

(b) How many zero elements are there in the inverse of the n × n matrix

(\begin{matrix}1 & & 1 & & 1 & & 1 & … & & 1 \\ 1 & & 2 & & 2 & & 2 & … & & 2 \\ 1 & & 2 & & 1 & & 1 & … & & 1 \\ 1 & & 2 & & 1 & & 2 & … & & 2 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 1 & & 2 & & 1 & & 2 & … & & … \end{matrix})?

Answer:

(a) I think the problem is put in a somewhat confusing way. In effect, you have to show that A^{−1} has at least 2n non-zero elements. Let the rows of A be represented by vectors a_{1}, …, a_{n}; and let the columns of B = A^{−1} be represented by vectors b_{1}, …, b_{n}. Then the scalar products

a_{i}.b_{j} = \begin{cases}1 & if i = j, \\ 0 & otherwise. \end{cases}

Evidently each b_{j} is non-empty, ie it contains at least one non-zero entry. Suppose b_{j} only contains one nonzero entry. Since all the elements of A are non-zero, it follows that

a_{i}.b_{j} ≠ 0

for all i, contrary to the definition of B = A^{−1}. So each b_{j} contains at least 2 non-zero elements, giving at least 2n non-zero elements in A^{−1}.

(b) I overheard one of the students saying that each row differed in only one place from the rows 2 places away, and I realized that this gave the answer. (Here we are counting the rows modulo n, ie the 2nd row is considered to be 2 rows away from the bottom row.) I doubt if I would have been able to solve the problem if I had not heard this! More precisely a_{i−1}−a_{i+1} has a single non-zero element, in position i. Now suppose j ≠ i ± 1. Then

a_{i±1}.b_{j} = 0.

If follows that the ith element in b_{j} is zero:

b_{ij} = 0.

Thus all the elements in b_{j} are zero, except those in positions i = j ± 1. So there are just 2 non-zero elements in b_{j}, and 2n non-zero elements in B = A^{−1}. Nb I think there must be an easier way of expressing this …. Also we assume from the statement of the problem that A is non-singular; presumably we are not meant to prove this. (I think this is not difficult, by subtracting row n − 2 from row n, then row n − 3 from row n − 1, and so on.)

2. Let a_{1}, a_{2}, ..., a_{n} be distinct integers. Show that

f(x) = (x − a_{1})(x − a_{2})...(x − a_{n}) − 1

is irreducible over the rationals.

Answer: Firstly, if a monic polynomial (leading coefficient 1) with integer coefficients factors over the rationals then it factors over the integers. This is sometimes called Gauss’s Lemma, and comes relatively often into competition problems. The basic fact is that

f(x) = 1

for x = a_{1}, …, a_{n}. The trick is to note that if

f(x) = g(x)h(x),

where g, h are polynomials with integer coefficients then

g(a_{i})h(a_{i}) = 1

for i = 1, …, n. But since g(a_{i}), h(a_{i}) are integers, this implies that

g(a_{i}) = h(a_{i}) = ±1

for each i. This almost solves the problem. Since a_{1}, …, a_{n} are all roots of

u(x) = g(x) − h(x)

(and deg(g − h) < n since we are assuming that g and h are not constants) it follows that

u(x) ≡ 0,

ie

g(x) = h(x).

Thus

f(x) = g(x)^{2},

which is impossible since the constant term in f(x) is negative.