Putnam 2018: determinant of an adjacency matrix

Wildon's Weblog 2019-10-21

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. My eyes lit on A2, which asks for the determinant of the adjacency matrix of the graph on the non-empty subsets of $\{1,2,\ldots, n\}$ in which two subsets are connected if and only if they intersect.

As a supposed expert on algebraic combinatorics, I arrogantly assumed it would be a few minutes’ work. Three hours later, hardly overloaded by student visits (although I did get to wheel out $0.\dot{9} = 1$ and infinitely many primes to the evident interest of several potential students — and their parents), I had at most the outline of a solution.

Here is the slightly simpler solution I found when it came to write it up. The post ends with some some comments connecting the problem with representations of the symmetric group and 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 $\{1,2,\ldots, n\}$ , for reasons I do not yet fully understand.

A2. Let $S_1, S_2, \ldots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\ldots, n\}$ in some order and let $M$ be the $(2^n-1) \times (2^n-1)$ matrix whose $(i,j)$ entry is

$\displaystyle m_{ij} = \begin{cases} 0 & S_i \cap S_j = \varnothing \\ 1 & S_i \cap S_j \neq \varnothing \end{cases}$

Calculate the determinant of $M$ .

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 $M$ . We put the $2^{n-1} - 1$ sets not having $1$ first, then the $2^{n-1}$ sets having $1$ . With this order, continued recursively, the matrix $M_n$ for $n$ -subsets has the block form

$\left( \begin{matrix} M_{n-1} & R_{n-1} \\ R_{n-1}^t & K_{n-1} \end{matrix} \right)$

where $R_k$ is the $(2^k-1) \times 2^k$ matrix with first column all zero and then $M_{k}$ to its right, and $K_k$ is the $k \times k$ all-ones matrix. For example,

$M_3 = \left( \begin{matrix} 1 & 0 & 1 & {\bf 0} & 1 & 0 & 1 \\ 0 & 1 & 1 & {\bf 0} & 0 & 1 & 1 \\ 1 & 1 & 1 & {\bf 0} & 1 & 1 & 1 \\ {\bf 0} & {\bf 0} & {\bf 0} & 1 & 1 & 1 & 1 \\ 1& 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 &1 &1 \\ 1 & 1 & 1 & 1 & 1 &1 &1 \end{matrix} \right)$

where the exceptional zero column in $R_{2}$ and zero row in $R_{2}^t$ are shown in bold.

Clearly $\det M_1 = 1$ . We shall show, by induction on $n$ , that $\det M_n = -1$ if $n \ge 2$ . The $3 \times 3$ matrix $M_2$ can be seen as a submatrix of $M_3$ above; computing the determinant as a sum over the $6$ permutations of $\{1,2,3\}$ gives $1 - 1 -1 = -1$ , as required.

For the inductive step, we multiply $M_n$ on the left and on the right by the block matrix with $M_{n-1}^{-1}$ in its top left and $I_4$ , the $4 \times 4$ identity matrix, in its bottom right. Since $\det M_{n-1} = -1$ , this does not change the determinant. We get

$\left( \begin{matrix} M_{n-1}^{-1} & J_{n-1} \\ J_{n-1}^t & K_{n-1} \end{matrix} \right)$

where $J_k$ is the $(2^k-1) \times 2^k$ matrix with first column all zero and the $(2^k-1) \times (2^k-1)$ identity matrix to its right. Observe that row $2^{n-1}$ has $2^{n-1}-1$ zeros (from the top row of $J_{n-1}^t$ ) followed by $2^{n-1}$ ones (from the top row of $K_{n-1}$ ). By row operations subtracting this row from each of the rows below, we obtain

$\left( \begin{matrix} M_{n-1}^{-1} & 0_{(2^{n-1}-1) \times 1} & I_{n-1} \\ 0_{1 \times (2^{n-1}-1)} & 1 & 1_{1 \times (2^{n-1}-1)} \\ I_{2^{n-1}-1} & 0_{(2^{n-1}-1) \times 1)} & 0_{(2^{n-1}-1) \times (2^{n-1}-1)} \end{matrix} \right).$

The unique non-zero entry in row $2^{n-1}$ and column $2^{n-1}$ is the one in position $(2^{n-1},2^{n-1})$ . Therefore deleting this row and column, we find that

$\det M_n = \det \left( \begin{matrix} M_{n-1}^{-1} & I_{2^{n-1}-1} \\ I_{2^{n-1}-1} & 0_{(2^{n-1}-1) \times (2^{n-1}-1)} \end{matrix} \right).$

The unique permutation giving a non-zero contribution to the determinant does not involve any entry from $M_{n-1}^{-1}$ . It is the product of $2^{n-1}-1$ transpositions, and so is odd. Therefore $\det M_n = -1$ as claimed.

Representations of symmetric groups

Let $M_n^{(k)}$ denote the analogously defined matrix with rows and columns indexed by the set $\Omega^{(k)}$ of all $k$ -subsets of $\{1,2,\ldots, n\}$ . This is a subblock of $M_n$ . Observe that $M_n^{(k)}$ is the endomorphism of the $\mathbb{Q}S_n$ -permutation module $\mathbb{Q}\Omega^{(k)}$ that sends a $k$ -subset to the sum of all $k$ -subsets that it meets. This endomorphism commutes with the action of $S_n$ . Since $U$ has a multiplicity-free direct sum decomposition

$U = U_0 \oplus U_1 \oplus \cdots U_k$

where $U_i$ has irreducible character canonically labelled by the partition $(n-i,i)$ , it follows from Schur’s Lemma that $M_n^{(k)}$ has $k+1$ integer eigenvalues whose multiplicities are the dimensions $d_i$ of the $U_i$ . Moreover, the eigenvalues $\alpha_0, \alpha_1, \ldots, \alpha_k$ are a solution to the system of equations

$d_0 \alpha_0^j + d_1\alpha_1^j + \cdots + d_k\alpha_{k}^j = \mathrm{tr} (M_n^{(k)})^j$

for $j \in \mathbb{N}$ . Thinking of $M_n^{(k)}$ as the adjacency matrix of the graph on $\Omega^{(k)}$ where two $k$ -subsets are connected if and only if they intersect gives a combinatorial interpretation of these traces.

Inverse

The inverse matrix $M_n^{-1}$ can be computed explicitly: labelling rows and columns by subsets of $\{1,2,\ldots, n\}$ we have

$\displaystyle -(M_n^{-1})_{XY} = \begin{cases} (-1)^{|Y \backslash X'|} & Y \supseteq X' \\ 0 & Y \not\supseteq X' \end{cases}$

where $X'$ is the complement of $X$ in $\{1,2,\ldots, n\}$ . Is there a conceptual reason why the Möbius function $\mu(Z,Y) = (-1)^{Y \backslash Z}$ of the poset of subsets of $\{1,2,\ldots, n\}$ appears?