%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Thursday 08 Dec 2022 06:39:02pm -03 by yoshi on ponpoko.local>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno,a4paper]{amsart}

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

%right pdf-output for special characters
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}
\usepackage{dsfont}

%\usepackage{lmodern}
\usepackage{amssymb}
\usepackage{mathtools}

\usepackage{xcolor}
\usepackage[backref]{hyperref}
\hypersetup{
    colorlinks,
    linkcolor={red!60!black},
    citecolor={green!60!black},
    urlcolor={blue!90!black}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  Page Layout
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{bbm}
\footskip28pt
\usepackage{fancyhdr}
\pagestyle{fancy}

\lhead{}
\chead{}
\rhead{}
%\lfoot{}
\cfoot{}
%\rfoot{\today, \currenttime}
\fancyfoot[RO,LE]{\thepage}
\fancyfoot[LO,RE]{{\footnotesize\today, \currenttime}}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%------------------ disjoint union with dot -------------------------------%
\makeatletter
\def\moverlay{\mathpalette\mov@rlay}
\def\mov@rlay#1#2{\leavevmode\vtop{%
   \baselineskip\z@skip \lineskiplimit-\maxdimen
   \ialign{\hfil$\m@th#1##$\hfil\cr#2\crcr}}}
\newcommand{\charfusion}[3][\mathord]{
    #1{\ifx#1\mathop\vphantom{#2}\fi
        \mathpalette\mov@rlay{#2\cr#3}
      }
    \ifx#1\mathop\expandafter\displaylimits\fi}
\makeatother

\newcommand{\dcup}{\charfusion[\mathbin]{\cup}{\cdot}}
\newcommand{\bigdcup}{\charfusion[\mathop]{\bigcup}{\cdot}}
%------------------ disjoint union with dot -------------------------------%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{datetime}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{lineno}
\newcommand*\patchAmsMathEnvironmentForLineno[1]{%
\expandafter\let\csname old#1\expandafter\endcsname\csname #1\endcsname
\expandafter\let\csname oldend#1\expandafter\endcsname\csname end#1\endcsname
\renewenvironment{#1}%
{\linenomath\csname old#1\endcsname}%
{\csname oldend#1\endcsname\endlinenomath}}% 
\newcommand*\patchBothAmsMathEnvironmentsForLineno[1]{%
\patchAmsMathEnvironmentForLineno{#1}%
\patchAmsMathEnvironmentForLineno{#1*}}%
\AtBeginDocument{%
\patchBothAmsMathEnvironmentsForLineno{equation}%
\patchBothAmsMathEnvironmentsForLineno{align}%
\patchBothAmsMathEnvironmentsForLineno{flalign}%
\patchBothAmsMathEnvironmentsForLineno{alignat}%
\patchBothAmsMathEnvironmentsForLineno{gather}%
\patchBothAmsMathEnvironmentsForLineno{multline}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\Div{\mathop{\rm Div}\nolimits}
\def\mdc{\mathop{\rm mdc}\nolimits}
\def\occ{\mathop{\rm occ}\nolimits}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\Im{\mathop{\rm Im}\nolimits}
\def\prof{\mathop{\rm prof}\nolimits}
\def\bsigma{\bar\sigma}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\QQ{\mathbb Q}
\def\One{{\ensuremath{\mathbbm{1}}}}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}  
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil)}  
\let\sim=\thicksim
\def\qand{\quad\text{e}\quad}
\def\qqand{\qquad\text{e}\qquad}

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

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

\def\tG{\widetilde G}
\def\tcG{\widetilde\cG}

\def\barp{{\bar p}}

\def\Ave{\mathop{\rm Ave}}
\def\Null{\mathop{\rm Null}}
\def\Ker{\mathop{\rm Ker}}
\def\Span{\mathop{\rm Span}}
\def\Sol{\mathop{\rm Sol}}
\def\posto{\mathop{\rm posto}}
\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\diam{\mathop{\rm diam}\nolimits}
\def\PG{\mathop{\rm PG}\nolimits}
\def\GF{\mathop{\rm GF}\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\FF{\mathbb{F}}

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

\def\bfa{\mathbf{a}}
\def\bfb{\mathbf{b}}
\def\bfc{\mathbf{c}}
\def\bfd{\mathbf{d}}
\def\bfe{\mathbf{e}}
\def\bff{\mathbf{f}}
\def\bfi{\mathbf{i}}
\def\bfp{\mathbf{p}}
\def\bfu{\mathbf{u}}
\def\bfv{\mathbf{v}}
\def\bfw{\mathbf{w}}
\def\bfx{\mathbf{x}}
\def\bfy{\mathbf{y}}
\def\bfX{\mathbf{X}}
\def\bfdelta{\boldsymbol\delta}
\def\bfzero{\mathbf{0}}
\def\dsone{\mathds{1}}

\def\ee{\mathrm{e}}
\def\ldens{\underline\bfd}
\def\udens{\overline\bfd}
\def\lldens{\underline\bfdelta}
\def\uldens{\overline\bfdelta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother
\def\itemtrig{$\vartriangleright$}
\def\itemcirc{$\circ$}
\def\itemT{\item[\itemtrig]}
\def\itemC{\item[$\circ$]}
\usepackage{enumitem}
\newcommand\rmlabel{\upshape({\itshape\roman*\,\/})}
\newcommand\RMlabel{\upshape(\Roman*)}
\newcommand\alabel{\upshape({\itshape\alph*\,\/})}
\newcommand\Alabel{\upshape({\itshape\Alph*\,\/})}
\newcommand\nlabel{\upshape({\itshape\arabic*\,\/})}
\newcommand\nlabelp{\upshape(P\arabic*)}
\newcommand\nlabelE{\bf\upshape E\arabic*}

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

\begin{document}
\title[MAC0122 Álgebra Linear I]%
{Álgebra Linear~I\\
  \bigskip\bigskip{\bf\textit{2$^{\text{\tiny o}}$ Semestre de 2022}}\\
  \bigskip\bigskip Exercícios
}  

\shortdate
\yyyymmdddate
\def\today{\number\year/\number\month/\number\day}
\settimeformat{ampmtime}
\date{Versão de \today, \currenttime}
%\date{Versão de \today}
\maketitle
\linenumbers
\onehalfspace
%\pagestyle{plain}
\pagestyle{fancy}

\noindent\textbf{Entrega.}
Entregue suas soluções no e-Disciplinas.

\medskip

\noindent\textbf{Política de colaboração e uso de fontes.}
Todo trabalho entregue por você deve ser seu.  Você é encorajado a
discutir com seus colegas o material visto em sala e os enunciados dos
exercícios, mas tome cuidado para não compartilhar seu trabalho além
do permitido.  Nos \textit{exercícios individuais}, você não pode
compartilhar suas soluções ou mesmo ideias de soluções.  Nos
\textit{exercícios em grupo}, você só pode compartilhar suas ideias e
soluções com membros de seu grupo.  Nos exercícios em grupo,
\textit{cada membro do grupo deve escrever uma solução própria}.  Ao
entregar um exercício feito em grupo, não esqueça de escrever o nome
de todos os membros do grupo em sua solução.

Você não deve procurar soluções de terceiros (como de amigos ou na
Web).  Caso você acidentalmente encontre e leia a solução de algum
exercício em algum lugar, você deve citar esta fonte em sua solução.
Caso você acidentalmente acabe colaborando com colegas na descoberta
de uma solução, você deve citar esta colaboração em sua solução.  Seu
desempenho nesta disciplina ficará prejudicado caso você viole essas
regras.

\medskip
\noindent\textbf{Fontes dos exercícios.}  Vários dos exercícios vêm de
nossa bibliografia.  Usamos as seguintes abreviaturas (outras
abreviaturas poderão ser adicionadas posteriormente). \textbf{PNK:}
Philip N. Klein, \textit{Coding the matrix}; \textbf{SA:} Sheldon
Axler, \textit{Linear algebra done right} (3a~edição).

\medskip
\noindent\textbf{Exercícios para entrega.}  Os exercícios para entrega
estão marcados com uma data de entrega e são em geral individuais.  Os
exercícios que podem ser feitos em grupo estão claramente marcados
dessa forma, e o número máximo de alunos por grupo está especificado.

\medskip
\noindent\textbf{Exercícios marcados (\textit{M}).}  Os exercícios
marcados~(\textit{M}) são para os matematicamente inclinados, e não
serão cobrados nessa disciplina.

\bigskip
\hfill* * * * *\hfill\null
\bigskip

\begin{enumerate}[label=\nlabelE]
  
\item Faça os Problemas~0.8.1 e~0.8.2 de \textbf{PNK}.

\item Faça o Problema~0.8.3 de \textbf{PNK}.  \NB{Em exercícios que
    envolvem programação, entregue o código.  Lembre-se de colocar o
    cabeçalho obrigatório.}  \datedue{25/8/2022}

\item Faça os Problemas~0.8.4 e~0.8.11 de \textbf{PNK}.

\item\label{E:4} Sejam~$A$ e~$B$ conjuntos.
  Seja~$\cP(A)=\{S\:S\subset A\}$ o conjunto dos subconjuntos de~$A$
  (o \textit{conjunto potência} de~$A$ ou \textit{conjunto das partes}
  de~$A$).  Lembre que~$B^A$ é o conjunto das funções $f\:A\to B$.
  Considere a função $F\:\cP(A)\to\{0,1\}^A$ tal que, para
  todo~$S\in\cP(A)$, temos
  \begin{equation}
    \label{eq:4}
    (F(S))(a)=
    \begin{cases}
      1 &\text{se $a\in S$}\\
      0 &\text{caso contrário}.
    \end{cases}
  \end{equation}
  Prove que~$F$ é bijetora.  \NB{A função~$F(S)$ é conhecida como a
    \textit{função característica} de~$S$.  É comum denotar~$F(S)$
    por~$\dsone_S$ ou~$\chi_S$.}  \datedue{25/8/2022}
\item Faça o Task~1.4.10 de \textbf{PNK}.  \textit{Importante.} Não
  deixe de ver a errata para a 1a~edição do livro na página do livro.
  
\item Faça o Problema~1.5.1 de \textbf{PNK}.  Não deixe de explicar
  como você chegou à resposta.  \datedue{1/9/2022}

\item Faça o Problema~2.14.4 de \textbf{PNK}.
  
\item Faça o Problema~2.14.5 de \textbf{PNK}.  No caso em que não haja
  subconjunto de $\{\mathbf{a},\dots,\mathbf{f}\}$ que tem como soma o
  vetor desejado, justifique sua resposta (de forma
  elegante \texttt{:-)}).  \hint{Considere o produto escalar com o
    vetor $1011011$.}  \datedue{1/9/2022}
  
\item Faça o Problema~2.14.6 de \textbf{PNK}.
  
\item Faça o Problema~2.14.10 de \textbf{PNK}.

\item Considere o sistema de~$n\geq1$ equações lineares
  \begin{equation}
    \label{eq:6}
    \begin{cases}
      \bfa_1\cdot\bfx=\beta_1\\
      \;\quad\;\dots\\
      \bfa_n\cdot\bfx=\beta_n
    \end{cases}
  \end{equation}
  onde $\bfa_i=(a_{i1},\dots,a_{in})\in\RR^n$ e $\beta_i\in\RR$
  ($1\leq i\leq n$), nas variáveis $\bfx=(x_1,\dots,x_n)$.  Ademais,
  suponha que $a_{ij}=0$ para todo $1\leq j<i\leq n$.
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:11i} Suponha que~$a_{ii}\neq0$ para
    todo~$1\leq i\leq n$.  Prove que o sistema~\eqref{eq:6} admite uma
    solução~$\hat\bfx=(\hat x_1,\dots,\hat x_n)\in\RR^n$.
  \item\label{it:11ii} Prove que a solução~$\hat\bfx$ acima é única.
  \item Suponha agora que, para um certo $1\leq k\leq n$, temos
    que~$a_{kk}=0$.  Prove que existe uma escolha de
    $(\beta_1,\dots,\beta_n)\in\RR^n$ tal que o sistema~\eqref{eq:6}
    não admite nenhuma solução.
    
  \item No caso em que existe um~$k$ como no item anterior, é verdade
    que~\eqref{eq:6} não admite nenhuma solução qualquer que seja
    $(\beta_1,\dots,\beta_n)\in\RR^n$?  Justifique sua resposta.
  \end{enumerate}
  Em~\ref{it:11i} e~\ref{it:11ii}, use indução em~$n$.
  \datedue{8/9/2022}
  
\item\label{E:12} Considere a seguinte sessão interativa de Python:
  {\small
\begin{verbatim}
$ python
Python 3.9.13 (main, May 21 2022, 10:37:33) 
[Clang 13.0.0 (clang-1300.0.29.30)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> D = {'A', 'B', 'C', 'D'}
>>> from vec import Vec
>>> a = Vec(D, {'B': 1, 'D': 5})
>>> b = Vec(D, {'A': -2, 'B': 1, 'C': 4, 'D': .5})
>>> c = Vec(D, {'B': 2})
>>> d = Vec(D, {'A': 2, 'B': 3, 'D':3})
>>> from vecutil import list2vec
>>> from triangular import triangular_solve
\end{verbatim}
  }\noindent
  Queremos agora executar o comando
  {\small
\begin{verbatim}
>>> x = triangular_solve([X, X, X, X], [Y, Y, Y, Y], list2vec([Z, Z, Z, Z]))
\end{verbatim}
  }\noindent
  para resolver o sistema de~$4$ equações lineares
  \begin{align*}
    \begin{cases}
      \bfa\cdot\bfx=3\\
      \bfb\cdot\bfx=6\\
      \bfc\cdot\bfx=-8\\
      \bfd\cdot\bfx=-4.
    \end{cases}
  \end{align*}
  Neste exercício, você deve dizer o que devem ser as listas %
  \verb|[X, X, X, X]|, \verb|[Y, Y, Y, Y]| e \verb|[Z, Z, Z, Z]|
  na chamada de \verb|triangular_solve()| acima.  Diga brevemente como
  você chegou a sua resposta.  \datedue{8/9/2022}

\item Suponha que executamos uma sessão interativa do Python idêntica
  à sessão do Exercício~\ref{E:12}, exceto pelo fato de definirmos
  \verb|d| da seguinte forma: {\small
\begin{verbatim}
>>> d = Vec(D, {'A': 2, 'B': 3, 'C': -1, 'D':3})
\end{verbatim}
  }\noindent%
  Queremos novamente resolver o sistema linear do Exercício~\ref{E:12}
  fazendo uma chamada do procedimento \verb|triangular_solve()| da
  forma {\small
\begin{verbatim}
>>> x = triangular_solve([X, X, X, X], [Y, Y, Y, Y], list2vec([Z, Z, Z, Z]))
\end{verbatim}
  }\noindent%
  Isso é possível fazer?  Justifique sua resposta.

  \def\sdiff{\bigtriangleup}
\item A \textit{diferença simétrica}~$A\sdiff B$ dos conjuntos~$A$
  e~$B$ é o
  conjunto~$(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus(A\cap
  B)$.  Prove que a operação de diferença simétrica é associativa,
  isto é, que~$A\sdiff(B\sdiff C)=(A\sdiff B)\sdiff C$ para quaisquer
  conjuntos~$A$, $B$ e~$C$.  \hint{Seja~$U$ um conjunto tal
    que~$A\cup B\subset U$, e considere as funções
    características~$\dsone_A$ e~$\dsone_B$ de~$A$ e~$B$ como
    vetores em~$\GF(2)^U$ (lembre-se do Exercício~\ref{E:4}).  O que é
    o vetor~$\dsone_A+\dsone_B\in\GF(2)^U$?}
  \datedue{8/9/2022}
  
\item\label{E:15} (\textit{M}) Leia a definição (abstrata) de espaços
  vetoriais
  \href{https://en.wikipedia.org/wiki/Vector_space#Definition_and_basic_properties}{na
    Wikipedia}.  Considere o conjunto dos números reais~$\RR$, com as
  operações usuais de soma e produto.  Verifique que~$\RR$ é então um
  espaço vetorial sobre o corpo dos números racionais~$\QQ$.

\item Leia o Exemplo~3.4.13 de \textbf{PNK}.

\item\label{E:17} Faça o Problema~3.8.3 de \textbf{PNK}.  Note que,
  com os vetores~$011$ e $101$ de entrada, sua função deve devolver
  uma lista com os~$4$ elementos~$000$, $011$, $101$ e~$110$ (a ordem
  pode ser qualquer).  Ademais, com a lista vazia de vetores de
  entrada, sua função deve devolver o vetor nulo de~$\GF(2)^D$.
  \datedue{15/9/2022}
  
\item Faça os Problemas~3.8.7 e~3.8.8 de~\textbf{PNK}.  Lembre que um
  espaço vetorial é um conjunto de vetores que satisfaz as
  Propriedades~V1, V2 e~V3 (veja a Definição~3.4.1 em~\textbf{PNK}).

\item Faça o Problema~3.8.10 de~\textbf{PNK}.  \datedue{15/9/2022}

\item Faça o Problema~4.17.12 de~\textbf{PNK}.

\item Leia o Exemplo~4.6.4 de~\textbf{PNK}.

\item\label{E:grs} Um \textit{grafo}~$G$ é um par ordenado~$(V,E)$,
  onde
  \begin{equation}
    \label{eq:1}
    E\subset{V\choose2}=\{e\subset V\:|e|=2\}.
  \end{equation}
  Isto é, os elementos de~$E$ são da forma~$\{x,y\}$ com~$x$ e~$y$
  elementos distintos de~$V$.  Os elementos de~$V$ são os
  \textit{vértices} de~$G$ e os de~$E$ são as \textit{arestas} de~$G$.
  Se $e=\{x,y\}$ é uma aresta, então~$e$ tem \textit{extremos} ou
  \textit{pontas}~$x$ e~$y$ e~$e$ \textit{liga}~$x$ a~$y$.  Você pode
  ler um pouco sobre grafos
  \href{https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)}{na
    Wikipedia}.  O grafo ilustrado na
  \href{https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#/media/File:6n-graf.svg}{primeira
    figura} naquela página da Wikipedia é o grafo~$(V,E)$ com
  $V=\{1,\dots,6\}$ e
  \begin{equation}
    \label{eq:2}
    E=\big\{\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,1\}, \{2,5\},
    \{4,6\}\big\}.
  \end{equation}
  Para grafos pequenos, é usual especificar um desenho do grafo em vez
  dos conjuntos~$V$ e~$E$, pois o desenho é mais simples de se
  entender.  Desenhe todos os grafos com conjunto de
  vértices~$V=\{1,2,3\}$ (são~$8$ grafos no total).
  
\item (Continuação de~\ref{E:grs})\, Às vezes, é útil permitir
  ``arestas múltiplas'' ou ``arestas paralelas'' em grafos: isto é,
  queremos mais de uma aresta ligando um par de vértices.  Às vezes, é
  também útil permitir arestas que ligam um vértice a si próprio (tais
  arestas são chamadas de \textit{laços}).  Em tais contextos,
  trabalhamos com ``multigrafos''.  Um \textit{multigrafo}~$G$ é uma
  tripla~$(V,E,\phi)$, onde~$V$ e~$E$ são conjuntos e
  $\phi\:E\to {V\choose2}\cup V$ é o que chamamos de \textit{função de
    incidência} de~$G$.  Se $\phi(e)=\{x,y\}\in{V\choose2}$, então a
  aresta~$e$ tem \textit{extremos}~$x$ e~$y$ e ela \textit{liga}~$x$
  a~$y$ em~$G$.  Se $\phi(e)=x\in V$, então a aresta~$e$ é um
  \textit{laço}, que \textit{liga} o vértice~$x$ consigo próprio.  O
  multigrafo na Seção~4.11.2 de~\textbf{PNK} (veja o segundo desenho
  desse multigrafo, em que as arestas estão rotuladas) é o multigrafo
  $(V,E,\phi)$, onde $V=\{1,2,3,4\}$, $E=\{a,b,c,d,e\}$ e
  $\phi(a)=\{1,2\}$, $\phi(b)=\phi(c)=\{2,3\}$, $\phi(d)=\{1,4\}$ e
  $\phi(e)=\{2,4\}$.
  \begin{enumerate}[label=\rmlabel]
  \item No multigrafo da Seção~4.11.2 de~\textbf{PNK}, quantos
    passeios há do vértice~$3$ para o vértice~$2$ de comprimento~$4$?
    E de comprimento~$32$?  (Como você pode ler naquela seção, há~$12$
    deles de comprimento~$3$.)
  \item No grafo do Exercício~\ref{E:grs} (com conjunto de
    arestas~\eqref{eq:2}), quantos passeios há do vértice~$1$ ao
    vértice~$6$ de comprimento~$32$?
  \end{enumerate}
  Em ambos os casos, diga como você chegou às respostas.
  \datedue{22/9/2022}

\item\label{E:incidence} Seja~$G=(V,E)$ um grafo.  Dizemos
  que~$F\subset E$ é um \textit{ciclo} se todo vértice~$x$ de~$G$ é
  ponta de um número par de arestas em~$F$, isto é, há um número par
  de~$e\in F$ tal que $x\in e$.  O \textit{espaço de ciclos} de~$G$ é
  \begin{equation}
    \label{eq:cycle_space}
    \cC=\{F\subset E\:F\text{  é um ciclo em }G\}.
  \end{equation}
  Seja~$M$ a \textit{matriz de incidência} de~$G$: a matriz em
  $\GF(2)^{V\times E}$ que tem como sua $e$-ésima coluna ($e\in E$) a
  função característica~$\dsone_e\in\GF(2)^V$ de~$e$ (veja o
  Exercício~\ref{E:4}).  Prove que
  $\cC=\{F\subset E\:\dsone_F\in\Null M\}$.  \NB{Lembre que, dada uma
    matriz~$A\in\FF^{R\times C}$, pomos
    \begin{equation}
      \label{eq:null_def}
      \Null A = \{\bfx\in\FF^C\:A\bfx=\bfzero\}.
    \end{equation}
    Chamamos~$\Null A$ de \textit{núcleo} de~$A$.  Você pode ler sobre
    núcleos de matrizes na Seção~4.7 de~\textbf{PNK} (nesse exercício,
    você só precisa saber a definição~\eqref{eq:null_def} acima).
    Note que $\Null A$ nada mais é que o conjunto de soluções do
    sistema de equações lineares homogêneas ``codificado''
    por~$A\bfx=\bfzero$.  Finalmente, é importante que, neste
    exercício, $\FF=\GF(2)$.}  \datedue{22/9/2022}

\item Seja~$G=(V,E)$ um grafo e seja~$M\in\GF(2)^{V\times E}$ sua
  matriz de incidência (veja Exercício~\ref{E:incidence}).
  Caracterize os grafos~$G$ tais que $\Null M=\{\bfzero\}$.  Prove que
  sua caracterização está correta.  \hint{Um \textit{circuito} em um
    grafo é uma sequência de vértices e arestas
    \begin{equation}
      \label{eq:circ_def}
      v_0,e_1,v_1,\dots,e_\ell,v_\ell
    \end{equation}
    do grafo com~$\ell>0$ e tal que (\textit{a})~$e_i=\{v_{i-1},v_i\}$
    para todo~$1\leq i\leq\ell$, (\textit{b})~os vértices
    $v_0,v_1,\dots,v_{\ell-1}$ são todos distintos e
    (\textit{c})~$v_\ell=v_0$.  O que ocorre se~$G$ contém um
    circuito?}

\item Seja~$G=(V,E)$ um grafo e~$F\subset E$ um ciclo de~$G$ (veja
  Exercício~\ref{E:incidence}).  Prove que existem circuitos
  $C_1,\dots,C_t$ ($t\geq0$) tais que
  \begin{enumerate}[label=\rmlabel]
  \item os~$C_i$ ($1\leq i\leq t$) dois a dois não têm arestas em
    comum e
  \item $F=E(C_1)\cup\dots\cup E(C_t)$, onde~$E(C_i)$ denota o
    conjunto de arestas que ocorrem em~$C_i$.
  \item Conclua que $\dsone_F=\sum_{1\leq i\leq t}\dsone_{C_i}$.
  \end{enumerate}
  
\item Seja~$G=(V,E)$ um grafo.  Assim como no
  Exercício~\ref{E:incidence}, trabalhamos neste exercício
  sobre~$\GF(2)$.  O \textit{espaço dos cociclos} de~$G$ é
  \begin{equation}
    \label{eq:cycle_space_perp}
    \cC^\perp=\{B\subset E\:\dsone_B^\top\dsone_C=0\text{ para
      todo ciclo $C$ de $G$}\}.
  \end{equation}
  Seja agora~$U\subset V$ e seja
  \begin{equation}
    \label{eq:5}
    B_U=\{e\in E\:e\text{ tem uma ponta em $U$ e a outra ponta em
      $V\setminus U$}\}.
  \end{equation}
  Prove que~$B_U$ é um cociclo de~$G$ para qualquer~$U\subset V$.

\item Seja~$G=(V,E)$ um grafo.  Neste exercício, vamos dizer
  que~$F\subset E$ é \textit{ímpar-regular} se todo vértice~$x$ de~$G$
  é ponta de um número ímpar de arestas em~$F$, isto é, há um número
  ímpar de~$e\in F$ tal que $x\in e$.
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$G$ o grafo exemplo na página
    \href{https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)}{da
      Wikipedia}, com conjunto de arestas~\eqref{eq:2}.  Encontre um
    conjunto ímpar-regular de arestas em~$G$.
  \item Seja~$M\in\GF(2)^{V\times E}$ a matriz de incidência de~$G$.
    Prove que~$F\subset E$ é ímpar-regular se e só se $M\dsone_F=\dsone_V$.
  \item Suponha agora que~$G$ seja o grafo de Petersen (veja, por
    exemplo, \href{https://en.wikipedia.org/wiki/Petersen_graph}{essa
      página}).  Encontre um conjunto ímpar-regular de arestas em~$G$
    ou prove que não existe tal conjunto.  \hint{Multiplique os dois
      lados de $M\dsone_F=\dsone_V$ por~$\dsone_V^\top$.  Não se
      esqueça que estamos trabalhando sobre~$\GF(2)$}.
  \end{enumerate}

\item Leia sobre \textit{Lights Out}
  \href{https://en.wikipedia.org/wiki/Lights_Out_(game)}{nessa
    página}.  Você pode jogar a versão~$5\times5$ do Lights Out, por
  exemplo, \href{https://www.logicgamesonline.com/lightsout/}{nessa
    página}.  Leia agora o Exemplo~4.5.12 de~\textbf{PNK}.  Em
  particular, experimente executar o procedimento
  \verb|button_vectors()| para valores pequenos de~$n$ para conferir
  que os vetores gerados correspondem realmente aos botões do jogo.
  Use o procedimento que você escreveu no Exercício~\ref{E:17} para
  decidir se todas as configurações iniciais têm solução para~$n=2$,
  $3$ e~$4$.  Explique como você chegou a suas respostas.
  \datedue{29/9/2022}

\item\label{E:30} Leia o Exemplo~4.5.16 de~\textbf{PNK}.  Note que,
  para o uso de \verb|solve| do módulo \verb|solver.py|, você terá de
  usar Python 3.$x$ com $x\in\{4, 5, 6\}$.  Visite
  \href{https://www.logicgamesonline.com/lightsout/}{esta página} e
  resolva a instância de Lights Out dada por ela usando o procedimento
  dado no Exemplo~4.5.16.

\item\label{E:31} (Continuação de~\ref{E:30})\, O Exemplo~4.5.16
  de~\textbf{PNK} descreve como resolver o Lights Out em uma sessão
  interativa do Python.  Naturalmente, você pode escrever um programa
  para automatizar o processo.  Escreva um programa Python, chamado
  \verb|lo_solver.py|, que segue as seguintes especificações:
  \begin{itemize}
  \item[\itemtrig] \textit{Entrada}: um inteiro~$N$ na linha de
    comando e pares de inteiros na entrada padrão especificando quais
    lâmpadas de uma instância $N\times N$ do Lights Out estão acesas;
  \item[\itemtrig] \textit{Saída} (na saída padrão): pares de inteiros
    especificando quais botões devem ser pressionados para se resolver
    a instância dada.
  \end{itemize}
  Seu programa deve comportar-se como você pode ver no exemplo
  \href{https://www.ime.usp.br/~yoshi/2022ii/mat0122/sandbox/LIGHTS_OUT/}{nesse
    diretório}.

\item (Continuação de~\ref{E:30})\, Se você fosse pôr no ar uma página
  \href{https://www.logicgamesonline.com/lightsout/}{como essa}, não
  seria muito bom se você permitisse que a página gerasse instâncias
  que não admitem solução.  Diga como você pode gerar instâncias que
  sempre têm solução, usando a rotina \verb|button_vectors()| do
  Exemplo~4.5.12 de~\textbf{PNK}.

\item Sejam~$U$ e~$V$ espaços vetoriais sobre~$\FF$ e seja $f\:U\to V$
  uma função linear.  Suponha que~$f$ seja inversível e
  seja~$g=f^{-1}\:V\to U$ sua inversa.  Prove que~$g$ é uma função
  linear.  \datedue{29/9/2022}

\item Prove ou dê contraexemplos:
  \begin{enumerate}[label=\rmlabel]
  \item Sejam $g\:X\to Y$ e $f\:Y\to Z$ funções tais que~$f\circ g$ é
    inversível.  Então tanto~$f$ quanto~$g$ são inversíveis.
  \item Sejam~$A\in\FF^{R\times C}$ e~$B\in\FF^{C\times D}$ matrizes
    tais que o produto $AB\in\FF^{R\times D}$ é inversível.  Então
    tanto~$A$ quanto~$B$ são inversíveis.
  \item\label{it:one_sided} Sejam $A\in\FF^{R\times C}$ e
    $B\in\FF^{C\times R}$ matrizes.  Sejam $I_R$ a matriz identidade
    em~$\FF^{R\times R}$ e~$I_C$ a matriz identidade
    em~$\FF^{C\times C}$.  Se~$AB=I_R$ então~$A$ é inversível
    e~$A^{-1}=B$.
  \item Sejam~$A$, $B$, $I_R$ e~$I_C$ como em~\ref{it:one_sided}
    acima.  Se~$BA=I_C$, então~$A$ é inversível e~$A^{-1}=B$.
  \end{enumerate}
  \datedue{6/10/2022}

\item Leia a Seção~4.14 de~\textbf{PNK} (partes iniciais).  Lembre que
  o código de Hamming que vimos em sala é, por definição, o conjunto
  $\Null H=\Ker f_H$, onde
  \begin{equation}
    \label{eq:3}
    H=
    \begin{bmatrix}
      0 & 0 & 0 & 1 & 1 & 1 & 1\\
      0 & 1 & 1 & 0 & 0 & 1 & 1\\
      1 & 0 & 1 & 0 & 1 & 0 & 1
    \end{bmatrix}
  \end{equation}
  e $f_H\:\GF(2)^7\to\GF(2)^3$ é função que leva $\bfv\in\GF(2)^7$
  em~$H\bfv\in\GF(2)^3$ (veja Seção~4.7.5 de~\textbf{PNK}).  Seja~$G$
  a matriz dada na Seção~4.14.3 de~\textbf{PNK}.  Sejam
  $G_{*1},\dots,G_{*4}$ as quatro colunas de~$G$, de forma que
  $G=[G_{*1}\mid\dots\mid G_{*4}]$.  O espaço das colunas de~$G$ é,
  por definição, $\Span\{G_{*1},\dots,G_{*4}\}\subset\GF(2)^7$.  Prove
  que o espaço das colunas de~$G$ coincide com o código de Hamming,
  isto é, prove que
  \begin{equation}
    \label{eq:7}
    \Null H=\Span\{G_{*1},\dots,G_{*4}\}.
  \end{equation}
  \hint{É fácil verificar que~$\Null
    H\supset\Span\{G_{*1},\dots,G_{*4}\}$.  Para verificar a outra
    direção, considere um elemento $[c_1\,\cdots\,\,c_7]^\top\in\Null
    H$.  Considere~$G\bfw$, onde
    $\bfw=[c_7\;\,c_6\;\,c_5\;\,c_3]^\top$.}  \datedue{6/10/2022}

\item\label{E:36} Seja~$G=(V,E)$ um grafo e~$x$ e~$y$ dois vértices
  em~$G$.  Seja~$F\subset E$ um subconjunto de arestas de~$G$.
  Suponha que
  \begin{equation}
    \label{eq:8}
    \sum_{f\in F}\dsone_f=\dsone_{\{x,y\}},
  \end{equation}
  onde estamos trabalhando em~$\GF(2)$.  Isto é, as funções
  características~$\dsone_f\in\GF(2)^V$ das arestas~$f$ em~$F$ somam a
  função característica~$\dsone_{\{x,y\}}\in\GF(2)^V$ de~$\{x,y\}$.
  \begin{enumerate}[label=\rmlabel]
  \item Verifique que~\eqref{eq:8} é equivalente a dizer que
    $M\dsone_F=\dsone_{\{x,y\}}$, onde~$M$ é a matriz de incidência
    de~$G$ (veja o Exercício~\ref{E:incidence}).
  \item É verdade que~\eqref{eq:8} implica que~$F$ é o conjunto de
    arestas de um $(x,y)$-caminho em~$G$?  Lembre que um
    \textit{$(x,y)$-caminho} é um caminho que começa em~$x$ e termina
    em~$y$.
  \item Considere o grafo $H=(V,F)$, que tem o mesmo conjunto de
    vértices que~$G$, mas tem como conjunto de arestas o conjunto~$F$.
    Deduza de~\eqref{eq:8} que existe um $(x,y)$-caminho
    em~$H$.
  \end{enumerate}
  
\item\label{E:37} Seja~$G=(V,E)$ um grafo.  Lembre que~$F\subset E$ é
  aresta-gerador se para toda aresta $\{x,y\}\in E$, existe um
  $(x,y)$-caminho em~$G$ que usa somente arestas em~$F$.  Considere as
  funções características~$\dsone_e\in\GF(2)^V$ ($e\in E$) das arestas
  de~$G$.  Prove que $F\subset E$ é aresta-gerador se e só se
  \begin{equation}
    \label{eq:9}
    \Span\{\dsone_f\:f\in F\}=\Span\{\dsone_e\:e\in E\}.
  \end{equation}
  \NB{O espaço no lado direito de~\eqref{eq:9} é às vezes conhecido
    como o \textit{espaço das arestas de~$G$} e é denotado~$C_1(G)$}

\item Verifique os seguintes fatos.
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$A\in\FF^{R\times C}$ uma matriz e $\{C_1,C_2\}$ uma
    partição de~$C$, isto é, $C=C_1\cup C_2$, $C_1\cap
    C_2=\emptyset$ e~$C_1\neq\emptyset$ e~$C_2\neq\emptyset$.
    Sejam~$A_1\in\FF^{R\times C_1}$ e~$A_2\in\FF^{R\times C_2}$ as
    matrizes naturalmente definidas por~$A$ por restrição (por
    exemplo, $A_1(r,c)=A(r,c)$ para todo~$(r,c)\in R\times C_1$).
    Seja~$\bfv\in\FF^C$ e defina~$\bfv_1\in\FF^{C_1}$
    e~$\bfv_2\in\FF^{C_2}$ de forma análoga.  Prove que
    $A\bfv=A_1\bfv_1+A_2\bfv_2$.  Uma forma intuitiva de se entender
    esse fato é escrever algo como
    \begin{equation}
      \label{eq:11}
      A\bfv=\begin{bmatrix}
        A_1\,\big|\,A_2
      \end{bmatrix}
      \begin{bmatrix}
        \bfv_1\\
        \rule[2pt]{1.2em}{.5pt}\\
        \bfv_2
      \end{bmatrix}
      =
      A_1\bfv_1+A_2\bfv_2
    \end{equation}
    ou simplesmente
    \begin{equation}
      \label{eq:11a}
      A\bfv=\begin{bmatrix}
        A_1 \hskip3pt A_2
      \end{bmatrix}
      \begin{bmatrix}
        \bfv_1\\
        \bfv_2
      \end{bmatrix}
      =
      A_1\bfv_1+A_2\bfv_2
    \end{equation}
  \item Sejam~$A$, $\bfv$, $C_1$ e~$C_2$, $A_1$ e~$A_2$ e~$\bfv_1$
    e~$\bfv_2$ como acima.  Suponha agora que $\{R_1,R_2\}$ seja uma
    partição de~$R$.  Sejam $A_{ij}\in\FF^{R_i\times C_j}$ para
    todo~$i$ e~$j$ definidos por restrição de~$A$.  Prove que
    $A\bfv=\bfu_1\cup\bfu_2$, onde $\bfu_1=A_{11}\bfv_1+A_{12}\bfv_2$,
    $\bfu_2=A_{21}\bfv_1+A_{22}\bfv_2$ e você precisa encontrar a
    interpretação correta para a união $\bfu_1\cup\bfu_2$.  Uma forma
    intuitiva de se entender esse fato é escrever algo como
    \begin{equation}
      \label{eq:11b}
      A\bfv=\begin{bmatrix}
              A_{11} &A_{12} \\
              A_{21} &A_{22}
      \end{bmatrix}
      \begin{bmatrix}
        \bfv_1\\
        \bfv_2
      \end{bmatrix}
      =
      \begin{bmatrix}
        A_{11}\bfv_1+A_{12}\bfv_2\\
        A_{21}\bfv_1+A_{22}\bfv_2
      \end{bmatrix}.
    \end{equation}
  \item Nos itens anteriores, podemos substituir~$\bfv$ por uma
    matriz~$B\in\FF^{C\times D}$ e considerar uma partição
    $\{D_1,D_2\}$ de~$D$.  Interprete adequadamente e verifique a
    identidade 
    \begin{equation}
      \label{eq:12}
      AB=\begin{bmatrix}
              A_{11} &A_{12} \\
              A_{21} &A_{22}
      \end{bmatrix}
      \begin{bmatrix}
        B_{11} &B_{12}\\
        B_{21} &B_{22}
      \end{bmatrix}
      =
      \begin{bmatrix}
        A_{11}B_{11}+A_{12}B_{21} &A_{11}B_{12}+A_{12}B_{22}\\
        A_{21}B_{11}+A_{22}B_{21} &A_{21}B_{12}+A_{22}B_{22}
      \end{bmatrix}.
    \end{equation}
  \end{enumerate}

\item Como de usual, sejam~$R$ e~$C$ conjuntos de índices que indexam
  as linhas e colunas de matrizes.  Suponha que~$R\subset C$ e
  seja~$C'=C\setminus R$ de forma que $C=R\cup C'$.  Seja
  $H\in\FF^{R\times C}$ com o seguinte formato especial:
  $H_1\in\FF^{R\times R}$ obtido por restrição de~$H$ é a matriz
  identidade~$I_R\in\FF^{R\times R}$.  Intuitivamente,
  \begin{equation}
    \label{eq:10}
    H=
    \begin{bmatrix}
      I_R\hskip4pt M
    \end{bmatrix}
  \end{equation}
  onde~$M$ é uma matriz em~$\FF^{R\times C'}=\FF^{R\times(C\setminus
    R)}$.  Seja
  \begin{equation}
    \label{eq:14}
    G=
    \begin{bmatrix}
      -M\\
      I_{C'}
    \end{bmatrix}\in\FF^{C\times C'},
  \end{equation}
  onde $I_{C'}\in\FF^{C'\times C'}$ é a matriz identidade.
  \begin{enumerate}[label=\rmlabel]
  \item Calcule~$HG$.
  \item Prove que 
    \begin{equation}
      \label{eq:13}
      \Null H=\Span\{G_{*c}\:c\in C'\},
    \end{equation}
    onde $G_{*c}\in\FF^C$ é a $c$-ésima coluna de~$G$ para todo~$c\in C'$.
    \setcounter{MaxMatrixCols}{20}
  \item Seja
    \begin{equation}
      \label{eq:15}
      H=
      \begin{bmatrix}
        0 &0 &0 &0 &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 &1\\
        0 &0 &0 &1 &1 &1 &1 &0 &0 &0 &0 &1 &1 &1 &1\\
        0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1\\
        1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1
      \end{bmatrix}\in\GF(2)^{4\times15}
    \end{equation}
    Encontre uma matriz~$G$ tal que $\Null H$ é o espaço gerado pelas
    colunas de~$G$.  \NB{Tal matriz~$G$ é meio grande, mas ela não é
      muito densa e com um pouco de paciência você consegue escrevê-la
      explicitamente.}
  \end{enumerate}\datedue{13/10/2022}

\item\label{E:40} Sejam $\bfv_1,\dots,\bfv_n\in\FF^m$ vetores e
  seja~$M=[\bfv_1\mid\dots\mid\bfv_n]\in\FF^{m\times n}$ a matriz
  cujas colunas são os~$\bfv_i$.  Suponha que exista uma matriz
  $N\in\FF^{n\times m}$ tal que $NM=I_n$, onde~$I_n\in\FF^{n\times n}$
  é a matriz identidade~$n\times n$.  Prove que os~$\bfv_i$
  ($1\leq i\leq n$) são linearmente independentes.

\item Fixe um inteiro~$n\geq3$ e seja~$R=\{1,\dots,n\}$.  Para
  todo~$1\leq i<n$, seja $\bff_i=\dsone_{\{i,i+1\}}$, e seja
  $\bff_n=\dsone_{\{1,n\}}$ (isto é, estamos considerando as funções
  características dos conjuntos $\{1,2\}$, $\{2,3\}$, \dots,
  $\{n-1,n\}$ e $\{n,1\}$).
  \begin{enumerate}[label=\rmlabel]
  \item Suponha que estamos trabalhando sobre~$\GF(2)$.  Mostre que os
    vetores $\bff_i$ ($1\leq i\leq n$) são linearmente dependentes
    sobre~$\GF(2)$.
  \item Suponha agora que~$n$ seja par e que estamos agora trabalhando
    sobre os números reais~$\RR$.  Mostre que os vetores $\bff_i$
    ($1\leq i\leq n$) são linearmente dependentes sobre~$\RR$.
  \item Suponha agora que~$n$ seja ímpar.  Mostre que os vetores
    $\bff_i$ ($1\leq i\leq n$) são linearmente independentes
    sobre~$\RR$.  \hint{Observe, por exemplo, que
      \begin{equation}
        \label{eq:16}
        \begin{bmatrix*}[r]
          1 &1 &-1\\
          -1 &1 &1\\
          1 &-1 &1
        \end{bmatrix*}
        \begin{bmatrix}
          1 &0 &1\\
          1 &1 &0\\
          0 &1 &1
        \end{bmatrix}
        =2I_3
      \end{equation}
      e
      \begin{equation}
        \begin{bmatrix*}[r]
          1 & 1 &-1 & 1 &-1\\
         -1 & 1 & 1 &-1 & 1\\
          1 &-1 & 1 & 1 &-1\\
         -1 & 1 &-1 & 1 & 1\\
          1 &-1 & 1 &-1 & 1
        \end{bmatrix*}
        \begin{bmatrix}
          1 &0 &0 &0 &1\\
          1 &1 &0 &0 &0\\
          0 &1 &1 &0 &0\\
          0 &0 &1 &1 &0\\
          0 &0 &0 &1 &1
        \end{bmatrix}
        =2I_5.
      \end{equation}
      Generalize e use o resultado do Exercício~\ref{E:40}.}
  \end{enumerate}\datedue{13/10/2022}

\item (\textit{M}) Lembre que~$\RR$ é um espaço vetorial sobre o corpo
  dos números racionais~$\QQ$ (veja o Exercício~\ref{E:15}).  Prove
  que~$\sqrt2$ e~$\sqrt3$ são linearmente independentes sobre~$\QQ$.
  Generalize (você pode considerar valores diferentes de~$2$ e~$3$ e
  pode também considerar mais de dois valores).

\item\begin{enumerate}[label=\rmlabel]
  \item Encontre dois vetores em~$\CC^2$ que são linearmente
    independentes sobre~$\RR$, mas que são linearmente dependentes
    sobre~$\CC$.
  \item Sejam $\bfv_1,\dots,\bfv_n$ vetores em~$\RR^N$ que são
    linearmente independentes sobre~$\RR$.  Prove que eles são
    linearmente independentes sobre~$\CC$.
  \end{enumerate}
  
\item Senhor Cético não acredita que \textit{Lights Out} no tabuleiro
  $20\times20$ sempre tem solução.  Como você pode convencê-lo desse
  fato?  Sr.~C está disposto a verificar soluções de instâncias
  específicas de \textit{Lights Out} (ele tem um programa que verifica
  a correção de soluções apresentadas a ele), mas não está disposto a
  muito mais que isso.  Por outro lado, Sr.~C tem acesso a um gerador
  de bits aleatórios e ele acredita que eventos com probabilidade
  menor ou igual a~$1/2^{70}\approx10^{-21}$ não acontecem (a idade do
  universo é algo como $5\times10^{17}$ segundos).

\item\label{E:odd_town} Seja~$X$ um conjunto finito.
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:odd_town.i} Suponha que $\cF\subset\cP(X)$ seja uma
    família de subconjuntos de~$X$ tal que (\textit{a})~$|F|$ é ímpar
    para todo~$F\in\cF$ e (\textit{b})~$|F\cap F'|$ é par para
    quaisquer dois~$F$ e~$F'$ membros distintos de~$\cF$.  Prove
    que~$\cF$ tem no máximo~$|X|$ membros.  \hint{Considere as funções
      características~$\dsone_F\in\GF(2)^X$ dos membros de~$\cF$.}
  \item Encontre uma família~$\cF$ como em~\ref{it:odd_town.i} acima
    com~$|\cF|=|X|$.
  \item Encontre uma família~$\cF\subset\cP(X)$ tal que $|F\cap F'|$ é
    par para quaisquer dois~$F$ e~$F'$ membros de~$\cF$ com
    $|\cF|\geq2^{\lfloor|X|/2\rfloor}$.
  \end{enumerate}

\item Seja~$p$ um primo e~$X$ um conjunto finito.
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:p_town.i} Suponha que $\cF\subset\cP(X)$ seja uma
    família de subconjuntos de~$X$ tal que
    (\textit{a})~$|F|\not\equiv0\pmod p$ para todo~$F\in\cF$ e
    (\textit{b})~$|F\cap F'|\equiv0\pmod p$ para quaisquer dois~$F$ e~$F'$
    membros distintos de~$\cF$.  Prove que~$\cF$ tem no máximo~$|X|$
    membros.
  \item Encontre uma família~$\cF$ como em~\ref{it:p_town.i} acima
    com~$|\cF|=|X|$.
  \item Encontre uma família~$\cF\subset\cP(X)$ tal que
    $|F\cap F'|\equiv0\pmod p$ para quaisquer dois~$F$ e~$F'$ membros
    de~$\cF$ com $|\cF|\geq2^{\lfloor|X|/p\rfloor}$.
  \end{enumerate}

\item Seja~$V$ um espaço vetorial.  Prove que valem as seguintes
  afirmações:
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$S\subset V$ um conjunto \textit{gerador minimal}, isto
    é, tal que $\Span S=V$, mas tal que, para todo~$S'\subset S$
    com~$S'\neq S$, vale que $\Span S'\neq V$.  Prove que~$S$ é uma
    base de~$V$.
  \item Seja~$S\subset V$ um conjunto \textit{linearmente independente
      maximal}, isto é, tal que~$S$ é linearmente independente, mas
    tal que, para todo~$S'\subset V$ com $S\subset S'$ e~$S\neq S'$,
    vale que~$S'$ não é linearmente independente.  Prove que~$S$ é uma
    base de~$V$.
  \end{enumerate}\datedue{20/10/2022}

\item\label{E:48} Dizemos que um grafo~$G$ é uma \textit{árvore} se
  ele for \textit{acíclico} (não contém circuitos) e \textit{conexo}
  (para quaisquer dois vértices~$x$ e~$y$ em~$G$, há um
  $(x,y)$-caminho em~$G$).  Prove que as seguintes asserções são
  equivalentes para um grafo~$G=(V,E)$:
  \begin{enumerate}[label=\rmlabel]
  \item $G$ é uma árvore.
  \item (Unicidade dos caminhos) Para quaisquer vértices~$x$ e~$y$
    de~$G$, existe um único $(x,y)$-caminho em~$G$.
  \item (Minimalmente conexo) $G$ é conexo, e a remoção de qualquer
    aresta de~$G$ resulta em um grafo desconexo, isto é,
    $(V,E\setminus\{e\})$ é desconexo para qualquer~$e\in E$.
  \item (Maximalmente acíclico) $G$ não contém circuitos, mas a adição
    de qualquer nova aresta $f\subset V$ a~$G$ resulta em um grafo que
    contém um circuito, isto é, $(V,E\cup\{f\})$ contém um circuito
    para qualquer $f\in{V\choose2}\setminus E$.
  \item $G$ é conexo e $|E|=|V|-1$.
  \end{enumerate}

\item\label{E:49} Seja~$G=(V,E)$ um grafo conexo, isto é, tal que para
  todo~$x$ e~$y\in V$, existe um $(x,y)$-caminho em~$G$.  Lembre que o
  \textit{espaço das arestas} de~$G$ é
  \begin{equation}
    \label{eq:18}
    C_1(G)=\Span\{\dsone_e\:e\in E\}\subset\GF(2)^V.
  \end{equation}
  Note que aqui estamos trabalhando sobre~$\GF(2)$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que
    \begin{equation}
      \label{eq:26}
      C_1(G)=\Span\big\{\dsone_{\{x,y\}}\:x,\,y\in V\text{ e }x\neq
      y\big\}. 
    \end{equation}
  \item Prove que $F\subset E$ é tal que
    $\Span\{\dsone_f\:f\in F\}=C_1(G)$ se e só se o grafo~$(V,F)$ é
    conexo.
  \item Prove que $F\subset E$ é tal que os vetores~$\dsone_f$
    ($f\in F$) são linearmente independentes se e só se o
    grafo~$(V,F)$ é acíclico.
  \item Deduza que $\dsone_f$ ($f\in F$) formam uma base de~$C_1(G)$
    se e só se~$F$ é tal que~$(V,F)$ é uma árvore.
  \item Prove que a dimensão de~$C_1(G)$ é $n-1$, onde~$n$ é o número
    de vértices em~$G$.
  \item Qual é a dimensão de~$C_1(G)$ quando~$G$ tem~$k$ componentes
    conexas?  ($G$~tem $k$~componentes conexas se~$G$ é a união
    disjunta de $k$~grafos conexos.)
  \end{enumerate}  
  \hint{Revise o Exercício~\ref{E:36}.}

\item\label{E:50} Sejam $A\in\FF^{P\times Q}$ e $B\in\FF^{R\times S}$
  duas matrizes.  Definimos a matriz
  $A\otimes B\in\FF^{(P\times R)\times(Q\times S)}$ como a matriz com
  entradas
  \begin{equation}
    \label{eq:17}
    (A\otimes B)\big((p,r),(q,s)\big)=A(p,q)B(r,s)
  \end{equation}
  para todo~$\big((p,r),(q,s)\big)\in(P\times Q)\times(R\times S)$.
  Mais intuitivamente, suponha que
  \begin{equation}
    \label{eq:19}
    A=
    \begin{bmatrix}
      a_{11}&\dots&a_{1n}\\
      \vdots&\ddots&\vdots\\
      a_{m1}&\dots&a_{mn}
    \end{bmatrix}.
  \end{equation}
  Então
  \begin{equation}
    \label{eq:20}
    A\otimes B=
    \begin{bmatrix}
      a_{11}B&\dots&a_{1n}B\\
      \vdots&\ddots&\vdots\\
      a_{m1}B&\dots&a_{mn}B
    \end{bmatrix}.
  \end{equation}
  Sejam agora $H_1,H_2,\dots$ matrizes com entradas em~$\{-1,1\}$
  dadas por
  \begin{equation}
    \label{eq:21}
    H_1=
    \begin{bmatrix*}[r]
      1&1\\
      1&-1
    \end{bmatrix*}
  \end{equation}
  e, para todo~$n\geq2$,
  \begin{equation}
    \label{eq:22}
    H_n=H_1\otimes H_{n-1}.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Calcule $H_2$ e~$H_3$.
  \item Quantas linhas e quantas colunas tem~$H_n$?
  \item Calcule~$H_n^2$ para todo~$n$.
  \end{enumerate}

\item Considere as matrizes~$H_n$ ($n\geq1$) do Exercício~\ref{E:50}.
  Sejam~$\bfv_1,\dots,\bfv_N\in\{-1,1\}^N$ as~$N$ colunas de~$H_n$, de
  forma que
  \begin{equation}
    \label{eq:23}
    H_n=[\bfv_1\mid\dots\mid\bfv_N].
  \end{equation}
  Prove que os~$\bfv_i$ ($1\leq i\leq N$) formam uma base de~$\FF^N$
  para $\FF=\RR$ e~$\FF=\CC$, isto é, prove que eles geram~$\FF^N$ e
  que eles são linearmente independentes sobre~$\FF$.  Esses vetores
  são uma base de~$\GF(2)^N$?  \datedue{20/10/2022}

\item Responda e justifique:
  \begin{enumerate}[label=\rmlabel]
  \item Qual é a dimensão do espaço vetorial das matrizes
    $\{M\:M\in\FF^{R\times C}\}$ sobre~$\FF$?
  \item Qual é a dimensão do espaço vetorial das \textit{matrizes
    simétricas}
    \begin{equation}
      \label{eq:24}
      \{M\:M\in\FF^{S\times S}\text{ tal que }M=M^\top\}
    \end{equation}
    sobre~$\FF$?
  \item Qual é a dimensão do espaço vetorial das \textit{matrizes
    antissimétricas}
    \begin{equation}
      \label{eq:24b}
      \{M\:M\in\FF^{S\times S}\text{ tal que }M=-M^\top\}
    \end{equation}
    sobre~$\FF$?
  \end{enumerate}
  
\item (\textit{M}) Considere~$\RR$ como um espaço vetorial
  sobre~$\QQ$.  Prove que a dimensão desse espaço é infinito.  Prove
  que essa dimensão não é nem enumerável.
  
\item
  %Neste exercício, trabalhamos sobre~$\CC$.  Em particular,
  %$\bfi=\sqrt{-1}$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que, para todo inteiro~$n\geq0$, temos
    \begin{equation}
      \label{eq:25}
      \sum_{0\leq i<n}x^i={1-x^n\over1-x}.
    \end{equation}
  \item Fixe~$n\geq1$ e seja $\omega=\ee^{2\pi\bfi/n}$,
    onde~$\bfi=\sqrt{-1}$.  Seja~$S=\{0,1,\dots,n-1\}$ e considere a
    matriz $F_n\in\CC^{S\times S}$ tal que $F_n(i,j)=\omega^{ij}$ para
    todo~$i$ e~$j$ em~$S$.
    Calcule~$F_2$, $F_3$ e~$F_4$ explicitamente.
  \item Considere a matriz~$G_n\in\CC^{S\times S}$ tal
    que~$G_n(i,j)=\omega^{-ij}$ para todo~$i$ e~$j$ em~$S$.
    Calcule~$G_nF_n$ e~$F_nG_n$ para todo~$n\geq1$.
  \item Sejam~$\bfv_0,\dots,\bfv_{n-1}\in\CC^S$ as~$n$ colunas
    de~$F_n$, de forma que
    \begin{equation}
      \label{eq:F_n}
      F_n=[\bfv_0\mid\dots\mid\bfv_{n-1}].
    \end{equation}
    Prove que os~$\bfv_i$ ($0\leq i<n$) formam uma base
    de~$\CC^S$.  Prove o mesmo para as colunas de~$G_n$.
  \end{enumerate}
  \datedue{27/10/2022}
  
\item Sejam~$V$ e~$W$ espaços vetoriais sobre~$\FF$.
  Seja~$S=\{\bfv_1,\dots,\bfv_n\}$ um conjunto de~$n$ vetores
  linearmente independentes de~$V$ e seja $\phi\:S\to W$ uma função
  qualquer.
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:55.i} Prove que existe uma função linear
    $f\:\Span S\to W$ tal que $f(\bfv_i)=\phi(\bfv_i)$ para todo
    $1\leq i\leq n$.
  \item Prove que~$f$ como em~\ref{it:55.i} acima é única.
  \end{enumerate}
  \datedue{3/11/2022}

\item Seja~$G=(V,E)$ um grafo conexo.  Suponha que as arestas de
  conjunto $F\subset E$ \textit{formem uma árvore geradora} de~$G$,
  isto é, que~$F$ seja tal que~$(V,F)$ é uma árvore (veja os
  Exercícios~\ref{E:48} e~\ref{E:49}).  Seja~$A\subset E$ um conjunto
  acíclico (isto é, tal que~$(V,A)$ não contém circuitos).  Prove que
  existe~$F'\subset F$ tal que as arestas em $A\cup F'$ formam uma
  árvore geradora de~$G$.  

\item Seja~$S$ um conjunto de vetores de~$\FF^D$ com~$D$ finito.
  Definimos o \textit{posto} de~$S$ como sendo $\dim\Span S$.  Prove
  que o posto de~$S$ é
  \begin{equation}
    \label{eq:28}
    \max\{|T|\:T\subset S\text{ com $T$ linearmente independente}\}.
  \end{equation}

\item Denotemos o posto de uma matriz~$M$ por~$\posto M$.
  \begin{enumerate}[label=\rmlabel]
  \item Sejam~$A\in\FF^{R\times S}$ e~$B\in\FF^{S\times T}$ matrizes.
    Prove que
    \begin{equation}
      \label{eq:27}
      \posto(AB)\leq\min\{\posto A,\posto B\}.
    \end{equation}
  \item Suponha que $A\in\FF^{m\times n}$ e $B\in\FF^{n\times m}$ são
    tais $AB=I_m$ e $BA=I_n$, onde~$I_m$ e $I_n$ são as matrizes
    identidade.  Prove que~$m=n$.
  \item Suponha que~$M\in\FF^{m\times n}$ seja inversível.  Prove
    que $m=n$.
  \end{enumerate}
  \datedue{3/11/2022}

\item Seja~$I_n\in\FF^{n\times n}$ a matriz identidade.
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$A\in\FF^{n\times n}$ uma matriz com $\posto A=n$.  Prove
    que existe uma única matriz~$Q\in\FF^{n\times n}$ tal que
    $AQ=I_n$.
  \item Seja~$B\in\FF^{n\times n}$ uma matriz com $\posto B=n$.  Prove
    que existe uma única matriz~$P\in\FF^{n\times n}$ tal que
    $PB=I_n$.
  \item Seja~$M\in\FF^{n\times n}$ uma matriz com $\posto M=n$.  Prove
    que existe uma única matriz $N\in\FF^{n\times n}$ tal que
    $NM=MN=I_n$.
  \end{enumerate}
  \datedue{3/11/2022}
  
\item (\textit{M}) Lembre que~$\RR$ é um espaço vetorial sobre~$\QQ$
  (veja o Exercício~\ref{E:15}).  Seja $f\:\RR\to\RR$ uma função
  linear, com~$\RR$ sendo considerado como um espaço vetorial
  sobre~$\QQ$ (isto é, $f$~preserva somas e~$f$ é $\QQ$-linear:
  $f(\alpha r)=\alpha f(r)$ para todo~$\alpha\in\QQ$ e~$r\in\RR$).  É
  verdade que~$f$ é contínua?  É verdade que~$f$ é contínua
  em~$0\in\RR$?
  
\item Suponha que sorteamos $\bfa_i\in\GF(2)^n$ uniformemente ao acaso
  para todo~$1\leq i\leq n$, independentemente.  Prove que o valor
  esperado do posto da coleção de vetores $\bfa_1,\dots,\bfa_n$ é
  maior que $n-1$.

\item Sejam~$U$ e~$W$ subespaços complementares em~$V$, de forma que
  $V=U\oplus W$.  Prove que, para todo~$\bfv\in V$, existem~$\bfu\in
  U$ e~$\bfw\in W$ tais que $\bfv=\bfu+\bfw$ e que esses
  vetores~$\bfu$ e~$\bfw$ são únicos.

\item Sejam~$U$ e~$V$ espaços vetoriais e seja $f\:U\to V$ uma função
  linear.  Vimos que existe um subespaço~$U^*$ de~$U$ tal que
  $U=U^*\oplus\Ker f$.  Tal subespaço~$U^*$ é sempre único?  Pode
  existir um subespaço~$U^{**}$ tal que $U=U^{**}\oplus\Ker f$ e
  $\dim U^{**}\neq\dim U^*$?  \datedue{10/11/2022}
  
\item\label{E:64} Sejam~$U$ e~$V$ espaços vetoriais e seja $f\:U\to V$
  uma função linear.  Seja~$\sim$ a relação definida sobre~$U$ tal
  que, para quaisquer~$\bfu$ e~$\bfu'$ em~$U$, temos $\bfu\sim\bfu'$
  se e só se~$\bfu-\bfu'\in\Ker f$.  Prove que~$\sim$ é uma relação de
  equivalência.
  
\item\label{E:65} (Continuação de~\ref{E:64})\, Para~$\bfu\in U$,
  seja~$[\bfu]$ a classe de equivalência de~$\bfu$ relativa à
  relação~$\sim$\,:
  \begin{equation}
    \label{eq:29}
    [\bfu]=\{\bfu'\in U\:\bfu'\sim\bfu\}.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que, para todo~$\bfu\in U$, temos
    \begin{equation}
      \label{eq:32}
      [\bfu]=\bfu+\Ker f.
    \end{equation}
  \item Seja
    \begin{equation}
      \label{eq:30}
      U/{\sim}=\big\{[\bfu]\:\bfu\in U\big\}.
    \end{equation}
    Lembre que existe~$U^*$ subespaço de~$U$ tal que
    $U=U^*\oplus\Ker f$.  Considere a função $\pi\:U^*\to U/{\sim}$
    tal que $\pi(\bfu)=[\bfu]$ para todo~$\bfu\in U^*$.  Prove
    que~$\pi$ é uma bijeção.
  \end{enumerate}
  \datedue{10/11/2022}

\item (Continuação de~\ref{E:65})\, Existe uma forma natural de se
  definir soma e produto por escalar em~$U/{\sim}$ que tornam
  $U/{\sim}$ um espaço vetorial\,: $[\bfu]+[\bfu']=[\bfu+\bfu']$ e
  $\alpha[\bfu]=[\alpha\bfu]$ para quaisquer $\bfu$ e~$\bfu'$ em~$U$
  e~$\alpha$ escalar (é necessário verificar (exercício) que essas
  operações estão bem definidas, pois elas estão sendo definidas em
  termos de representantes de classe, e precisamos provar que estas
  definições não dependem dos representantes escolhidos).  Prove que a
  função~$\pi$ do Exercício~\ref{E:65} é linear.  Conclua que a função
  \begin{equation}
    \label{eq:31}
    f^*\circ\pi^{-1}\:U/{\sim}\to\Im f
  \end{equation}
  é linear e bijetora.  Aqui, $f^*\:U^*\to\Im f$ é a função tal que
  $f^*(\bfu)=f(\bfu)$ para todo $\bfu\in U^*$.  \NB{Este exercício diz
    que o espaço quociente $U/{\sim}$ é isomorfo ao espaço $\Im f$.}
  
\item Lembre-se do Exercício~\ref{E:odd_town}.  Seja~$X$ um conjunto
  finito, e suponha que~$\cF\subset\cP(X)$ é tal que $|F\cap F'|$ é
  par para quaisquer dois~$F$ e~$F'$ membros de~$\cF$.  Prove que
  $|\cF|\leq2^{\lfloor|X|/2\rfloor}$.  \hint{Considere
    $U=\big\{\dsone_F\in\GF(2)^X\:F\in\cF\big\}$ e seu
    aniquilador~$U^\circ$.}

\item Dadas uma matrix~$A\in\RR^{m\times n}$ e um vetor~$\bfb\in\RR^m$,
  seja $\Sol(A,\bfb)=\{\bfx\in\RR^n\:A\bfx=\bfb\}$.  Para cada uma das
  afirmações abaixo, prove a afirmação ou prove que não existem os
  objetos descritos.
  \begin{enumerate}[label=\rmlabel]
  \item Exitem uma matriz escalonada~$U\in\RR^{3\times4}$
    e~$\bfb\in\RR^3$ tais que $\Sol(U,\bfb)$ é vazio.
  \item Existem uma matriz escalonada~$U\in\RR^{3\times4}$
    e~$\bfb\in\RR^3$ tais que $\Sol(U,\bfb)$ tem exatamente um
    elemento. 
  \item Existem uma matriz escalonada~$U\in\RR^{3\times4}$
    e~$\bfb\in\RR^3$ tais que $\Sol(U,\bfb)$ tem infinitos elementos. 
  \end{enumerate}
  \datedue{1/12/2022}

\item No que segue, escrevemos~$[m]$ para o conjunto $\{1,2,\dots,m\}$
  para qualquer inteiro~$m$.  Seja $\sigma\:[m]\to[m]$ uma bijeção.
  Seja~$P_\sigma=(a_{ij})$ a matriz $m\times m$ tal que, para todo
  $i\in[m]$,
  \begin{equation}
    \label{eq:33}
    a_{ij}=
    \begin{cases}
      1 &\text{se $j=\sigma(i)$}\\
      0 &\text{caso contrário.}
    \end{cases}
  \end{equation}
  Seja $A\in\FF^{m\times n}$ uma matriz.
  \begin{enumerate}[label=\rmlabel]
  \item Descreva a matriz~$P_\sigma A$ em termos das linhas de~$A$.
    Isto é, pense em~$A$ da seguinte forma:
    \begin{equation}
      \label{eq:34}
      A=
      \begin{bmatrix}
        A_{1*}\\
        A_{2*}\\
        \vdots\\
        A_{m*}
      \end{bmatrix}, 
    \end{equation}
    onde $A_{i*}$ é a $i$-ésima linha de~$A$, e descreva~$P_\sigma A$
    em termos dos $A_{i*}$.
  \item Suponha agora que temos uma bijeção $\tau\:[n]\to[n]$.
    Pensemos agora em~$A$ em termos de suas colunas:
    \begin{equation}
      \label{eq:34b}
      A=
      \begin{bmatrix}
        A_{*1} &A_{*2} &\dots &A_{*n}
      \end{bmatrix}, 
    \end{equation}
    onde $A_{*j}$ é a $j$-ésima coluna de~$A$.  Defina uma matriz
    $Q_\tau$ parecida com a matriz~$P_\sigma$ acima de forma que
    \begin{equation}
      \label{eq:34c}
      AQ_\tau=
      \begin{bmatrix}
        A_{*\tau(1)} &A_{*\tau(2)} &\dots &A_{*\tau(n)}
      \end{bmatrix}. 
    \end{equation}
  \end{enumerate}
  
\item Considere a matriz
  \begin{equation}
    \label{eq:35}
    A=
    \begin{bmatrix*}[r]
      0 &2 &4 &2 &8 \\
      2 &1 &0 &5 &4 \\
      4 &1 &2 &4 &2 \\
      5 &0 &0 &2 &8
    \end{bmatrix*},
  \end{equation}
  que ocorre no Exemplo~7.3.3 de~\textbf{PNK}.
  \begin{enumerate}[label=\rmlabel]
  \item Continue o processo de escalonamento de~$A$ naquele exemplo,
    para obter a matriz escalonada
    \begin{equation}
      \label{eq:36}
      U=
      \begin{bmatrix*}[c]
        2 &1 &0 &5 &4\\
        0 &2 &4 &2 &8 \\
        0 &0 &4 &-5 &-2\\
        0 &0 &0 &-1.75 &10.5
      \end{bmatrix*}.
    \end{equation}
    Descreva claramente os passos (adicionais) que você executou para
    completar esse escalonamento.  
  \item Encontre um matriz inversível~$M$ tal que~$MA=U$.
  \item Monte agora a matriz
    \begin{equation}
      \label{eq:37}
      A'=
      \begin{bmatrix}
        A &I
      \end{bmatrix},
    \end{equation}
    com~$4$ linhas e~$9$ colunas, onde~$I$ é a matriz
    identidade~$4\times4$.  Execute novamente os passos do processo de
    escalonamento que levam~$A$ a~$U$, mas agora na matriz~$A'$ (por
    exemplo, o primeiro passo é multiplicar a segunda linha por~$-2$ e
    somar o resultado à terceira linha; você deve executar exatamente
    o mesmo processo com a matriz `estendida'~$A'$ no primeiro passo
    do processo).  Ao terminar este processo, você terá uma matriz da
    forma
    \begin{equation}
      \label{eq:37b}
      U'=
      \begin{bmatrix}
        U &B
      \end{bmatrix},
    \end{equation}
    onde~$B$ é uma certa matriz $4\times4$.  É natural que a `primeira
    parte' de~$U'$ seja~$U$, pois executamos exatamente o mesmo
    processo de escalonamento.  Entretanto, o que você obteve
    como~$B$?  

  \item Explique por que o fato que você observou no item anterior não
    é coincidência, e de fato sempre ocorre.  \NB{Note que isto dá um
      bom algoritmo para se obter~$M$.}
  \end{enumerate}
  \datedue{1/12/2022}

\item Seja~$\bfa\in\RR^n$ um vetor não-nulo.  Para
  cada~$\bfb\in\RR^n$, sabemos que há uma decomposição da forma
  $\bfb=\bfb^{\parallel\bfa}+\bfb^{\perp\bfa}$ tal que
  $\bfb^{\parallel\bfa}\in\Span\{\bfa\}$ e
  $\langle\bfb^{\perp\bfa},\bfa\rangle=0$ e essa decomposição é única.
  Prove que a aplicação $f\:\RR^n\to\RR^n$ dada por
  $f(\bfb)=\bfb^{\parallel\bfa}$ para todo~$\bfb\in\RR^n$ é linear.
  \sugestao{Considere a matriz $M=\|\bfa\|^{-2}\bfa\bfa^\top$.  Note
    que~$M$ é uma matriz $n\times n$ (aqui seguimos a convenção
    que~$\bfa$ é um vetor coluna).  Calcule $M\bfb$.}

\item Sejam~$\bfa$ e~$\bfb$ dois vetores em~$\RR^n$.  Prove a
  \textit{desigualdade de Cauchy e Schwarz}:
  \begin{equation}
    \label{eq:39}
    |\<\bfa,\bfb\>|\leq\|\bfa\|\|\bfb\|.
  \end{equation}
  Prove que vale a igualdade em~\eqref{eq:39} somente quando~$\bfb$ é
  múltiplo de~$\bfa$ ou vice-versa.  Deduza a \textit{desigualdade
    triangular}:
  \begin{equation}
    \label{eq:39b}
    \|\bfa+\bfb\|\leq\|\bfa\|+\|\bfb\|.
  \end{equation}
  Prove que vale a igualdade em~\eqref{eq:39b} somente quando~$\bfb$ é
  múltiplo de~$\bfa$ ou vice-versa.  \sugestao{Para
    provar~\eqref{eq:39}, deduza de
    $\bfb=\bfb^{\parallel\bfa}+\bfb^{\perp\bfa}$ que
    $\|\bfb\|^2=\|\bfb^{\parallel\bfa}\|^2+\|\bfb^{\perp\bfa}\|^2
    \geq\|\bfb^{\parallel\bfa}\|^2$ e use esse fato.
    Para~\eqref{eq:39b}, comece lembrando que
    $\|\bfa+\bfb\|^2=\<\bfa+\bfb,\bfa+\bfb\>$.}
  
\item Seja $V$ um subespaço linear de~$\RR^n$ e seja~$\bfb\in\RR^n$.
  Suponha que
  \begin{equation}
    \label{eq:38}
    \bfb=\bfb_1^{\parallel V}+\bfb_1^{\perp V}
  \end{equation}
  e
  \begin{equation}
    \label{eq:38}
    \bfb=\bfb_2^{\parallel V}+\bfb_2^{\perp V},
  \end{equation}
  onde $\bfb_i^{\parallel V}\in V$ e $\bfb_i^{\perp V}$ é ortogonal
  a~$V$, para $i\in\{1,2\}$.  Prove que
  $\bfb_1^{\parallel V}=\bfb_2^{\parallel V}$ e
  $\bfb_1^{\perp V}=\bfb_2^{\perp V}$.  Em outras palavras, a
  decomposição de~$\bfb$ como projeção ortogonal sobre~$V$ e projeção
  ortogonal a~$V$ é única.
  
\item Sejam $\bfv_1,\dots,\bfv_k\in\RR^n$ vetores unitários mutualmente
  ortogonais.  Seja $M=\sum_{1\leq i\leq k}\bfv\bfv^\top$.  Note
  que~$M$ é uma matriz $n\times n$.  Seja
  $V=\Span\{\bfv_1,\dots,\bfv_k\}$ e, para todo $\bfb\in\RR^n$,
  considere a decomposição $\bfb=\bfb^{\parallel V}+\bfb^{\perp V}$
  com $\bfb^{\parallel V}\in V$ e $\bfb^{\perp V}$ ortogonal a~$V$.
  Prove que $M\bfb=\bfb^{\parallel V}$.  \datedue{10/12/2022}

\item Seja~$W$ um subespaço vetorial de~$\RR^n$.  Seja~$U$ um
  subespaço vetorial de~$W$, e seja~$U^\perp$ o complemento ortogonal
  de~$U$, isto é,
  \begin{equation}
    \label{eq:40}
    U^\perp=\{\bfw\in W\:\<\bfw,\bfu\>=0\text{ para todo~$\bfu\in
      U$}\}. 
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $U\subset(U^\perp)^\perp$.
  \item Prove que $\dim U+\dim U^\perp=\dim W$.
  \item Prove que $U=(U^\perp)^\perp$ usando um argumento de dimensão
    apropriado. 
  \end{enumerate}
  \NB{Como estamos usando o produto interno padrão
    $\<\bfx,\bfy\>=\bfx\cdot\bfy$, este exercício segue imediatamento
    de nosso estudo de aniquiladores.  Entretanto, é interessante
    fazer este exercício supondo que temos um produto interno abstrato
    (e não necessariamente o \textit{dot product}).}

\item Seja~$M$ uma matriz $n\times n$ triangular superior, com todos
  seus elementos diagonais iguais a~$1$.  Prove que~$M$ é inversível e
  que sua inversa~$M^{-1}$ é triangular superior, com todos seus
  elementos diagonais iguais a~$1$.

\item
  \begin{enumerate}[label=\rmlabel]
  \item Sejam~$\bfv_1$ e~$\bfv_2\in\RR^3$ dois vetores ortonormais,
    isto é, tais que $\<\bfv_1,\bfv_2\>=0$ e $\|\bfv_i\|=1$
    para~$i\in\{1,2\}$.  Seja $M=[\bfv_1\;\bfv_2]\in\RR^{3\times 2}$ a
    matriz cujas colunas são os vetores~$\bfv_i$.  Verifique que
    $M^\top M$ é uma matriz identidade.  Prove que $MM^\top$ não é uma
    matriz identidade.
  \item Sejam $\bfv_1,\dots,\bfv_n\in\RR^n$ vetores ortonormais, isto
    é, tais que $\<\bfv_i,\bfv_j\>=0$ para todo $i\neq j$ e
    $\|\bfv_i\|=1$ para todo~$i$.  Seja
    $M=[\bfv_1\,\dots\,\bfv_n]\in\RR^{n\times n}$ a matriz quadrada
    cujas colunas são os vetores~$\bfv_i$.  Verifique que
    $M^\top M=I_n$, onde~$I_n$ é a matriz identidade $n\times n$.
    Prove que $MM^\top=I_n$.  Em particular, $M^{-1}=M^\top$.
  \end{enumerate}
  \datedue{10/12/2022}
  
\item Seja~$A\in\RR^{m\times n}$ uma matriz cujas colunas são
  linearmente independentes.  Prove que $A^\top A$ é uma matriz
  inversível.  \hint{Prove que~$A$ pode ser escrita como um
    produto~$QR$ onde~$Q$ tem colunas ortonormais e~$R$ é uma matriz
    inversível.  Use esse fato.}  \datedue{10/12/2022}

\item Neste exercício, como de usual, consideramos o produto interno
  padrão do~$\RR^n$.  Dizemos que uma matriz~$A\in\RR^{n\times n}$
  \textit{preserva} o produto interno se, para todo~$\bfx$ e~$\bfy$
  em~$\RR^n$, vale que $\<A\bfx,A\bfy\>=\<\bfx,\bfy\>$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que se~$A$ é ortogonal, então~$A$ preserva o produto
    interno.
  \item Prove que se~$A$ é ortogonal, então~$A$ preserva a norma, isto
    é, para todo~$\bfx\in\RR^n$, vale que $\|A\bfx\|=\|\bfx\|$.
  \item Prove que se~$A$ preserva o produto interno, então~$A$
    é ortogonal.
  \item Prove que se~$A$ preserva a norma, então~$A$ é ortogonal.
  \end{enumerate}

\item Seja~$\FF$ um corpo infinito.  Suponha que $U_1,\dots,U_k$ sejam
  subespaços de~$\FF^n$ com $\dim U_i<n$ para todo~$i$.  Prove que
  $\bigcup_{1\leq i\leq k}U_i\neq\FF^n$.
  
\item Sejam $\bfb_1,\dots,\bfb_n$ vetores ortonormais em~$\RR^n$.
  Seja~$S\subset\{1,\dots,n\}$ e considere $V_S=\Span\{\bfb_i\:i\in
  S\}$. Suponha $S=\{i_1,\dots,i_s\}$ e considere
  \begin{equation}
    \label{eq:41}
    N=[\bfb_{i_1}\mid\dots\mid\bfb_{i_s}]\in\RR^{n\times s}.
  \end{equation}
  Seja~$M=NN^\top$.  Prove que, para todo~$\bfx\in\RR^n$, temos
  \begin{equation}
    \label{eq:42}
    \bfx^{\parallel V_S}=M\bfx,
  \end{equation}
  onde $\bfx^{\parallel V_S}$ é a projeção ortogonal de~$\bfx$
  sobre~$V_S$.
  
\item Sejam $\bfa_1,\dots,\bfa_t$ vetores em~$\RR^n$.  Dizemos esses
  vetores são \textit{quase-co-hiperplanares}, se existem
  $\bfa_1',\dots,\bfa_t'\in\RR^n$ e~$\bfx\in\RR^n\setminus\{\bfzero\}$
  tais que, para todo~$i$,
  \begin{equation}
    \label{eq:44}
    \|\bfa_i-\bfa_i'\|\leq10^{-10}\|\bfa_i\|
  \end{equation}
  e
  \begin{equation}
    \label{eq:45}
    \<\bfa_i',\bfx\>=0.
  \end{equation}
  Naturalmente, \eqref{eq:45}~significa que os~$\bfa_i'$ pertencem ao
  hiperplano ortogonal a~$\bfx$.  Grosso modo, os~$\bfa_i$
  ($1\leq i\leq t$) são quase-co-hiperplanares se uma `pequena
  perturbação'~$\bfa_i'$ deles são co-hiperplanares (pertencem a um
  mesmo subespaço de dimensão $n-1$ de~$\RR^n$).  Prove que os vetores
  da base canônica $\bfe_1,\dots,\bfe_n\in\RR^n$ são
  quase-co-hiperplanares se~$n\geq n_0$, onde~$n_0$ é uma constante
  absoluta.
\end{enumerate}

\endgroup
\end{document}

%%% Local Variables:
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode t)
%%% eval: (flyspell-mode t)
%%% TeX-master: t
%%% End:
