Let r(n) be the number of n x n matrices A = (aij) such that: (1) each aij = -1, 0, or 1; and (2) if we take any n elements aij, 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 un + b vn + c wn + d.
Solution
Answer: r(n) = 2.3n + 4n - 4.2n + 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 a1, a2, ... , an, then the ith row is a1 + b, a2 + b, ... , an + 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 arc and asd, we have another sum which is identical except that these two elements are replaced by ard and asc. Hence arc - asc = ard - asd. So as we vary d the difference ard - asd 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 3n 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 3n. There are 2n possibilities where 1 is not present, 2n where -1 is not present, and 1 where neither 1 nor -1 is present. Hence the required number is 3n - 2.2n + 1.
In case (C), b in (*) must be 0 or -1. There are 2n - 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 2n-1 difference choices in all, giving a total of 22n-1 - 2n possibilities in total. Similarly, for case (D). So in (C) and (D) together there are 4n - 2.2n possibilities.
Adding up, we get 4n + 2.3n - 4.2n + 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