%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 20 Jan 2025 09:12:04pm -03 by yoshi on ponpoko>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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[mathlines]{lineno}
\usepackage{etoolbox} %% <- for \pretocmd, \apptocmd and \patchcmd

% Patch 'normal' math environment: (currently unused, but good to have)
\newcommand*\linenomathpatch[1]{%
   \expandafter\pretocmd\csname #1\endcsname {\linenomath}{}{}%
   \expandafter\pretocmd\csname #1*\endcsname{\linenomath}{}{}%
   \expandafter\apptocmd\csname end#1\endcsname {\endlinenomath}{}{}%
   \expandafter\apptocmd\csname end#1*\endcsname{\endlinenomath}{}{}%
 }
% Patch AMS math environment:
\newcommand*\linenomathpatchAMS[1]{%
    \expandafter\pretocmd\csname #1\endcsname {\linenomathAMS}{}{}%
    \expandafter\pretocmd\csname #1*\endcsname{\linenomathAMS}{}{}%
    \expandafter\apptocmd\csname end#1\endcsname {\endlinenomath}{}{}%
    \expandafter\apptocmd\csname end#1*\endcsname{\endlinenomath}{}{}%
}

%% Definition of \linenomathAMS depends on whether the mathlines option
%% is provided
\expandafter\ifx\linenomath\linenomathWithnumbers
\let\linenomathAMS\linenomathWithnumbers
%% The following line gets rid of an extra line numbers at the bottom:
\patchcmd\linenomathAMS{\advance\postdisplaypenalty\linenopenalty}{}{}{}
\else
\let\linenomathAMS\linenomathNonumbers
\fi

% \linenomathpatch{equation} %% <- unnecessary, equation is already patched
\linenomathpatchAMS{gather}
\linenomathpatchAMS{multline}
\linenomathpatchAMS{align}
\linenomathpatchAMS{alignat}
\linenomathpatchAMS{flalign}
\linenomathpatch{equation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\id{\mathop{\rm id}\nolimits}
\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\Row{\mathop{\rm Row}}
\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\bfj{\mathbf{j}}
\def\bfp{\mathbf{p}}
\def\bfq{\mathbf{q}}
\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\bfalpha{\boldsymbol\alpha}
\def\bfbeta{\boldsymbol\beta}
\def\bfgamma{\boldsymbol\gamma}
\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\}$}}
\let\duedate\datedue
\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 2024}}\\
  \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 mais matematicamente inclinados, e
não serão cobrados nessa disciplina.

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

\begin{enumerate}[label=\nlabelE]
  
\item Faça o Problema~0.8.3 de \textbf{PNK}.  

\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{22/8/2024}

  \def\sdiff{\bigtriangleup}
\item\label{E:E5} 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{22/8/2024}

\item Sejam $A_i$ ($0\leq i<N$) conjuntos e seja
  \begin{equation}
    \label{eq:1}
    B = A_0\sdiff\cdots\sdiff A_{N-1}
  \end{equation}
  sua diferença simétrica.  Seja~$I(x)$ a propriedade ``há um número
  ímpar de índices~$i$ ($0\leq i<N$) para os quais $x\in A_i$''.
  Prove que
  \begin{equation}
    \label{eq:2a}
    B = \Big\{x\in\bigcup_{0\leq i<N}A_i\:\ I(x)\Big\}.
  \end{equation}

\item Complete a implementação de \texttt{vec.py}.  Não deixe de
  executar \texttt{python -m doctest vec.py} para testar sua
  implementação.
  
\item\label{E:7} Faça o Problema~2.14.5 de \textbf{PNK}.  No caso em
  que não há subconjunto de $\{\mathbf{a},\dots,\mathbf{f}\}$ que tem
  como soma o vetor desejado, justifique sua resposta de forma
  elegante, considerando o produto escalar com o vetor $1011011$.
  
\item Seja~$N\geq2$ um inteiro.  Consideramos aqui matrizes
  $N\times N$ com entradas em~$\GF(2)$ e com as linhas e colunas indexadas por
  $\{0,1,\dots,N-1\}$.  Para cada $0\leq r<N-1$ e $0\leq s<N-1$,
  seja~$B_{rs}=(b_{ij}^{(rs)})_{0\leq i,\,j<N}$, onde
  \begin{equation}
    \label{eq:3}
    b_{ij}^{(rs)}=
    \begin{cases}
      1 &\text{se }(i,j)\in\{r,r+1\}\times\{s,s+1\},\\
      0 &\text{caso contrário}.
    \end{cases}
  \end{equation}
  Seja $A=(a_{ij})_{0\leq i,\,j<N}$, onde
  \begin{equation}
    \label{eq:4b}
    a_{ij}=
    \begin{cases}
      1 &\text{se }(i,j)\in\{0,N-1\}\times\{0,N-1\},\\
      0 &\text{caso contrário}.
    \end{cases}
  \end{equation}
  Finalmente, seja $A'=(a_{ij}')_{0\leq i,\,j<N}$, onde
  \begin{equation}
    \label{eq:5}
    a_{ij}'=
    \begin{cases}
      1 &\text{se }(i,j)\in\{(0,0), (0,N-1), (N-1,0)\},\\ 
      0 &\text{caso contrário}.
    \end{cases}
  \end{equation}
  Por exemplo, se $N=3$, as~$4$ matrizes~$B_{rs}$ ($0\leq r,s<2$) são
  \begin{equation}
    \label{eq:6}
    \begin{bmatrix}
      1 & 1 & 0\\
      1 & 1 & 0\\
      0 & 0 & 0\\
    \end{bmatrix},\;
    \begin{bmatrix}
      0 & 1 & 1\\
      0 & 1 & 1\\
      0 & 0 & 0\\
    \end{bmatrix},\;
    \begin{bmatrix}
      0 & 0 & 0\\
      1 & 1 & 0\\
      1 & 1 & 0\\
    \end{bmatrix}
    \;\text{ e }\;
    \begin{bmatrix}
      0 & 0 & 0\\
      0 & 1 & 1\\
      0 & 1 & 1\\
    \end{bmatrix}.
  \end{equation}
  Ademais,
  \begin{equation}
    \label{eq:7}
    A=
    \begin{bmatrix}
      1 & 0 & 1\\
      0 & 0 & 0\\
      1 & 0 & 1\\
    \end{bmatrix}
    \quad\text{ e }\quad
    A'=
    \begin{bmatrix}
      1 & 0 & 1\\
      0 & 0 & 0\\
      1 & 0 & 0\\
    \end{bmatrix}.
  \end{equation}
  Prove as seguintes afirmações (lembre que estamos trabalhando
  sobre~$\GF(2)$): 
  \begin{enumerate}[label=\rmlabel]
  \item Para qualquer $N\geq2$, temos
    $A\in\Span\{B_{rs}\:0\leq r,s<N-1\}$.
  \item Para qualquer $N\geq2$, temos
    $A'\notin\Span\{B_{rs}\:0\leq r,s<N-1\}$.  \hint{Veja o
      Exercício~\ref{E:7} e considere a matriz
      $Z=(z_{ij})_{0\leq i,\,j<N}$ sobre~$\GF(2)$ em que $z_{ij}=1$ se
      e só se $i+j$ é par.  Uma matriz mais simples que também serve é
      a matriz~$J$ sobre~$\GF(2)$ em que todas as entradas são~$1$.}
  \end{enumerate}
  \datedue{29/8/2024}
  
