\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{enumitem}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{15: Spectral Graph Theory}{Due Friday, Week 9}


Choose \textbf{three} problems below to solve!  


\begin{enumerate}
\item Given a $n \times n$ matrix $A$, the \textbf{trace} of $A$ is the sum of the entries on the diagonal of $A$: that is,
\begin{align*}
\textrm{tr}(A) = \sum_{i=1}^n A(i,i).
\end{align*}

\begin{enumerate}
\item Suppose that $A$ is a $n \times n$ matrix that has $n$ eigenvalues $\lambda_1, \ldots \lambda_n$ (counted with multiplicity.)  Prove that $\textrm{tr}(A) = \sum_{i=1}^n \lambda_i$.
\item Let $G$ be a finite graph with $n \times n$ adjacency matrix $A_G$ and eigenvalues $\lambda_1, \ldots \lambda_n$ (where each eigenvalue is listed as many times as its multiplicity indicates.)

Prove that $\lambda_1^2 + \ldots \lambda_n^2$ is a nonnegative integer.  What very simple graph property does this sum correspond to?
\end{enumerate}





\item Prove or disprove: there is no graph with $-1/2$ as an eigenvalue.


\item Let $K_{n,m}$ be the complete bipartite graph on $(n,m)$ vertices (i.e.\ $K_{n,m}$ consists of two parts, one with $n$ vertices and the other with $m$ vertices.  Every possible edge from one part to the other exists, and no edges exist within one given part.)  Find the spectra of $K_{n,m}$.

\item Prove or disprove the following claim: there is some way to partition the edges of the graph $K_{10}$ into three groups, each isomorphic to copies of the Petersen graph.


\item A \textbf{Latin square} is a $n \times n$ array filled with the symbols $\{1\ldots n\}$, so that there are no repeated symbols in any row or column.  Here is an example for when $n = 3:$
\begin{align*}
\begin{array}{|c|c|c|}
\hline 1 & 2 & 3\\\hline
2 & 3 & 1\\\hline
3 & 1 & 2\\\hline
\end{array}
\end{align*}
Given any such square, form its corresponding \textbf{Latin square graph} as follows: create $n^2$ vertices, one for each cell in the square.  Connect two vertices by an edge whenever one of the three following conditions hold:
\begin{itemize}
\item The two cells corresponding to this vertex lie in the same row.
\item The two cells corresponding to this vertex lie in the same column.
\item The two cells corresponding to this vertex contain the same symbol.
\end{itemize}
For any $n \geq 3$, prove that this graph is regular with degree $3(n-1)$.  Show that this graph has precisely three distinct eigenvalues in its spectrum.  What are they?

\end{enumerate}


\end{document}






