Exercise 3.4.2

Solution a) Consider the linear transformation $y=Px$ and each row of $P$. There is only one 1 in each row of $P$. Suppose in the first row of $P$, $P_{1,j}=1$, then $y_1=p_{1}x=x_j$, where $p_1$ is the first row of $P$. Namely, $x_j$ is moved to the 1st place after the linear transformation. Similarly, for the 2nd row of $P$, suppose $P_{2,k}=1$, then $y_2=x_k$ and $x_k$ is moved to the 2nd place, so on and so forth. There is also only one 1 in each column, then the column indices in 1 entry $P_{1,j},P_{2,k},P_{3,m},...$ comprise a permutation of $n$ as $(j,k,m,...)$. After multiplying by the permutation matrix $P$, the elements in $x$ change their orders to ${[x_j,x_k,x_m,...]}^{}$

T$.(Consideringfromtheperspectiveofcolumnvectorsof$P$alsoworks.)$

b) Suppose $P$ is invertible, by multiplying $P^{-1}$, $x=P^{-1}y$. But we know $y_1=x_j$, then we have $P_{j,1}^{-1}=1$ so that $x_j$ can return to its original position. Similarly, $y_2=x_k$, then $P_{k,2}^{-1}=1$. Following this we can see that $P_{i,j}^{-1}=P_{j,i}$ if $P_{j,i}=1$ and the rest are all 0. So we can see $P$ is invertible and $P^{-1}=P^{}$

T$.$

c) Note that $Px,P^{2}x,P^{3}x...P^{N}x$ are all permutations of $(x_1,x_2,...,x_n)$. If $P^N$ can never equal to $I$, $Px,P^{2}x,P^{3}x...P^{N}x$ will be different permutations. And $N$ can be infinitely big, so there will be infinitely many permutations of $(x_1,x_2,...,x_n)$, which is impossible. Thus there must be some $N>0$, $P^N=I$.