\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{1}{Week 3}

Attempt the problems that seem interesting!  Easier exercises are marked with $(-)$ signs; harder ones are marked by $(*)$.  Open questions are denoted by writing $(**)$, as they are presumably quite hard.  Oh!  Also, typos build character: if you find any (not that there ever could be such things in my problem sets,) correct them to the most reasonable thing you can think of and proceed from there!

\begin{enumerate}
\item $(*)$ Using ideas similar to the triangle-counting argument we employed earlier, find a closed formula for the number of 4-cycles on a graph involving the adjacency matrix.  If you succeed, attempt to find one for the number of 5-cycles!  Remember to test your formulas against some examples.  Wolfram Alpha is an excellent tool for taking powers of large matrices.
\item Use this tool to prove that the girth of the Petersen graph is 5.
\item Cows!
\item For any $n$, $k$, find a graph on $n$ vertices with $k$ as an eigenvalue.
\item Prove or disprove the following: if two graphs have the same spectrum, they are isomorphic.
\addtocounter{enumi}{3} 
\item Prove the series of linear algebra propositions we stated in class, should you not believe them:
\begin{enumerate}
\item $(-)$ Show that the inverse of a permutation matrix $P$ is a permutation matrix, and furthermore that this inverse is precisely $P^T$.
\item $(-)$ Show that multiplying $P_\sigma$ on the left by a vector $\mathbf{v}$ is the same as multiplying $P_{\sigma^{-1}}$ on the right by $\mathbf{v}$.
\item $(-)$ Show that permutation matrices are unitary.  
\item Show that the product of any two unitary matrices is still unitary.
\item Show that if a matrix $A = EDE^T$, where $E$ is a unitary matrix and $D$ is a diagonal matrix, then $A$'s eigenvalues are precisely the diagonal entries of $D$ (with multiplicity.)
\end{enumerate}
\end{enumerate}


\end{document}