Appendices

A1. Basic Properties of a Field

Let the structure \(\ (K,\,+\,,\,\cdot\,)\ \) be a field. The additive neutral element (zero of the field) and the multiplicative neutral element (identity of the field) are denoted by \(\ 0\ \) and \(\ 1,\ \) respectively.

Proposition 0.

In a field the zero is always different from the identity: \(\quad 0\neq 1.\)

Proof. \(\,\) According to the Axiom 2. of the definition of a field, the identity is a member of the multiplicative group of the field, wherefrom the zero is excluded: \(\ 1\in K\!\smallsetminus\!\{0\}.\quad\bullet\)

Proposition 1.

A product of zero and any scalar results in zero:

\[0\,\cdot\,\alpha\ =\ \alpha\,\cdot\,0\ =\ 0\,, \quad\forall\ \alpha\in K\,.`\]

Proof. \(\,\) The multiplication being distributive over addition, we may write

\[0\,\cdot\,\alpha\ +\ 0\,\cdot\,\alpha\ =\ (0\,+\,0)\,\cdot\,\alpha\ =\ 0\,\cdot\,\alpha\,.\]

We add to both sides of the above equation the scalar opposite to \(\ 0\cdot\alpha\) :

\[[\ 0\cdot\alpha\,+\,0\cdot\alpha\,]\ +\ [\,-(\,0\cdot\alpha)\,]\ =\ 0\cdot\alpha\ +\ [\,-(\,0\cdot\alpha)\,]\,,\]

and make use of the associativity of addition :

\[0\cdot\alpha\,+\,\{\,0\cdot\alpha\ +\ [\,-(\,0\cdot\alpha)\,]\,\}\ =\ 0\cdot\alpha\ +\ [\,-(\,0\cdot\alpha)\,]\,.\]

A sum of two opposite elements being equal to zero, we get finally

\[0\cdot\alpha\ =\ 0\,.\qquad\bullet\]

Proposition 2.

Multiplying a scalar by the opposite of identity yields the opposite of that scalar:

\[(-1)\,\cdot\,\alpha\ =\ -\ \alpha\,,\qquad\forall\ \alpha\in K\,.\]

Proof. \(\\\) Due to the distributive property of multiplication and the above Proposition 1., we obtain

\[(-1)\cdot\,\alpha\ +\ \alpha\ =\ (-1)\cdot\alpha\ +\ 1\cdot\alpha\ =\ [\,(-1)\,+\,1\,]\,\cdot\,\alpha\ =\ 0\,\cdot\,\alpha\ =\ 0\,.\]

Thus the scalars \(\ \ (-1)\cdot\,\alpha\ \ \) and \(\ \alpha\ \) are mutually opposite: \(\quad (-1)\cdot\,\alpha\ =\ -\,\alpha\,.\quad\bullet\)

Proposition 3.

A product of two scalars is equal to zero if and only if at least one factor is zero:

\[\alpha\,\cdot\,\beta\ =\ 0 \quad\Leftrightarrow\quad (\alpha=0\ \ \lor\ \ \beta=0)\,,\qquad\forall\ \ \alpha,\,\beta\in K\,.\]

Proof. \(\,\) The implication

\[(\alpha=0\ \ \lor\ \ \beta=0) \quad\Rightarrow\quad \alpha\cdot\beta\ =\ 0\]

is the contents of Proposition 1. validated above. To prove its converse

(1)\[\alpha\cdot\beta\ =\ 0 \quad\Rightarrow\quad (\alpha=0\ \ \lor\ \ \beta=0)\]

let’s assume that \(\ \ \sim (\alpha=0\ \ \lor\ \ \beta=0)\,,\ \) that is \(\ \ (\alpha\neq 0\ \ \land\ \ \beta\neq 0)\,,\ \) that is \(\ \ \alpha,\beta \in K\!\smallsetminus\!\{0\}\,.\)

The set \(\ K\!\smallsetminus\!\{0\}\ \) being a multiplicative group, we infer that \(\ \alpha\cdot\beta \in K\!\smallsetminus\!\{0\}\,,\ \) that is \(\ \alpha\cdot\beta\neq 0\,.\)

Thus we have proved the inference

\[(\alpha\neq 0\ \ \land\ \ \beta\neq 0) \quad\Rightarrow\quad \alpha\cdot\beta\neq 0\,,\]

which is equivalent, by contraposition, to (1). \(\quad\bullet\)

A2. Basic Properties of a Vector Space

Subtraction in a field \(\,K\ \) or in a vector space \(\,V\,\) is by definition the addition \(\\\) of an opposite element within an appropriate additive group:

(2)\[ \begin{align}\begin{aligned}\alpha - \beta\ :\,=\ \alpha\,+\,(-\beta)\,, \qquad\forall\ \ \alpha,\beta\in K\,;\\v - w\ :\,=\ v\,+\,(-w)\,,\qquad\forall\ \ v,w\in V\,.\end{aligned}\end{align} \]

Suppose \(\,V\,\) is a vector space over a field \(\,K.\ \) The symbols \(\ 0\ \) and \(\ \theta\ \) denote \(\\\) the zero scalar (usually the number \(\,0\)) \(\,\) and \(\,\) the zero vector, \(\,\) respectively.

Proposition 0.

A product of the zero scalar and any vector equals the zero vector, \(\\\) a product of any scalar and the zero vector results in the zero vector :

\[0\cdot v\,=\,\theta\,,\quad\alpha\cdot\theta\,=\,\theta\,, \qquad\forall\ \alpha\in K,\ \ \forall\ v\in V.\]

Proof. \(\ \) The scalar multiplication being distributive over addition, we get

\[0\cdot v\,+\,0\cdot v\ \,=\ \,(0+0)\cdot v\ \,=\ \,0\cdot v\,.\]

Now we add to both sides of the above equation the vector opposite to \(\,0\cdot v\,\):

\[[\,0\cdot v\,+\,0\cdot v\,]\,+\,[\,-(0\cdot v)\,]\ \,=\ \, 0\cdot v\,+\,[\,-(0\cdot v)\,]\,.\]

Using the definition (2) of vector subtraction and taking \(\\\) into account the associativity of vector addition, we get

\[0\cdot v\,+\,[\,0\cdot v\,-\,0\cdot v\,]\ \,=\ \,0\cdot v\,-\,0\cdot v\,.\]

A difference of two identical vectors being the zero vector, we obtain

\[0\cdot v\,+\,\theta\ \,=\ \,\theta\,.\]

The vector \(\,\theta\,\) is the additive neutral element, hence finally

\[0\cdot v\ =\ \theta\,.\qquad\bullet\]

The proof of the second part of the proposition goes along similar lines:

\[ \begin{align}\begin{aligned}\alpha\cdot\theta\,+\,\alpha\cdot\theta\ \,=\ \,\alpha\cdot(\theta+\theta)\ =\ \alpha\cdot\theta\,,\\\left[\,\alpha\cdot\theta\,+\,\alpha\cdot\theta\,\right]\,+\,\left[\,-(\alpha\cdot\theta)\,\right]\ \,=\ \, \alpha\cdot\theta\,+\,\left[\,-(\alpha\cdot\theta)\,\right]\,,\\\alpha\cdot\theta\,+\,\left[\,\alpha\cdot\theta\,-\,\alpha\cdot\theta\,\right]\ =\ \alpha\cdot\theta\,-\,\alpha\cdot\theta\,,\\\alpha\cdot\theta\,+\,\theta\ =\ \theta\,,\\\alpha\cdot\theta\,=\,\theta\,.\qquad\bullet\end{aligned}\end{align} \]

Proposition 1.

The product of a vector \(\,v\,\) with a scalar opposite to \(\,\alpha\,\) equals \(\\\) the product of the vector opposite to \(\,v\,\) with the scalar \(\,\alpha\,\) and equals \(\\\) the vector opposite to the product of \(\,\alpha\,\) and \(\,v\,:\)

\[(-\alpha)\cdot v\ =\ \alpha\cdot (-v)\ =\,-\,(\alpha\cdot v)\,, \qquad\forall\ \alpha\in K,\ \ \forall\ v\in V.\]

Proof. \(\ \) Making use of the previous Proposition 0. we may write

\[ \begin{align}\begin{aligned}(-\alpha)\cdot v \,+\, \alpha\cdot v\ \,=\ \,[\,(-\alpha) + \alpha\,]\cdot v\ \,=\ \, 0\cdot v\ =\ \theta\,;\\\alpha\cdot (-v)\,+\,\alpha\cdot v\ \,=\ \,\alpha\cdot[\,(-v)+v\,]\ \,=\ \, \alpha\cdot\theta\ =\ \theta\,.\end{aligned}\end{align} \]

Thus the vectors \(\ (-\alpha)\cdot v\ \) and \(\ \alpha\cdot v\,,\ \) as well as \(\ \alpha\cdot (-v)\ \) and \(\ \alpha\cdot v\,,\ \) are mutually opposite:

\[(-\alpha)\cdot v\ =\ -\,(\alpha\cdot v)\,,\qquad\alpha\cdot (-v)\ =\ -\,(\alpha\cdot v)\,.\qquad\bullet\]

Corollary. \(\ \) Inserting \(\,\alpha = 1\,\) we get: \(\quad (-1)\,v\,=\,-\,v\,,\quad\forall\ v\in V.\)

Proposition 2.

The scalar multiplication of vectors is distributive \(\\\) both over the scalar and over the vector subtraction :

\[ \begin{align}\begin{aligned}(\alpha-\beta)\cdot v\ =\ \alpha\cdot v\,-\,\beta\cdot v\,, \qquad\forall\ \ \alpha,\beta\in K,\ \ \forall\ v\in V\,;\\\alpha\cdot (v-w)\ =\ \alpha\cdot v\,-\,\alpha\cdot w\,, \qquad\forall\ \ \alpha\in K,\ \ \forall\ \ v,w\in V\,.\end{aligned}\end{align} \]

Proof. \(\ \) The proposition results from the definition (2) of subtraction and the distributivity of scalar multiplication over addition, as well as from the above Proposition 1.:

\[ \begin{align}\begin{aligned}(\alpha-\beta)\cdot v\ =\ [\,\alpha + (-\beta)\,]\cdot v\,=\, \alpha\cdot v\,+\,[\,(-\beta)\cdot v\,]\,=\, \alpha\cdot v\,+\,[-(\beta\cdot v)\,]\,=\, \alpha\cdot v\,-\,\beta\cdot v\,;\\\alpha\cdot (v-w)\,=\,\alpha\cdot [\,v + (-w)\,]\,=\, \alpha\cdot v\,+\,[\,\alpha\cdot (-w)\,]\,=\, \alpha\cdot v\,+\,[-(\alpha\cdot w)\,]\,=\, \alpha\cdot v\,-\,\alpha\cdot w.\end{aligned}\end{align} \]

Proposition 3.

A product of a scalar and a vector is equal to the zero vector \(\\\) if and only if the scalar is zero or the vector is the zero vector:

(3)\[\alpha\cdot v\,=\,\theta\quad\Leftrightarrow\quad\ \left(\ \alpha\,=\,0\ \ \lor\ \ v\,=\,\theta\ \right)\,, \qquad\forall\ \alpha\in K,\ \ \forall\ v\in V.\]

Proof. \(\\\) The equivalence is decomposed into a conjunction of two implications to be proved separately.

\(\Rightarrow\ :\ \ \) We assume that \(\ \ \alpha\cdot v\,=\,\theta\ \ \) and have to show that \(\ \ \alpha\,=\,0\ \ \) or \(\ \ v\,=\,\theta\,.\)

Obviously \(\ \ \alpha = 0\ \ \) or \(\ \ \alpha\neq 0\,.\)

If \(\ \,\alpha = 0\,,\ \) the disjunction on the right-hand side of (3) is true.

If \(\ \,\alpha\neq 0\,,\ \ \) then \(\ \,\alpha\ \) is invertible. Multiplying both sides of the assumption by \(\,\alpha^{-1}\ \) we get

\[\alpha^{-1}\cdot(\alpha\cdot v)\ =\ \alpha^{-1}\cdot\theta\,.\]

But \(\ \ \alpha^{-1}\cdot(\alpha\cdot v)\ =\ (\alpha^{-1}\,\alpha)\cdot v\ =\ 1\cdot v\ =\ v\,,\ \,\) and on the other hand \(\ \ \alpha^{-1}\cdot\theta\ =\ \theta\,.\)

Thus \(\ \ v\,=\,\theta\ \ \) and the disjunction in (3) is again true.

\(\Leftarrow\ :\ \ \) Now we assume that \(\ \,\alpha\,=\,0\ \ \) or \(\ \ v\,=\,\theta\ \ \) and have to deduce that \(\ \,\alpha\cdot v\,=\,\theta\,.\)

If \(\ \alpha\,=\,0\,,\ \,\) then \(\ \alpha\cdot v\ =\ 0\cdot v\ =\ \theta\,,\ \ \) and if \(\ v\,=\,\theta\,,\ \,\) then \(\ \,\alpha\cdot v\ =\ \alpha\cdot \theta\ =\ \theta\,.\)

In both cases \(\ \,\alpha\cdot v\,=\,\theta\,.\qquad\bullet\)

A3. Criteria for substructures

We shall here rewrite and prove in detail the (mentioned in a previous section) criteria for subsets of the appropriate underlying sets to be subgroups or subspaces.

\(\ \)

Criterion for a subgroup. \(\\\)

Let \(\ (G,\;\bot\,)\ \,\) be a group, \(\ \,\emptyset\neq H\,\subset G\,.\ \) Then \(\ H<G\ \) if and only if

(4)\[a,b\,\in\, H\quad \Rightarrow\quad \left(\ a\;\bot\;b\ \in\ H\ \ \land\ \ a^{-1}\,\in\,H \ \right) \qquad\forall\ \ a,b \in G\,.\]

Proof. \(\\\) The condition \(\,\) (4) \(\,\) is obviously a necessary condition for a subset \(\,H\,\) of \(\,G\,\) to be a subgroup.

To prove the sufficiency, we assume that the condition \(\,\) (4) \(\,\) is true and check whether the consecutive axioms from the definition of a group are satisfied for \(\,H\,.\)

0. \(\,\) The condition (4) explicitly asserts that the set \(\,H\,\) is closed under the operation \(\,\bot\,.\)

1. \(\,\) The operation \(\,\bot\,,\ \) associative in \(\,G\,,\ \) is also associative in \(\,H\subset G\,.\)

2. \(\,\) To ensure that the identity \(\ e\ \) belongs to \(\,H,\,\) we note that a (non-empty) set \(\,H\,\) contains

   \(\,\) at least one element \(\,a\,.\ \) Due to (4), also \(\,a^{-1}\ \) as well as \(\,a\,\bot\,a^{-1}=\,e\ \) belong to \(\,H\,.\)

3. \(\,\) The condition \(\,\) (4) \(\,\) explicitly guarantees that \(\,H\,\) contains inverses of all its elements.

\(\ \)

Criterion for a vector subspace. \(\\\)

Let \(\ \,\emptyset\neq W \subset V(K)\,.\ \) Then \(\ W < V\ \) if and only if \(\,\) for all \(\ \alpha\in K\,,\ w_1,\,w_2 \in V :\)

(5)\[w_1,w_2\,\in\,W \quad\Rightarrow\quad \left(\ w_1+w_2\,\in\,W\ \ \land\ \ \alpha\,w_1\,\in\,W \ \right)\,.\]

Proof. \(\,\) We assume that the condition \(\,\) (5) \(\,\) is true and check whether the consecutive axioms from the definition of a vector space hold true for the set \(\,W\).

0. The condition \(\,\) (5) \(\,\) explicitly affirms the closure of \(\,W\ \) under vector addition

   and scalar multiplication.
1. To show that \(\ (W,\ +\,)\ \) is a group (a subgroup of \(\ (V,\ +\,)\,\)), we rewrite the criterion

   (4) \(\,\) adapted to the present context. Namely, the condition for \(\ W<V\ \) is:

   \(\ \,w_1,\,w_2\,\in\,W\quad \Rightarrow\quad \left(\ w_1 +\,w_2\ \in\ W\ \ \land\ \ -\,w_1\,\in\,W \ \right)\,, \qquad\forall\ \ w_1,w_2\in V.\)

   Inserting \(\ \alpha = -1\ \) in \(\,\) (5) \(\,\) and taking into account that \(\ \,(-1)\,w = -w\,,\) \(\\\) we see that the above condition is fulfilled.

3. 4. 5. The distributivity and compatibility laws, being satisfied in the whole set \(\ V,\ \) obviously hold true also in \(\ W\subset V.\)

Thus we have proved that the condition (5) is sufficient for \(\,W\,\) to be a subspace of \(\,V.\ \bullet\)

\(\ \)

Criterion for a subalgebra. \(\\\)

A subset \(\ B\ \) of the algebra \(\ A\ \) over a field \(\ K\ \) is a subalgebra if and only if \(\\\) for arbitrary \(\ x_1,x_2\in A\ \) and \(\ \alpha\in K:\)

(6)\[x_1,x_2\,\in\,B \quad\Rightarrow\quad \left(\ x_1+x_2\,\in\,B\ \ \land\ \ x_1\,x_2\,\in B \,\ \ \land\ \ \alpha\,x_1\,\in\,B\ \right)\,.\]

Proof \(\,\) is similar to that given above for a subspace and we render it in short. Putting \(\,\alpha = -1\ \) in (6) we see that \(\ B\ \) is a subgroup of the additive group of the ring \(\ A\ \) and is a subgroup of the additive group of the vector space \(\ A.\ \) The associativity, distributivity and compatibility conditions are in \(\ B\ \) trivially fulfilled, whereby the set \(\ B\ \) is a ring (subring of the ring \(\ A\)) and vector space (subspace of the space \(\ A\)), thus satisfying all axioms for an algebra. \(\quad\bullet\)

A4. Basis and Dimension of a Vector Space

Proposition 1.

If a vector space has an \(\,n\)-element basis, \(\\\) then every set of more than \(\,n\,\) vectors is linearly dependent.

Proof.

Let’s assume that the set \(\ B\,=\,\{\,v_1,\,v_2,\,\ldots,\,v_n\}\ \) is a basis of the vector space \(\,V(K).\ \)

We have to show that for \(\ p>n\ \) every set \(\ C = \{\,w_1,\,w_2,\,\ldots,\,w_p\}\ \) is linearly dependent.

This condition states that there exists a non-trivial linear combination of vectors \(\ w_1,\,w_2,\,\ldots,\,w_p\,,\ \) equal to the zero vector \(\,\theta,\ \,\) to wit, that the equation

(7)\[c_1\ w_1\ +\ c_2\ w_2\ +\ \ldots\ +\ c_p\ w_p\ =\ \theta\]

for the coefficients \(\ c_1,\,c_2,\,\ldots,\,c_p\in K\ \,\) has non-zero solutions.

Each vector \(\ w_j\in C\ \) can be expressed as a linear combination of basic vectors from \(\ B:\)

(8)\[w_j\ =\ \sum_{i\,=\,1}^n\ a_{ij}\,v_i\,,\qquad j=1,2,\ldots,p.\]

Here \(\ a_{1j},\,a_{2j},\,\ldots,\,a_{nj}\ \) are coordinates of the vector \(\ w_j\ \) in the basis \(\ B,\ \ j=1,2,\ldots,p.\)

Now we insert (8) into (7) and write the left-hand side of Eq. (7) as a linear combination of basic vectors:

\[ \begin{align}\begin{aligned}\sum_{j\,=\,1}^p\ c_j\,w_j\ \ =\ \ \sum_{j\,=\,1}^p\ c_j\;\left(\ \sum_{i\,=\,1}^n\ a_{ij}\,v_i\right)\ \ =\ \ \sum_{i\,=\,1}^n\ \left(\ \sum_{j\,=\,1}^p\ a_{ij}\,c_j\right)\ v_i\ \ =\\\ \ =\ \ \left(\ \sum_{j\,=\,1}^p\,a_{1j}\,c_j\right)\ v_1\ \ +\ \ \left(\ \sum_{j\,=\,1}^p\,a_{2j}\,c_j\right)\ v_2\ \ +\ \ \dots\ \ +\ \ \left(\ \sum_{j\,=\,1}^p\,a_{nj}\,c_j\right)\ v_n\ \ =\ \ \theta\,.\end{aligned}\end{align} \]

The vectors \(\ v_1,\,v_2,\,\ldots,\,v_n\ \) being linearly independent, we come to the system of equations

\[\sum_{j\,=\,1}^p\ a_{ij}\ c_j\ \,=\ \,0\,,\qquad i=1,2,\ldots,n\,,\]

which has the expanded form

\[\begin{split}\begin{array}{l} a_{11}\ c_1\ +\ \,a_{12}\ c_2\ +\ \,\dots\ \,+\ \,a_{1p}\ c_p\ \,=\ \ 0 \\ a_{21}\ c_1\ +\ \,a_{22}\ c_2\ +\ \,\dots\ \,+\ \,a_{2p}\ c_p\ \,=\ \ 0 \\ \ \ \dots\qquad\quad\dots\qquad\,\dots\qquad\ \dots\qquad\ \dots\quad \\ a_{n1}\ c_1\ +\ \,a_{n2}\ c_2\ +\ \,\dots\ \,+\ \,a_{np}\ c_p\ \,=\ \ 0 \end{array} \,,\end{split}\]

This is a homogeneous system of \(\,n\,\) linear equations with \(\,p\,\) unknowns \(\ c_1,\,c_2,\,\ldots,\,c_p\,,\ \) \(\\\) where the number of equations is less than the number of unknowns: \(\ \,n<p.\)

Such a system of linear equations has always non-zero solutions (see Chapter 8.). \(\quad\bullet\)

Corollary 1.

If an \(\,n\)-element set \(\,B\subset V\,\) is a basis of the vector space \(\,V,\ \) \(\\\) then every basis of \(\,V\,\) contains \(\,n\ \) elements.

Proof. \(\ \) Suppose that a space \(\,V\,\) has two bases: \(\\\) a basis \(\,B\,\) with \(\,n\,\) elements, \(\,\) and a basis \(\,C\,\) with \(\,m\,\) elements.

If \(\,n>m,\ \) the basis \(\,B\,\) would be linearly dependent (contradiction). \(\,\) Thus \(\ \,n \le m.\)

If \(\,m>n,\ \) the basis \(\,C\,\) would be linearly dependent (contradiction). \(\,\) Thus \(\ \,m \le n.\)

So simultaneously \(\ \,n\le m\ \,\) and \(\ m\le n,\ \) hence \(\ \,m=n.\) \(\quad\bullet\)

A dimension of a vector space being defined, the above Proposition 1. may be rephrased as

Corollary 2.

In an \(\,n\)-dimensional vector space any set of more than \(\,n\,\) vectors is linearly dependent.

When we have to check whether a given set of vectors is a basis of a vector space, it’s worth to make use of the following

Corollary 3.

In an \(\,n\)-dimensional vector space every linearly independent set of \(\,n\,\) vectors is a basis.

Proof. \(\,\) It’s enough to note that, in view of Corollary 2., in an \(\,n\)-dimensional vector space every linearly independent set of \(\,n\,\) vectors is a maximal linearly independent set. Furthermore, every maximal linearly independent set of vectors is a basis. \(\quad\bullet\)

A5. Parity of a Permutation

Given a symmetric group \(\,S_n\,,\ n\geq 2,\ \) we define the auxiliary \(\\\) function \(\,P\ \) that ascribes integer numbers to permutations:

\[\begin{split}P:\quad S_n\ni\,\sigma =\ \left(\begin{array}{cccccc} 1 & 2 & 3 & \dots & n \\ s_1 & s_2 & s_3 & \dots & s_n \end{array}\right) \ \ \rightarrow\ \ P(\sigma)\ :\,= \!\!\!\prod_{1\,\leq\,i\,<\,j\,\leq\,n} \!\!\! \left(s_j-\,s_i\right)\ \ \in\ \ Z\,.\end{split}\]

For example, \(\,\) if \(\,n=3,\ \ \) then \(\ \ \{\,(i,j):\ \ 1 \leq i<j \leq 3\,\}\ =\ \{\,(1,2),\,(1,3),\,(2,3)\,\}\,,\ \ \) and

\[\begin{split}P\left(\begin{array}{ccc} 1 & 2 & 3 \\ s_1 & s_2 & s_3 \end{array}\right)\ \ =\ \ (s_2-\,s_1)(s_3-\,s_1)(s_3-\,s_2)\,.\end{split}\]

In particular, \(\quad P\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\right) \ =\ (1-2)(3-2)(3-1)\ =\ (-1)(+1)(+2)\ =\ -2\,.\)

\(\ \)

We notice at once two simple properties of the function \(\,P(\sigma).\)

1. Permutations are bijections, whereby

   \[i<j\quad\Rightarrow\quad s_i \neq s_j\,,\qquad\forall\ \ i,j\in\{\,1,\,2,\,\ldots,\,n\}.\]

   A product of non-zero factors being also non-zero, we infer that the function \(\,P(\sigma)\,\) assumes only non-zero integer values:

   (9)\[\blacktriangleright\quad P(\sigma) \neq 0\,,\qquad\forall\ \sigma\in S_n\,.\]

2. If \(\ \,\sigma\ =\ \text{id}\ =\ \left(\begin{array}{cccc} 1 & 2 & \ldots & n \\ 1 & 2 & \ldots & n \end{array}\right),\ \ \) then \(\ \,\sigma(i)\equiv s_i = i,\ \ i=1,2,\ldots,n.\ \,\) Therefore

   (10)\[\blacktriangleright\quad P(\text{id})\ \ =\ \!\!\!\prod_{1\,\leq\,i\,<\,j\,\leq\,n} \!\!\! (j-i) \ \ >\ \ 0\,,\]

   since a product of positive integers is a positive integer, too.

The next property is more elaborate and we shall formulate it as

Lemma. \(\,\)

Let \(\ \sigma\in S_n\,,\ n\geq 2;\ \ \) \(\ k,l\in\{1,2,\ldots,n\},\ \ k<l\,.\ \)

Then for any transposition \(\,\tau_{kl}\equiv (k,l)\,:\quad\) \(\,P(\sigma\ \tau_{kl})\ =\ -\,P(\sigma)\,.\)

Proof. \(\,\)

Let \(\ \ \sigma\ =\ \left(\begin{array}{ccccccccc} 1 & 2 & \ldots & k & \ldots & l & \ldots & n-1 & n \\ s_1 & s_2 & \ldots & s_k & \ldots & s_l & \ldots & s_{n-1} & s_n \end{array}\right)\,.\)

Then \(\ \ \sigma\ \tau_{kl}\ =\ \left(\begin{array}{ccccccccc} 1 & 2 & \ldots & k & \ldots & l & \ldots & n-1 & n \\ s_1 & s_2 & \ldots & s_l & \ldots & s_k & \ldots & s_{n-1} & s_n \end{array}\right)\,.\)

First, let’s assume that \(\ l=k+1.\ \) Thus

\(\sigma\ =\ \left(\begin{array}{cccccccc} 1 & 2 & \ldots & k & k+1 & \ldots & n-1 & n \\ s_1 & s_2 & \ldots & s_k & s_{k+1} & \ldots & s_{n-1} & s_n \end{array}\right)\,,\ \)

\(\ \sigma\ \tau_{\,k,\,k+1}\ =\ \left(\begin{array}{cccccccc} 1 & 2 & \ldots & k & k+1 & \ldots & n-1 & n \\ s_1 & s_2 & \ldots & s_{k+1} & s_k & \ldots & s_{n-1} & s_n \end{array}\right)\,;\ \)

\(\ P(\sigma)\ =\ (s_2-\,s_1)\,\ldots\,(s_{k+1}-\,s_k)\,\ldots\,(s_n-\,s_{n-1})\,,\ \)

\(\ P(\sigma\ \tau_{\,k,\,k+1})\ =\ (s_2-\,s_1)\,\ldots\,(s_k-\,s_{k+1})\,\ldots\,(s_n-\,s_{n-1})\,.\ \)

The two products, \(\,P(\sigma)\,\) and \(\,P(\sigma\ \tau_{\,k,\,k+1})\,,\ \) differ only in one factor: \(\ (s_{k+1}-\,s_k)\ \) has been replaced by \(\ (s_k-\,s_{k+1})\ \,=\ \,-\ (s_{k+1}-\,s_k)\,.\ \) This substitution results in change of sign of the whole expression.

That way we have proved the Lemma for an adjacent transposition \(\,\tau_{\,k,\,k+1}\,.\ \) Since every transposition \(\,\tau_{kl}\,\) can be represented as a product of an odd number of adjacent ones, the Lemma holds true in general. \(\quad\bullet\)

Now we are in position to write down and prove the main statement of this section.

Theorem. \(\,\)

Suppose a permutation \(\ \sigma\in S_n\,,\ n\geq 2,\ \ \) can be decomposed into a product of transpositions in two different ways: \(\ \ \sigma\ =\ \tau_1\,\tau_2\,\dots\,\tau_r\ =\ \tau'_1\ \tau'_2\ \dots\ \tau'_s\,.\ \)

Then the numbers, \(\,r,s,\ \) of factors in the decompositions are either both odd, or both even (that is, they have the same parity): \(\ \,(-1)^r\ =\ \,(-1)^s\,.\)

Proof. \(\,\) Using the Lemma and Eq. (9), \(\,\) we obtain

\[ \begin{align}\begin{aligned}P(\sigma)\ =\ P(\text{id}\circ\tau_1\,\tau_2\,\dots\,\tau_r)\ =\ (-1)^r\ P(\text{id})\,,\\P(\sigma)\ =\ P(\text{id}\circ\tau'_1\ \tau'_2\ \dots\ \tau'_s)\ =\ (-1)^s\ P(\text{id})\,;\\(-1)^r\ P(\text{id})\ =\ (-1)^s\ P(\text{id})\,,\quad P(\text{id})\neq 0;\\(-1)^r\ =\ \,(-1)^s\,.\quad\bullet\end{aligned}\end{align} \]

The Theorem allows to define a sign of a permutation \(\,\sigma\,\) as \(\ \text{sgn}\,\sigma = (-1)^r\,,\ \) where \(\,r\,\) is the number of factors in any decomposition of \(\,\sigma\,\) into a product of transpositions. Let’s note that

\[P(\sigma)\ \,=\ \,(-1)^r\,P(\text{id})\ \,=\ \, \text{sgn}\,\sigma\,\cdot\,P(\text{id}),\]

where, according to Eq. (10), \(\ P(\text{id})>0.\ \)

Thus the sign of a permutation \(\,\sigma\,\) is the sign of the integer number \(\,P(\sigma):\)

\[ \begin{align}\begin{aligned}\text{sgn}\,\sigma = +1\qquad\Leftrightarrow\qquad P(\sigma) > 0\,,\\\text{sgn}\,\sigma = -1\qquad\Leftrightarrow\qquad P(\sigma) < 0\,.\end{aligned}\end{align} \]