%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 17 Sep 2025 05:19:22p.m. -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[dvipsnames]{xcolor}
\newcommand\myshade{85}
\colorlet{mylinkcolor}{violet}
\colorlet{mycitecolor}{YellowOrange}
\colorlet{myurlcolor}{Aquamarine}

\usepackage[backref]{hyperref}
% \hypersetup{
%     colorlinks,
%     linkcolor={red!60!black},
%     citecolor={green!60!black},
%     urlcolor={blue!90!black}
%   }
\hypersetup{
  linkcolor  = mylinkcolor!\myshade!black,
  citecolor  = mycitecolor!\myshade!black,
  urlcolor   = myurlcolor!\myshade!black,
  colorlinks = true,
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  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\bfs{\mathbf{s}}
\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 2025}}\\
  \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.  Todos os exercícios a serem entregues nesta disciplina
serão
\begin{center}
  \textbf{INDIVIDUAIS.}
\end{center}
Nestes exercícios individuais, você não deve compartilhar suas
soluções ou mesmo ideias de soluções com seus colegas.  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.

\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 nesta 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{14/8/2025}

  \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{14/8/2025}

\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 Sejam $f\:A\to B$ e $g\:B\to C$ funções e seja
  $h=g\circ f$.  Prove ou dê contraexemplo:
  \begin{enumerate}[label=\rmlabel]
  \item Se~$h$ é injetora, então~$f$ é injetora.
  \item Se~$h$ é injetora, então~$g$ é injetora.
  \item Se~$h$ é sobrejetora, então~$f$ é sobrejetora.
  \item Se~$h$ é sobrejetora, então~$g$ é sobrejetora.
  \end{enumerate}

\item\label{E:7} 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 identidade sobre~$X$
  e~$Y$.  Suponha que $h\circ g=\id_Y$.  É verdade que necessariamente
  $g\circ h=\id_X$?  Prove ou dê um contraexemplo.
  
\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$.  

\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.  Veja o Problema~2.14.10 de~\textbf{PNK}.

\item\label{E:11} 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
  \textbf{elegante}, considerando o produto escalar com o vetor
  $1011011$.  \datedue{21/8/2025}

\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$, a matriz~$A$ pode ser escrita como a
    soma de uma certa coleção das matrizes~$B_{rs}$ ($0\leq r,s<N-1$).
  \item Para qualquer $N\geq2$, a matriz~$A'$ não pode ser escrita
    como a soma de nenhuma coleção das matrizes~$B_{rs}$
    ($0\leq r,s<N-1$).  \hint{Veja o Exercício~\ref{E:11} e considere
      a matriz~$N$ por~$N$ em que todas as entradas são~$1$ (tal
      matriz é frequentemente denotada por~$J$).}
  \end{enumerate}
  
\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.  \datedue{21/8/2025}

