
\documentclass[11pt]{report}

\usepackage{../../StyleFiles/ksmac}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{../../StyleFiles/cprog}
\usepackage{../../StyleFiles/fullpage-old}
\usepackage{epsfig}
\usepackage{graphics}

\newcommand{\real}{\mathbb{R}}


\def\lectnumb{1}
%---------------------------------------------------------------------------

\shortrep

\lhead[{\bfseries 15-859N\quad HW \lectnumb}]{{\bfseries 15-859N\quad HW \lectnumb}}
\chead[]{}
\rhead[{\bfseries\thepage}]{{\bfseries\thepage}}
\lfoot[]{}
\cfoot[]{}
\rfoot[]{}

\pagestyle{fancy}

\parskip 1ex
\parindent 0mm

\renewcommand{\arraystretch}{1.5}
\def\titledquestion#1#2{\section{Problem: {#1} ({#2} pts.)}}

%----------------------------------------------------------------------


%-----------Danny's Macros-------------

\newcommand{\problem}[1]{\section{#1}\vspace{-1em}}
\newcounter{partnumber}
\newenvironment{parts}{\begin{list}{
%     \arabic{problemnumber}\alph{partnumber}:}{
     (\alph{partnumber})}{
     \usecounter{partnumber} \setlength{\rightmargin}{\leftmargin}}
     \setlength{\itemsep}{.0 in}}{
     \end{list} \vspace*{.0 in}}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\comment}[1]{}
%---------------------------------------

\begin{document}


\framebox{
\begin{minipage}[t]{\textwidth}
\vspace{1ex}

\begin{center}
{\LARGE\bf  15-859N --- Spectral Graph Theory \\ and Scientific Computing  ---  Fall 2005}\newline
{\large\bf Miller

\vspace{2ex}

Assignment 1
\vspace{1ex}
Due date: Thursday, October 6, 2005.\\
}
\end{center}

\end{minipage}
}%% end framebox

\begin{problem}{Spectral Theorem}
Let $A$ be a symmetric matrix.
\begin{parts}
\item Let ${\cal Y}= \{y_1,\ldots,y_k\}$ be a set of linearly independent eigenvectors of $A$ with
eigenvalue $\lambda$. Show that  any linear combination of the vectors in $\cal X$ is  an
eigenvector with eigenvalue $\lambda$. Then, show that we can find $k$ vectors ${\cal X}=
\{x_1,\ldots,x_k\}$ such that $x_i^T x_j =0$ for all $i,j$, and each $x_i$ is an eigenvector with
eigenvalue $\lambda$.

\item Show that if $x$ and $y$ are eigenvectors of $A$ corresponding to different eigenvalues, then
$x^T y =0$. \item Combining (a) and (b), we conclude that $A$ has eigenvectors ${\cal X}=
\{x_1,\ldots,x_n\}$, such that $x_i^T x_j=0$. Let $X$ be the matrix whose columns are the
eigenvectors in ${\cal X}$. Show that $X$ is an invertible matrix.

\item Let $\Lambda$ be a diagonal matrix, where $\Lambda(i,i)$ is the eigenvalue with eigenvector
$x_i$. Show that $A X = X \Lambda $, and thus $ A= X\Lambda  X^{-1} $. Use this to prove that the
trace of $A$, defined as the sum of its diagonal elements, is equal to the sum of its eigenvalues.
\end{parts}
\end{problem}

\begin{problem}{Computing Roots}
Let $A$ be the adjacency matrix of an undirected graph $G$. Suppose we know $A^k$ and $k$. Recall that the
$(i,j)$ entry of $A^k$ contains the number of walks of length $k-1$ between nodes $i$ and $j$ in
$G$.
\begin{parts}
\item
Is it possible to reconstruct $A$ when $k$ is odd? Prove it or disprove by counterexample.
\item
Is it possible to reconstruct $A$ when $k$ is even? Prove it or disprove by counterexample.
\end{parts}
\end{problem}

\begin{problem}{Particular Graphs}
If $L_G$ is the Laplacian of $G$, the normalized Laplacian of $G$ is defined
to be the matrix $D^{-1/2} L_G D^{-1/2} $ where $D$ is the diagonal matrix of the degrees of the
nodes in $G$.
\begin{parts}
\item
Compute the eigenvalues and eigenvectors of the normalized Laplacian of the $n$-nodes star graph.
Compare with the eigenvalues of the Laplacian.
\item
Consider the graph formed by two stars with their centers joined by an edge. Use Matlab to
compute the eigenvalues of its normalized Laplacian, as $n$ increases. What is the asymptotic
behavior of the second and third smallest eigenvalues? Soon we will see how the asymptotic behavior
of the second eigenvalue can be predicted by connectivity properties of the graph.
\end{parts}
\end{problem}

\begin{problem}{Even and Odd Eigenvectors}
We say a permutation $\phi$ of a set $V$ is an {\bf involution} if $\phi^2$ is the identity permutation.
A function $f:V \rightarrow \real$ is {\bf even(odd)} for $\phi$ if $f(v) = +(-) f(\phi(v))$  for all $v \in V$.

Let $G$ be a graph possibly with nonnegative edge weights and $L_G$ its Laplacian. Suppose that
$\phi$ is automorphism of $G$ and also an involution.
\begin{parts}
\item Show that if $f$ is an eigenvector for $L_G$ with eigenvalue $\lambda$ then $\phi f$ is also
an eigenvector with eigenvalue $\lambda$. \item Show that $L_G$ has a full set of eigenvectors each
of which is either even or odd. \item Show that the decomposition into even and odd eigenvectors is
in some sense unique.  That is for each eigenvalue with eigenspace $\cal X$, if $X_1$ and $X_2$ are
bases of $\cal X$ consisting of odd and even vectors, the number of odd vectors in $X_1$ is equal
to the number of odd vectors in $X_2$.
\end{parts}
\end{problem}






\end{document}
