Preparations for Graphs and Matrices

Prerequisites

You have to be familiar with the language of graphs, and the theory of matrices, especially eigenvalues, eigenvectors and characteristic polynomial.

Some Problems to Think of

Introduction

Take a look on this problem, and think the following questions. (You don't have to work it out, but at least think a little bit.)

Problem. Let $n > 1$ be a positive integer. Consider the polynomial defined by

F_{n} (x) = \sum_{i = 1}^{n} x^{gcd (i, n)}

Have you ever seen this $F_{n}$ elsewhere?
Prove, by any means, that $F_{n} (x)$ is divisible by $n$ , for all integer $x$ .
Prove that $F_{n} (x) + 1$ has no linear factors.
Using exactly the same method, try to prove that $F_{n} (x) + 1$ has no factors of degree $0 < d < n$ . Which properties of $F_{n}$ would you expect if this method should work?
Prove that $F_{n} (x) + 1$ is irreducible over $Z$ .

Spectra of Graphs

The following questions have no "correct" answer.

Do you know the definition of the adjacency matrix?
What can you say about the eigenvalues of the adjacency matrix? Are they all real? Can they all be positive?
If you're only given the eigenvalues of the adjacency matrix, but not the graph, what information can you get?
Give a combinatorial interpretation of the eigenvalues of the adjacency matrix.