\item Sejam dados $\bfa_i=(a_{ij})_{0\leq j<n}\in\FF^n$ ($0\leq i<n$)
  e $\bfb=(b_i)_{0\leq i<n}\in\FF^n$ e considere o sistema de equações
  lineares
  \begin{equation}
    \label{eq:lin_sys}
    \left\{
    \begin{aligned}
      \bfa_0\cdot\bfx&=b_0\\
                     &\dots\\
      \bfa_{n-1}\cdot\bfx&=b_{n-1},\\    
    \end{aligned}
    \right.
  \end{equation}
  onde $\bfx=(x_j)_{0\leq j<n}$.  Suponha ainda que, para
  todo~$0\leq i<n$, temos que $a_{ij}=0$ para todo~$j$ com $j<i$, de
  forma que~\eqref{eq:lin_sys} é um sistema \textit{triangular}.

  Lembre que, se~$a_{ii}\neq0$ para todo $0\leq i<n$,
  então~\eqref{eq:lin_sys} admite uma solução e essa solução é única.
  Prove que se existe um~$k$ com $0\leq k<n$ tal que~$a_{kk}=0$, então
  existe um $\bfb=(b_i)_{0\leq i<n}\in\FF^n$ para o
  qual~\eqref{eq:lin_sys} não admite nenhuma solução.

\item\label{E:10} 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{equation*}
    \left\{
      \begin{aligned}
      \bfa\cdot\bfx&=3\\
      \bfb\cdot\bfx&=6\\
      \bfc\cdot\bfx&=-8\\
      \bfd\cdot\bfx&=-4.
      \end{aligned}
    \right.
  \end{equation*}
  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.  \NB{Não deixe de calcular
    $\bfa\cdot\bfx$, $\bfb\cdot\bfx$, \dots, para verificar que você
    encontrou~$\bfx$ corretamente.}
  \datedue{5/9/2024}

\item Suponha que executamos uma sessão interativa do Python idêntica
  à sessão do Exercício~\ref{E:10}, 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:10}
  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.

\item (Em preparação)

\item\label{E:13}
  \begin{enumerate}[label=\rmlabel]
  \item Seja
    $A=(\alpha_{ij})_{0\leq i<m,\,0\leq j<n}\in\FF^{m\times n}$ uma
    matriz $m\times n$ com entradas em~$\FF$ e
    seja~$\bfbeta=(\beta_j)_{0\leq j<n}\in\FF^n$ um vetor coluna.
    Verifique que, para todo~$0\leq i<m$, a $i$-ésima entrada
    de~$A\bfbeta$ é~$\bfalpha_i\cdot\bfbeta$, onde~$\bfalpha_i$ é a
    $i$-ésima linha de~$A$, isto é,
    \begin{equation}
      \label{eq:9}
      A=
      \begin{bmatrix}
        \bfalpha_0\\
        \vdots\\
        \bfalpha_{m-1}
      \end{bmatrix}.
    \end{equation}
  \item Seja $M=(m_{ij})_{0\leq i<r,\,0\leq j<m}\in\FF^{r\times m}$
    uma matriz $r\times m$ com entradas em~$\FF$ e seja
    $\bfalpha=(\alpha_j)_{0\leq j<m}\in\FF^m$ um vetor coluna.
    Ademais, suponha que $\bfv_j$ ($0\leq j<m$) sejam as colunas
    de~$M$:
    \begin{equation}
      \label{eq:10}
      M=
      \begin{bmatrix}
        \bfv_0\mid\dots\mid\bfv_{m-1}
      \end{bmatrix}.
    \end{equation}
    Verifique que a combinação linear dos~$\bfv_j$ com
    coeficientes~$\alpha_j$ é simplesmente~$M\bfalpha$, isto é, 
    \begin{equation}
      \label{eq:11_sum}
      \sum_{0\leq j<m}\alpha_j\bfv_j=M\bfalpha.
    \end{equation}
  \end{enumerate}

\item Sejam $\bfv_0,\dots,\bfv_{m-1}\in\FF^r$ e
  $\bfu_0,\dots,\bfu_{n-1}\in\FF^r$ vetores coluna.  Suponha que, para
  todo $0\leq j<n$,
  \begin{equation}
    \label{eq:12}
    \bfu_j=\sum_{0\leq i<m}\alpha_{ij}\bfv_i.
  \end{equation}
  Seja $\bfw=\sum_{0\leq j<n}\beta_j\bfu_j$ uma combinação
  dos~$\bfu_j$.  Prove que~$\bfw$ é uma combinação linear
  dos~$\bfv_i$; mais precisamente, prove que
  $\bfw=\sum_{0\leq i<m}\gamma_i\bfv_i$, onde, para todo $0\leq i<m$,
  \begin{equation}
    \label{eq:13}
    \gamma_i=\bfalpha_i\cdot\bfbeta, 
  \end{equation}
  onde~$\bfalpha_i$ é o vetor linha $(\alpha_{ij})_{0\leq j<n}$
  e~$\bfbeta$ é o vetor coluna $(\beta_i)_{0\leq i<n}$.
  \hint{Considere a matriz $A=(\alpha_{ij})_{0\leq i<m,\,0\leq j<n}$ e
    use~\ref{E:13}.}  \datedue{5/9/2024}

\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\label{E:16} 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 entrada, sua
  função deve devolver a lista contendo somente o vetor nulo
  de~$\GF(2)^D$.  \NB{O enunciado do Problema~3.8.3 de \textbf{PNK}
    não deixa claro se a lista da saída pode ou não ter elementos
    repetidos.  Em sua solução, você deve garantir que não haja
    elementos repetido em sua saída.}  \datedue{19/9/2024}

\item Faça os Problemas~3.8.7 a~3.8.10 de~\textbf{PNK} (são quatro
  problemas).  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\label{E:span} Seja~$D$ um conjunto arbitrário.
  \begin{enumerate}[label=\rmlabel]
  \item Sejam~$U$ e~$V\subset\FF^D$ dois espaços vetoriais.  Prove
    que~$U\cap V$ é um espaço vetorial.
  \item Seja dado~$S\subset\FF^D$.  Prove que existe um ``menor''
    espaço vetorial que contém~$S$, isto é, um espaço vetorial
    $W\subset\FF^D$ tal que (\textit{a})~$S\subset W$ e que
    (\textit{b})~se $S\subset V\subset\FF^D$ e~$V$ é um espaço
    vetorial, então $W\subset V$.  Note que um~$W$ que
    satisfaz~(\textit{a}) e~(\textit{b}) é único (isto é, tal
    ``menor'' espaço vetorial que contém~$S$ é único).  \hint{Para
      obter~$W$, considere a interseção de todos os subespaços
      vetoriais de~$\FF^D$ que contêm~$S$.}
  \end{enumerate}

\item (\textit{M}) Continuamos aqui o Exercício~\ref{E:span}.
  \begin{enumerate}[label=\rmlabel]
  \item Lembre que, dados vetores $\bfv_i\in\FF^D$ ($1\leq i\leq n$),
    o espaço gerado por estes~$n$ vetores é
    \begin{equation}
      \label{eq:span}
      \Span\{\bfv_1,\dots,\bfv_n\}
      =\Bigg\{\sum_{1\leq i\leq n}\alpha_i\bfv_i\:\alpha_i\in\FF\text{ para todo
      }i\Bigg\}.
    \end{equation}
    Seja~$S$ como no item~(\textit{ii}) do Exercício~\ref{E:span}, e
    note que~$S$ pode ser um conjunto infinito.  Colocamos
    \begin{equation}
      \label{eq:span_general}
      \Span S = \bigcup_T\Span T,
    \end{equation}
    onde a união é sobre todo subconjunto finito~$T$ de~$S$ (se
    $T=\{\bfv_1,\dots,\bfv_n\}$ ($n\geq0$), o conjunto $\Span T$ é
    dado por~\eqref{eq:span}).  Prove que $\Span S$ definido
    em~\eqref{eq:span_general} é um espaço vetorial e que
    $S\subset\Span S$.
  \item Prove que $\Span S$ definido em~\eqref{eq:span_general} é o
    menor espaço vetorial que contém~$S$.
  \item Suponha agora que~$D=\NN=\{0,1,\dots\}$ e, para
    todo~$n\in\NN$, seja $e_n\in\FF^D$ a função tal que $e_n(m)=1$
    se~$m=n$ e $e_n(m)=0$ se $m\neq n$.  Seja $S=\{e_n\:n\in\NN\}$.
    Descreva os elementos de $\Span S$.  É verdade que $\Span
    S=\FF^D$? 
  \end{enumerate}

\item Seja~$D$ um conjunto arbitrário e seja
  $\emptyset\neq S\subset\FF^D$.  Prove que existe um ``menor'' espaço
  afim~$A\subset\FF^D$ que contém~$S$.

\item Neste exercício, suponha $\FF=\RR$ ou~$\FF=\CC$.  Seja~$D$ um
  conjunto arbitrário e seja~$K\subset\FF^D$.  Dizemos que~$K$ é
  \textit{convexo} se para quaisquer~$\bfx$ e~$\bfy\in K$, qualquer
  combinação convexa de~$\bfx$ e~$\bfy$ pertence a~$K$ (isto é, para
  quaisquer $\alpha$ e~$\beta\geq0$ tais que $\alpha+\beta=1$, temos
  que $\alpha\bfx+\beta\bfy\in K$).  Seja $S\subset\FF^D$.  Prove que
  existe um ``menor'' conjunto convexo~$K\subset\FF^D$ que contém~$S$.

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

\item\label{E:grs} Um \textit{grafo}~$G$ é um par ordenado~$(V,E)$,
  onde
  \begin{equation}
    \label{eq:1b}
    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{19/9/2024}

\item Leia sobre \textit{Lights Out}
  \href{https://en.wikipedia.org/wiki/Lights_Out_(game)}{nesta
    página}.  Você pode jogar a versão~$5\times5$ do Lights Out, por
  exemplo, \href{https://www.logicgamesonline.com/lightsout/}{nesta
    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 (o
  melhor é criar \verb|B| com \verb|coldict2mat()| e então fazer
  \verb|print(B)|).  Use o procedimento que você escreveu no
  Exercício~\ref{E:16} 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.  

\item\label{E:26} 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:27} (Continuação de~\ref{E:26})\, 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 necessariamente como você vê
  \href{https://www.ime.usp.br/~yoshi/2024ii/mat0122/sandbox/LIGHTS_OUT/}{neste
    diretório}.  \datedue{26/9/2024}

\item (Continuação de~\ref{E:26})\, 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\label{E:incidence} Seja~$G=(V,E)$ um grafo (veja~\ref{E:grs}).  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\}$.
  
