\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[total={6in,8in}]{geometry}

\usepackage{tikz}
%\usepackage{pgfplots}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]

%\usepackage{graphicx}

\usepackage[shortlabels]{enumitem}
\setlist[enumerate]{leftmargin=*,label=(\alph*)}

%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\ve}{\varepsilon}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Span}{\mathrm{Span}}
\DeclareMathOperator{\rk}{\mathrm{rank}}
\DeclareMathOperator{\trace}{\mathrm{tr}}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\Sym}{\mathrm{Sym}}
\DeclareMathOperator{\Hom}{\mathrm{Hom}}
\DeclareMathOperator{\diag}{\mathrm{diag}}
\DeclareMathOperator{\rank}{rank}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
  \refstepcounter{problem}\par\medskip
  \def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in

%\pagestyle{empty}

\begin{document}
\centerline{Math 201 Homework for Tuesday, Week 12}
\bigskip
{\bf Due:} Tuesday, November 23.

\begin{prob}
  Consider the {\em cycle graph} $C_4$:
  \begin{center}
    \begin{tikzpicture}
      \node[ball,label={below left:{$v_1$}}] (1) at (0,0) {};
    \node[ball,label={below right:{$v_2$}}]  (2) at (1,0) {};
    \node[ball,label={above right:{$v_3$}}] (3) at (1,1) {};
    \node[ball,label={above left:{$v_4$}}] (4) at (0,1) {};
    \draw (1)--(2)--(3)--(4)--(1);
    \end{tikzpicture}
  \end{center}
  \begin{enumerate}
   \item Find the adjacency matrix $A=A(G)$.
   \item Compute $A^4$ and use it to determine the number of walks from~$v_1$
     to~$v_3$ of length~$4$.  List all of these walks (these will be ordered lists
     of~$5$ vertices).
   \item What is the total number of {\em closed} walks of length~$4$?
  \item Compute and factor the characteristic polynomial for~$A$.  
  
  \item What are the algebraic multiplicities of each of the eigenvalues?
  
   \item Diagonalize~$A$ using our algorithm: compute bases for the eigenspaces of
     each of the eigenvalues you just found, and use them to construct a
     matrix~$P$ such that~$P^{-1}AP$ is a diagonal matrix with the eigenvalues along the diagonal.
   \item Use part (f) to find a closed expression
     for~$A^{\ell}$ for each~$\ell\geq 1$.
   \item Take the trace of~$A^{\ell}$ to get a formula for the number of closed
     walks of length~$\ell$ for each~$\ell\geq 1$.  (You can check your result
       against the formula given in class.)
  \end{enumerate}
\end{prob}
\begin{prob}
  In this exercise we will prove the theorem from class: 
  
  ``Let $A$ be the adjacency matrix for a graph $G$ with vertices $v_1, \dots , v_n$, and let $\ell \in \Z_{\geq 0}$. Then then number of walks of length $\ell$ from $v_i$ to $v_j$ is $(A^\ell)_{ij}$.''
  \begin{enumerate}
   \item Let $p(i,j,\ell)$ denote the number of walks of length $\ell$ in $G$ from $v_i$ to $v_j$. Prove that for all $i,j=1,\dots, n$ and $\ell \geq 1$,
    \[p(i,j,\ell)=\sum _{k=1}^n p(i,k,\ell -1) p(k,j,1).\]
    (\emph{Hint:} Part of the trick is to parse this formula appropriately.)
    \item Prove the theorem by induction on $\ell$, using the result from part (a).
  \end{enumerate}
\end{prob}
\end{document}
