[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Matrices and graphs

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

Given a directed graph G with vertices { 1 ... n }, define the adjacency matrix A(G) of G by the rule Aij = 1 if there is an edge from i to j in G and Aij = 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 Aik(Am-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 Aik) 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 qa(x) in ℤp[x] with degree at most p-1 such that qa(x) = 1 if x = a and qa(x) = 0 otherwise.

  2. Show that for any function f:ℤp→ℤp, there exists a polynomial qf(x) in ℤp[x] with degree at most p-1 such that qf(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 xp-1 = 1 in ℤp if x ≠ 0, and that xp-1 = 0 when x = 0. So the polynomial 1-xp-1 is 1 just in case x = 0. Now shift 0 to a by setting qa(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 qf(x) = ∑a f(a)qa(x), where qa(x) is defined as above. Then for any particular value a, exactly one term in the sum will be nonzero, and this will supply qf(a) = qaf(a) = f(a). Furthermore, as the sum of degree-(p-1) polynomials, qf 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| = pp, 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) = qf 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 qf(a)≠qf'(a), which can only occur if q≠q'. Suppose now that there is some q∈B that is not equal to qf for any f; then the remaining pp-1 polynomials in B must supply the images of all pp functions in A, a contradiction. So for every q in B, there is an f in A such that q = qf. Now suppose qf(a) = qf'(a) for all a; then f(a) = f'(a) for all a ⇒ f = f' ⇒ qf = qf'.

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

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

2014-06-17 11:57