\item\label{E:14} 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:14}, 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:14}
  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 Sejam dados $\bfa_i=(a_{ij})_{0\leq j<n}\in\FF^n$ ($0\leq i<n$).
  Suponha que $a_{ij}=0$ para todo $i>j$.  Ademais, suponha que
  $a_{00}=0$ mas que $a_{ii}\neq0$ para todo $i>0$.  Para cada
  $\bfbeta=(\beta_j)_{0\leq j<n}\in\FF^n$, podemos considerar o
  sistema de equações lineares
  \begin{equation}
    \label{eq:lin_sys_beta}
    (S_\bfbeta)\quad\left\{
    \begin{split}
      \bfa_0\cdot\bfx&=\beta_0\\
      \quad\;\;\dots\\
      \bfa_{n-1}\cdot\bfx&=\beta_{n-1}, 
    \end{split}
    \right.
  \end{equation}
  onde $\bfx=(x_j)_{0\leq j<n}$ é o vetor de indeterminadas. 
  Seja
  \begin{equation*}
    Z_\bfbeta=\{\bfs\in\FF^n\:\bfs\text{ é uma solução de
    }(S_\bfbeta)\}
  \end{equation*}
  o conjunto das soluções de~$(S_\bfbeta)$.
  \begin{enumerate}[label=\rmlabel]
  \item Lembre que~$(S_\bfbeta)$ é um sistema triangular com $a_{00}=0$.
    É verdade que~$(S_\bfbeta)$ necessariamente não tem solução (isto é,
    $Z_\bfbeta=\emptyset$)?  Prove ou dê um contraexemplo.
  \item Prove que vale uma e exatamente uma das seguintes duas
    alternativas:
    \begin{enumerate}
    \item[(A)] $Z_\bfbeta\neq\emptyset$, isto é, $(S_\bfbeta)$ admite
      ao menos uma solução;
    \item[(B)] existem $\alpha_1,\dots,\alpha_{n-1}\in\FF$ tais que
      \begin{equation}
        \label{eq:9_25}
        \sum_{1\leq j<n}\alpha_j\bfa_j=\bfa_0
      \end{equation}
      mas
      \begin{equation}
        \label{eq:9_25b}
        \sum_{1\leq j<n}\alpha_j\beta_j\neq\beta_0.
      \end{equation}
      \hint{Se valerem ambos~(A) e~(B), note que podemos deduzir uma
        contradição calculando uma combinação linear de equações
        em~$(S_\bfbeta)$.  Para provar que deve valer pelo menos uma
        das alternativas~(A) e~(B), prove e use o fato que sempre
        existem $\alpha_1,\dots,\alpha_{n-1}$ para os
        quais~\eqref{eq:9_25} vale.}
    \end{enumerate}
  \end{enumerate}\datedue{28/8/2025}
  
\item Podemos expressar um sistema linear com~$n$ equações e~$n$
  incógnitas como $A\bfx=\bfb$,
  onde~$A=(a_{ij})_{0\leq i,j<n}\in\FF^{n\times n}$ e~$\bfb\in\FF^n$.
  O caso em~$A$ é \textit{triangular superior}, isto é, $a_{ij}=0$
  para todo $i>j$, é particularmente simples e importante.  Sabemos
  que, no caso de tais matrizes~$A$ com $a_{ii}\neq0$ para todo~$i$, o
  sistema tem uma única solução.  Isso sugere o seguinte problema
  computacional: \textsl{dada uma matriz~$B\in\FF^{n\times n}$,
    decidir se é possível permutar as linhas e colunas de~$B$ de modo
    a obter uma matriz triangular superior}.  (Na linguagem de
  sistemas lineares, isso equivale a encontrar uma ordenação
  apropriada das equações e uma ordenação apropriadas das variáveis
  para obtermos um sistema triangular.)  Considere o caso particular
  em que sabemos que~$B$ é tal que existem tais permutações que
  permitem obter uma matriz triangular superior~$A=(a_{ij})$ com
  $a_{ii}\neq0$ para todo~$i$.  Encontre um algoritmo eficiente que
  encontra tais permutações nesse caso particular.
  
\item Seja~$S$ um conjunto finito.  Uma \textit{distribuição de
    probabilidade} sobre~$S$ é um vetor $\bfp=(p_s)_{s\in S}\in\RR^S$
  tal que $\sum_{s\in S}p_s=1$ e $0\leq p_s\leq1$ para todo~$s\in S$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que a combinação convexa de duas distribuições de
    probabilidade sobre~$S$ é uma distribuição de probabilidade
    sobre~$S$.
  \item Ao \textit{sortearmos um elemento~$X$ de~$S$ de acordo com a
      distribuição~$\bfp$} acima, para cada $s\in S$, obtemos~$s$ com
    probabilidade~$p_s$, e escrevemos
    \begin{equation}
      \label{eq:8}
      \PP(X=s)=p_s
    \end{equation}
    para expressar esse fato.  Suponha agora que temos as
    distribuições de probabilidade $\bfp^{(i)}=(p_s^{(i)})_{s\in S}$
    ($i\in\{0,1\}$) sobre~$S$.  Suponha também que temos
    $0\leq\alpha_i\leq1$ ($i\in\{0,1\}$) tais que
    $\alpha_0+\alpha_1=1$.  Considere agora o seguinte processo, que
    sorteia um elemento~$Y$ de~$S$: sorteamos~$j\in\{0,1\}$ de forma
    que $\PP(j=i)=\alpha_i$ ($i\in\{0,1\}$) e então sorteamos~$Y$ de
    acordo com a distribuição~$\bfp^{(i)}$.  Determine a distribuição
    de probabilidade $\bfq\in\RR^S$ que rege~$Y$.
  \end{enumerate}

\item\label{E:18}
  \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:18}.}  %\datedue{5/9/2024}

