# Linear algebra preminary theorem

I'm self studying linear algebra from the book by L.Mersky and struggling with the below theorem.

If $(λ1,....λn),(μ1,...μn)$ and $(K1,....Kn)$ are arrangements of $(1,....n)$ then 1.

The proof starts by saying that if $(λ1,...λn)$ and $(μ1,...μn)$ are subjected to the same derangement,then the value of the left hand side of the above equation remains unaltered. To prove this we observe that $$(λk_j- λk_i)(μk_j- μk_i) = (λs-λr)(μs-μr)$$ where $r=\min(k_i,k_j)$ and $s=\max(k_i,k_j)$

If $r,s$(such that $1\leq r < s \leq n$) are given,then there exist unique integers $i,j$ (such that $1\leq i < j \leq n$) satisfying $r=\min(k_i,k_j)$ and $S=\max(K_i,K_j)$. Thus there exist biunique correspondence between the pairs $K_i,K_j$ and the pairs $r,s$. Hence,..(the multiplicative function and signum function is applied to both sides of the above observation line and proved the theorem)

Can somebody please explain what is the meaning of $r=\min(k_i,k_j)$ and $s=\max(k_i,k_j)$?

Thank you.

-
I'm not entirely sure if this helps you but min(number1, number2) is just the minimum of the two numbers i.e. the smaller one. Similarly max(number1, number2) is the maximum i.e. the bigger of the two numbers. – AndreasS Nov 23 '12 at 7:15
It would be great if you could at least clarify what's going on in the proof. You define $(x_1,\ \cdots,\ x_n)$ and $(y_1,\ \cdots,\ y_n)$ but neither seem to be used in your image. What does the $\varepsilon$ denote? – EuYu Nov 23 '12 at 7:21
@ EuYu-sorry I made a mistake.Both are same.I just edited it. – Grazel Nov 23 '12 at 7:37
This remains a bit unclear. Is this a proof about the sign of a permutation? Would it be possible to include an image of the page in question perhaps? Does it look a bit like the first page of this pdf? – EuYu Nov 23 '12 at 8:14

Maybe it will sound pretentious, but your textbook is old and it seems Mirsky just wanted to get this result out of the way without properly developing its background. Instead, let's use elementary group theory to prove the same in a conceptual way!

1) Verify that permutations of $(1, \ldots, n)$ are in bijective correspondence with bijective functions $\{1, \ldots, n\} \to \{1, \ldots, n\}$: a function corresponding to a permutation $k$ is $P_k:i \mapsto k_i$. Denote the set of all such functions $S_n$. Together with function composition, it forms a group, but we won't need any fancy piece of group theory here, so it's just FYI. Oh, and we'll denote by $1 \in S_n$ the identity function.

2) Prove that $$\left(\begin{matrix}a_1 & a_2 & \cdots & a_n \\ b_1 & b_2 & \cdots & b_n\end{matrix}\right) = P_a \circ P_b^{-1}.$$

3) We say that $P_x \in S_n$ is a transposition if it acts on $\{1, \ldots, n\}$ by only interchanging two numbers. Prove that any permutation from $S_n$ can be given as composition of transpositions. To do that, compose an arbitrary permutation $P_x$ with a transposition $P_{t_n}$ determined as $n \mapsto P_x(n)$ to obtain a permutation with a fixed element $n$. It can be viewed as an element of $S_{n-1}$ (in a sense that can be made precise in group theory). Proceed by induction to obtain an equality of the form $P_{t_2} \circ \ldots \circ P_{t_n} \circ P_{x} = 1$. Use the fact that a transposition is its own inverse and manipulate this equality to move all transpositions on the right hand side.

4) Define $\varepsilon: S_n \to \pm 1$ by setting it as having value $1$ on the identity $1 \in S_n$ and $-1$ on any transposition and prove that it preserves composition: $\varepsilon(P_x \circ P_y) = \varepsilon(P_x) \cdot \varepsilon(P_y)$ for any $x, y \in S_n$.

5) Use the previous steps to prove the identity in the picture.

-
Thank you all for the help.I got what the proof says.It's so simple and beautiful.:) – Grazel Nov 24 '12 at 10:53