# Permutation as Linear Transformation

Could you help me please to move forward with the problem.

I'm trying to show that a function $\varphi_{\sigma }: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$

$\varphi_{\sigma }(x_{1}, x_{2}, ... x_{n}) = (x_{i_{1}}, x_{i_{2}}, ... x_{i_{n}})$ is a linear transformation.

Where $\sigma =\begin{bmatrix} 1 &2 & ... &n \\ i_{1} & i_{2} & ... & i_{n} \end{bmatrix}$ from $S_{n}$ is a permutation.

To show it I need to check 2 conditions: 1. that sum of vectors under transformation and sum of transformations of two vectors are equal; 2. and product with scalar of a vector under transformation is equal to the product of the transformation of the vector with scalar.

So I have chosen some other vector y and try to test first condition.

I got $\varphi_{\sigma }(x_{1} + y_{1}, x_{2} + y_{2}, ... , x_{n} + y_{n}) = ..$ and It must be equal to $(x_{i_{1}} + y_{i_{1}}, x_{i_{2}} + y_{i_{2}}, ... x_{i_{n}} + y_{i_{n}})$ But can I just put "=" between them? I don't know how to make this step. Is it that obvious? I mean, I can say, let's say $x_{1} + y_{1} = z_{1}$ which goes to $z_{i_{1}}$ but how should I then show that it equals to the sum of transformations of x and y?

-
My problem is, I don't understand why we can say $x_{1}+y_{1}$ goes to $x_{i_{1}}+y_{i_{1}}$? I'm applying transformation-function to the sum x+y, why do I treat this sum as separate x and y and say they transform to $x_{i_{1}}+y_{i_{1}}$. – Lissa Nov 22 '11 at 22:36

Given $x=(x_1,\dots, x_n)$ and $y=(y_1,\dots, y_n)$, you can call $z=x+y$. That is, as you have said, $z=(z_1,\dots, z_n)$ where $z_i=x_i+y_i$ for $i=1,\dots,n$. Now by definition of $\varphi_\sigma$, we have $$\varphi_\sigma(z)=\varphi_\sigma(z_1,\dots, z_n)=(z_{i_1},\dots, z_{i_n})=(x_{i_1}+y_{i_1},\dots, x_{i_n}+y_{i_n})$$ since $z_i=x_i+y_i$ for all $i$.

On the other hand, by by definition of $\varphi_\sigma$, we also have $$\varphi_\sigma(x)=\varphi_\sigma(x_1,\dots, x_n)=(x_{i_1},\dots, x_{i_n}), \varphi_\sigma(y)=\varphi_\sigma(y_1,\dots, y_n)=(y_{i_1},\dots, y_{i_n}),$$ which implies that $$\varphi_\sigma(x)+\varphi_\sigma(y)=(x_{i_1},\dots, x_{i_n})+(y_{i_1},\dots, y_{i_n})= (x_{i_1}+y_{i_1},\dots, x_{i_n}+y_{i_n}).$$ Combining the above two equalities, we obtain $$\varphi_\sigma(z)=\varphi_\sigma(x+y)=\varphi_\sigma(x)+\varphi_\sigma(y)$$ as required.

-

If you're being explicitly asked to show it (I suppose it's a homework problem), you can't just claim that the result is obvious -- even if it is.

In order to structure the proof, you should give names to the entire vectors: Define $x=(x_1,\ldots,x_n)$, $y=(y_1,\ldots,y_n)$. Then set $z=\varphi_\sigma(x)+\varphi_\sigma(y)$ and $w=\varphi_\sigma(x+y)$. This gives you the vocabulary to speak about what it is you need to prove, namely for each $i$ the $i$th component of $z$ equals the $i$th component of $w$. Compute each of the components using the various definitions, and point out that they are equal as required.

-
Could you read my comment under my post, please. I'd be thankful, if you help me to understand it. – Lissa Nov 22 '11 at 22:48
By definition of $\varphi_\sigma$, the $i$th component of $\varphi_\sigma(x+y)$ is the $\sigma(i)$th component of $x+y$. Now the $j$th component of $x+y$ is $x_j+y_j$ for all $j$. So to find the $\sigma(i)$th component of $x+y$, just set $j=\sigma(i)$ and you get $x_{\sigma(i)}+y_{\sigma(i)}$. – Henning Makholm Nov 22 '11 at 22:55

Well, essentially, let $z = x + y$. Then, on one hand, $$\begin{eqnarray} \varphi_{\sigma }(z_{1}, z_{2}, \ldots, z_{n}) &=& (z_{i_{1}}, z_{i_{2}}, \ldots, z_{i_{n}}) = (x_{i_{1}} + y_{i_{1}} , x_{i_{2}} + y_{i_{2}}, \ldots, x_{i_{n}} + y_{i_{n}}) \\ &=& (x_{i_{1}} , x_{i_{2}}, \ldots, x_{i_{n}}) + (y_{i_{1}} , y_{i_{2}}, \ldots, y_{i_{n}}) = \varphi_{\sigma }(x_{1}, x_{2}, \ldots, x_{n}) + \varphi_{\sigma }(y_{1}, y_{2}, \ldots, y_{n}) \end{eqnarray}$$ On another hand, $\varphi_{\sigma }(z_{1}, z_{2}, \ldots, z_{n}) = \varphi_{\sigma }(x_{1} + y_{1}, x_{2}+y_{2}, \ldots, x_{n}+y_{n})$. This establishes property 1. Property 2 is proved similarly.

-
that's my problem.. why can I say $z_{i}$ goes to $x_{i}+y_{i}$? I'm applying transformation-function to the sum x+y, why do I treat this sum as separate x and y and say they transform to $x_{i}+y_{i}$. Could you please help to understand this point? – Lissa Nov 22 '11 at 22:33
@Lissa This is what vector addition does. If $z=x+y$, the $i$-th component of vector $z$ is the sum of $i$-th components of vectors $x$ and $y$, i.e. $z_i = x_i+y_i$. – Sasha Nov 22 '11 at 22:36
My question is a lil bit other. I mean, x1+y1=z1.. this goes under function (transformation) to some z_i_1. Why do we say, that it's just the same as x_i_1+y_i_1? – Lissa Nov 22 '11 at 22:43
@Lissa Think of these indexes as slots (containers), which are being permuted. It is irrelevant what the container holds, as long as permutation does not change the content of the container. – Sasha Nov 22 '11 at 22:47