Skip to main content
Removing spurious whitespace while this is on the front page
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

$\newcommand{\QQ}{\mathbb{Q}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]} \newcommand{\suml}{\sum\limits} \newcommand{\sumS}{\suml_{S \in P}} \newcommand{\prodl}{\prod\limits} \newcommand{\prodS}{\prodl_{S \in P}} \newcommand{\subs}{\subseteq} \newcommand{\sups}{\supseteq}$

HereHere are proofs for both the original question (Theorem 1 below) and for the postscript (Theorem 5 below) that follow my argument at https://artofproblemsolving.com/community/u432h1747709p11384734 as closely as possible. Sorry for their length, much of it due to exposition of matrix folklore. (If you know this, scroll all the way down to section 2.)

$\newcommand{\QQ}{\mathbb{Q}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]} \newcommand{\suml}{\sum\limits} \newcommand{\sumS}{\suml_{S \in P}} \newcommand{\prodl}{\prod\limits} \newcommand{\prodS}{\prodl_{S \in P}} \newcommand{\subs}{\subseteq} \newcommand{\sups}{\supseteq}$

Here are proofs for both the original question (Theorem 1 below) and for the postscript (Theorem 5 below) that follow my argument at https://artofproblemsolving.com/community/u432h1747709p11384734 as closely as possible. Sorry for their length, much of it due to exposition of matrix folklore. (If you know this, scroll all the way down to section 2.)

$\newcommand{\QQ}{\mathbb{Q}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]} \newcommand{\suml}{\sum\limits} \newcommand{\sumS}{\suml_{S \in P}} \newcommand{\prodl}{\prod\limits} \newcommand{\prodS}{\prodl_{S \in P}} \newcommand{\subs}{\subseteq} \newcommand{\sups}{\supseteq}$Here are proofs for both the original question (Theorem 1 below) and for the postscript (Theorem 5 below) that follow my argument at https://artofproblemsolving.com/community/u432h1747709p11384734 as closely as possible. Sorry for their length, much of it due to exposition of matrix folklore. (If you know this, scroll all the way down to section 2.)

correction and simplification
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

Every subset $U$ of $N$ that satisfies $U \sups S$ and $U \sups T$ is automatically nonempty (since $U$ contains the nonempty set $S$ as a subset), and thus belongs to $P$. Hence, the $U \in P$ that satisfy $U \sups S$ and $U \sups T$ are precisely the subsets $U$ of $N$ that satisfy $U \sups S$ and $U \sups T$. Thus, we have \begin{align*} & \set{ U \in P \mid U \sups S \text{ and } U \sups T } \\ = & \set{ U \subs N \mid U \sups S \text{ and } U \sups T } \\ = & \set{ U \subs N \mid U \sups \underbrace{S \cap T}_{=G} } \\ = & \set{ U \subs N \mid U \sups G } \\ = & \set{ U \subs N \mid N \setminus U \subs N \setminus G } \end{align*}\begin{align*} &\ \set{ U \in P \mid U \sups S \text{ and } U \sups T } \\ = &\ \set{ U \subs N \mid U \sups S \text{ and } U \sups T } \\ = &\ \set{ U \subs N \mid U \sups \underbrace{S \cup T}_{=G} } \\ = &\ \set{ U \subs N \mid U \sups G } \\ = &\ \set{ U \subs N \mid N \setminus U \subs N \setminus G } \end{align*} (because the condition "$U \sups G$" on a subset $U$ of $N$ is equivalent to the condition "$N \setminus U \subs N \setminus G$"). Hence, the summation sign "$\suml_{\substack{U \in P; \\ U \sups S \text{ and } U \sups T}}$" in \eqref{darij1.pf.l6.1} can be rewritten as "$\suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}}$". Thus, \eqref{darij1.pf.l6.1} rewrites as \begin{align} & \suml_{U \in P} \tup{q-1}^{n-\abs{U}} q^{\abs{S}-n} \ive{ U \sups S } q^{\abs{T}} \ive{ U \sups T } \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}} \tup{q-1}^{n-\abs{U}} . \label{darij1.pf.l6.2} \tag{3} \end{align} Every subset $U$ of $N$ satisfies $n - \abs{U} = \abs{N \setminus U}$ (since $U \subs N$ yields $\abs{N \setminus U} = \underbrace{\abs{N}}_{=n} - \abs{U} = n - \abs{U}$). Thus, \eqref{darij1.pf.l6.2} becomes \begin{align} & \suml_{U \in P} \tup{q-1}^{n-\abs{U}} q^{\abs{S}-n} \ive{ U \sups S } q^{\abs{T}} \ive{ U \sups T } \\ &= q^{\abs{S}-n} q^{\abs{T}} \underbrace{\suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}}}_{\substack{= \suml_{\substack{U \subs N; \\ N \setminus U \subs H}} \\ \tup{ \text{since } N \setminus G = H } }} \underbrace{\tup{q-1}^{n-\abs{U}}}_{\substack{= \tup{q-1}^{\abs{N \setminus U}} \\ \tup{ \text{since } n - \abs{U} = \abs{N \setminus U} } }} \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ N \setminus U \subs H}} \tup{q-1}^{\abs{N \setminus U}} \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ U \subs H}} \tup{q-1}^{\abs{U}} \label{darij1.pf.l6.3} \tag{4} \end{align} (here, we have substituted $U$ for $N \setminus U$ in the sum, since the map \begin{align} \set{U \subs N} \to \set{U \subs N}, \qquad U \mapsto N \setminus U \end{align} is a bijection).

