Assignment Store | Assignment Chef

[SOLVED] A37847 Algebra Combinatorics 2

A37847 2AC 06 25665 Level I LI Algebra & Combinatorics 2 2AC3 06 27142 Level H LH Algebra & Combinatorics 2 May/June Examinations 2023-24 Section A 1. (a) (i) State the second subring test. (ii) Is a, b ∈ R} a subring of M2(R)? Justify your answer. (iii) Is a subring of M2(R)? Justify your answer. In 1(a), you may assume M2(R) is a ring with the usual matrix addition and multipli-cation operations. [8] (b) (i) Let R and S be rings and let θ : R → S. Define what it means for θ to be a homo- morphism. (ii) Let a ∈ C. Define θa: C → C by θa(x) = ax. For which values of a is θa a homomorphism of rings? For which values of a is θa an isomorphism of rings? Justify your answers. [4] (c) (i) Define what it means for a ring R to be an integral domain. (ii) Determine, with justification, the set {n ∈ N, n ≥ 2 | Zn is an integral domain }. You may assume that if a ∈ Z, then [a]n is a unit in Zn if and only if a and n are coprime. [6] (d) Let F5 = {0, 1, 2, 3, 4} be the field with 5 elements. Let m(X) = X2 +2 ∈ F5[X], and let I = ⟨m(X)⟩ . (i) Prove that m(X) is irreducible in F5[X]. (ii) Deduce that F5[X]/I is a field. You may apply results from the lectures in (ii). (iii) Show that [X2]I = [—2]I. (iv) Calculate [3X +2]I·[X +4]I, giving your answer in the form [aX +b]I where a, b ∈ F5 . [7] 2. (a) State the rule of double counting. [3] (b) Define the combinatorial numbers {k(n)} and [k(n)], for any 0 < k ≤ n. [6] (c) What is the number of permutations on the set {1, . . . , n} that have exactly two fixed points? Justify your answer. [6] (d) Show that a graph G = (V, E) that has maximum degree Δ(G) can be properly coloured Section B 3. (a) State the division theorem for polynomials over integral domains. [2] (b) Let F be a field. Prove that every ideal of F[X] is principal. You may assume that F[X] is an integral domain. [5] (c) Let R be an integral domain. Suppose that every ideal of R[X] is principal. (i) Let r ∈ R{0} and consider the ideal I = ⟨r,X⟩ R[X]. Show that I = ⟨a⟩, where a ∈U(R), and deduce that I = R[X]. (ii) By considering 1 ∈ R[X] = ⟨r,X⟩, or otherwise, show that r ∈ U(R). Deduce that R is a field. [6] (d) In 3(d), you may apply results from the lectures provided you explain which results you use and when you apply them. Let α = √3+ √7 and let m(X) = X4 - 6X2 + 2 ∈ Z[X]. Let m (X) ∈ F7[X] be the polynomial obtained from m(X) by reduction modulo 7, and let g(X) = X2 +4 ∈ F7[X]. (i) Show that g(X) is irreducible in F7[X]. (ii) Show that m (X) = g(X)2 . (iii) By using (ii), or otherwise, show that m(X) is irreducible in Z[X]. (b) Calculate the number of permutations on the set of numbers {1, . . . , n}, where n ≥ 2, that have exactly two cycles. [6] (c) For a graph G = (V, E), let χ(G), α (G) and ω (G) be its chromatic, independence and clique number, respectively. Suppose that G satisfies χ(G) = ω (G). Show that |V| ≤ α (G)ω (G). [6] (d) Describe an algorithm that finds the smallest key in a given binary search tree. Prove that the algorithm you provided is correct. [7]