\item\label{E:21} (\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$.  Seja~$V$
  este espaço vetorial (o espaço vetorial sobre~$\QQ$ cujos elementos
  são os reais).  Não é muito claro se podemos considerar~$V$ como um
  subespaço vetorial de~$\QQ^D$ para algum~$D$.  É possível fazer
  isso?

\item\label{E:22} 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}).  \datedue{28/8/2025}

\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 Seja dado $S=\{\bfv_1,\dots,\bfv_n\}\subset\FF^D$.  Prove que o
  ``menor'' espaço vetorial que contém~$S$ (veja~\ref{E:span}) é
  $\Span S=\Span\{\bfv_1,\dots,\bfv_n\}$.

\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} (implementação da classe
  \texttt{Mat}).

\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:22} 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 Considere a versão $N\times N$ do Lights Out.  O conjunto das
  instâncias deste jogo é~$V=\GF(2)^{N\times N}$.  Seja $U\subset V$ o
  conjunto das instâncias que admitem solução.
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:34i} Prove que~$U$ é um espaço vetorial.
  \item\label{it:34ii} O item~\ref{it:34i} acima implica que
    $|U|/|V|=2^{-k}$ para algum inteiro $k\geq0$ (veremos como provar
    este fato mais à frente).  Usando este fato, escreva um programa
    que, dado~$N$, estima~$|U|/|V|$.  \hint{Estime este valor
      estatisticamente.}
  \item Para quais valores de~$N$ ($2\leq N\leq10$), vale que
    \textit{toda} instância de Lights Out $N\times N$ admite uma
    solução?  \hint{Use seu programa de~\ref{it:34ii}.}
  \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$,\footnote{Definimos $\Ker f_H$ como sendo o
    conjunto dos~$\bfv$ no domínio de~$f_H$ tais que~$f_H(\bfv)=\bfzero$.}
  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}$.\footnote{Isto é, $I(r,r)=1$ para
    todo $r\in R$ e $I(r,r')=0$ para todo par~$(r,r')$ com
    $r\neq 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{4/9/2025}

\item\label{E:38} 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_{\{c\}}$ 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\label{E:39} Sejam dadas matrizes $A\in\FF^{R\times S}$ e
  $B\in\FF^{S\times T}$.  Sejam $f_A\in L(\FF^S,\FF^R)$ e
  $f_B\in L(\FF^T,\FF^S)$ as funções lineares associadas às
  matrizes~$A$ e~$B$, como definidas no Exercício~\ref{E:38}.
  Considere também a matriz $AB\in\FF^{R\times T}$ e a função linear
  associada $f_{AB}\in L(\FF^T,\FF^R)$.  Prove que
  $f_A\circ f_B=f_{AB}$.  \NB{Este é o ``Lema da Multiplicação de
    Matrizes''.}

\item Sejam~$U$ e~$V$ espaços vetoriais quaisquer sobre~$\FF$ e seja
  $f\:U\to V$ uma função linear.  Suponha que~$f$ seja uma função
  inversível e seja~$g=f^{-1}\:V\to U$ sua inversa.  Prove que~$g$ é
  uma função linear.  \datedue{4/9/2025}
  
\item Faça o Lab~4.14 \textit{Error-correcting codes} de~\textbf{PNK},
  seguindo as instruções específicas dadas no e-Disciplinas.
  \datedue{11/9/2025}

\item Sejam dadas funções lineares $g\in L(\FF^S,\FF^R)$ e
  $h\in L(\FF^T,\FF^S)$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $g\circ h\in L(\FF^T,\FF^R)$.  
  \item Sejam~$A_g\in\FF^{R\times S}$, $A_h\in\FF^{S\times T}$
    e~$A_{g\circ h}\in\FF^{R\times T}$ as matrizes associadas a~$g$,
    $h$ e~$g\circ h$, como definidas no Exercício~\ref{E:38}.  Prove
    que $A_{g\circ h}=A_gA_h$.  \NB{Você pode provar esta identidade
      diretamente, mas também pode deduzi-la dos Exercícios~\ref{E:38}
    e~\ref{E:39}.}
  \end{enumerate}

\item\label{E:43} 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 Sejam $\bfe_1,\dots,\bfe_n\in\FF^n$ os geradores canônicos
  de~$\FF^n$ (assim, $\bfe_i=(0,0,\dots,1,\dots,0)$ onde a única
  entrada não-nula~$1$ ocorre na $i$-ésima posição).  Seja
  $\bfa=(\alpha_1,\dots,\alpha_n)\in\FF^n$ um vetor.  Temos
  \begin{equation}
    \label{eq:2_44}
    \bfa=\alpha_1\bfe_1+\dots+\alpha_n\bfe_n.
  \end{equation}
  Suponha agora que 
  \begin{equation}
    \label{eq:2_44b}
    \bfa=\beta_1\bfe_1+\dots+\beta_n\bfe_n.
  \end{equation}
  Prove que $\alpha_i=\beta_i$ para todo~$i$.  \NB{Isto é fácil de
    ver.  Para uma prova compacta, considere o produto escalar padrão
    de~\eqref{eq:2_44} e~\eqref{eq:2_44b} pelo vetor~$\bfe_i$.}

\item Considere as matrizes~$H_n$ ($n\geq1$) do Exercício~\ref{E:43}.
  Sejam~$\bfv_1,\dots,\bfv_N\in\{-1,1\}^N$ as~$N$ colunas de~$H_n$, de
  forma que
  \begin{equation}
    \label{eq:_45}
    H_n=[\bfv_1\mid\dots\mid\bfv_N].
  \end{equation}
  Seja agora $\bfa\in\FF^N$ um vetor e
  suponha que
  \begin{equation}
    \label{eq:3_45}
    \bfa=\alpha_1\bfv_1+\dots+\alpha_N\bfv_N
  \end{equation}
  e que 
  \begin{equation}
    \label{eq:3_45b}
    \bfa=\beta_1\bfv_1+\dots+\beta_N\bfv_N.
  \end{equation}
  Prove que $\alpha_i=\beta_i$ para todo~$i$.  \datedue{18/9/2025}

\item Prove ou dê contraexemplo:
  \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.  Seja~$I_R$ a matriz identidade
    em~$\FF^{R\times R}$.  Se~$AB=I_R$, então~$A$ é inversível
    e~$A^{-1}=B$.
  \item Sejam~$A$, $B$ e~$I_R$ como em~\ref{it:one_sided} acima.
    Se~$AB=I_R$, então~$B$ é inversível e~$B^{-1}=A$.
  \end{enumerate}

\item Seja~$A\in\FF^{n\times n}$ uma matriz e sejam
  $A_{*1},\dots,A_{*n}\in\FF^n$ as colunas de~$A$.  Suponha que para
  certos índices $r$, $s$ e~$t$ e escalares~$\alpha$ e~$\beta$, temos
  $\alpha A_{*r}+\beta A_{*s}=A_{*t}$.  Prove que~$A$ não é
  inversível.  \hint{Considere o vetor~$\bfv\in\FF^n$ que tem
    coordenadas~$\alpha$, $\beta$ e~$-1$ nas posições~$r$, $s$ e~$t$ e
  calcule~$A^{-1}A\bfv$ de dois jeitos.}

\item Seja $A\in\FF^{R\times C}$ uma matriz inversível.  Considere a
  função linear $f_A\in L(\FF^R,\FF^R)$ associada a~$A$.  Prove que
  $(f_A)^{-1}=f_{A^{-1}}$. 

\item Seja~$A$ uma matriz inversível.  Prove que a transposta~$A^\top$
  de~$A$ é inversível.  Prove que $(A^\top)^{-1}=(A^{-1})^\top$.
  \hint{Lembre que $(AB)^\top=B^\top A^{\top}$.}

\item Neste exercício, trabalhamos em~$\RR^n$.  Dados
  $\bfx=(x_1,\dots,x_n)$ e~$\bfy=(y_1,\dots,y_n)$ em~$\RR^n$,
  definimos a \textit{distância}~$d(\bfx,\bfy)$ entre~$\bfx$ e~$\bfy$
  como sendo
  \begin{equation}
    \label{eq:16}
    \sqrt{(\bfx-\bfy)\cdot(\bfx-\bfy)}
    =\sqrt{(x_1-y_1)^2+\dots+(x_n-y_n)^2}.
  \end{equation}
  Seja $\bfu=(u_1,\dots,u_n)\in\RR^n$ um ``versor'', isto é, suponha
  que $u_1^2+\dots+u_n^2=1$, e considere a reta
  \begin{equation}
    \label{eq:17}
    r_\bfu=\Span\{\bfu\}=\{\alpha\bfu\:\alpha\in\RR\}.
  \end{equation}
  Fixe~$\bfv\in\RR^n$.  Definimos a \textit{projeção} de~$\bfv$
  em~$r_\bfu$ como sendo um elemento~$\bfp^*$ de~$r_\bfu$ tal que
  $d(\bfp^*,\bfv)$ é o menor possível, isto é, tal que
  \begin{equation}
    \label{eq:18}
    d(\bfp^*,\bfv)=\min\{d(\bfp,\bfv)\:\bfp\in r_\bfu\}.
  \end{equation}
  Para provar que tal projeção~$\bfp^*$ existe e é único, considere
  \begin{equation}
    \label{eq:19}
    \bfq=M\bfv,
  \end{equation}
  onde~$M$ é a matriz~$\bfu\bfu^\top$ (aqui estamos
  considerando~$\bfu$ como sendo um vetor coluna, de forma que~$M$ é
  uma matriz $n\times n$).
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $\bfq$ pertence a~$r_\bfu$.
  \item Prove que, para todo~$\bfp\in r_\bfu$, vale que
    \begin{equation}
      \label{eq:24}
      d(\bfp,\bfv)\geq d(\bfq,\bfv), 
    \end{equation}
    e que vale a igualdade em~$\eqref{eq:24}$ se e só se~$\bfp=\bfq$. 
  \item Conclua que a projeção de~$\bfv$ em~$r_\bfu$ é única, e
    que~$\bfq$ é tal projeção.
  \item Prove que a função~$\pi\:\RR^n\to r_\bfu$ que
    leva~$\bfv\in\RR^n$ em sua projeção~$\bfp^*\in r_\bfu$ é uma
    função linear.
  \item Prove que a função~$\pi$ é tal que $\pi(\bfx)=\bfx$ para
    todo~$\bfx\in r_\bfu$.
  \end{enumerate}
  \hint{Considere os elementos de~$\RR^n$ como vetores coluna.  Use
    que $\bfx\cdot\bfy$ pode ser interpretado como o
    produto~$\bfy^\top\bfx$ para todo~$\bfx$ e~$\bfy$ em~$\RR^n$.}
  \datedue{22/9/2025}

\item\label{E:51} 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 $MN=I_m$, onde~$I_m\in\FF^{m\times m}$
  é a matriz identidade~$m\times m$.  Prove que os~$\bfv_i$
  ($1\leq i\leq n$) geram~$\FF^m$.

\item\label{E:51b} 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: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_52}
    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_52}), 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.
  \hint{Leia a Seção~4.11.2 de \textbf{PNK}.} \datedue{25/9/2025} 