\item\label{E:30} Seja~$G=(E,V)$ um grafo e~$\cC$ o espaço dos ciclos
  de~$G$.  Prove que
  \begin{equation}
    \label{eq:cycle_space_dash}
    \cC'=\{\dsone_F\in\GF(2)^E\:F\in\cC\}
  \end{equation}
  é um espaço vetorial sobre~$\GF(2)$.  \NB{Para simplificar a
    notação, em geral identificamos~$\cC'$ com~$\cC$, identificando a
    função indicadora~$\dsone_F$ com~$F$.}
\item Seja~$G=(V,E)$ um grafo e seja~$M\in\GF(2)^{V\times E}$ sua
  matriz de incidência (veja~\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}).
  \begin{enumerate}[label=\rmlabel]
  \item Prove que existem circuitos $C_1,\dots,C_t$ ($t\geq0$) tais
    que
    \begin{enumerate}[label=\alabel]
    \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$.
    \end{enumerate}
  \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^{\vphantom{\top}}=0\text{ para todo
      ciclo $C$ de $G$}\}. 
  \end{equation}
  Os elementos de~$\cC^\perp$ são os \textit{cociclos} de~$G$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $\cC^\perp$ é um subespaço vetorial de~$\GF(2)^E$.
    \NB{Como no Exercício~\ref{E:30}, aqui identificamos $B\subset E$
      com $\dsone_B\in\GF(2)^E$.}
  \item Para todo~$U\subset V$, seja
    \begin{equation}
      \label{eq:5b} 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$.
    \NB{O conjunto~$B_U$ é o assim chamado \textit{corte} definido
      por~$U$.}
  \item Sejam dados~$U$ e~$W\subset V$.  Prove que
    \begin{equation}
      \label{eq:5bc}
      B_U\sdiff B_W=B_{U\sdiff W},
    \end{equation}
    onde~$\sdiff$ denota a diferença simétrica.
  \item Prove que
    \begin{equation}
      \label{eq:5c}
      \cB=\{B_U\:U\subset V\}
    \end{equation}
    é um subespaço vetorial de~$\cC^\perp$, onde estamos identificando
    aqui~$B_U\subset E$ com~$\dsone_{B_U}\in\GF(2)^E$.
  \end{enumerate}
  
