Skip to main content
2 of 6
deleted 48 characters in body
T. Amdeberhan
  • 43.2k
  • 5
  • 57
  • 217

A Putnam problem with a twist

This question is motivated by one of the problem set from this year's Putnam Examination. 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$, is this true? $$\det(A)=-\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