Exercise $9$, Section $5.3$ of Hoffman’s Linear Algebra

Question

Let $n$ be a positive integer and $F$ a field. If $\sigma$ is a permutation prove that the function $$T(x_1,…,x_n)=(x_{\sigma (1)},…,x_{\sigma (n)})$$ is an invertible linear operator on $F^n$.

Approach(1): Let $c\in F$ and $x,y\in F^n$. Then $$\begin{align*} T(cx+y)&=T(cx_1+y_1,\ldots,cx_n+y_n)\\ &=(cx_{\sigma (1)}+y_{\sigma (1)},\ldots,cx_{\sigma (n)}+y_{\sigma (n)})\\ &=c(x_{\sigma (1)},\ldots,x_{\sigma (n)})+ (y_{\sigma (1)},\ldots,y_{\sigma (n)})\\ &=cT(x)+T(y). \end{align*}$$ Thus $T$ is a linear map.

Since $\sigma:J_n\to J_n$ is bijective, we have $\exists !$ $\sigma^{-1}:J_n\to J_n$ such that $\sigma \circ \sigma^{-1}$ $=\sigma^{-1}\circ \sigma$ $=\text{id}_{J_n}$. Define $E:F^n\to F^n$ such that $E(x_1,…,x_n)$ $=(x_{\sigma^{-1}(1)},…,x_{\sigma^{-1}(n)})$. Let $x\in F^n$. Then $T\circ E(x)$ $=T(E(x))$ $=T(x_{\sigma^{-1}(1)},…,x_{\sigma^{-1}(n)})$ $=(x_{\sigma(\sigma^{-1}(1))},…,x_{\sigma(\sigma^{-1}(n))})$ $=(x_1,…,x_n)$ $=x$. Thus $T\circ E=\text{id}_{J_n}$. Let $x\in F^n$. Then $E\circ T(x)$ $=E(T(x))$ $=E(x_{\sigma (1)},…,x_{\sigma (n)})$ $=(x_{\sigma^{-1}(\sigma (1))},…,x_{\sigma^{-1}(\sigma (n))})$ $=(x_1,…,x_n)$ $=x$. Thus $E\circ T=\text{id}_{J_n}$. So $\exists E:F^n \to F^n$ such that $T\circ E$ $=E\circ T$ $=\text{id}_{J_n}$. Hence $T$ is bijective.

Approach(2): If $T(x)$ $=T(y)$ $=(x_{\sigma (1)},…,x_{\sigma (n)})$ $=(y_{\sigma (1)},…,y_{\sigma (n)})$, then $x_{\sigma (i)}=y_{\sigma (i)}$, $\forall i\in J_n$. Since $\sigma$ is injective, we have $x_i=y_i$, $\forall i\in J_n$. So $x=(x_1,…,x_n)=(y_1,…,y_n)=y$. Thus $T$ is injective. Let $y=(y_1,…,y_n)$. Since $\sigma$ is surjective, we have $\forall i\in J_n$, $\exists !$ $k_i\in J_n$ such that $\sigma(k_i)=i$. Take $x=(y_{k_1},…,y_{k_n})$. Then $T(x)$ $=T (y_{k_1},…,y_{k_n})$ $= (y_{\sigma (k_1)},…,y_{\sigma (k_n)})$ $= (y_{1},…,y_{n})$ $=y$. So $\exists x\in F^n$ such that $T(x)=y$. Thus $T$ is surjective. Hence $T$ is bijective. Is my proof correct?

Answer 1

Approach (1) is fine.

In approach (2), you separate the uses of surjectivity and injectivity, for both $T$ and $\sigma$. You use the injectivity of $\sigma$ to prove the injectivity of $T$, and the surjectivity of $\sigma$ to prove the surjectivity of $T$. In reality, it's the other way around!

It might help to consider $T$ in a more general setting, as a map from $F^m$ to $F^n$: $$T(x_1, \ldots, x_m) = (x_{\sigma(1)}, \ldots, x_{\sigma(n)}),$$ where $\sigma : J_n \to J_m$ is a function, not necessarily injective or surjective. This way, we can decouple the properties of injecitivty and surjectivity, as they are equivalent when $n = m$. It induces maps like $$T_1(x_1, x_2, x_3) = (x_3, x_1),$$ and $$T_2(x_1, x_2) = (x_1, x_2, x_1).$$ The former comes from $\sigma_1 : J_2 \to J_3$, defined by $1 \mapsto 3$ and $2 \mapsto 1$. The latter comes from $\sigma_2 : J_3 \to J_2$, defined by $1 \mapsto 1$, $2 \mapsto 2$, $3 \mapsto 1$. Note that $\sigma_1$ is only injective, while $\sigma_2$ is only surjective, but $T_1$ is only surjective, while $T_1$ is only injective.

Let's examine the details from your proof:

...then $x_{\sigma (i)}=y_{\sigma (i)}$, $\forall i\in J_n$. Since $\sigma$ is injective, we have $x_i=y_i$, $\forall i\in J_n$.

This implies $x_j = y_j$ for all $i$ in the form $\sigma(i)$, i.e. all $j$ in the range of $\sigma$. If $\sigma$ is not surjective, then we only get $x_i = y_i$ for some $i$, but not others. It's not a problem if $\sigma$ happens not to be injective, as this will just mean that we can conclude $x_j = y_j$ from multiple equations $x_{\sigma(i)} = y_{\sigma(i)}$.

Let $y=(y_1,…,y_n)$. Since $\sigma$ is surjective, we have $\forall i\in J_n$, $\exists !$ $k_i\in J_n$ such that $\sigma(k_i)=i$. Take $x=(y_{k_1},…,y_{k_n})$. Then $T(x)$ $=T (y_{k_1},…,y_{k_n})$ $= (y_{\sigma (k_1)},…,y_{\sigma (k_n)})$ $= (y_{1},…,y_{n})$ $=y$.

It took me a rather (somewhat embarrassingly) long time to figure out why this was wrong. The problem here is with the step: $$T (y_{k_1},…,y_{k_n}) = (y_{\sigma (k_1)},…,y_{\sigma (k_n)}).$$ What it should be is: $$T (y_{k_1},…,y_{k_n}) = (y_{k_{\sigma(1)}},…,y_{k_{\sigma(n)}}).$$ After all, you're taking $x_1 = y_{k_1}$, $x_2 = y_{k_2}$, etc, so it makes sense for $(Tx)_i = x_{\sigma(i)} = y_{k_{\sigma(i)}}$.

Here is an alternative argument, in the general setting, relying only on injectivity:

Suppose $y = (y_1, \ldots, y_n)$. For all $j \in \sigma(J_n) \subseteq J_m$, there exists an $i_j \in J_n$ such that $\sigma(i_j) = j$. Since $\sigma$ is surjective, $i_j$ is unique. Define: $$x_j = \begin{cases} y_{i_j} & \text{if } j \in \sigma(J_n) \\ 0 & \text{if }j \in J_m \setminus \sigma(J_n). \end{cases}$$ Also, define $x = (x_1, \ldots, x_m)$. Then $Tx = (x_{\sigma(1)}, \ldots, x_{\sigma(n)})$.

Suppose $i \in J_n$. Then $\sigma(i) \in \sigma(J_n)$, so $x_{\sigma(i)} = y_{i_{\sigma(i)}}$. But, $i_{\sigma(i)} = i$, by the definition of $i_j$. Hence, $x_{\sigma(i)} = y_i$ for all $i \in J_n$, i.e. $Tx = y$.

Of course, your first proof is fine, so you might as well go with that one.