1. Matrices and graphs

Recall that a n×n matrix A has elements A_ij for each i and j in { 1 ... n }, and that the product of two such matrices AB is defined as the matrix C where C_ij = ∑_k∈{1...n} A_ikB_kj,,.

Given a directed graph G with vertices { 1 ... n }, define the adjacency matrix A(G) of G by the rule A_ij = 1 if there is an edge from i to j in G and A_ij = 0 otherwise.

Prove that for each m > 0 and each i, j in { 1 ... n }, (A(G)^m)_ij is equal to the number of distinct paths of length m from i to j in G.

1.1. Solution

By induction on m: when m = 1, A(G)^m = A(G) and there is exactly 1 path from i to j if and only if A(G) = 1.

For larger m, observe that A(G)^m = A(G)⋅A(G)^m-1. So (A(G)^m)_ij = ∑_k A_ik(A^m-1)_kj. By the induction hypothesis, the second factor in each term counts the number of length m-1 paths from k to j. Note that every path from i to j of length m consists of an edge ik (and thus a nonzero entry A_ik) followed by a path of length m-1 from k to j, and that all such classes of paths are disjoint because each starts with a different edge. But this is exactly what is counted by the sum.

2. Functions and polynomials

Let p be a prime.

1. Show that for any element a of ℤ_p there exists a polynomial q_a(x) in ℤ_p[x] with degree at most p-1 such that q_a(x) = 1 if x = a and q_a(x) = 0 otherwise.

2. Show that for any function f:ℤ_p→ℤ_p, there exists a polynomial q_f(x) in ℤ_p[x] with degree at most p-1 such that q_f(x) = f(x) for all x in ℤ_p.

3. Show that if any two polynomials q and q' of degree p-1 or less in ℤ_p[x] satisfy q(a) = q'(a) for all a in ℤ_p, then q = q' (i.e., q and q' have the same coefficients).

2.1. Solution

1. Recall that Fermat's Little Theorem implies that x^p-1 = 1 in ℤ_p if x ≠ 0, and that x^p-1 = 0 when x = 0. So the polynomial 1-x^p-1 is 1 just in case x = 0. Now shift 0 to a by setting q_a(x) = 1-(x-a)^p-1 (or the equivalent polynomial obtained using the binomial theorem). It's easy to see that this has degree at most p-1, since (x-a) has degree 1, (x-a)^p-1 has degree at most 1+1+⋯1 (p-1 times) = p-1, and 1-(x-a)^p-1 has degree ≤ max(1, p-1).

2. Let q_f(x) = ∑_a f(a)q_a(x), where q_a(x) is defined as above. Then for any particular value a, exactly one term in the sum will be nonzero, and this will supply q_f(a) = q_af(a) = f(a). Furthermore, as the sum of degree-(p-1) polynomials, q_f also has degree at most p-1.

3. Let A = { f:ℤ_p→ℤ_p } and B = { q ∈ ℤ_p[k] | deg(q) ≤ p-1 }. Observe that |A| = |B| = p^p, as we can specify either a function f∈A or a polynomial q∈B by supplying p values from ℤ_p (function values in the first case, coefficients in the latter). Now consider the function g:A→B given by g(f) = q_f as in the preceding construction. It is not hard to show that g is injective: if f≠f' then there is some a such that f(a)≠f'(a) and thus q_f(a)≠q_f'(a), which can only occur if q≠q'. Suppose now that there is some q∈B that is not equal to q_f for any f; then the remaining p^p-1 polynomials in B must supply the images of all p^p functions in A, a contradiction. So for every q in B, there is an f in A such that q = q_f. Now suppose q_f(a) = q_f'(a) for all a; then f(a) = f'(a) for all a ⇒ f = f' ⇒ q_f = q_f'.

3. Rationality and idealism

Show that ℚ has no nontrivial proper ideals, i.e., that any ideal of ℚ is either { 0 } or ℚ itself.

3.1. Solution

We can actually show that this is is true for any field. Let F be a field and let S be an ideal of F. We know that any ideal contains 0, and one possibility is that S = { 0 }. Suppose now that S contains a nonzero element s. Since S is an ideal, sx ∈ S for any x. Now choose some arbitrary y ∈ F and let x = s^-1y; it follows that sx = ss^-1y = y is in S. But since y is arbitrary, S = F.

4. Irreducible polynomials

Let p be prime.

1. Show that a polynomial f of degree 2 or 3 over ℤ_p is irreducible if and only if f(a) ≠ 0 for all a in ℤ_p.

2. Use this fact to compute a list of all irreducible polynomials of degree 2, 3, or 4 over ℤ₂.

4.1. Solution

1. We have that if f(a) = 0 then (x-a) divides f and f is not irreducible. In the other direction, suppose that f(a) ≠ 0 for all a. Then f has no factor of the form (x-a), and if f = gh then g and h both have degree at least 2 and f has degree at least 4. So if f has degree 3 and f(a) ≠ 0 for all a, f is irreducible.

2. Note that f(a) = 0 implies f not irreducible doesn't depend on the degree. So we can instantly knock out any polynomial with a zero constant term, since such polynomials have f(0) = 0. We can also knock out any polynomials with an even number of terms, since for these polynomials f(1) = 0. For degree 2 or 3 this completely characterizes the irreducible polynomials by the preceding argument, so we have x² + x + 1 as the only irreducible degree-2 polynomial and x³ + x² + 1 and x³ + x + 1 as the two degree-3 irreducible polynomials. For degree 4, we again need an odd number of terms and a 1 term, but we have to watch out for the product of irreducible degree 2 polynomials, which excludes (x²+x+1)² = x⁴+x²+1. This leaves x⁴+x^3+x2^{+x+1, x}4^+x3^{+1, and x}4^+x+1 as the three degree-4 irreducible polynomials.