\item Um grafo $G=(V,E)$ é uma \textit{árvore} se~$G$ é uma floresta
  (isto é, não contém circuitos) e é conexo (isto é, existe caminho
  de~$x$ a~$y$ para qualquer par de vértices~$x$ e~$y\in V$).
  Seja~$G$ uma árvore com $n\geq1$ vértices.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$G$ tem $n-1$ arestas.
  \item\label{E:34ii} Determine~$\cC^\perp$ e~$\cB$ definidos
    em~\eqref{eq:cycle_space_perp} e~\eqref{eq:5c} para~$G$.
  \item Seja $F\subset E$ um conjunto qualquer de arestas de~$G$.
    Prove que $F=B_U$ para algum $U\subset V$.  \NB{Esse fato pode ser
      provado diretamente, com um argumento envolvendo grafos, ou pode
      ser derivado imediatamente de~\ref{E:34ii} acima.}
  \end{enumerate}
  \datedue{6/10/2024} 
    
\item\label{E:35odd} Seja~$G=(V,E)$ um grafo.  Neste exercício, vamos
  dizer que~$F\subset E$ é \textit{ímpar-regular em~$G$} 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 Suponha que~$G$ seja 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 um
    grafo~$G$.  Prove que~$F\subset E$ é ímpar-regular em~$G$ se e só
    se $M\dsone_F=\dsone_V$.
  \item\label{E:35iii} Suponha agora que~$G$ seja um grafo com número
    ímpar de vértices.  Prove que~$G$ não admite um conjunto
    ímpar-regular de arestas (isto é, não existe $F\subset E$
    ímpar-regular em~$G$).  \hint{Multiplique os dois lados de
      $M\dsone_F=\dsone_V$ por~$\dsone_V^\top$ pela esquerda.  Não se
      esqueça que estamos trabalhando sobre~$\GF(2)$}.
  \end{enumerate}
  
\item\label{E:35} Sejam~$R$ e~$C$ conjuntos finitos e~$\FF$ um corpo.
  Seja~$\FF^{R\times C}$ o conjunto das matrizes $R\times C$
  e~$L(\FF^C,\FF^R)$ o conjunto das funções lineares de~$\FF^C$
  para~$\FF^R$.  Dado~$A\in\FF^{R\times C}$, definimos
  $f_A\in L(\FF^C,\FF^R)$ pondo $f_A(\bfx)=A\bfx$ para
  todo~$\bfx\in\FF^C$.  Ademais, dado $f\in L(\FF^C,\FF^R)$,
  construímos a matriz~$A_f$ que tem como sua $c$-ésima coluna o vetor
  $f(\bfe_c)\in\FF^R$ para todo $c\in C$, onde~$\bfe_c\in\FF^R$ é a
  função característica~$\dsone_{\{e\}}$ do conjunto~$\{c\}\subset C$.
  Prove que estas duas operações são inversas uma da outra, isto é,
  prove as seguintes duas afirmações:
  \begin{enumerate}[label=\rmlabel]
  \item Para todo $A\in\FF^{R\times C}$, vale que $A_{f_A}=A$.
  \item Para todo $f\in L(\FF^C,\FF^R)$, vale que $f_{A_f}=f$.
  \end{enumerate}
  
\item Sejam dados $f\in F(\FF^R,\FF^S)$ e $g\in L(\FF^S,\FF^T)$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $g\circ f\in F(\FF^R,\FF^T)$.  
  \item Sejam~$A_f$, $A_g$ e~$A_{g\circ f}$ como definidos no
    Exercício~\ref{E:35}.  Prove que $A_{g\circ f}=A_gA_f$.
  \end{enumerate}

\item\label{E:37} Sejam $h\:X\to Y$ e $g\:Y\to X$ duas funções.  Sejam
  $\id_X\:X\to X$ e $\id_Y\:Y\to Y$ as funções identidades sobre~$X$
  e~$Y$.  Suponha que $h\circ g=\id_Y$.  É verdade que necessariamente
  $g\circ h=\id_X$?  Prove ou dê um contra-exemplo.
  
\item Sejam~$X$ e~$Y$ dois conjuntos finitos de mesma cardinalidade.
  \begin{enumerate}[label=\rmlabel]
  \item Suponha que $f\:X\to Y$ seja uma função injetora.  Prove
    que~$f$ é sobrejetora.
  \item Suponha que $f\:X\to Y$ seja uma função sobrejetora.  Prove
    que~$f$ é injetora.
  \end{enumerate}

\item Sejam~$X$ e~$Y$ dois conjuntos finitos de mesma cardinalidade, e
  sejam $h\:X\to Y$ e $g\:Y\to X$ duas funções tais que
  $h\circ g=\id_Y$.  Prove que $g\circ h=\id_X$.  \datedue{6/10/2024}

\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.  

\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~$AB=I_R$, então~$B$ é inversível e~$B^{-1}=A$.
  \end{enumerate}

\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:3b}
    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:7b}
    \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$.  O Exercício~\ref{E:45}
    mostra como podemos obter a matriz~$G$ a partir de~$H$ de forma
    sistemática.}

\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:12b}
      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\label{E:45} 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:10b}
    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:13b}
      \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/2024}  

\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\label{E:47} Seja $G=(V,E)$ um grafo.  Para cada $e\in E$,
  seja~$\dsone_e\in\GF(2)^V$ a função característica de~$e$.  
  \begin{enumerate}[label=\rmlabel]
  \item Seja
    \begin{equation}
      \label{eq:17}
      \bfd=\sum_{e\in E}\dsone_e.
    \end{equation}
    Verifique que $\bfd\in\GF(2)^V$ é tal que $\bfd(v)=1$ se e só
    se~$v$ tem grau ímpar em~$G$ (o \textit{grau} de um vértice é o
    número de arestas que contém aquele vértice).
  \item Seja $\bfj_V\in\GF(2)^V$ tal que $\bfj_V(v)=1$ para todo
    $v\in V$.  Prove que
    \begin{equation}
      \label{eq:16}
      \bfj_V^\top\,\sum_{e\in E}\dsone_e=0,
    \end{equation}
    lembrando que estamos trabalhando em~$\GF(2)$.
  \item Deduza que~$G$ tem um número par de vértices de grau ímpar.
    \NB{Note que este fato generaliza o
      Exercício~\ref{E:35odd}\ref{E:35iii}.}
  \end{enumerate}

