Problem of the Month (February 2002)

This month we explore sum matrices, n x n matrices with the property that every entry is the sum of the adjacent horizontal and vertical entries mod b. For example, the only 4x4 matrices (up to reflection and rotation) which are sum matrices mod 2 are:

For other values of n and b, how many sum matrices are there? What do they look like? For other values of n and b, how many sum matrices are there? What do they look like? We say a sum matrix is primitive if it does not have any rows or columns of all 0's, and the GCD of all the entries is 1. How many primitive sum matrices are there?


ANSWERS

Berend Jan van der Zwaag found the primitive 2x2 and 5x5 sum matrices in base 2.

Jeremy Galvagni found some small sum matrices, including the n=4 and n=5 ones in any base.

Joseph DeVincentis proved using algebra that there are 2x2 sum matrices only in bases divisible by 3 with only 1 primitive 2x2 sum matrix, and that there are 3x3 sum matrices only in bases divisible by 7 with only 6 primitive 3x3 matrices. Claudio Baiocchi used a computer to prove the above.

Ludek Frey, Boris Bukh, and Olexandr Ravsky showed that the maximum number of solutions for a fixed n and b is no more than bn.

Berend Jan van der Zwaag was able to count the number of sum matrices for various n and b:

Number of n x n Sum Matrices in Base b

n \ b23456789101112131415
212112112112112
311111711111171
456171536286245956613591182120
537662310154021231712836100
61111111111132211
711111411111111
81251125117011
94346289325
1011111
1121
121
131
145
151
1643

Number of Primitive n x n Sum Matrices in Base b

n \ b23456789101112131415
201000000000000
300000600000000
4451214262745397665879015099
513231167271122540212178
60000000000032100
7000000000000
8023000004200
93305230246
1000000
1110
120
130
140
150

Claudio Baiocchi, Helmut Postl, and Olexandr Ravsky noticed that the set of solutions for a fixed n and b form a vector space. Any potential solution is completely determined by its left column, and those which give solutions are those in which the (n+1)st column vanishes. For each trivial unit vector which form a basis for the first column, find the corresponding (n+1)st column, and try to find some linear combination of these that vanishes.

If we form a matrix A(n) from these vectors, we can find non-trivial solutions when the determinant of A(n) equals zero. This happens when n = 4, 5, 9, 11, 14, 17, 19, 23, 24, 29, 34, 35, 39, 41, 44, 47, 49, 53, 54, 59, 64, 65, 69, 71, 74, 77, 79, 83, 84, 89, 94, 95, 99, . . . . Somewhat surprisingly, the nullspace of these matrices all have dimension 2.

When the determinant is non-zero, it tells us something about which b will have solutions. The determinants are shown in the table below. Those for n ≤ 11 were furnished by Claudio Baiocchi, and I extended the table.

Determinant of Matrix A(n)

n234567891011121314151617
Det A(n)-3-700133-7 173-36 172 190235 430-36 56 533 79-36 133 296 25107 173 318 1272 223-216 675 1012 1032 4090

n18192021122324
Det A(n)-3711 1134 1912 64703 78 133 417 438 832 379235 439 896 1312 2632 1451-4710 1374 1394 2772 9192 174700

Helmut Postl defined a sum matrix to be basic if it is a sum matrix in any base. He investigated up to n=100 and found n=4 and n=5 have basic matrices, and that all larger basic matrices seem to be extensions of these. This is confirmed by the fact that the values of n for which the determinant of A(n)=0 are those of the form n=5k-1 or n=6k-1.

1  0  0  1     1  1  0 -1 -1
1 -1 -1  1     0  0  0  0  0
1 -1 -1  1    -1 -1  0  1  1
1  0  0  1     0  0  0  0  0
               1  1  0 -1 -1

Helmut Postl also sent me the first rows of all linearly independent n x n sum matrices in base b for n ≤ 20 and b ≤ 100, and which sum matrices exist for n ≤ 100 and b ≤ 100.

Let s(n,b) be the number of n x n sum matrices in base b. Then Olexandr Ravsky and Boris Bukh showed that s(n,b) is a multiplicative function of b: if a and b are relatively prime, then s(n, ab) = s(n, a) s(n, b). The proof is a consequence of the unique factorization of elements in Zab into a product of elements from Za and Zb.

Olexandr Ravsky went on to find a formula for s(n,b) in terms of the Smith Form of a matrix. Consider the transformations of a matrix of adding to a row (or column) some multiple of another row (or column) or switching two rows (or columns). Using these transformations, we can reduce any matrix to a diagonal matrix where each diagonal element divides the next. This is the Smith Form of the matrix. If we denote the diagonal elements of the Smith Form of A(n) as (d1, d2, ... dn), then s(n,b) is the product of the GCD(di,b).

Boris Bukh showed that if b is prime, then s(n,b) is a power of b and (b-1) bk-1 divides s(n,bk) - s(n,bk-1) His proof: Consider all sum matrices modulo bk such that not all elements are divisible by b. There are s(n,bk) - s(n,bk-1) such sum matrices. Denote their set as M. Now we consider a family of maps over M, ft : a -> at where GCD(t,b)=1. Obviously ft is a bijection. Call two sum matrices in M equivalent if there is a mapping ft that maps one onto another. It is easy to check this is an equivalence relation on M. In each equivalence class there are phi(bk) = (b-1) bk-1 elements. Therefore, the cardinality of M is divisible by (b-1) bk-1. As a corollary, he shows that in this case, (b-1) divides s(n,bk)-1.

Sasha Ravsky proved some things about the binary case. His results can be found here.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 1/5/03.