MATH2301, SEMESTER 2, 2022 MIDTERM EXAMINATION
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
PRACTICE PROBLEMS TO HELP PREPARE FOR THE MIDTERM EXAMINATION
MATH2301, SEMESTER 2, 2022
1. SHORTER QUESTIONS TO TEST BASIC UNDERSTANDING
These are quick questions that you should be able to answer if you have been keeping up to date with lectures. These are good to do in discussion with classmates. Don’t be tempted to skip these! If you struggle with these, it is important that you come to office hour or drop-in sessions to see where you need to catch up.
(1) How many subsets does the empty set have?
(2) How many elements are in N × {3, 4, 5}?
(3) How many possible relations are there on the set {1, 2, 3}?
(4) Consider the relation {(a, b) | a | b} on N. Can this be thought of as a function on N?
(5) Do you know how to draw the graph of a relation on a set?
(6) If A is a 4 × 5 matrix and B is a 2 × 4 matrix, does the matrix product AB make sense?
(7) What do you know about the adjacency matrix of a relation if the relation is reflexive/symmetric/anti- symmetric?
(8) How many different equivalence classes of modular numbers do you have if the modulus is 2020?
(9) Let G be a directed graph with 10 vertices. Let a and b be vertices that are connected by at least one path from a to b. Can the shortest path from a to b have length 12?
(10) Is it always the case that the Boolean powers of an adjacency matrix stabilise after a certain point? If yes, justify. If not, find a counterexample.
(11) Is it always the case that the min-plus powers of a weighted adjacency matrix stabilise after a certain point? If yes, justify. If not, find a counterexample.
(12) When do we say that two Hasse diagrams are“the same”? That is, how can we check if two Hasse diagrams give rise to isomorphic partially ordered sets?
(13) Find all possible topological sorts of the“bow-tie”Hasse diagram of four elements, shown below.
a b
c d
(14) Do you know how to write down the matrix representation of any element of the incidence algebra?
(15) If P is the divisor poset of 36, then what is the size of the matrix Mζ corresponding to the zeta function in the incidence algebra of this poset?
2. LONGER QUESTIONS
These questions are closer to the kind you may see on an exam. Try to solve these independently first, without consulting anyone else. Once you have attempted all of them, you can discuss with me or with classmates.
2.1. Equivalence relations.
(1) Consider the relation {((a, b), (c, d)) ∈ R2 × R2 | max{a, b} = max{c, d}}. Is this an equivalence relation? If yes, can you describe and draw the equivalence classes? If not, which of the three required properties does and doesn’t it satisfy?
(2) Show that if ∼ is an equivalence relation on a set S, then the equivalence classes of ∼ partition the set S . That is, the equivalence classes are disjoint subsets of S whose union is S .
(3) Show that the relation {((a, b), (c, d)) ∈ R2 × R2 | b − a2 = d − c2 } is an equivalence relation. What are the equivalence classes? Can you draw them on the plane?
(4) Consider equivalence under the modular relation (x ∼ y if d | (x − y)) for d = 10. How many different equivalence classes [x] are there such that [x2 ] = [ 1]? How many are there such that [x3 ] = [ 1]?
(5) Consider equivalence under the modular relation (x ∼ y if d | (x − y)) for d = 12. Is it possible to find an equivalence class [x] such that [3] · [x] = [1]? Why or why not?
2.2. Graphs and adjacency matrices.
(1) Find an example of a graph such that when you order the vertices in two different ways, the adjacency matrix changes.
(2) Find the transitive closure of the relation {(a, b) | b = a · p for some prime number p} on the set {1, 2, 3, 4, 5, 6}. See if you can check your answer using Boolean powers of the adjacency matrix. (Yes, I know it’s a large matrix!)
(3) Draw your favourite weighted directed graph on 4 vertices, and compute the least-cost path weights between any pair of vertices using min-plus powers of the weighted adjacency matrix.
2.3. Partially ordered sets and the incidence algebra. Let (P, ⪯) be a poset, and fix a topological sorting of the elements of P .
(1) Let P be the “bow-tie” poset drawn earlier with a chosen topological sorting. Find by hand the element µ ∈ AP such that µ ∗ ζ = δ . You may find it useful to move back and forth between the matrix representations of these functions.
(2) Verify that if ζ is the zeta function in AP , then Mζ is just the adjacency matrix of the poset relation.
(3) A chain of length k in a poset is a finite sequence p1 ≺ p2 ≺ · · · ≺ pk of length k, of strict inequalities in the poset. Show that the (i, j)th entry of (Mζ − Mδ )k counts the number of chains of length k + 1 that start at pi and end at pj .
(4) Now give an example of a poset (P, ⪯) and some (non-topological) ordering on P , so that the matrix of ζ (or any other element of the incidence algebra) is not upper-triangular.
2022-08-27