Let s : {1,2,...,n} {1,2,...,n} be a function of sets that is invertible. Such a map determines a linear transformation S : Rn Rn given by S(ei) = es(i), and we call such linear maps S permutations.

(Permutations are Handy) Let s : {1,2,...,n} + {1,2,...,n} be a function of sets that is invertible. Such a map determines a linear transformation S:R + R" given by S(ei) = {s(i), and we call such linear maps S permutations. (a) Show that for any invertible function s : {1, 2, ..., n} + {1, 2, ..., n}, the corre- sponding linear map S:R" + R" is invertible. (b) Let si and s2 be two invertible functions from {1, 2, ...,n} to itself, and let Si and S2 be the corresponding linear maps. Is So S2 a permutation? If yes, write down an invertible map 812 : {1, 2, ...,n} + {1, 2, ..., n} such that S.(S2(e)) es12(i) Hint: Consider si o s2! (c) (THIS PART IS EXTREMELY HARD JUST SAYIN') Fix n = 3. Turns out there are six permutation matrices M1, ..., M. (matrices that represent the per- mutation transformations). Let (a1, A2, ...,26) be any vector in R such that Li-1 Qi = 1 and a; > 0 for each i. Show that aiM; is a regular stochastic matrix. (d) There are regular stochastic matrices that do not arise in the above form. Fix n = 2. Here there are only two permutation matrices M and M2. Find a regular stochastic matrix A such that A +aM1 + a2M2 for any positive real numbers a1, Q2 such that a1 + a2 = 1. (Permutations are Handy) Let s : {1,2,...,n} + {1,2,...,n} be a function of sets that is invertible. Such a map determines a linear transformation S:R + R" given by S(ei) = {s(i), and we call such linear maps S permutations. (a) Show that for any invertible function s : {1, 2, ..., n} + {1, 2, ..., n}, the corre- sponding linear map S:R" + R" is invertible. (b) Let si and s2 be two invertible functions from {1, 2, ...,n} to itself, and let Si and S2 be the corresponding linear maps. Is So S2 a permutation? If yes, write down an invertible map 812 : {1, 2, ...,n} + {1, 2, ..., n} such that S.(S2(e)) es12(i) Hint: Consider si o s2! (c) (THIS PART IS EXTREMELY HARD JUST SAYIN') Fix n = 3. Turns out there are six permutation matrices M1, ..., M. (matrices that represent the per- mutation transformations). Let (a1, A2, ...,26) be any vector in R such that Li-1 Qi = 1 and a; > 0 for each i. Show that aiM; is a regular stochastic matrix. (d) There are regular stochastic matrices that do not arise in the above form. Fix n = 2. Here there are only two permutation matrices M and M2. Find a regular stochastic matrix A such that A +aM1 + a2M2 for any positive real numbers a1, Q2 such that a1 + a2 = 1