Skip to main content
1 of 6
T. Amdeberhan
  • 43.2k
  • 5
  • 57
  • 217

A Putnam problem with a twist

This question is motivated by one of the problems from this year's Putnam Exam set. That is,

Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some order, and let $M$ be the $(2^n-1) \times (2^n-1)$ matrix whose $(i,j)$ entry is $$M_{ij} = \begin{cases} 0 & \mbox{if }S_i \cap S_j = \emptyset; \\ 1 & \mbox{otherwise.} \end{cases}.$$ Calculate the determinant of $M$. Answer: $-1$.

I like to consider the following variant which got me puzzled.

Question. Preserve the notation from above, let $A$ be the matrix whose $(i,j)$ entry is $$A_{ij} = \begin{cases} 1 & \# (S_i \cap S_j) =1; \\ 0 & \mbox{otherwise.} \end{cases}.$$ If $n>1$, depending (?) on the ordering of the subsets, is this true? $$\det(A)=\pm\prod_{k=1}^nk^{\binom{n}k}.$$

Remark. Amusingly, the same number counts "product of sizes of all the nonempty subsets of $[n]$" according to OEIS.

T. Amdeberhan
  • 43.2k
  • 5
  • 57
  • 217