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]