Skip to main content
4 of 6
added 157 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: If $n=1$ then $\det M=1$; else $\det(M)=-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.

POSTSCRIPT.

If $B$ is the matrix whose $(i,j)$ entry is $B_{ij} = q^{\#(S_i\cap S_j)}$ then does this hold? $$\det(B)=q^n(q-1)^{n(2^{n-1}-1)}.$$

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