Here are the /Solutions.

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

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

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

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