Uniform Squares

An NxN array of numbers is said to be "uniform" if the numbers are arranged such that the sum of any N numbers, no two from the same row or column, is always the same.  A standard uniform square is a uniform square consisting of the integers 0 to N² − 1.

The most obvious example of a standard uniform square of size NxN is a simple monotonic arrangement of the numbers 0 to N² − 1 listed in order from left to right and top to bottom.  This arrangement is clearly uniform because the value in the ith row and jth column is Ni + j, and each row and column index (0, 1,.., N−1) occurs exactly once among all the N selected locations.  Thus the sum of the N numbers is

Obviously every sub-square and every co-factor of a uniform square is uniform.  Also, uniformity is preserved under rotations and reflections of the square, and under any permutations of rows and columns. 

This raises the question of whether every standard uniform square of a given order can be transformed into the simple monotonic array by rotations, reflections, and row/column permutations. The answer is no. If N is composite we can easily construct uniform squares that cannot be transformed into the simple monotonic square. For example, with N=4 we have the following three distinct standard uniform squares

The first one is the simple 4x4 monotonic square.  The other two are both, in a sense, 2x2 monotonic arrays of 2x2 monotonic squares. They are distinct because of the "polarity" of the sub-squares.  Any monotonic array has two polarities, related by flipping them over in the plane, so that one lists the numbers left-to-right first and then top-to-bottom, whereas the other lists the numbers top-to-bottom first and then left-to-right.  The middle and right-hand arrays above differ because in one case the 2nd level polarity is the same as the 1st level, while in the other case the 1st and 2nd level have opposite polarities.

The case N=6 is more interesting. In addition to the simple 6x6 monotonic square we have 3x3 arrays of 2x2 squares, and 2x2 arrays of 3x3 squares, and in each case the 2nd-level polarity can be the same as or opposite to the 1st level polarity. Thus we have five fundamentally distinct uniform squares of order 6.

In general, I suspect that if N is a prime then there is only one standard uniform NxN square up to rotations, reflections, and row/column swaps. If N is composite, then I think each distinct ordered factorization of N into k factors represents 2^k−1 distinct uniform squares. This is because the polarity at each level can either agree or disagree with the top level polarity (but the polarity on any given level must be the same throughout the square).

To illustrate, consider the case N=8.  I think there are exactly 9 distinct standard uniform squares of sixe 8x8, corresponding to the factorizations

Thus the number of distinct 8x8 uniform squares is

One of the 4 squares corresponding to the factorization (2)(2)(2) has the 2nd level polarity reversed relative to the 1st and 3rd levels, so it looks like this

Any 8 numbers selected from this array such that no two are in the same row or column will sum to 252.

If the conjecture about prime-order squares being unique is correct, and if polarity on a given level has to be constant, then it would seem that the number of distinct standard uniform squares of size NxN depends only on the formal prime decomposition of N, without regard to the actual primes. For example, if we let u(N) denote the number of distinct standard uniform squares of size N (up to rotations, reflections, and row/col permutations), then I think

where the sum is taken over every distinct ordered factorization of N into k parts.  Thus for any primes p, q, and r we have

and so on. For example, the number of distinct 60x60 standard uniform squares is 217, because 60 is of the form p²qr.

Does the function u(N) as defined above actually give the number of distinct standard uniform NxN squares up to rotations, reflections, and row/column permutations?  Also, what is the simplest way of computing the function u(N) as defined above for arbitrary values of N = (p₁^a1)(p₂^a2)...(p_k^ak)? One possible approach would be to note that all of the NxN arrays correspond to factorizations of

When N is prime, we don't have too many factors.  If we can show that every standard uniform square corresponds to a factorization, this might lead to a good method.  At the very least it seems as if it might encode the problem in a convenient form. 

However, taking a different approach, it appears that u(N), the number of distinct standard uniform NxN arrangements (up to rotations, reflections, and row/column permutations) is

