Proving that for $\sigma\in S_n$ one has $\left|\prod_{i<j} \frac{\sigma(j)-\sigma(i)}{j-i}\right|=1$

Question

Good evening,

Could someone please demonstrate why this property is valid?

Given $\sigma\in S_n$

$$\left|\prod_{i<j} \frac{\sigma(j)-\sigma(i)}{j-i}\right|=1$$

Answer 1

This is because $\sigma$ is a permutation, and therefore a one-to-one correspondence.

You can rewrite the product in terms of numerators and denominators by way of $$ \begin{align*} \left\lvert\prod_{i<j}\frac{\sigma(j)-\sigma(i)}{j-i}\right\rvert&=\frac{\prod\limits_{i<j}\left\lvert\sigma(j)-\sigma(i)\right\rvert}{\prod\limits_{i<j}(j-i)}. \end{align*} $$ Re-index the product in the numerator by letting $h=\sigma^{-1}(i)$ and $k=\sigma^{-1}(j)$. Note that we can't assume $h<k$; however, we can still index the product in the numerator over all sets $\{h,k\}$ of two distinct integers in $[1,n]$.

This reindexing yields $$ \prod_{i<j}\lvert\sigma(j)-\sigma(i)\rvert=\prod_{\{h,k\}}\lvert k-h\rvert=\prod_{h<k}(k-h). $$

Answer 2

Detailed proof: See Exercise 5.13 (a) in my Notes on the combinatorial fundamentals of algebra, 10th of January 2019. The claim I prove there is more general: I show that if $x_1, x_2, \ldots, x_n$ are any $n$ complex numbers, and if $\sigma$ is any permutation of $\left\{1,2,\ldots,n\right\}$, then \begin{equation} \prod_{i < j} \left(x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)}\right) = \left(-1\right)^{\sigma} \cdot \prod_{i < j} \left(x_i - x_j\right) , \label{darij1.eq.1} \tag{1} \end{equation} where $\left(-1\right)^{\sigma}$ denotes the sign of the permutation $\sigma$. In order to obtain your equation from \eqref{darij1.eq.1}, you have to set $x_i = i$ and take absolute values (so that the sign $\left(-1\right)^{\sigma}$ disappears, since its absolute value is $1$).

Let me sketch how to quickly prove the weaker equality \begin{equation} \left|\prod_{i < j} \left(x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)}\right)\right| = \left|\prod_{i < j} \left(x_i - x_j\right)\right| \label{darij1.eq.2} \tag{2} \end{equation} (which is still sufficient for your purposes). This is what @NickPeterson has already suggested, but my more rigorous notations shall hopefully close the cracks which let confusion slip through.

First of all, the absolute value of a product equals the product of the absolute values of the factors; thus, \begin{align} \left|\prod_{i < j} \left(x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)}\right)\right| = \prod_{i < j} \left| x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)} \right| . \end{align}

Next, let $P$ be the set of all pairs $\left(i, j\right)$ of integers $i, j \in \left\{1,2,\ldots,n\right\}$ satisfying $i < j$; also, let $G$ be the set of all $2$-element subsets of $\left\{1,2,\ldots,n\right\}$. Note that the product sign "$\prod\limits_{i < j}$" is equivalent to "$\prod\limits_{\left(i, j\right) \in P}$".

The two sets $P$ and $G$ have the same size (namely, $\dbinom{n}{2} = n\left(n-1\right) / 2$), and this is no coincidence: There is a bijection from $P$ to $G$. This bijection simply maps each pair $\left(i, j\right)$ to the two-element set $\left\{i, j\right\}$. The inverse of this bijection maps each two-element set to the pair consisting of its smaller element and its larger element (in this order).

