%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Prova de MAC5827 Topicos de Matemática Discreta                    %
% 2o. semestre de 2003                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 03 Mar 2004 12:01:20pm BRT yoshi@erdos.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}

\def\barp{{\bar p}}

\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC436 Matemática Discreta]{Prova de Matemática 
  Discreta\\2{\tiny o.} semestre de 2003} 
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=20pt

\noindent\textbf{Instruções.}  Esta prova é \textit{individual}, mas
naturalmente você pode consultar suas anotações, livros, etc.  Entregue a
soluções das questões 1 e 2 até as 14:00.  Entregue as demais soluções até as
20:00 do dia 4/03/2004, em minha sala, quando faremos uma pequena entrevista. 

\bigskip

\begin{enumerate}

\def\rk{\mathop{\text{\rm rk}}\nolimits}  
\def\bfA{{\mathbf A}}
\def\tr{\mathop{\text{\rm tr}}\nolimits}
\item \textsl{Prove o seguinte lema}: For any symmetric
  matrix~$\bfA=(A_{ij})_{1\leq i,j\leq n}$, we have
  \begin{equation}
    \label{eq:pudlak}
    \rk(\bfA)\geq{(\tr(\bfA))^2\over\tr(\bfA^2)}
    ={\(\sum_{1\leq i\leq n}A_{ii}\)^2\over\sum_{1\leq i,j\leq
        n}A_{ij}^2}.
  \end{equation}
  Consequently, if~$A_{ii}=1$ for all~$i$ and~$|A_{ij}|\leq\epsilon$ for
  all~$i\neq j$, then
  \begin{equation}
    \label{eq:rk_half}
    \rk(\bfA)\geq{n\over1+\epsilon^2(n-1)}.
  \end{equation}
  In particular, if~$\epsilon=\sqrt{1/n}$, then~$\rk(\bfA)\geq n/2$.
  \sugestao{Let~$r=\rk(\bfA)$.  Show that~$\bfA$ has~$r$ non-zero
    eigenvalues, say, $\lambda_1,\dots,\lambda_r$.  Apply Cauchy--Schwarz to
    deduce that
  \begin{equation*}
    (\tr(\bfA))^2=(\lambda_1+\dots+\lambda_r)^2
    \leq r(\lambda_1^2+\dots+\lambda_r^2)=r\tr(\bfA^2).
  \end{equation*}
  Now use that~$\bfA$ is symmetric and compute~$\tr(\bfA^2)$.
  }
  
\def\RR{{\mathbb R}}
\def\bfv{{\mathbf v}}
\item Aplique o lema acima para encontrar uma cota superior para o número
  máximo de vetores unitários~$\bfv_1,\dots,\bfv_m\in\RR^n$
  com~$|\<\bfv_i,\bfv_j\>|\leq1/100\sqrt n$ para todo~$i\neq j$.
  \sugestao{Considere a matrix $m\times m$ cujas entradas
  são~$\<\bfv_i,\bfv_j\>$.} 

\item Escolha dois problemas da lista 1.  (A sua nota dependerá de sua
  escolha: exercícios muito simples valem pouco.)
  
\item Escolha um problema da lista 2.  (Idem.)

\end{enumerate}  
 
\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 