\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)$.  \hint{Basta observar que
    $\cC'=\Null M$, onde~$M$ é a matriz de incidência de~$G$.}
  \NB{Para simplificar a notação, em geral
    identificamos~$\cC'=\Null M$ com~$\cC$, identificando a função
    indicadora~$\dsone_F$ com~$F$.  Com esta identificação,
    $\cC=\Null M$.}
\item\label{E:circuito} Seja~$G=(V,E)$ um grafo.  Um \textit{circuito}
  em~$G$ é 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}
    de~$G$ 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,\dots,v_{\ell-1}$ são todos distintos e
    (\textit{c})~$v_\ell=v_0$.  Seja~$M\in\GF(2)^{V\times E}$ a matriz
    de incidência de~$G$ (veja~\ref{E:incidence}).  Prove que se~$G$
    contém um circuito, então $\Null M\neq\{\bfzero\}$.
    
\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 comentado 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}
    é tal que $\cB\subset\cC^\perp$, e que~$\cB$ é um subespaço
    vetorial de~$\GF(2)^E$ (aqui estamos identificando
    aqui~$B_U\subset E$ com~$\dsone_{B_U}\in\GF(2)^E$).
  \item Suponha que~$G$ tenha~$n$ vértices e~$c$ componentes conexas.
    Encontre um conjunto gerador de~$\cB$ com $n-c$ elementos. 
  \end{enumerate}
  
