A PROBLEM RELATED TO FOULKES CONJECTURE

In this paper we study a class of symmetric matrices T indexed by positive integers m greater-than-or-equal-to n greater-than-or-equal-to 2 and defined as follows: for any positive integers p and q let B(p,q) be the set of partitions of U = {1, 2, 3,..., pq} into p blocks each of size q. Let m greater-than-or-equal-to n greater-than-or-equal-to 2 be positive integers. By a transversal of alpha = A1/A2/.../A(n) is-an-element-of B(n,m) we mean a partition beta = B1/B2/ ... /B(m) is-an-element-of B(m,n) such that parallel-to A(i) and B(j) parallel-to = 1 for every i = 1, 2,..., n and every j = 1, 2,..., m. Let M be the zero-one matrix with rows indexed by the elements of B(n,m) and columns indexed by the elements of B(m,n) such that M(alpha,beta) = 1 iff beta is a transversal of alpha. We are interested in finding the eigenvalues and eigenspaces of the symmetric matrix T = MM(t). The nonsingularity of T implies Foulkes's Conjecture (for these values of m and n). In the case n = 2 we completely determine the eigenvalues and eigenspaces of T and in so doing demonstrate the nonsingularity of T. For n = 3 we develop a fast algorithm for computing the eigenvalues of T, and give numerical results in the cases m = 3, 4, 5, 6.