\item\label{E:36} Seja~$G=(V,E)$ um grafo e sejam~$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\label{E:36iii} 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$.  Prove que~\eqref{eq:8} implica que existe um
    $(x,y)$-caminho em~$H$.  \hint{Considere o conjunto~$A\subset V$
      dos vértices acessíveis a partir do vértice~$x$ no grafo~$H$.
      Seja $B=V\setminus A$.  Verifique que toda aresta $f\in F$ é tal
      que ou suas duas pontas estão em~$A$ ou suas duas pontas estão
      em~$B$.  Seja $F_A\subset F$ o conjunto das arestas em~$F$ que
      têm suas duas pontas em~$A$ e seja $F_B=F\setminus F_A$.
      Considere o grafo $J=(A,F_A)$.  O que~\eqref{eq:8} diz
      sobre~$J$?  (Tenha em mente o Exercício~\ref{E:47}).}
  \end{enumerate}
  
\item\label{E:49} Seja~$G=(V,E)$ um grafo.  Dizemos que~$F\subset E$ é
  \textit{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:9b}
    \Span\{\dsone_f\:f\in F\}=\Span\{\dsone_e\:e\in E\}.
  \end{equation}
  \NB{O espaço no lado direito de~\eqref{eq:9b} é às vezes conhecido
    como o \textit{espaço das arestas de~$G$} e é denotado~$C_1(G)$}

  \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:16b}
        \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/2024}

\item (\textit{M}) Lembre que~$\RR$ é um espaço vetorial sobre~$\QQ$
  (veja o Exercício~\ref{E:15}).
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$1$ e~$\sqrt2$ são linearmente independentes
    sobre~$\QQ$.
  \item 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).
  \end{enumerate}

\item Note que~$\CC$ é um espaço vetorial sobre~$\RR$ de forma natural
  (isto é semelhante ao fato que~$\RR$ é um espaço vetorial
  sobre~$\QQ$; veja o Exercício~\ref{E:15}).  Encontre dois vetores
  em~$\CC$ 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 em~$\RR^N$.  Naturalmente, podemos também
  considerar $\bfv_1,\dots,\bfv_n$ como vetores em~$\CC^N$.  Prove que
  eles também são linearmente independentes em~$\CC^N$.

\item Senhor Cético não acredita que \textit{Lights Out} no tabuleiro
  $20\times20$ \textit{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 procurar soluções.  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).  Use o fato que você resolveu o Exercício~\ref{E:27}, e
  você pode usar seu programa \verb|lo_solver.py|.

\item\label{E:55} Sejam~$V$ um espaço vetorial e~$S$ um subconjunto
  de~$V$.  Prove que as seguintes afirmações são equivalentes.
  \begin{enumerate}[label=\rmlabel]
  \item $S$ é uma base de~$V$.
  \item $S$ é um conjunto gerador \textit{minimal} de~$V$, isto
    é, $\Span S=V$, mas, para todo~$S'\subset S$
    com~$S'\neq S$, vale que $\Span S'\neq V$.
  \item $S$ é um conjunto linearmente independente \textit{maximal}
    em~$V$, isto é, $S$~é linearmente independente, mas, para
    todo~$S'\subset V$ com $S\subset S'$ e~$S\neq S'$, vale que~$S'$
    não é linearmente independente.
  \item $S$ é um conjunto gerador de~$V$ com a propriedade de
    \textit{representação única}, isto é, $\Span S=V$ e, para
    todo~$\bfv\in V$, existe uma única combinação linear de elementos
    de~$S$ que é igual a~$\bfv$.
  \end{enumerate}
  \datedue{20/10/2024}

\item\label{E:56a} Lembre que um grafo~$G$ é \textit{acíclico} se ele
  não contém circuitos e é \textit{conexo} se, para quaisquer dois
  vértices~$x$ e~$y$ em~$G$, há um $(x,y)$-caminho em~$G$.  Seja
  $G=(V,E)$ um grafo e considere
  \begin{equation}
    \label{eq:19}
    S=\{\dsone_e\:e\in E\}\subset\GF(2)^V
  \end{equation}
  e
  \begin{equation}
    \label{eq:18}
    W=\Span\{\dsone_{\{x,y\}}\:x,\,y\in V\text{ e }x\neq
    y\}\subset\GF(2)^V. 
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$\Span S=W$ se e só se~$G$ for conexo.  
  \item Prove que~$S$ é linearmente independente se e só se~$G$ for
    acíclico.
  \end{enumerate} \hint{Use o Exercício~\ref{E:36}\ref{E:36iii}.}

\item\label{E:56} Lembre que um grafo~$G$ é uma \textit{árvore} se ele
  for \textit{conexo} e \textit{acíclico}.  Prove que as seguintes
  asserções são equivalentes para um grafo~$G=(V,E)$:
  \begin{enumerate}[label=\rmlabel]
  \item $G$ é uma árvore.
  \item Os vetores $\dsone_e\in\GF(2)^V$ ($e\in E$) formam um base do
    espaço
    \begin{equation}
      \label{eq:18b}
      W=\Span\{\dsone_{\{x,y\}}\:x,\,y\in V\text{ e }x\neq
      y\}\subset\GF(2)^V. 
    \end{equation}
  \end{enumerate}
  
\item\label{E:57} Deduza dos Exercícios~\ref{E:55}--\ref{E:56} que
  as seguintes asserções são equivalentes para um grafo~$G=(V,E)$:
  \begin{enumerate}[label=\rmlabel]
  \item $G$ é uma árvore.
  \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 (Unicidade dos caminhos) Para quaisquer vértices~$x$ e~$y$
    de~$G$, existe um único $(x,y)$-caminho em~$G$.
  % \item $G$ é conexo e $|E|=|V|-1$.
  % \item $G$ é acíclico e $|E|=|V|-1$.
  \end{enumerate}
  
\item Provamos em sala que o Algoritmo~\textsc{Grow} encontra uma
  floresta de peso mínimo em um grafo com custo nas arestas.  A prova
  dependeu de uma hipótese adicional, a saber, que os custos das
  arestas são todos distintos.  Prove o resultado sem essa hipótese.
  \hint{Ao escolher~$F^*$, suponha adicionalmente que~$F^*$ e~$F$
    tenham o maior número possível de arestas em comum, e repita o
    argumento.}
  \datedue{20/10/2024}

