# 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_{ik}B_{k}j,,.

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.

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.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}.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

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).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_{a}f(a) = f(a). Furthermore, as the sum of degree-(p-1) polynomials, q_{f}also has degree at most p-1.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^{-1}y; it follows that sx = ss^{-1}y = y is in S. But since y is arbitrary, S = F.

# 4. Irreducible polynomials

Let p be prime.

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}.Use this fact to compute a list of all irreducible polynomials of degree 2, 3, or 4 over ℤ

_{2}.

## 4.1. Solution

- 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.
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

^{2}+ x + 1 as the only irreducible degree-2 polynomial and x^{3}+ x^{2}+ 1 and x^{3}+ 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^{2}+x+1)^{2}= x^{4}+x^{2}+1. This leaves x^{4}+x^{3+x}2^{+x+1, x}4^{+x}3^{+1, and x}4^+x+1 as the three degree-4 irreducible polynomials.