\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_52}.  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: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_61}
      \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_61}
      \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_36}
    \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_36} é 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 Suponha que~$F$ seja o conjunto de arestas de um
    $(x,y)$-caminho em~$G$, isto é, de um caminho que começa em~$x$ e
    termina em~$y$.  Verifique que~\eqref{eq:8_36} vale.
  \item É verdade que a validade de~\eqref{eq:8_36} implica que~$F$ é
    o conjunto de arestas de um $(x,y)$-caminho em~$G$?  Prove ou dê
    contraexemplo. 
  \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_36} implica que existe um
    $(x,y)$-caminho em~$H$.  \hint{Considere o conjunto~$A\subset V$
      dos vértices acessíveis a partir de~$x$ por caminhos 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_36} diz sobre~$J$?  (Tenha em mente o
      Exercício~\ref{E:47}).}
  \end{enumerate}
 
\item\label{E:63} Seja~$G=(V,E)$ um grafo.  Seja~$F\subset E$ um
  subconjunto de arestas de~$G$ e suponha que
  \begin{equation}
    \label{eq:8_36}
    \sum_{f\in F}\dsone_f=\bfzero,
  \end{equation}
  onde estamos trabalhando em~$\GF(2)$.  Prove que~$F$ contém o
  conjunto de arestas de um circuito de~$G$ (veja o
  Exercício~\ref{E:circuito}).  Continuando com o
  Exercício~\ref{E:circuito}, prove agora que se
  $\Null M\neq\{\bfzero\}$, então~$G$ contém um circuito.  Conclua que
  as seguintes três afirmações são equivalentes:
  \begin{enumerate}[label=\rmlabel]
  \item o grafo~$G$ é \textit{acíclico}, isto é, não contém circuitos,
  \item $\Null M=\{\bfzero\}$,
  \item os vetores $\dsone_e\in\GF(2)^V$ ($e\in E$) são linearmente
    independentes.
  \end{enumerate}