Recall that $\abs{P} = 2^n - 1$ (as we proved during our proof of Lemma 4 (b)). Also, $\sumS \abs{S} = n 2^{n-1}$ (by Lemma 4 (a)). Thus, \begin{align} \sumS \tup{n - \abs{S}} &= \underbrace{\sumS n}_{= \abs{P} \cdot n} - \underbrace{\sumS \abs{S}}_{= n 2^{n-1}} \\ &= \underbrace{\abs{P}}_{= 2^n - 1} \cdot n - n 2^{n-1} = \tup{2^n - 1} \cdot n - n 2^{n-1} \\ &= n \tup{2^n - 1 - 2^{n-1}} = n \tup{2^{n-1} - 1} \end{align} (since $\underbrace{2^n}_{= 2 \cdot 2^{n-1}} - 1 - 2^{n-1} = 2 \cdot 2^{n-1} - 1 - 2^{n-1} = 2^{n-1} - 1$).

Endow our set $P$ with the same total ordering that we used in the proof of Theorem 1. Now, it is easy to see that the $P \times P$-matrix $E$ is upper-triangular. Since the determinant of an upper-triangular $P \times P$-matrix equals the product of its diagonal entries, we thus conclude that \begin{align} \det E &= \prodS \tup{ \underbrace{\tup{q-1}^{n-\abs{S}} q^{\abs{S}-n}}_{= \tup{\dfrac{q-1}{q}}^n \tup{\dfrac{q}{q-1}}^{\abs{S}} } \underbrace{\ive{ S \sups S }}_{= 1} } = \prodS \tup{ \tup{\dfrac{q-1}{q}}^n \tup{\dfrac{q}{q-1}}^{\abs{S}} } \\ &= \underbrace{ \tup{ \prodS \tup{\dfrac{q-1}{q}}^n } }_{= \tup{\tup{\dfrac{q-1}{q}}^n}^{\abs{P}} } \underbrace{ \tup{ \prodS \tup{\dfrac{q}{q-1}}^{\abs{S}} } }_{= \tup{\dfrac{q}{q-1}}^{\sumS \abs{S}} } \\ &= \tup{\tup{\dfrac{q-1}{q}}^n}^{\abs{P}} \tup{\dfrac{q}{q-1}}^{\sumS \abs{S}} \\ &= \underbrace{ \tup{\tup{\dfrac{q-1}{q}}^n}^{2^n - 1} }_{= \tup{\dfrac{q-1}{q}}^{n \tup{2^n - 1}} } \underbrace{ \tup{\dfrac{q}{q-1}}^{n 2^{n-1}} }_{= \tup{\dfrac{q-1}{q}}^{-n 2^{n-1}}}\\ & \qquad \tup{ \text{since } \abs{P} = 2^n - 1 \text{ and } \sumS \abs{S} = n 2^{n-1} } \\ &= \tup{\dfrac{q-1}{q}}^{n \tup{2^n - 1}} \tup{\dfrac{q-1}{q}}^{-n 2^{n-1}} \\ &= \tup{\dfrac{q-1}{q}}^{n \tup{2^n - 1} - n 2^{n-1}} = \tup{\dfrac{q-1}{q}}^{n 2^{n-1} - n} \end{align}\begin{align} \det E &= \prodS \tup{ \underbrace{\tup{q-1}^{n-\abs{S}} q^{\abs{S}-n}}_{= \tup{\dfrac{q-1}{q}}^{n-\abs{S}} } \underbrace{\ive{ S \sups S }}_{= 1} } \\ &= \prodS \tup{\dfrac{q-1}{q}}^{n-\abs{S}} = \tup{\dfrac{q-1}{q}}^{\sumS \tup{n - \abs{S}}} = \tup{\dfrac{q-1}{q}}^{n 2^{n-1} - n} \end{align} (since $n \tup{2^n - 1} - n 2^{n-1} = n 2^{n-1} - n$$\sumS \tup{n - \abs{S}} = n \tup{2^{n-1} - 1} = n 2^{n-1} - n$).

