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
as claimed.
Inverse
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?
Symmetric group
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
Diagonal blocks
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?
Schur algebra
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.