I took in the October issue of the American Mathematical Monthly to entertain me during the lulls while manning the mathematics desk at our open day on Saturday. As traditional, the first article was the questions in this year’s Putnam. Question A2 asked for the determinant of the adjacency matrix of the graph on the non-empty subsets of in which two subsets are connected if and only if they intersect.
Three hours later, hardly overwhelmed by student visits, although I did get to wheel out infinitely many primes and to the evident interest of several potential students — and their parents, I had at most the outline of a fiddly solution that piled row operations on half-remembered determinantal identities.
Here is the far simpler solution I found when it came to write it up. The real purpose of this post is to make the connection with the Schur algebra and permutation representations of the symmetric group, and to record some related matrices that also have surprisingly simple determinants or spectral behaviour. I also include an explicit formula for the inverse of the adjacency matrix; this can be expressed using the Möbius function of the poset of subsets of , for reasons I do not yet fully understand.
A2. Let be the nonempty subsets of in some order and let be the matrix whose entry is
Calculate the determinant of .
Solution. As is implicit in the question, we can order the sets as we like, since swapping two rows and then swapping the two corresponding columns does not change the determinant of . We put the sets not having first, then the sets having . With this order, continued recursively, the matrix for -subsets has the block form
where is the matrix with first column all zero and then to its right, and is the all-ones matrix. For example,
where the exceptional zero column in and zero row in are shown in bold.
Clearly . We shall show, by induction on , that if . The matrix can be seen as a submatrix of above; computing the determinant as a sum over the permutations of gives , as required.
For the inductive step, observe that row of has zeros (from the top row of ) followed by ones (from the top row of ). By row operations subtracting this row from each of the rows below, we obtain
The unique non-zero entry in row and column is the one in position . Therefore deleting this row and column, we find that
Given the zero matrix in the bottom right, it is impossible to obtain a non-zero contribution in the determinant by any permutation that picks an entry in the top-left copy of . Therefore
The inverse matrix can be computed explicitly: labelling rows and columns by subsets of we have
where is the complement of in . Can the appearance of the Möbius function of the poset of subsets of be explained as an instance of Mobius inversion?
Let be the set of all subsets of and let be an infinite field. The vector space with basis is a permutation module for the symmetric group on . The Putnam matrix, extended by an extra zero row and column corresponding to the empty set, is the endomorphism of this permutation module that sends a subset to the sum of all the subsets that it intersects. This interpretation of the Putnam matrix suggests a rich family of variations on the theme.
Variations on the Putnam matrix
Fix . Let be the set of -subsets of and let be the block of corresponding to -subsets of . Thus is the endomorphism of the permutation module sending a -subset to all the sum of all the -subsets that it intersects. The permutation module has a multiplicity-free direct sum decomposition
where has irreducible character canonically labelled by the partition . It therefore follows from Schur’s Lemma that has integer eigenvalues whose multiplicities are the dimensions of the . Varying and , these numbers form a triangle whose diagonal entries are the Catalan Numbers.
For example, by working with the filtration of by the Specht modules , and one can show that the eigenvalues are , and with multiplicities , and , respectively. Computational data suggests that in general the eigenvalue associated to the partition for is ; probably this can be proved by a generalization of the filtration argument. (But maybe there is a better approach just using character theory.) Since the unique trivial submodule is spanned by the sum of all -subsets, the eigenvalue for the partition is simply the number of -subsets meeting , namely .
Weighting additions and removals by indeterminates
Let be the generalization of the Putnam matrix where the entry remains zero for disjoint subsets, and if meets then the entry is . For example, is shown below, with rows and columns labelled , , , , , ,
Specializing and to we get the Putnam matrix for shown above. Since swapping and corresponds to transposing the matrix, the determinant is a function of and . Each summand in the determinant corresponds to a product of cycles in the Putnam graph; each has the same power of as , and so the determinant depends only on . The determinants of for small are shown below
For , the exponents of the factors of the determinant are and there is a further factor of
Weighting by integers
Given , let be the generalization of the Putnam matrix where the entry remains zero for disjoint subsets, and if meets then the entry is . When and for , the determinants for are , , , , , , and then for ,
which suggests something interesting is going on. Now suppose that for each , so now . For instance the matrix for is
where denotes and denotes . The determinants for are
The sequence of exponents is in OEIS A05887, as the number of labelled acyclic digraphs with vertices containing exactly points of in-degree zero. The determinant itself enumerates unions of directed cycles, with sign and a weighting, in the complete graph on vertices; does this give the connection, or is it a new interpretation of sequence A05887?
Let me finish by making the connection with an apparently completely unrelated object. Consider representations of the general linear group in which the entries of the representing matrices are polynomials of a fixed degree in the four entries of each matrix. For example, let be the natural representation of . Then itself is a polynomial representation of degree , and its symmetric square with basis is a polynomial representation of degree , in which
By definition, is a quotient of . More generally, any polynomial representation of degree is a subquotient of a direct sum of copies of . Observe that there is a linear isomorphism defined by
The action of on induces the place permutation action on , defined (using right actions) by
For example, the -cycle sends to , moving each factor one to the right (with wrap around). This gives some motivation for introducing the Schur algebra , defined to be the algebra of linear endomorphisms of the polynomial representation of that commute with the place permutation action of . In symbols,
Somewhat remarkably one can show that the category of polynomial representations of of degree is equivalent to the module category of the Schur algebra. (See for instance the introduction to Green’s lecture notes.) The extended Putnam matrix corresponds to the element of the Schur algebra sending the pure tensor to the sum of all the pure tensors such that for at least one . For example, if then
We see that is -dimensional, and, since the image of has equal coefficients in the required positions, it lies in as expected. For another example,
corresponds to the endomorphism of sending a subset of to the sum of all its subsets, weighted by a power of recording how many elements were removed. This case is unusual in that the Schur algebra element comes from a single matrix in , rather than a linear combination of matrices lying in the group algebra , as would be required for the Putnam matrix. Passing to the Schur algebra replaces the infinite dimensional algebra with a finite dimensional quotient.