The permutation $\sigma$ of $\left\{1,2,\ldots,n\right\}$ gives rise to a permutation $\sigma_*$ of the set $G$, which sends each two-element subset $I$ to $\sigma\left(I\right)$ (in other words, it sends each two-element subset $\left\{i,j\right\}$ to $\left\{\sigma\left(i\right), \sigma\left(j\right)\right\}$). Why is this a permutation of $G$? Well, again, its inverse is easy to find (it does the same thing, just with $\sigma^{-1}$ instead of $\sigma$). So $\sigma_*$ is a permutation of $G$, i.e., a bijection from $G$ to $G$.

Now the crucial insight: If $\left(i, j\right) \in P$, then the absolute value $\left| x_i - x_j \right|$ depends only on the set $\left\{i, j\right\} \in G$ (not on the pair $\left(i, j\right) \in P$). In other words, if $I \in G$ is any two-element subset, then we can define a real number $f_I$ by setting \begin{align} f_I = \left| x_i - x_j \right|, \qquad \text{ where $I$ is written as $I = \left\{i, j\right\}$}. \end{align} In order to formally prove this, you should recall that there are exactly two ways of writing $I$ as $I = \left\{i, j\right\}$, and check that these two ways lead to the same value of $\left| x_i - x_j \right|$ (easy: these two ways only differ in the order of elements, and we have $\left| x_a - x_b \right| = \left| x_b - x_a \right|$).

Note that every $\left(i, j\right) \in P$ satisfies $\sigma_* \left( \left\{ i, j \right\} \right) = \left\{ \sigma\left(i\right), \sigma\left(j\right) \right\}$ and thus \begin{align} f_{\sigma_* \left( \left\{ i, j \right\} \right)} = f_{\left\{ \sigma\left(i\right), \sigma\left(j\right) \right\}} = \left| x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)} \right| \label{darij1.eq.3} \tag{3} \end{align} (by the definition of $f_{\left\{ \sigma\left(i\right), \sigma\left(j\right) \right\}}$).

Now, \begin{align} \left|\prod_{i < j} \left(x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)}\right)\right| & = \prod_{i < j} \left| x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)} \right| \\ & = \prod_{\left(i, j\right) \in P} \underbrace{\left| x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)} \right|}_{\substack{ = f_{\sigma_* \left( \left\{ i, j \right\} \right)} \\ \left(\text{by \eqref{darij1.eq.3}}\right)}} \\ & \qquad \left(\text{since "$\prod\limits_{i < j}$" is equivalent to "$\prod\limits_{\left(i, j\right) \in P}$"}\right) \\ & = \prod_{\left(i, j\right) \in P} f_{\sigma_* \left( \left\{ i, j \right\} \right)} \\ & = \prod_{I \in G} f_{\sigma_* \left(I\right)} \end{align} (here, we have substituted $I$ for $\left\{ i, j \right\}$ in the product, since the map $G \to P, \ \left(i, j\right) \mapsto \left\{ i, j \right\}$ is a bijection). Thus, \begin{align} \left|\prod_{i < j} \left(x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)}\right)\right| = \prod_{I \in G} f_{\sigma_* \left(I\right)} = \prod_{I \in G} f_I \label{darij1.eq.4} \tag{4} \end{align} (here, we have substituted $I$ for $\sigma_* \left(I\right)$ in the product, since $\sigma_*$ is a bijection).

Note that the right hand side of \eqref{darij1.eq.4} does not depend on $\sigma$. Applying the same reasoning to the permutation $\operatorname{id}$ instead of $\sigma$, we thus obtain \begin{align} \left|\prod_{i < j} \left(x_{\operatorname{id}\left(i\right)} - x_{\operatorname{id}\left(j\right)}\right)\right| = \prod_{I \in G} f_I . \end{align} In other words, \begin{align} \left|\prod_{i < j} \left(x_i - x_j\right)\right| = \prod_{I \in G} f_I . \end{align} Comparing this equality with \eqref{darij1.eq.4}, we obtain $\left|\prod_{i < j} \left(x_{\sigma\left(i\right)} - x_{\sigma\left(j\right)}\right)\right| = \left|\prod_{i < j} \left(x_i - x_j\right)\right|$. Thus, \eqref{darij1.eq.2} is proven.