Every subset $U$ of $N$ that satisfies $U \sups S$ and $U \sups T$ is automatically nonempty (since $U$ contains the nonempty set $S$ as a subset), and thus belongs to $P$. Hence, the $U \in P$ that satisfy $U \sups S$ and $U \sups T$ are precisely the subsets $U$ of $N$ that satisfy $U \sups S$ and $U \sups T$. Thus, we have \begin{align*} & \set{ U \in P \mid U \sups S \text{ and } U \sups T } \\ = & \set{ U \subs N \mid U \sups S \text{ and } U \sups T } \\ = & \set{ U \subs N \mid U \sups \underbrace{S \cap T}_{=G} } \\ = & \set{ U \subs N \mid U \sups G } \\ = & \set{ U \subs N \mid N \setminus U \subs N \setminus G } \end{align*} (because the condition "$U \sups G$" on a subset $U$ of $N$ is equivalent to the condition "$N \setminus U \subs N \setminus G$"). Hence, the summation sign "$\suml_{\substack{U \in P; \\ U \sups S \text{ and } U \sups T}}$" in \eqref{darij1.pf.l6.1} can be rewritten as "$\suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}}$". Thus, \eqref{darij1.pf.l6.1} rewrites as \begin{align} & \suml_{U \in P} \tup{q-1}^{n-\abs{U}} q^{\abs{S}-n} \ive{ U \sups S } q^{\abs{T}} \ive{ U \sups T } \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}} \tup{q-1}^{n-\abs{U}} . \label{darij1.pf.l6.2} \tag{3} \end{align} Every subset $U$ of $N$ satisfies $n - \abs{U} = \abs{N \setminus U}$ (since $U \subs N$ yields $\abs{N \setminus U} = \underbrace{\abs{N}}_{=n} - \abs{U} = n - \abs{U}$). Thus, \eqref{darij1.pf.l6.2} becomes \begin{align} & \suml_{U \in P} \tup{q-1}^{n-\abs{U}} q^{\abs{S}-n} \ive{ U \sups S } q^{\abs{T}} \ive{ U \sups T } \\ &= q^{\abs{S}-n} q^{\abs{T}} \underbrace{\suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}}}_{\substack{= \suml_{\substack{U \subs N; \\ N \setminus U \subs H}} \\ \tup{ \text{since } N \setminus G = H } }} \underbrace{\tup{q-1}^{n-\abs{U}}}_{\substack{= \tup{q-1}^{\abs{N \setminus U}} \\ \tup{ \text{since } n - \abs{U} = \abs{N \setminus U} } }} \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ N \setminus U \subs H}} \tup{q-1}^{\abs{N \setminus U}} \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ U \subs H}} \tup{q-1}^{\abs{U}} \label{darij1.pf.l6.3} \tag{4} \end{align} (here, we have substituted $U$ for $N \setminus U$ in the sum, since the map \begin{align} \set{U \subs N} \to \set{U \subs N}, \qquad U \mapsto N \setminus U \end{align} is a bijection).

Recall that $\abs{P} = 2^n - 1$ (as we proved during our proof of Lemma 4 (b)). Also, $\sumS \abs{S} = n 2^{n-1}$ (by Lemma 4 (a)).

