Simple permutations proof

In summary, the conversation is about the set of all permutations on 'N' values, denoted by S_N, and the definition of a function called Delta. They also define a function called sgn, which takes a permutation in S_N and outputs either 1 or -1. The discussion then shifts to proving that for any two permutations in S_N, the sgn function behaves in a specific way.
  • #1
bomba923
763
0
Consider
[tex]S_N = \left\{ {\left. {\sigma :\left\{ {1, \ldots ,N} \right\} \to \left\{ {1, \ldots ,N} \right\}} \right|\sigma {\text{ is a bijection}}} \right\}[/tex]
i.e., the set of all permutations on 'N' values.

Define
[tex]\Delta \left( {x_1 , \ldots ,x_N } \right) = \prod\limits_{i < j} {\left( {x_i - x_j } \right)} [/tex]
and, for [tex]\sigma \in S_N[/tex],
[tex]\sigma \left( \Delta \right)\left( {x_1 , \ldots ,x_N } \right) = \prod\limits_{i < j} {\left( {x_{\sigma \left( i \right)} - x_{\sigma \left( j \right)} } \right)} [/tex]

Also, define [tex]{\mathop{\rm sgn}} : S_N \to \left\{ {\pm 1} \right\} [/tex] as
[tex]{\mathop{\rm sgn}} \left( \sigma \right) = \left\{ \begin{array}{l}
1,\;\sigma \left( \Delta \right) = \Delta \\
- 1,\;\sigma \left( \Delta \right) = - \Delta \\
\end{array} \right.[/tex]

How do I prove that, for [tex]\sigma ,\pi \in S_N [/tex],
[tex]{\mathop{\rm sgn}} \left( {\sigma \circ \pi } \right) = {\mathop{\rm sgn}} \left( \sigma \right){\mathop{\rm sgn}} \left( \pi \right) \; ?[/tex]
 
Last edited:
Physics news on Phys.org
  • #2
sgn(sigma o pi)=1
then sigma(pi(delta))=delta
if pi(delta)=delta then sigma(delta)=delta so both sgn are 1.
if pi(delta)=-delta sigma(-delta)=delta, which is the same as sigma(delta)=-delta, you can see it by obserivng that sigma(delta)+sigma(-delta)=0.
the same goes when sgn (sigma(pi))=-1.
 
  • #3


To prove this, we will use the fact that the sign of a permutation is determined by the number of inversions it has. An inversion in a permutation is defined as a pair of elements that are in the opposite order in the permutation as they are in the original sequence.

First, let's consider the permutation \sigma \circ \pi. This permutation is obtained by first applying \pi and then applying \sigma. So, if we have a pair of elements x_i and x_j such that x_i < x_j in the original sequence, then after applying \pi, we will have x_{\pi(i)} < x_{\pi(j)}. Similarly, after applying \sigma, we will have x_{\sigma(\pi(i))} < x_{\sigma(\pi(j))}. This shows that the number of inversions in \sigma \circ \pi is the same as the number of inversions in \sigma and in \pi separately.

Next, we will show that the sign of a permutation is determined by the number of inversions it has. Recall that if a permutation has an even number of inversions, its sign is 1, and if it has an odd number of inversions, its sign is -1.

Now, let's consider \sigma. If \sigma has an even number of inversions, then applying \sigma does not change the number of inversions, and therefore, \sigma \left( \Delta \right) = \Delta. This means that {\mathop{\rm sgn}} \left( \sigma \right) = 1. Similarly, if \sigma has an odd number of inversions, then applying \sigma will change the number of inversions by 1, and therefore, \sigma \left( \Delta \right) = - \Delta. In this case, {\mathop{\rm sgn}} \left( \sigma \right) = -1.

Now, let's consider \pi. We can apply the same logic as above to show that {\mathop{\rm sgn}} \left( \pi \right) = 1 if \pi has an even number of inversions and {\mathop{\rm sgn}} \left( \pi \right) = -1 if \pi has an odd number of inversions.

Combining these results, we can see that if \sigma and \pi both have an even number
 

1. What is a simple permutations proof?

A simple permutations proof is a mathematical method used to demonstrate the existence of a certain number of possible arrangements or combinations of a set of objects. It involves using the principles of permutations, which is the study of the ways in which objects can be ordered or arranged.

2. How is a simple permutations proof different from other mathematical proofs?

Unlike other mathematical proofs that rely on complex equations and formulas, a simple permutations proof uses a straightforward and logical approach to demonstrate the existence of possible arrangements. It is often used in introductory math courses to help students develop critical thinking and problem-solving skills.

3. Can you give an example of a simple permutations proof?

Sure, let's say you have 5 different colored blocks and you want to know how many different ways you can arrange them in a row. Using a simple permutations proof, you would first determine the total number of options for the first block (5), then the second block (4), and so on. This would result in 5 x 4 x 3 x 2 x 1 = 120 possible arrangements.

4. What are some real-life applications of simple permutations proofs?

Simple permutations proofs can be used in various fields such as genetics, computer science, and statistics. For example, in genetics, it can be used to determine the number of possible genotypes that can result from a specific combination of alleles.

5. Can a simple permutations proof be used to solve more complex problems?

Yes, while simple permutations proofs are usually used for basic arrangements and combinations, they can also be applied to more complex problems. By breaking down the problem into smaller, simpler parts, a simple permutations proof can still be used to find the solution.

Similar threads

  • Linear and Abstract Algebra
Replies
7
Views
414
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
Replies
3
Views
1K
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
629
Replies
7
Views
2K
  • General Math
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
1K
  • Math Proof Training and Practice
Replies
8
Views
1K
Back
Top