where τ(N) is the number of divisors of N. Of course if N has the prime factorization

then τ(N) is equal to the product (1+a¹)(1+a²)...(1+a^k), so if this is the correct formula for u(N) it confirms that u(N) is only dependent on the formal factorization of N. (The cyclotomic polynomial factorizations might perhaps lead to the same result.)

Equation (1) rests on the idea that a standard square is uniform if (and only if?) the elements of the square are given by an equation of the form

where x%d signifies the positive reduced value of x modulo d, and the moduli d₁, d₂, .., d_k are divisors of N. The "if" part is immediate, because the indices x and y each take on each value from 0 to N−1 exactly once, and these values are uniformly distributed among the equivalence classes modulo d if and only if N is divisible by d. Thus, any standard square whose elements are generated by an equation of the form (2) is uniform.

The "only if" part seems less easy to prove, although it would be amazing if it weren't true, i.e., if there was a uniform square of prime order that was not equivalent (up to rotations, reflections, and row/column permutations) to the simple monotonic arrangement. I've checked the case N=5 and found no exceptional uniform arrangements (and of course there are none for N = 2 or 3).  Perhaps the cyclotomic factors approach would provide a means to prove this "only if" part.

I haven't exhaustively checked the case N=6 to see if there are any exceptional uniform squares, but I've checked all the squares given by (2) with d₁=2, d₂=3, and d₃=6 and all possible combinations of coefficients in the range −6 to +6.  This reveals 46 sets of coefficients that give standard uniform squares. By symmetry between x and y (flipping the squares) this reduces to 23 sets, but the majority of those are row/column permutations. Focusing on just the monotonic solutions we find there are 7 distinct standard uniform squares of order 6, given by the formula

with the coefficients shown below.

These results indicate that it suffices to consider only a single polarity for the entire square, so we can say without loss of generality that ordering of the elements is always left-to-right first and then top-to-bottom. They also show that a square can be divided into rectangles, not just squares.

To illustrate, consider the 6x6 squares. Clearly sub-dividing the overall square with just horizontal lines doesn't produce a new square, because the monotonically ordered sequence of numbers would remain unchanged. We need to first divide the square with one or more equally-spaced vertical lines, and then for each such partition we can produce a distinct square with 0, 1, or 2 equally spaced horizontal dividing lines.  (Notice that we don't divide by 6 itself because then the square reduces again to the simple monotonic square.) The seven fundamental 6x6 standard uniform squares are illustrated schematically below.  Within each rectangle the numbers are listed monotonically, and the rectangles themselves are taken monotonically.

The number of ways of evenly dividing the square with one or more vertical lines is τ(N) − 2, and the number of ways of evenly dividing the square with 0 or more horizontal lines is τ(N) − 1.  Therefore, in addition to the simple monotonic square we have [τ(N) − 2][τ(N) − 1] distinct arrangements, which leads to equation (1) for u(N).

There are several interesting aspects of uniform squares. First, notice that in an NxN square there are N! distinct sets of N elements such that no two are in the same row or column.  This seems to be a very large number of conditions to satisfy simultaneously, but it can be shown that a necessary and sufficient condition for uniformity is that in every 2x2 sub-cell is uniform, i.e., for every

we have a+b = c+d. There are only (N−1)² such sub-squares in an NxN square, so this is a more accurate indication of the constraints. It is, however, still far more constrained than, for example, a magic square, which must satisfy only 2N+2 conditions.

It's also interesting to consider the "trace" of an array, which is defined as the sum of the diagonal elements. The trace has several nice properties, such as trace(AB) = trace(BA) and trace(AB−BA) = 0. Notice that an array is uniform if and only if its trace is invariant under all permutations of its rows and columns (and reflections).

