Let r(n) be the number of n x n matrices A = (a_{ij}) such that: (1) each a_{ij} = -1, 0, or 1; and (2) if we take any n elements a_{ij}, no two in the same row or column, then their sum is the same. Find rational numbers a, b, c, d, u, v, w such that r(n) = a u^{n} + b v^{n} + c w^{n} + d.

**Solution**

Answer: r(n) = 2.3^{n} + 4^{n} - 4.2^{n} + 1.

*Moderately hard.*

The key insight is that the elements in any two rows have a fixed difference between corresponding elements. In other words, if the first row is a_{1}, a_{2}, ... , a_{n}, then the ith row is a_{1} + b, a_{2} + b, ... , a_{n} + b for some b (*). Indeed, a little thought shows that this is a necessary and sufficient condition for (2) to hold. Because if we have r ≠ s and c ≠ d, then given a sum involving a_{rc} and a_{sd}, we have another sum which is identical except that these two elements are replaced by a_{rd} and a_{sc}. Hence a_{rc} - a_{sc} = a_{rd} - a_{sd}. So as we vary d the difference a_{rd} - a_{sd} remains fixed.

We now examine the following disjoint cases: (A) all elements of the first row are the same; (B) both -1 and 1 appear somewhere in the first row; (C) 1 and 0, but not -1, appear in the first row; (D) -1 and 0, but not 1, appear in the first row.

In case (A), (*) implies that the same must be true for the other rows, and then (1) is automatically satisfied. We have 3 choices for each row, so 3^{n} possibilities in all.

In case (B), the other rows must all be identical to the first, because if the difference b in (*) is non-zero then we get an element that does not satisfy (1). In other words each column has all elements the same. So we have to find the number of possibilities for the first row. The total number of possibilities is 3^{n}. There are 2^{n} possibilities where 1 is not present, 2^{n} where -1 is not present, and 1 where neither 1 nor -1 is present. Hence the required number is 3^{n} - 2.2^{n} + 1.

In case (C), b in (*) must be 0 or -1. There are 2^{n} - 2 ways of choosing the first row so that it includes 1 or 0, but not -1. We then have 2 choices for the difference b for each of the other n-1 rows, or 2_{n-1} difference choices in all, giving a total of 2^{2n-1} - 2^{n} possibilities in total. Similarly, for case (D). So in (C) and (D) together there are 4^{n} - 2.2^{n} possibilities.

Adding up, we get 4^{n} + 2.3^{n} - 4.2^{n} + 1. As a check, this is correct for n = 1.

In a sense, everything after the first paragraph above is fairly routine (once you grasp that the small number of available values for the elements places severe restrictions on b). But *care* is needed to avoid double counting.

Notice also the typical Putnam misdirection of *rational* values.

Finally, a formula of this type should instantly suggest recurrence relations. But I did not find that a productive approach. Does anyone else have a solution of that type?

© John Scholes

jscholes@kalva.demon.co.uk

2 Oct 1999