\item Seja $2^\NN=\cP(\NN)$ o conjunto das partes de~$\NN$.  Para cada
  uma das famílias~$\cF\subset2^\NN$ abaixo, diga se existe em~$\cF$
  um elemento maximal em~$\cF$, isto é, um~$F^*\in\cF$ tal que
  se~$F^*\subset F'$ e~$F^*\neq F'$, então $F'\notin\cF$.  Justifique
  suas respostas.
  \begin{enumerate}[label=\rmlabel]
  \item $\cF=\{F\subset\NN\:\NN\setminus F\text{ é um conjunto
      infinito}\}$
  \item
    $\cF=\{F\subset\NN\:F\text{ é tal que
    }n^{-1}|F\cap\{0,1,\dots,n-1\}|\leq1/2\text{ para todo }n>0\}$
  \end{enumerate}  
  
\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~$F$ de~$\cF$ e
      prove que eles são linearmente independentes (considere uma
      combinação linear deles, considere um~$F_0\in\cF$ arbitrário, e
      multiplique a combinação linear por~$\dsone_{F_0}$).}
  \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} \datedue{3/11/2024}

\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\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:17b}
    (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:19b}
    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$?

\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}
      (1-x)\sum_{0\leq i<n}x^i=1-x^n.
    \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}
  
\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/2024}

\item Seja~$G=(V,E)$ um grafo conexo e seja $T=(V,F)$ com~$F\subset E$
  uma árvore (veja Exercício~\ref{E:56}).  Como~$G$ e~$T$ têm o mesmo
  conjunto de vértices, dizemos que~$T$ é uma \textit{árvore geradora}
  de~$G$ (em teoria dos grafos, esse fato é expressado dizendo que~$T$
  não só é um \textit{subgrafo} de~$G$, mas é um subgrafo
  \textit{gerador} de~$G$).  Seja $A\subset E$ um conjunto acíclico de
  arestas de~$G$ (isto é, tal que $(V,A)$ não contém um circuito).
  Mostre que existe $F'\subset F$ tal que $T'=(V,A\cup F')$ é uma
  árvore geradora de~$G$.  \hint{Aplique o morphing lemma.}
  
\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 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$.  \hint{Considere os eventos
    $E_i=\{\bfa_i\notin\Span\{\bfa_1,\dots,\bfa_{i-1}\}\}$ e note que
    $\posto\{\bfa_1,\dots,\bfa_n\}=\sum_i\dsone_{E_i}$.  Note que
    $\EE(\dsone_{E_i})=\PP(E_i)\geq1-2^{i-1-n}$.}

\item Sejam~$U$ e~$W$ subespaços complementares em~$V$, de forma que
  $V=U\oplus W$.  Sabemos 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.  Defina a função
  $f\:V\to U$ pondo $f(\bfv)=\bfu$ para todo~$\bfv\in V$, onde~$\bfu$
  é como acima.  Prove que~$f$ é uma função linear.  
  
\item Sejam~$V$ e~$W$ espaços vetoriais, $f\:V\to W$ uma função
  linear, e $\bfb_1,\dots,\bfb_n\in V$ elementos de~$V$.
  \begin{enumerate}[label=\rmlabel]
  \item Suponha que $f$ seja injetor e que $\bfb_1,\dots,\bfb_n$ sejam
    linearmente independentes.  Prove que $f(\bfb_1),\dots,f(\bfb_n)$
    são linearmente independentes.
  \item Suponha que $f$ seja sobrejetor e que $\bfb_1,\dots,\bfb_n$
    gerem~$V$.  Prove que $f(\bfb_1),\dots,f(\bfb_n)$ geram~$W$.
  \item Suponha agora que~$f$ seja bijetor.  Prove que
    $\dim V=\dim W$.
  \end{enumerate}
  
\item Sejam~$V$ e~$W$ espaços vetoriais e $f\:V\to W$ uma função
  linear.  Seja $W^*=\Im f$.  Seja~$V^*\subset V$ um complemento
  de~$\Ker f$ em~$V$, isto é, suponha que $V=\Ker f\oplus V^*$.
  Defina $f^*\:V^*\to W^*$ pondo $f^*(\bfv)=f(\bfv)$ para todo
  $\bfv\in V^*$.  Prove que $f^*$ é bijetora.  Deduza que
  \begin{equation}
    \label{eq:20b}
    \dim\Ker f+\dim\Im f=\dim V.
  \end{equation}
  \NB{Este exercício dá uma prova alternativa para o teorema
    núcleo-imagem.}
  
\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 Dê exemplos de matrizes~$A$ e~$B$ para os quais~\eqref{eq:27}
    vale com desigualdade estrita.
  \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/2024}

\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}
  
\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 Sejam~$U$ e~$W$ subespaços de~$V\subset\FF^D$, com~$D$ finito.
  Suponha que~$U$ e~$W$ são complementares em~$V$, de forma que
  $V=U\oplus W$.  Suponha que, para um subespaço $W'\subset V$, também
  vale que~$U$ e~$W'$ são complementares em~$V$.
  \begin{enumerate}[label=\rmlabel]
  \item É verdade que, necessariamente, $W=W'$?  Prove ou dê 
    contraexemplo.
  \item É verdade que, necessariamente, $\dim W=\dim W'$?  Prove ou dê
    contraexemplo.
  \end{enumerate} 

\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}

\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$.} \datedue{10/11/2024}

\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{10/11/2024}

\item No que segue, escrevemos~$[m]$ para o conjunto $\{1,2,\dots,m\}$
  para qualquer inteiro~$m$.  Seja $\sigma\:[m]\to[m]$ uma permutação
  (isto é, 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 permutaçã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$ ``com lápis e papel''.}
  \end{enumerate}

\item Seja~$V\subset\FF^D$ um espaço vetorial, onde~$D$ é finito.
  Seja~$I\subset V$ um conjunto de vetores linearmente independentes.
  Prove que é possível estender~$I$ a uma base~$B$ de~$V$ (isto é,
  prove que existe~$B$ base de~$V$ com $I\subset B$).  \hint{Você pode
    considerar uma variante apropriada de \textsc{Grow} e provar que
    tal algoritmo necessariamente termina com uma base~$B$ como
    queremos.  Você pode também considerar conjuntos linearmente
    independentes~$B\subset V$ com~$I\subset B$ com~$|B|$ o maior
    possível e argumentar que tais conjuntos são como queremos.  De
    qualquer forma, diga explicitamente onde você usou a hipótese
    que~$D$ é finito.}
  
\item Sejam~$U$ e~$V$ subespaços de~$\FF^D$, com~$D$ finito.  Defina o
  conjunto $U+V\subset\FF^D$ pondo
  \begin{equation}
    \label{eq:26}
    U + V = \{u+v\:u\in U\text{ e }v\in V\}.
  \end{equation}
  Isto é, os elementos de $U+V$ são todas as somas $u+v$ com~$u\in U$
  e $v\in V$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $U+V$ é um espaço vetorial.
  \item Prove que
  \begin{equation}
    \label{eq:38}
    \dim(U+V) + \dim(U\cap V) = \dim U + \dim V.
  \end{equation}
  \hint{Verifique $U\cap V$ é um espaço vetorial.  Considere uma base~$B$
    de $U\cap V$.  Estenda~$B$ a uma base~$B_U$ de~$U$.  Estenda~$B$ a
  uma base~$B_V$ de~$V$.  Prove que $B_U\cup B_V$ é uma base de~$U+V$.}
  \end{enumerate}\duedate{24/11/2024}  
  