\item\label{E:min_circ} Seja~$G=(V,E)$ um grafo e~$F\subset E$ um
  conjunto de arestas de~$G$.  No que segue, trabalhamos
  sobre~$\GF(2)$.  Suponha que os vetores $\dsone_f\in\GF(2)^V$
  ($f\in F$) são linearmente dependentes, mas que para
  todo~$F'\subset F$ com~$F'\neq F$, temos que os vetores
  $\dsone_f\in\GF(2)^V$ ($f\in F'$) são linearmente independentes.
  Prove que~$F$ é o conjunto de arestas de um circuito de~$G$.
  
\item\label{E:49} Seja~$G=(V,E)$ um grafo.  Dizemos que~$F\subset E$ é
  \textit{aresta-gerador} em~$G$ se para toda aresta $\{x,y\}\in E$
  de~$G$, 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_e\:e\in E\}\subset\Span\{\dsone_f\:f\in F\}.
  \end{equation}
  \NB{O espaço no lado esquerdo de~\eqref{eq:9b} é às vezes conhecido
    como o \textit{espaço das arestas de~$G$} e é denotado~$C_1(G)$}
  \hint{Estude o Exercício~\ref{E:36}} \datedue{25/9/2025}
  
  \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 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}
      Lembre-se do Exercício~\ref{E:51b}.}
  \end{enumerate}% \datedue{13/10/2024}

\item (\textit{M}) Lembre que~$\RR$ é um espaço vetorial sobre~$\QQ$
  (veja o Exercício~\ref{E:21}).
  \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:21}).  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\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{2/10/2025}

\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_69}
    S=\{\dsone_e\:e\in E\}\subset\GF(2)^V
  \end{equation}
  e
  \begin{equation}
    \label{eq:18_69}
    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.  \hint{Use o Exercício~\ref{E:36}\ref{E:36iii} ou
      lembre-se do Exercício~\ref{E:63}.}
  \end{enumerate} 

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