MATHEMATICS 152, FALL 2004METHODS OF DISCRETE MATHEMATICSHomework Problems relevant to the third quizLast modified: November 10, 2004Reading• Notes on Vector Spaces over Finite Fields• Apostol, Vol. 2, Chapter 13 (the course pack)• Notes on Probability to accompany Apostol, Vol. 2, Chapter 13The third quiz will be on Thursday, Dec. 16, not on Dec. 9 as listed in thesyllabus.Required ProblemsProblems due Tuesday, Nov. 30. Nothing is due Nov. 23. Don’t forget problem26 from the previous set.1. With the two-component vectors over F4arranged into lines as in thenotes, i.e.Line 1: multiples of [10].Line 2: multiples of [01].Line 3: multiples of [1x].Line 4: multiples of [11].Line 5: multiples of [1x+1].determine the action of each of the following matrices from the groupSL(2, F4) on the lines, and hence associate a permutation with the ma-trix. You will learn more if you start by determining the eigenvalues andeigenvectors, but you can also just use a brute-force approach and letthe matrix operate on a vector from each of the five lines.(a) [x 11 0](b) [1 x0 1](c) [x+1 10 x]2. With the two-component vectors over F4arranged into lines as in thepreceding problem, construct the matrix of SL(2, F4) that representseach of the following permutations:1(a) (13)(25)(b) (13254)(c) (132)Hint: the first and second columns of the matrix in each case are multi-ples a and b of some vectors on the lines to which lines 1 and 2 respec-tively are mapped. Use a piece of information about the other lines to setup an equation relating the multiple a for the first column to the multipleb for the second, then choose a and b to make the determinant 1.3. With the two-component vectors over Z5arranged into lines as in thenotes, i.e.Line 1: multiples of [10]Line 2: multiples of [01]Line 3: multiples of [11]Line 4: multiples of [12]Line 5: multiples of [1−2] or [13] if you preferLine 6: multiples of [1−1] or [14] if you prefer.determine the action of each of the following matrices from the groupP SL(2, Z5) on the lines, and hence associate a permutation with thematrix. You will learn more if you start by determining the eigenvaluesand eigenvectors, but you can also just use a brute-force approach andlet the matrix operate on a vector from each of the six lines.a. [1 20 1]b. [2 11 1]c. [0 22 0]4. With the two-component vectors over Z5arranged into lines as in thepreceding problem, let G = P SL2(Z5) be the group acting on Z25bypermuting the lines.(a) Write down the four matrices in SL2(Z5) which take Line 2 to Line6 and Line 1 to Line 4.(b) Which two of these matrices take Line 5 to itself? Write down thecomplete permutation (in S6) that corresponds to these matrices.To what line do the other two matrices take Line 5?(c) Using a generalization of the technique from parts (a) and (b),invent a counting argument to show that |G| = |A5|.5. A much smaller group than SL(2, F4) is SL(2, Z2). Write down the sixmatrices of this group, and show that it is isomorphic to S3.26. Show that the permutationsa = (15)(24)(36)andb = (14)(26)(35)generate a subgroup of S6that is isomorphic to S3, containing three oddpermutations and three even permutations. Hint: think of an equilateraltriangle with the vertices numbered 1,2,3 on one side and 4,5,6 on theother.7. Find a subgroup of 6 matrices in P SL(2, Z5) that is isomorphic to S3.Explicitly identify each matrix in the subgroup with a permutation suchas (12) or (123).8. Find a subgroup of 12 matrices in SL(2, F4) that is isomorphic to A4.Explicitly identify each matrix in the subgroup with a permutation suchas (12)(34) or (123). (Hint: each matrix has the same eigenvector.)9. A much smaller group than SL(2, Z5) is SL(2, Z3). For this group, de-termine how many elements of order 1, 2, and 3 there are. Show thatif you pair up matrices that differ only by an overall sign into cosets,thereby creating P SL(2, Z3), you get a group that is isomorphic to thegroup of symmetries of a regular tetrahedron.10. Two parts:a. Exhibit subgroups of A5and of A6that are both isomorphic to D5and so to one another. (If you use Groups.exe, this will b e veryeasy!)b. Exhibit subgroups of SL(2, F4) and P SL(2, Z5) that are both iso-morphic to D5and so to one another. (Hint: the correspondingpermutations that you found in part a tell you how each matrixpermutes the lines of vectors.)Problems due Tuesday, December 7.11. Apostol, Section 13.4, exercise 1. If no simpler approach occurs to you,try the following:To show that sets X and Y are disjoint, show that• if x is in X it is not in Y• and if x is in Y it is not in X.To show that sets X and Y are equal, show that• if x is in X it is also in Y3• and if x is in Y it is also in X.12. Apostol, Section 13.4, number 4. To prove the formula by induction,• first show that it is true for n = 2,• then assume that it is true for arbitrary n and show that it is truefor n + 1.13. Let the universal set S be the set of all 10000 undergraduates at a uni-versity. Here are some subsets.• A is the set of 2500 freshmen• B is the set of 3000 athletes• C is the set of 5000 women• D is the set of 200 football playersThere are 1200 female athletes, but none of them play football. Of thefreshmen, 1000 are athletes and 1250 are women. 400 are both.Express each of the following subsets in terms of A, B, and C, andspecify its size.(a) The set of female upperclassmen.(b) The set of male freshman who are not athletes.(c) Translate into the language of sets the statement, “If a freshmanplays football, then he is a male athlete.”(d) An alumnus asks the university to choose a student at random toreceive a scholarship. What is the probability that the recipient iseither a male freshman athlete or an upp erclass woman?14. Apostol, section 13.9, exercise 10.15. Apostol, Section 13.11, #7 and #8. In part c, you ne ed to know thatace, 2, 3, 4, 5 in a suit counts as a straight flush.16. A chance device used by the Lottery Commission can generate any num-ber between 2 and 30 for the “daily numbers game”, with the probabilityof any individual number determined by a secret formula.Event A is “the number is prime,” and P(A)= 0.4.Event B is “the number is less than 15,” and P(B) = 0.5.Event C is “the number is a prime less than 15,” and P(C) = 0.3.(a) Are events A and B independent? Explain.For each of the following events, specify the event in terms of A andB, and calculate its probability.4(b) Event D: “the number is a prime greater than or equal