\item Para $\bfv\in\FF^\NN$, seja $\supp\bfv=\{i\in\NN\:\bfv(i)\neq0\}$.
  Seja
  \begin{equation}
    \label{eq:39}
    V=\{\bfv\in\FF^N\:\supp\bfv\text{ é um conjunto finito}\}.
  \end{equation}
  Note que o produto $\bfu\cdot\bfv=\sum_{i\in\NN}\bfu(i)\bfv(i)$ está
  bem definido em~$V$, de forma que, dado um subespaço~$U$ de~$V$,
  podemos definir
  \begin{equation}
    \label{eq:40}
    U^\circ=\{\bfv\in V\:\bfv\cdot\bfu=0\text{ para todo~$\bfu\in
      U$}\}
  \end{equation}
  de forma usual.

  Para cada $i<j$ naturais, seja~$\bfv_{ij}\:\NN\to\FF$ com
  $\bfv_{ij}(i)=-1$ e~$\bfv_{ij}(j)=1$.  Seja
  $U=\Span\{\bfv_{ij}\:i<j\}$ o espaço vetorial gerado por tais
  vetores~$\bfv_{ij}$.  Note que $U\subset V$.
  \begin{enumerate}[label=\rmlabel]
  \item Determine~$U^\circ$.
  \item Determine~$(U^\circ)^\circ$.
  \item É verdade que $(U^\circ)^\circ=U$?
  \end{enumerate}  

\item Vimos que é de interesse termos um algoritmo, que chamamos de
  Algoritmo~X, que, ao receber vetores $\bfa_1,\dots,\bfa_m\in\FF^n$,
  devolve um conjunto gerador para o aniquilador~$V^\circ$ de
  $V=\Span\{\bfa_1,\dots,\bfa_m\}$.
  \begin{enumerate}[label=\rmlabel]
  \item Descreva como podemos implementar o Algoritmo~X usando como
    subrotina o processo de eliminação de Gauss.  Seu algoritmo
    encontra uma base de~$V^\circ$?
  \item Prove que seu Algoritmo~X está correto.
  \item Codifique seu Algoritmo~X em Python.
  \end{enumerate}  

\item
  \begin{enumerate}[label=\rmlabel]
  \item Considere a matriz
    \begin{equation}
      \label{eq:41}
      A =
      \begin{bmatrix}
        1 &0 &1 &1 &0\\
        1 &0 &0 &1 &1\\
        0 &1 &0 &0 &1
      \end{bmatrix}\in\GF(2)^{3\times5}.
    \end{equation}
    Encontre uma base para $\Null A$.

  \item Considere a matriz
    \begin{equation}
      \label{eq:41}
      B =
      \begin{bmatrix}
        1 &1 &1 &0 &1\\
        1 &0 &0 &1 &0
      \end{bmatrix}\in\GF(2)^{2\times5}.
    \end{equation}
    Encontre uma matriz~$A$ com entradas em~$\GF(2)$ tal que $\Null A =
    \Row B$.
  \end{enumerate}
  \NB{Em ambos os itens acima, justifique sua resposta.}
  \duedate{24/11/2024}

\item Sejam $M\in\FF^{a\times b}$ e~$A\in\FF^{b\times c}$ duas
  matrizes.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $\posto(MA)\leq\posto A$.
  \item Prove que, se~$M$ é inversível, então $\posto(MA)=\posto A$.
  \end{enumerate}

\item\label{E:92} Sejam $A\in\FF^{R\times S}$ e $B\in\FF^{S\times T}$
  duas matrizes.  Sejam $A_{*s}$ ($s\in S$) as colunas de~$A$
  e~$B_{s*}$ ($s\in S$) as linhas de~$B$ (essa notação é como
  em~\eqref{eq:34} e~\eqref{eq:34b}).  Prove que
  \begin{equation}
    \label{eq:43}
    AB=\sum_{s\in S}A_{*s}B_{s*}.
  \end{equation}
  Note que~$AB$ e~$A_{*s}B_{s*}$ ($s\in S$) são matrizes~$R\times T$.  
  
\item Sejam $\bfq_1,\dots,\bfq_k\in\RR^n$ vetores unitários mutualmente
  ortogonais.  Seja $M=\sum_{1\leq i\leq k}\bfq\bfq^\top$.  Note
  que~$M$ é uma matriz $n\times n$.  Seja
  $V=\Span\{\bfq_1,\dots,\bfq_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}$.  \hint{Você pode 
    usar que $\bfq^\top\bfb=\<\bfb,\bfq\>$ e então verificar que $M\bfb$
    e $\bfb-M\bfb$ satisfazem as propriedades que definem a
    decomposição de~$\bfb$.  Alternativamente, você pode
    usar~\ref{E:92} e invocar uma fórmula matricial que provamos
    para~$\bfb^{\parallel V}$.}

\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 $W=U\oplus U^\perp$ e deduza 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 basicamente segue de
    nosso estudo de aniquiladores (ele segue imediatamente no caso em
    que~$W=\RR^n$).  Entretanto, é interessante fazer este exercício
    supondo que temos um produto interno abstrato (e não
    necessariamente o \textit{dot product}).}

\item Seja $U\subset\GF(2)^n$ um espaço vetorial.  
  \begin{enumerate}[label=\rmlabel]
  \item Vale necessariamente que $\GF(2)^n=U\oplus U^\circ$?
  \item Vale necessariamente que $\dim U+\dim U^\circ=n$?
  \end{enumerate}
  
\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~$M$ é uma matriz inversível, que $M^{-1}=M^\top$ e que
    $MM^\top=I_n$.
  \end{enumerate}
  \datedue{1/12/2024}
  
\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{Lembre que~$A$ pode ser escrita como um
    produto~$QR$ onde~$Q$ tem colunas ortonormais e~$R$ é uma matriz
    inversível.  Use esse fato.}

\item Seja~$A\in\FF^{m\times n}$ uma matriz cujas colunas são
  linearmente independentes.  É necessariamente verdade que~$A^\top A$
  é uma matriz inversível?  Prove ou dê um contraexemplo.  \NB{Note
    que aqui você não pode usar a fatoração~$QR$, pois estamos em um
    corpo arbitrário~$\FF$.}  \datedue{8/12/2024}

