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.

Here are the /Solutions.

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

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

# 3. Rationality and idealism

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

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

2014-06-17 11:57