Endow our set $P$ with the same total ordering that we used in the proof of Theorem 1. Now, it is easy to see that the $P \times P$-matrix $E$ is upper-triangular. Since the determinant of an upper-triangular $P \times P$-matrix equals the product of its diagonal entries, we thus conclude that \begin{align} \det E &= \prodS \tup{ \underbrace{\tup{q-1}^{n-\abs{S}} q^{\abs{S}-n}}_{= \tup{\dfrac{q-1}{q}}^n \tup{\dfrac{q}{q-1}}^{\abs{S}} } \underbrace{\ive{ S \sups S }}_{= 1} } = \prodS \tup{ \tup{\dfrac{q-1}{q}}^n \tup{\dfrac{q}{q-1}}^{\abs{S}} } \\ &= \underbrace{ \tup{ \prodS \tup{\dfrac{q-1}{q}}^n } }_{= \tup{\tup{\dfrac{q-1}{q}}^n}^{\abs{P}} } \underbrace{ \tup{ \prodS \tup{\dfrac{q}{q-1}}^{\abs{S}} } }_{= \tup{\dfrac{q}{q-1}}^{\sumS \abs{S}} } \\ &= \tup{\tup{\dfrac{q-1}{q}}^n}^{\abs{P}} \tup{\dfrac{q}{q-1}}^{\sumS \abs{S}} \\ &= \underbrace{ \tup{\tup{\dfrac{q-1}{q}}^n}^{2^n - 1} }_{= \tup{\dfrac{q-1}{q}}^{n \tup{2^n - 1}} } \underbrace{ \tup{\dfrac{q}{q-1}}^{n 2^{n-1}} }_{= \tup{\dfrac{q-1}{q}}^{-n 2^{n-1}}}\\ & \qquad \tup{ \text{since } \abs{P} = 2^n - 1 \text{ and } \sumS \abs{S} = n 2^{n-1} } \\ &= \tup{\dfrac{q-1}{q}}^{n \tup{2^n - 1}} \tup{\dfrac{q-1}{q}}^{-n 2^{n-1}} \\ &= \tup{\dfrac{q-1}{q}}^{n \tup{2^n - 1} - n 2^{n-1}} = \tup{\dfrac{q-1}{q}}^{n 2^{n-1} - n} \end{align} (since $n \tup{2^n - 1} - n 2^{n-1} = n 2^{n-1} - n$).

Every subset $U$ of $N$ that satisfies $U \sups S$ and $U \sups T$ is automatically nonempty (since $U$ contains the nonempty set $S$ as a subset), and thus belongs to $P$. Hence, the $U \in P$ that satisfy $U \sups S$ and $U \sups T$ are precisely the subsets $U$ of $N$ that satisfy $U \sups S$ and $U \sups T$. Thus, we have \begin{align*} &\ \set{ U \in P \mid U \sups S \text{ and } U \sups T } \\ = &\ \set{ U \subs N \mid U \sups S \text{ and } U \sups T } \\ = &\ \set{ U \subs N \mid U \sups \underbrace{S \cup T}_{=G} } \\ = &\ \set{ U \subs N \mid U \sups G } \\ = &\ \set{ U \subs N \mid N \setminus U \subs N \setminus G } \end{align*} (because the condition "$U \sups G$" on a subset $U$ of $N$ is equivalent to the condition "$N \setminus U \subs N \setminus G$"). Hence, the summation sign "$\suml_{\substack{U \in P; \\ U \sups S \text{ and } U \sups T}}$" in \eqref{darij1.pf.l6.1} can be rewritten as "$\suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}}$". Thus, \eqref{darij1.pf.l6.1} rewrites as \begin{align} & \suml_{U \in P} \tup{q-1}^{n-\abs{U}} q^{\abs{S}-n} \ive{ U \sups S } q^{\abs{T}} \ive{ U \sups T } \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}} \tup{q-1}^{n-\abs{U}} . \label{darij1.pf.l6.2} \tag{3} \end{align} Every subset $U$ of $N$ satisfies $n - \abs{U} = \abs{N \setminus U}$ (since $U \subs N$ yields $\abs{N \setminus U} = \underbrace{\abs{N}}_{=n} - \abs{U} = n - \abs{U}$). Thus, \eqref{darij1.pf.l6.2} becomes \begin{align} & \suml_{U \in P} \tup{q-1}^{n-\abs{U}} q^{\abs{S}-n} \ive{ U \sups S } q^{\abs{T}} \ive{ U \sups T } \\ &= q^{\abs{S}-n} q^{\abs{T}} \underbrace{\suml_{\substack{U \subs N; \\ N \setminus U \subs N \setminus G}}}_{\substack{= \suml_{\substack{U \subs N; \\ N \setminus U \subs H}} \\ \tup{ \text{since } N \setminus G = H } }} \underbrace{\tup{q-1}^{n-\abs{U}}}_{\substack{= \tup{q-1}^{\abs{N \setminus U}} \\ \tup{ \text{since } n - \abs{U} = \abs{N \setminus U} } }} \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ N \setminus U \subs H}} \tup{q-1}^{\abs{N \setminus U}} \\ &= q^{\abs{S}-n} q^{\abs{T}} \suml_{\substack{U \subs N; \\ U \subs H}} \tup{q-1}^{\abs{U}} \label{darij1.pf.l6.3} \tag{4} \end{align} (here, we have substituted $U$ for $N \setminus U$ in the sum, since the map \begin{align} \set{U \subs N} \to \set{U \subs N}, \qquad U \mapsto N \setminus U \end{align} is a bijection).