\item Neste exercício, como de usual, consideramos o produto interno
  padrão do~$\RR^n$, de forma que
  $\<\bfx,\bfy\>=\bfy^\top\bfx=\bfx\cdot\bfy$ para $\bfx$,
  $\bfy\in\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\>$.  Prove as
  seguintes asserções: 
  \begin{enumerate}[label=\rmlabel]
  \item Se~$A$ é ortogonal, então~$A$ preserva o produto interno.
  \item Se~$A$ preserva o produto interno, então~$A$ preserva a norma,
    isto é, para todo~$\bfx\in\RR^n$, vale que $\|A\bfx\|=\|\bfx\|$.
  \item Se~$A$ preserva a norma, então~$A$ é ortogonal.  \hint{Calcule
      $\<A(\bfx+\bfy),A(\bfx+\bfy)\>$.}
  \end{enumerate}

\item Seja~$\FF$ um corpo infinito arbitrário.  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$.  \NB{A
    primeira solução satisfatória desse exercício vale um prêmio
    chocolático.  Você pode usar o fato que um polinômio~$p(X)$ de
    grau~$d$ com coeficientes em~$\FF$ tem no máximo~$d$ raízes.}
  
\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\geq10^{20}$.

\item Sejam~$\phi=(1+\sqrt5)/2$ e~$\psi=(1-\sqrt5)/2$.  Seja
  \begin{equation}
    \label{eq:48}
    S=
    \begin{bmatrix}
      \phi &\psi\\
      1    &1
    \end{bmatrix}.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Seja
    \begin{equation}
      \label{eq:48b}
      T=
      \begin{bmatrix*}[r]
        1/\sqrt5    &(1 - 1/\sqrt5)/2\\
        -1/\sqrt5   &(1 + 1/\sqrt5)/2
      \end{bmatrix*}.
    \end{equation}
    Verifique que~$T=S^{-1}$.
  \item Sejam
    \begin{equation}
      \label{eq:49}
      A=
      \begin{bmatrix}
        1 &1\\
        1 &0
      \end{bmatrix}
      \quad\text{ e }\quad
      \bfu_1=
      \begin{bmatrix}
        1\\ 
        0\\
      \end{bmatrix}.
    \end{equation}
    Defina $\bfu_t=A^{t-1}\bfu_1$ para todo~$t\geq1$.  Prove que
    $\bfu_t=[F_t\;F_{t-1}]^\top$ para todo~$t\geq1$, onde~$F_n$ é o
    $n$-ésimo número de Fibonacci ($F_n=n$ para $n\in\{0,1\}$ e
    $F_n=F_{n-1}+F_{n-2}$ para todo~$n\geq2$).
  \item Calcule~$S^{-1}AS$.
  \item Use os itens anteriores para provar que
    \begin{equation}
      \label{eq:46}
      F_t={1\over\sqrt5}(\phi^t-\psi^t)
    \end{equation}
    para todo~$t\geq0$.
  \end{enumerate}

\item Seja $A=(a_{ij})\in\FF^{n\times n}$ uma matriz triangular
  superior, isto é, tal que $a_{ij}=0$ se $i>j$.  Ademais, suponha que
  alguma entrada diagonal de~$A$ seja nula ($a_{ii}=0$ para pelo menos
  um índice~$i$).  Prove que~$A$ não é inversível.

\item Seja $A=(a_{ij})\in\FF^{n\times n}$ uma matriz triangular
  superior.  Suponha que alguma entrada diagonal de~$A$
  seja~$\lambda$.  Prove que~$\lambda$ é um autovalor de~$A$.

\item Seja $A\in\FF^{n\times n}$ uma matriz diagonalizável.  Considere
  a função linear $f_A\:\FF^n\to\FF^n$ associada a~$A$ usual, dada for
  $f_A(\bfv)=A\bfv$ para todo $\bfv\in\FF^n$.  Prove que existe uma
  base $\bfv_1,\dots,\bfv_n$ de~$\FF^n$ e escalares
  $\lambda_1,\dots,\lambda_n$ tais que $f_A(\bfv_i)=\lambda_i\bfv_i$
  para todo~$i$.  De forma mais geral, dê uma fórmula
  para~$f_A(\bfv)$, escrevendo~$\bfv$ em termos dos~$\bfv_i$ ($1\leq
  i\leq n$).  \datedue{8/12/2024}

\item Seja $A\in\FF^{n\times n}$ uma matriz e~$\lambda$ um autovalor
  de~$A$.  O \textit{autoespaço} de~$A$ associado a~$\lambda$ é
  \begin{equation}
    \label{eq:47}
    V_\lambda=\{\bfv\in\FF^n\:A\bfv=\lambda\bfv\}.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$V_\lambda$ é um espaço vetorial
  \item Sejam~$\lambda$ e~$\lambda'$ autovalores de~$A$ distintos.
    Prove que os autoespaços correspondentes~$V_\lambda$
    e~$V_{\lambda'}$ tem interseção trivial: $V_\lambda\cap
    V_{\lambda'}=\{\bf0\}$. 
  \end{enumerate}

\item Seja $A\in\FF^{n\times n}$ uma matriz.
  \begin{enumerate}[label=\rmlabel]
  \item Suponha que $\lambda_1,\dots,\lambda_m$ sejam autovalores
    distintos de~$A$.  Sejam
    $\bfv_1,\dots,\bfv_m\in\FF^n\setminus\{\bf0\}$ tais que, para
    cada~$1\leq i\leq m$, o vetor $\bfv_i$ pertence ao
    autoespaço~$V_{\lambda_i}$ de~$A$ (veja~\eqref{eq:47}).  Prove que
    os vetores $\bfv_1,\dots,\bfv_m$ são linearmente independentes.
    \hint{Prove por indução em~$k$ que $\bfv_1,\dots,\bfv_k$ são
      linearmente independentes.}
  \item Prove que a matriz~$A$ tem no máximo~$n$ autovalores
    distintos. 
  \end{enumerate}
  \datedue{8/12/2024}
\item Suponha que $A\in\FF^{n\times n}$ tenha~$n$ autovalores
  distintos.  Prove que~$A$ é diagonalizável.

\item 
  \begin{enumerate}[label=\rmlabel]
  \item Sejam $A\in\FF^{r\times s}$ e $B\in\FF^{s\times t}$.  Prove
    que $(AB)^\top=B^\top A^\top$.
  \item Suponha que $A\in\FF^{n\times n}$ seja uma matriz inversível.
    Prove que $A^\top$ é inversível e que
    $(A^\top)^{-1}=(A^{-1})^\top$.
  \item Suponha que $A\in\FF^{n\times n}$ seja uma matriz
    diagonalizável.  Prove que $A^\top$ é diagonalizável. 
  \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:
