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?

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 2×2 sum matrices only in bases divisible by 3 with only 1 primitive 2×2 sum matrix, and that there are 3×3 sum matrices only in bases divisible by 7 with only 6 primitive 3×3 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 bⁿ.

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

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.

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×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 Z_ab into a product of elements from Z_a and Z_b.

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 (d₁, d₂, ... d_n), then s(n,b) is the product of the GCD(d_i,b).

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