Recall that $\abs{P} = 2^n - 1$ (as we proved during our proof of Lemma 4 (b)). Also, $\sumS \abs{S} = n 2^{n-1}$ (by Lemma 4 (a)). Thus, \begin{align} \sumS \tup{n - \abs{S}} &= \underbrace{\sumS n}_{= \abs{P} \cdot n} - \underbrace{\sumS \abs{S}}_{= n 2^{n-1}} \\ &= \underbrace{\abs{P}}_{= 2^n - 1} \cdot n - n 2^{n-1} = \tup{2^n - 1} \cdot n - n 2^{n-1} \\ &= n \tup{2^n - 1 - 2^{n-1}} = n \tup{2^{n-1} - 1} \end{align} (since $\underbrace{2^n}_{= 2 \cdot 2^{n-1}} - 1 - 2^{n-1} = 2 \cdot 2^{n-1} - 1 - 2^{n-1} = 2^{n-1} - 1$).

Endow our set $P$ with the same total ordering that we used in the proof of Theorem 1. Now, it is easy to see that the $P \times P$-matrix $E$ is upper-triangular. Since the determinant of an upper-triangular $P \times P$-matrix equals the product of its diagonal entries, we thus conclude that \begin{align} \det E &= \prodS \tup{ \underbrace{\tup{q-1}^{n-\abs{S}} q^{\abs{S}-n}}_{= \tup{\dfrac{q-1}{q}}^{n-\abs{S}} } \underbrace{\ive{ S \sups S }}_{= 1} } \\ &= \prodS \tup{\dfrac{q-1}{q}}^{n-\abs{S}} = \tup{\dfrac{q-1}{q}}^{\sumS \tup{n - \abs{S}}} = \tup{\dfrac{q-1}{q}}^{n 2^{n-1} - n} \end{align} (since $\sumS \tup{n - \abs{S}} = n \tup{2^{n-1} - 1} = n 2^{n-1} - n$).

Commonmark migration
Source Link

Lemma 4. (a) We have $\sumS \abs{S} = n 2^{n-1}$.

 

(b) We have $\sumS \tup{ \abs{S} - 1 } = n 2^{n-1} - 2^n + 1$.

 

(c) We have $\prodS \tup{-1}^{\abs{S} - 1} = \tup{-1}^{\ive{n \neq 1}}$.

 

(d) We have $\prodS \abs{S} = \prodl_{k=1}^n k^{\dbinom{n}{k}}$.

Lemma 4. (a) We have $\sumS \abs{S} = n 2^{n-1}$.

 

(b) We have $\sumS \tup{ \abs{S} - 1 } = n 2^{n-1} - 2^n + 1$.

 

(c) We have $\prodS \tup{-1}^{\abs{S} - 1} = \tup{-1}^{\ive{n \neq 1}}$.

 

(d) We have $\prodS \abs{S} = \prodl_{k=1}^n k^{\dbinom{n}{k}}$.

Lemma 4. (a) We have $\sumS \abs{S} = n 2^{n-1}$.

(b) We have $\sumS \tup{ \abs{S} - 1 } = n 2^{n-1} - 2^n + 1$.

(c) We have $\prodS \tup{-1}^{\abs{S} - 1} = \tup{-1}^{\ive{n \neq 1}}$.

(d) We have $\prodS \abs{S} = \prodl_{k=1}^n k^{\dbinom{n}{k}}$.

add proof of postscriptum so that the whole question is answered; streamline latex using newcommands
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253
Loading
added 10217 characters in body
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253
Loading
you called it A, not M
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253
Loading
typos
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253
Loading
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253
Loading