We noted above that the "only if" part seems less easy to prove, although it would be amazing if it weren't true, i.e., if there was a uniform square of prime order that was not equivalent (up to rotations, reflections, and row/column permutations) to the simple monotonic arrangement. A rough and inelegant proof that there's essentially only one standard uniform square of any given prime order can be pieced together from a direct review of the process of constructing uniform squares. We know that uniformity is preserved under permutations of the rows and columns, so without loss of generality we can focus on squares with [0] in the upper-left corner and with strictly increasing numbers along the top row and down the left hand column.

Also, from the local property that each 2x2 sub-square

is uniform, we know that a+d = b+c, from which it follows immediately that the value in the location (i,j) is simply the sum of the value in location (i,0) and the value in location (0,j). Thus, every uniform square can be transformed into one of the form

where 0 < y₁ < y₂ < ... < y_N−1  and  0 < x₁ < x₂ < x₃ ... < x_N−1. For this to be a standard square each integer from 0 to N² − 1 must appear exactly once. This implies that either x₁ or y₁ must equal 1, so without loss of generality can assume y₁ = 1. In fact, we can assume the first k positive integers are assigned to the locations y₁, y₂, ..., y_k. If k = N−1 then the rest of the square is entirely determined, and we have the simple monotonic square.

If k is less than N−1, so the value of y_k+1 is not k+1, then we must have x₁ = k+1 because otherwise k+1 will not appear in the square at all. To illustrate, here's what we have so far if k = 3:

The numbers in brackets are implied as soon as we set x₁ = 4. The next smallest unused number is now 8. Notice that at each stage the next available number must appear in the top row or the left hand column, because otherwise it can't appear in the square at all. So we have two choices; we can place 8 in x₂ or in y₄. If we place it in x₂ the result is

and so the next smallest number is 12. We could then continue to place the sequence of next smallest numbers down the left hand column, until eventually we either reach the bottom of the square (in which case we haven't divided the square by rows) or we decide to place a number on the top row. Whenever we decide to do this the result is the same, so we can just consider the case when we immediately decide to place 8 in y₄ (instead of x₂ as we did above). The result is

Now the next smallest number is 9, but we can't place it in the left hand column because the would give us another [12] (in the column under [3]). Thus we have no choice but to place the number 9 in the top row, which gives

Now the next smallest number is 10, and by the same reasoning we must place this in the top row (because otherwise we'd have two 13's). The same applies to 11, so we are forced to

Now the next available number is 16, and we have our choice of placing it on the top or the left hand edge. The point here is that once we interrupt an arithmetic sequence on either the top or the left, that "block size" must repeat thereafter, and the only way to add more rows is to complete a block of the columns.  Similarly, the only way to add more columns (once they've been interrupted) is by completing a block of the rows. Consequently, in order to produce a complete NxN square, the periods of the rows and columns must both be divisors of N.

This implies that if N is a prime there is essentially only one standard uniform square of size NxN, and it also confirms the general formula u(N) = [τ(N) − 2][τ(N) − 1] + 1 for the number of distinct standard uniform squares of order N.

Another interesting aspect of uniformity is the fact that the local condition for uniformity (a+d = b+c) shows that a uniform square is entirely determined by just it's boundary conditions, i.e., the values along two adjacent edges, together with the stipulation of uniformity, completely determine the array.

What is the continuous analog of uniformity? In other words, if we have a continuous scalar field q(x,y) defined on the continuous variables x and y, what would it mean for this surface to be "uniform" in the sense discussed here?  For each incremental square region on the surface we have the four values

The uniformity condition implies the two conditions

so this implies that

The vanishing of this mixed partial is equivalent to the one-dimensional wave equation, written in "diagonal" coordinates.  In terms of the coordinates u = (x+y) and v = (x-y) this partial differential equation becomes

Given a "uniform" continuous scalar field Q(x,y) defined on the continuous variables x and y, it's clear that if the scalar has values along the left-hand edge given by a function f(x) and along the top edge given by g(y) then the uniform scalar field is simply the sum

where C is the value at (0,0).  In other words, f(0) = g(0) = C.

Return to MathPages Main Menu