%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Sunday 05 Oct 2025 06:10:57p.m. -03 by yoshi on ponpoko>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno,a4paper]{amsart}

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

\addto\captionsbrazil{\renewcommand\proofname{Prova}}

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

%\usepackage{lmodern}
\usepackage{amssymb}

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

\makeatletter
\let\origsection=\section \def\section{\@ifstar{\origsection*}{\mysection}} 
\def\mysection{\@startsection{section}{1}\z@{.7\linespacing\@plus\linespacing}{.5\linespacing}{\normalfont\scshape\centering\S}}
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\usepackage[ruled]{algorithm2e}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%\usepackage{amsthm}
\newtheorem{teorema}{Teorema}
\newtheorem{conjectura}[teorema]{Conjectura}
\newtheorem{lema}[teorema]{Lema}
\newtheorem{proposicao}[teorema]{Proposição}
\newtheorem{fato}[teorema]{Fato}
\newtheorem{afirmacao}[teorema]{Afirmação}
\newtheorem{corolario}[teorema]{Corolário}

\numberwithin{teorema}{subsection} % important bit

% \newtheorem{rem}[teorema]{Remark}
% \newtheorem*{remark*}{Remark}
% \newtheorem{claim}[]{Claim}

\theoremstyle{remark}
\newtheorem{remark}{Observação}
\newtheorem*{uremark}{Observação}
\newtheorem{exemplo}[teorema]{Exemplo}
%\newtheorem*{remark}{Remark}
\newtheorem{definicao}  [teorema] {Definição}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  Page Layout
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{bbm}
\footskip28pt
\usepackage{fancyhdr}
\pagestyle{fancy}

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

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

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

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

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\sdiff{\bigtriangleup}
\def\Div{\mathop{\rm Div}\nolimits}
\def\id{\mathop{\rm id}\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\Span{\mathop{\rm Span}}
\def\Aff{\mathop{\rm Aff}}
\def\Conv{\mathop{\rm Conv}}
\def\Null{\mathop{\rm Null}}
\def\nullity{\mathop{\rm nuli}}
\def\Ker{\mathop{\rm Ker}}
\def\Im{\mathop{\rm Im}}
\def\posto{\mathop{\rm posto}}
\def\Sol{\mathop{\rm Sol}}
\def\Ave{\mathop{\rm Ave}}
\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\bfk{\mathbf{k}}
\def\bfp{\mathbf{p}}
\def\bfs{\mathbf{s}}
\def\bfu{\mathbf{u}}
\def\bfv{\mathbf{v}}
\def\bfw{\mathbf{w}}
\def\bfx{\mathbf{x}}
\def\bfy{\mathbf{y}}
\def\bfz{\mathbf{z}}
\def\bfalpha{\boldsymbol\alpha}
\def\bfbeta{\boldsymbol\beta}
\def\bfzero{\mathbf{0}}
\def\dsone{\mathds{1}}
\def\bfX{\mathbf{X}}
\def\bfdelta{\boldsymbol\delta}

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

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother
\usepackage{enumitem}
\newcommand\rmlabel{\upshape({\itshape\roman*\,\/})}
\newcommand\RMlabel{\upshape(\Roman*)}
\newcommand\alabel{\upshape({\itshape\alph*\,\/})}
\newcommand\Alabel{\upshape({\itshape\Alph*\,\/})}
\newcommand\nlabel{\upshape({\itshape\arabic*\,\/})}
\newcommand\nlabelp{\upshape(P\arabic*)}
\newcommand\nlabelE{\bf\upshape E\arabic*}

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

\begin{document}
\title[MAC0122 Álgebra Linear I (BCC)]%
{Álgebra Linear~I (BCC)\\
  \bigskip\bigskip{\bf\textit{2$^{\text{\tiny o}}$ Semestre de 2024}}\\
  \bigskip\bigskip Resumo
}  

\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{Observação.}
Este resumo pode ser útil para rever os conceitos mais importantes
vistos nesta disciplina.  Não há pretensão de ser um texto completo.
Este texto será atualizado e revisado conforme formos avançando no
semestre.  Correções, perguntas e comentários serão bem-vindos.

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

\setcounter{section}{-1}

\section{Funções e outras coisas básicas}
\label{sec:0}
Dados dois conjuntos~$A$ e~$B$, denotamos por~$A^B$ o conjunto das
funções $f\:B\to A$.

A função \textit{identidade} em~$A$ é a função $\id_A\:A\to A$ tal que
$\id_A(a)=a$ para todo~$a\in A$.  Suponha que $f\:B\to A$ e
$g\:A\to B$ sejam tais que $f\circ g=\id_A$ e $g\circ f=\id_B$.
Dizemos então que~$f$ e~$g$ são funções \textit{inversas} uma da
outra.  Se~$f$ admite uma função inversa, então ela é única.
Escrevemos~$f^{-1}$ para tal inversa.

Uma função $f\:A\to B$ admite uma inversa se e só se~$f$ for injetora
e sobrejetora.

\section{Corpos}
\label{sec:1}

Nesta disciplina, trabalhamos com os corpos~$\RR$, $\CC$ e~$\GF(2)$.
Ocasionalmente, poderemos também considerar o corpo~$\QQ$ ou o
corpo~$\ZZ/p\ZZ$ dos inteiros módulo~$p$.  Escrevemos~$\FF$ para
denotar o corpo sobre o qual estamos trabalhando.

\section{Vetores}
\label{sec:2}

Nesta disciplina, em geral, quando dizemos que~$\bfv$ é um vetor,
temos um corpo~$\FF$ e um conjunto~$D$ fixo, e~$\bfv\in\FF^D$.
Ademais, os elementos de~$\FF$ são chamados de \textit{escalares}.  Em
geral, $D$~será um conjunto finito e apenas ocasionalmente
consideraremos o caso em que~$D$ não é finito.

\subsection{Operações com vetores}
\label{sec:oper-com-vetor}
Sejam~$\bfu$ e~$\bfv$ vetores em~$\FF^D$ e~$\alpha$ um escalar (isto
é, $\alpha\in\FF$).  A soma $\bfu+\bfv$ dos vetores~$\bfu$ e~$\bfv$ é
o vetor em~$\FF^D$ tal que $(\bfu+\bfv)(d)=\bfu(d)+\bfv(d)$ para
todo~$d\in D$.  O produto~$\alpha\bfu$ é o vetor em~$\FF^D$ dado por
$(\alpha\bfu)(d)=\alpha\bfu(d)$ para todo~$d\in D$.  (Essa é a forma
usual de se definir a soma de duas funções com o mesmo domínio (``soma
ponto a ponto'') e produto de funções por escalares.)

Finalmente, definimos o \textit{produto escalar} ou \textit{produto
  interno}~$\bfu\cdot\bfv$ (\textit{dot-product}) de~$\bfu$ e~$\bfv$
como sendo o escalar
\begin{equation}
  \label{eq:dot-prod}
  \sum_{d\in D}\bfu(d)\bfv(d).
\end{equation}

Produtos escalares podem ser definidos de forma mais geral.  Assim, o
produto escalar que acabamos de definir é às vezes chamado de produto
escalar \textit{padrão}.

\section{Espaços vetoriais}
\label{sec:3}

\subsection{Combinações lineares}
\label{sec:combinacoes-lineares}
Dados vetores $\bfv_1,\dots,\bfv_n$ e
escalares~$\alpha_1,\dots,\alpha_n$, podemos considerar a
\textit{combinação linear}
\begin{equation}
  \label{eq:comb_lin}
  \alpha_1\bfv_1+\dots+\alpha_n\bfv_n.
\end{equation}

\subsection{Espaços gerados}
\label{sec:espacos-gerados}
Dados vetores $\bfv_1,\dots,\bfv_n$, o conjunto
\begin{equation}
  \label{eq:span}
  \Span\{\bfv_1,\dots,\bfv_n\}
  =\Big\{\sum_{1\leq i\leq n}\alpha_i\bfv_i\:\alpha_i\in\FF\text{ para todo
  }i\Big\}
\end{equation}
das combinações lineares dos~$\bfv_i$ é o \textit{espaço gerado} por
esses vetores.

\subsection{Variedades lineares (flats) contendo~$\bfzero$}
\label{sec:vari-line-flats}
Certos conjuntos de vetores são chamados de variedades lineares
(flats).  Consideramos aqui variedades lineares que contém~$\bfzero$.
Um conjunto $U\subset\FF^D$ é uma \textit{variedade linear} (ou
\textit{flat}) \textit{que contém~$\bfzero$} se valem as seguintes
três propriedades:
\begin{enumerate}
\item[(V1)] $\bfzero\in U$, 
\item[(V2)] $\bfu+\bfv\in U$ sempre que~$\bfu\in U$ e~$\bfv\in U$, e 
\item[(V3)] $\alpha\bfv\in U$ sempre que~$\alpha\in\FF$ e~$\bfv\in U$.
\end{enumerate}

\subsubsection{Espaços gerados por vetores}
\label{sec:espacos-gerados-por}
Sejam~$\bfv_i$ ($1\leq i\leq n$) vetores quaisquer e considere
$S=\Span\{\bfv_1,\dots,\bfv_n\}$.  Note que~$S$ satisfaz~(V1), (V2)
e~(V3) acima e assim~$S$ é uma variedade linear que contém~$\bfzero$.

\subsubsection{Espaço das soluções de sistemas lineares homogêneos}
\label{sec:espaco-das-solucoes}
Sejam dados $\bfa_i\in\FF^D$ ($1\leq i\leq n$) e considere o sistema
de equações lineares homogêneas\footnote{Equações lineares
  \textit{homogêneas} são equações da forma $\bfa\cdot\bfx=\beta$
  com~$\beta=0$.}
\begin{equation}
  \label{eq:lin_sys}
  \begin{cases}
    \bfa_1\cdot\bfx=0\\
    \quad\;\;\dots\\
    \bfa_n\cdot\bfx=0.\\    
  \end{cases}
\end{equation}
Seja $T=\{\bfx\in\FF^D\:\bfx\text{ satisfaz \eqref{eq:lin_sys}}\}$ o
conjunto das soluções de~\eqref{eq:lin_sys}.  Note que~$T$
satisfaz~(V1), (V2) e~(V3) e assim~$T$ é uma variedade linear que
contém~$\bfzero$.

\subsection{Espaços vetoriais}
\label{sec:espacos-vetoriais}
Nesta disciplina, definimos \textit{espaços vetoriais} como sendo
variedades lineares contidas em~$\FF^D$ que contém~$\bfzero$.  Dizemos
que tais espaços vetoriais são espaços vetoriais \textit{sobre~$\FF$}.
Os conjuntos~$S$ e~$T$ de~\S\ref{sec:espacos-gerados-por}
e~\S\ref{sec:espaco-das-solucoes} são portanto espaços vetoriais
sobre~$\FF$. 

\begin{uremark}
Em certas ocasiões, teremos conjuntos~$V$
que podem ser identificados com os espaços vetoriais definidos acima.
Nesses casos, vamos também nos referir a tais conjuntos como espaços
vetoriais.  
\end{uremark}

\begin{exemplo}
  \label{ex:poly}
  Seja~$V$ o conjunto dos polinômios de grau no máximo~$3$ com
  coeficientes em~$\FF$, munido com as operações de soma de polinômios
  e produto por escalar usuais: se $p(X)=a_0+a_1X+a_2X^2+a_3X^3$ e
  $q(X)=b_0+b_1X+b_2X^2+b_3X^3$ então
  \begin{equation}
    \label{eq:poly_sum}
    p(X) + q(X) = (a_0+b_0)+(a_1+b_1)X+(a_2+b_2)X^2+(a_3+b_3)X^3
  \end{equation}
  e se~$\alpha\in\FF$ então
  \begin{equation}
    \label{eq:poly_sum.2}
    \alpha p(X) = \alpha a_0+\alpha a_1X+\alpha a_2X^2+\alpha a_3X^3.
  \end{equation}
  Então~$V$ pode ser naturalmente identificado com~$\FF^4$ e assim~$V$
  é um espaço vetorial sobre~$\FF$.
\end{exemplo}

\subsubsection{Subespaços vetoriais}
\label{sec:subespacos-vetoriais}
Sejam~$U$ e~$V$ espaços vetoriais, com~$U\subset V$.  Dizemos então
que~$U$ é um \textit{subespaço} vetorial de~$V$.

\subsubsection{Espaços vetoriais abstratos}
\label{sec:espacos-abstratos}
Em um tratamento mais geral de álgebra linear, definimos espaços
vetoriais sobre um corpo~$\FF$ como sendo triplas~$(V,+,\,\cdot\,)$,
onde~$V$ é um conjunto arbitrário e~$+\:V\times V\to V$ (soma de
elementos de~$V$) e~$\,\cdot\,\:\FF\times V\to V$ (multiplicação de
elementos de~$V$ por escalares) são operações que satisfazem certos
axiomas (veja, por exemplo
\href{https://en.wikipedia.org/wiki/Vector_space#Definition_and_basic_properties}{esta
  página}).

Nesta disciplina, o conjunto~$V$ na definição acima será sempre um
subconjunto de~$\FF^D$ para algum~$D$ finito que satisfaz~(V1), (V2)
e~(V3) (ou~$V$ pode ser naturalmente identificado com um tal
subconjunto), e assim adotamos nossa definição bem mais restrita.  Do
ponto de vista computacional, sempre trabalharemos com tais~$V$
concretos.

\subsection{Espaços afins}
\label{sec:espacos-afins}
Consideramos até agora variedades lineares que contém~$\bfzero$, e
denominamos tais variedades de espaços vetoriais.  Uma variedade
linear geral não necessariamente contém~$\bfzero$.  Definimos uma
\textit{variedade linear} como sendo conjuntos de vetores da forma
\begin{equation}
  \label{eq:espaco afim}
  \bfu + V = \{\bfu + \bfv\:\bfv\in V\}, 
\end{equation}
onde~$V$ é um espaço vetorial.  Variedades lineares são também
conhecidas como \textit{espaços afins}.

\subsubsection{Fecho afim}
\label{sec:fecho-afim}
Sejam~$\bfw_0,\dots,\bfw_n$ vetores em um espaço vetorial e
sejam~$\beta_0,\dots,\beta_n$ escalares.  A combinação linear
\begin{equation}
  \label{eq:2}
  \sum_{0\leq i\leq n}\beta_i\bfw_i
\end{equation}
é uma \textit{combinação linear afim} dos~$\bfw_i$ ($0\leq i\leq n$)
se~$\sum_{0\leq i\leq n}\beta_i=1$.  O \textit{fecho afim} dos
vetores~$\bfw_i$ ($0\leq i\leq n$) é o conjunto
\begin{equation}
  \label{eq:aff_hull}
  \Aff\{\bfw_0,\dots,\bfw_n\}=\Big\{\sum_{0\leq i\leq
    n}\beta_i\bfw_i\:\beta_0+\dots+\beta_n=1\Big\}
\end{equation}
das combinações afins dos~$\bfw_i$ ($0\leq i\leq n$).

\begin{exemplo}
  \label{ex:aff}
  Sejam~$\bfw_0$ e~$\bfw_1$ dois pontos distintos em~$\RR^2$
  ou~$\RR^3$.  Então $\Aff\{\bfw_0,\bfw_1\}$ é a reta determinada por
  esses pontos.  Sejam agora~$\bfw_0$, $\bfw_1$ e~$\bfw_2$ três pontos
  no~$\RR^3$, não colineares.  Então $\Aff\{\bfw_0,\bfw_1,\bfw_2\}$ é
  o plano determinado por esses pontos.
\end{exemplo}

\begin{proposicao}
  \label{prop:0}
  Sejam~$\bfu$ e~$\bfv_1,\dots,\bfv_n$ vetores em~$\FF^D$.  Então
  \begin{equation}
    \label{eq:5}
    \bfu+\Span\{\bfv_1,\dots,\bfv_n\}=\Aff\{\bfu,\bfu+\bfv_1,\dots,\bfu+\bfv_n\}. 
  \end{equation}
  Equivalentemente, se~$\bfw_0,\dots,\bfw_n$ são vetores em~$\FF^D$,
  então
  \begin{equation}
    \label{eq:1}
    \Aff\{\bfw_0,\dots,\bfw_n\}=\bfw_0+\Span\{\bfw_1-\bfw_0,\dots,\bfw_n-\bfw_0\}.
  \end{equation}\qed
\end{proposicao}
% \begin{proof}
%   Exercício.
% \end{proof}

\begin{corolario}
  \label{cor:0}
  Fechos afins são espaços afins.
\end{corolario}
\begin{proof}
  A identidade~\eqref{eq:1} diz que fechos afins são da
  forma~\eqref{eq:espaco afim}, isto é, são espaços afins, pois
  espaços da forma $\Span\{\bfx_1,\dots,\bfx_n\}$ são espaços
  vetoriais.
\end{proof}

\subsubsection{Sistemas lineares homogêneos e não-homogêneos}
\label{sec:sist-line-homog}
Considere o sistema de equações lineares
homogêneas~\eqref{eq:lin_sys}.  Sejam dados agora~$\beta_i\in\FF$
($1\leq i\leq n$), e considere o sistema~$(S)$ dado por
\begin{equation}
  \label{eq:lin_sys_beta}
(S)\quad
  \begin{cases}
    \bfa_1\cdot\bfx=\beta_1\\
    \quad\;\;\dots\\
    \bfa_n\cdot\bfx=\beta_n, 
  \end{cases}
\end{equation}
onde $\bfx=(x_d)_{d\in D}$ é o vetor de indeterminadas (lembre que
$\bfa_i\in\FF^D$ para todo~$1\leq i\leq n$).  O
sistema~\eqref{eq:lin_sys} é o \textit{sistema linear homogêneo
  associado} ao sistema~$(S)$ acima.  Chamemos o
sistema~\eqref{eq:lin_sys} de~$(H)$ (de homogêneo).

\begin{proposicao}
  \label{prop:1}
  Suponha que~$\bfu_1\in\FF^D$ seja uma solução de~$(S)$ e
  seja~$\bfu_2\in\FF^D$.  São equivalentes$:$
  \begin{enumerate}[label=\rmlabel]
  \item $\bfu_2$ é solução de~$(S)$,
  \item $\bfu_2-\bfu_1$ é solução de~$(H)$.
  \end{enumerate}\qed
\end{proposicao}
% \begin{proof}
%   Exercício.
%\end{proof}

Sejam
\begin{equation}
  \label{eq:S_sols}
  U=\{\bfu\:\bfu\text{ é solução de }(S)\}
\end{equation}
e
\begin{equation}
  \label{eq:H_sols}
  T=\{\bfv\:\bfv\text{ é solução de }(H)\}.
\end{equation}
Sabemos que~$T$ é um espaço vetorial
(veja~\S\ref{sec:espaco-das-solucoes}). 

\begin{teorema}
  \label{teo:system_sols}
  Há duas possibilidades para~$U$$:$
  \begin{enumerate}[label=\rmlabel]
  \item $U=\emptyset$ ou
  \item\label{item:ss_ii} $U=\bfu+T$, onde~$\bfu$ é uma solução
    de~$(S)$. 
  \end{enumerate}
  Em particular, se~$U$ é não-vazio, então~$U$ é um espaço afim. \qed
\end{teorema}

\begin{corolario}
  \label{cor:system_sols}
  Se~$(S)$ admite solução, então ela é única se e só
  se~$(H)$ admite apenas a
  solução~$\bfzero$.  Mais geralmente, o número de soluções
  de~$(S)$ é zero ou é igual ao número de soluções de~$(H)$.
\end{corolario}

\begin{corolario}
  \label{cor:system_sols2}
  O conjunto de soluções de um sistema linear ou é vazio ou é um
  espaço afim.
\end{corolario}

\subsection{Fechos convexos}
\label{sec:fechos-convexos}
Sejam~$\bfw_0,\dots,\bfw_n$ vetores em~$\FF^D$, com~$\FF=\RR$ ou~$\CC$
e sejam~$\beta_0,\dots,\beta_n$ escalares.  A combinação linear
\begin{equation}
  \label{eq:2b}
  \sum_{0\leq i\leq n}\beta_i\bfw_i
\end{equation}
é uma \textit{combinação convexa} dos~$\bfw_i$ ($0\leq i\leq n$)
se~$\sum_{0\leq i\leq n}\beta_i=1$ e~$\beta_i\geq0$ para
todo~$0\leq i\leq n$.  O \textit{fecho convexo} dos vetores~$\bfw_i$
($0\leq i\leq n$) é o conjunto
\begin{equation}
  \label{eq:conv_hull}
  \Conv\{\bfw_0,\dots,\bfw_n\}=\Big\{\sum_{0\leq i\leq
    n}\beta_i\bfw_i\:\beta_0+\dots+\beta_n=1\text{ e
  }\beta_i\geq0\text{ para todo }0\leq i\leq n\Big\}
\end{equation}
das combinações convexas dos~$\bfw_i$ ($0\leq i\leq n$).

\begin{exemplo}
  \label{ex:conv}
  Sejam~$\bfw_0$ e~$\bfw_1$ dois pontos distintos em~$\RR^2$
  ou~$\RR^3$.  Então $\Conv\{\bfw_0,\bfw_1\}$ é o segmento de reta com
  extremos~$\bfw_0$ e~$\bfw_1$.  Sejam agora~$\bfw_0$, $\bfw_1$
  e~$\bfw_2$ três pontos no~$\RR^2$ ou no~$\RR^3$, não colineares.
  Então $\Conv\{\bfw_0,\bfw_1,\bfw_2\}$ é o triângulo com
  vértices~$\bfw_0$, $\bfw_1$ e~$\bfw_2$.
\end{exemplo}

\section{Matrizes}
\label{sec:matrizes}

\subsection{Matrizes como funções}
\label{sec:matr-como-func}
Sejam~$R$ e~$C$ conjuntos finitos e~$\FF$ um corpo.  Uma matriz com
\textit{linhas indexadas por~$R$} e \textit{colunas indexadas por~$C$}
é um elemento de~$\FF^{R\times C}$.

Seja~$M\in\FF^{R\times C}$ uma matriz.  Para cada~$r\in R$, temos a
\textit{linha} $M(r,\,\cdot\,)\:C\to\FF$ que leva~$c$ em~$M(r,c)$ para
todo~$c\in C$.  Analogamente, para cada~$c\in C$, temos a
\textit{coluna} $M(\,\cdot\,,c)\:R\to\FF$ que leva~$r$ em~$M(r,c)$
para todo~$r\in R$.

Podemos denotar a linha $M(r,\,\cdot\,)$ por~$M_{r*}$ e a coluna
$M(\,\cdot\,,c)$ por~$M_{*c}$.

\subsubsection{Transposta}
\label{sec:transposta}
Dada uma matriz~$M\in\FF^{R\times C}$, definimos a \textit{transposta}
de~$M$ como sendo $M^\top\in\FF^{C\times R}$ dada por
$M^\top(c,r)=M(r,c)$ para todo~$(c,r)\in C\times R$.
Quando~$M^\top=M$, dizemos que~$M$ é \textit{simétrica}.

\subsection{Espaço das matrizes}
\label{sec:espaco-das-matrizes}
Note que as matrizes~$M$ em~$\FF^{R\times C}$ formam um espaço
vetorial sobre~$\FF$: basta considerar~$R\times C$ como um sendo
conjunto~$D$ e pensar em~$M$ como sendo um membro
de~$\FF^D=\FF^{R\times C}$.

\subsection{Espaço das linhas e espaço das colunas}
\label{sec:o-espaco-das}
Dada uma matriz~$M\in\FF^{R\times C}$, o espaço
\begin{equation}
  \label{eq:row_space}
  \Span\{M_{r*}\:r\in R\}\subset\FF^C
\end{equation}
gerado pelas linhas $M_{r*}$ ($r\in R$) de~$M$ é o
\textit{espaço das linhas} de~$M$.  Analogamente, 
\begin{equation}
  \label{eq:column_space}
  \Span\{M_{*c}\:c\in C\}\subset\FF^R
\end{equation}
é o \textit{espaço das colunas} de~$M$.

\subsection{Produtos matriz-vetor e vetor-matriz}
\label{sec:prod-matr-vetor}
Seja~$M\in\FF^{R\times C}$ uma matriz.  Sejam também~$\bfu\in\FF^R$
e~$\bfv\in\FF^C$.  Definimos os \textit{produtos} $\bfu*M\in\FF^C$
e~$M*\bfv\in\FF^R$ pondo
\begin{equation}
  \label{eq:uM}
  (\bfu*M)(c)=\sum_{r\in R}\bfu(r)M(r,c)
\end{equation}
para todo~$c\in C$ e
\begin{equation}
  \label{eq:Mv}
  (M*\bfv)(r)=\sum_{c\in C}M(r,c)\bfv(c)
\end{equation}
para todo~$r\in R$.

\subsubsection{Interpretações úteis dos produtos}
\label{sec:interpr-uteis-dos}
Sejam~$M\in\FF^{R\times C}$, $\bfu\in\FF^R$ e $\bfv\in\FF^C$.  Temos: 
\begin{enumerate}[label=\rmlabel]
\item $\bfu*M$ é a combinação linear $\sum_{r\in R}\bfu(r)M_{r*}$
  das linhas~$M_{r*}$ de~$M$.  Assim, $\bfu*M$ pertence ao espaço
  das linhas de~$M$.
\item\label{it:row_lc} $M*\bfv$ é a combinação linear
  $\sum_{c\in C}\bfv(c)M_{*c}$ das colunas~$M_{*c}$ de~$M$.  Assim,
  $M*\bfv$ pertence ao espaço das colunas de~$M$.
\end{enumerate}
Valem também:
\begin{enumerate}[label=\rmlabel]\setcounter{enumi}2
\item $\bfu*M$ tem como entradas os produtos internos $\bfu\cdot
  M_{*c}$ ($c\in C$); isto é, $(\bfu*M)(c)=\bfu\cdot M_{*c}$.
\item\label{it:row_dp} $M*\bfv$ tem como entradas os produtos internos
  $M_{r*}\cdot\bfv$ ($r\in R$); isto é, $(M*\bfv)(r)=M_{r*}\cdot\bfv$.
\end{enumerate}

\subsubsection{Sistemas lineares}
\label{sec:sistemas-lineares}
Considere o sistema linear~$(S)$ em~\eqref{eq:lin_sys_beta}.  Seja
$R=\{1,\dots,n\}$.  Lembre que $\bfa_i\in\FF^D$ ($1\leq i\leq n$) e
$\bfx=(x_d)_{d\in D}$ é o vetor das indeterminadas de~$(S)$.  Monte a
matriz $M\in\FF^{R\times D}$ cuja $i$-ésima linha é~$\bfa_i$
($i\in R$).  Então~$(S)$ é equivalente a resolver a equação
$M*\bfx=\bfbeta$, onde~$\bfbeta=(\beta_i)_{i\in R}$
(veja~\ref{it:row_dp} acima). 

Lembrando~\ref{it:row_lc} acima, a observação do parágrafo anterior
implica que resolver o sistema~\eqref{eq:lin_sys_beta} equivale a
encontrar coeficientes adequados para escrever~$\bfbeta$ como
combinação linear das colunas de~$M$.  Em particular, o sistema~$(S)$
tem solução se e só se $\bfbeta$ pertence ao espaço das colunas
de~$M$, isto é, se e só se $\bfbeta\in\Span\{M_{*d}\:d\in D\}$.

\subsection{Produto matriz-matriz}
\label{sec:prod-matr-matr}
Sejam $R$, $C$ e~$D$ conjuntos finitos e sejam~$A\in\FF^{R\times C}$
e~$B\in\FF^{C\times D}$ matrizes.  O \textit{produto}~$A*B$ de~$A$
e~$B$ é a matriz em~$\FF^{R\times D}$ com
\begin{equation}
  \label{eq:6}
  (A*B)(r,d)=\sum_{c\in C}A(r,c)B(c,d)
\end{equation}
para todo~$(r,d)\in R\times D$.

\subsubsection{Interpretações alternativas}
\label{sec:interpr-altern}
Sejam~$A$ e~$B$ como acima.  O produto~$A*B$ acima pode ser pensado de
formas alternativas:
\begin{enumerate}[label=\rmlabel]
\item $A*B$ é a matriz cuja $r$-ésima linha é $A_{r*}*B$ ($r\in R$), 
\item $A*B$ é a matriz cuja $d$-ésima coluna é $A*B_{*d}$ ($d\in D$) e 
\item $A*B$ é a matriz com $(AB)(r,d)=A_{r*}\cdot B_{*d}$
  ($(r,d)\in R\times D$).
\end{enumerate}

\subsubsection{Transposta do produto}
\label{sec:transp-do-prod}
Sejam~$A$ e~$B$ como acima.  Então $(A*B)^\top=B^\top*A^\top$.

\subsection{Notação de produto e vetores-coluna}
\label{sec:vetores-coluna}
Tradicionalmente, o símbolo~$*$ não é usado para denotar produtos de
vetores e matrizes.  A partir de agora vamos omitir~$*$ em nossos
produtos de vetores e matrizes.

Tradicionalmente, vetores em~$\FF^d$ são denotados como
matrizes~$d\times1$, isto é, como \textit{vetores-coluna}.  Podemos
adotar a convenção que vetores são vetores-coluna dentro do formalismo
que temos.  Para tanto, vamos pensar em $\bfv\in\FF^D$ como sendo uma
matriz em~$\FF^{D\times\{1\}}$.

Seja~$M\in\FF^{R\times C}$ uma matriz e sejam~$\bfu\in\FF^R$
e~$\bfv\in\FF^C$ vetores.  O produto $M*\bfv$ (veja~\eqref{eq:Mv})
pode ser pensado como o produto de matrizes~$M\bfv$, onde o
vetor~$\bfv$ é considerado como uma matriz em~$\FF^{C\times\{1\}}$.
Analogamente, o produto
$\bfu*M$ (veja~\eqref{eq:uM}) pode ser pensado como o produto de
matrizes $\bfu^\top M$, onde~$\bfu$ é considerado como uma matriz
em~$\FF^{R\times\{1\}}$ (note que, no produto, usamos a
transposta~$\bfu^\top\in\FF^{\{1\}\times R}$).

Finalmente, suponha que~$\bfx$ e~$\bfy$ sejam vetores em~$\FF^D$.
Podemos pensar no produto interno~$\bfx\cdot\bfy$ entre eles como
sendo o produto de matrizes~$\bfy^\top\bfx$ ou~$\bfx^\top\bfy$.

\subsection{A linearidade de aplicação $\bfv\mapsto A\bfv$ e $\Null
  A$} 
\label{sec:line-de-aplic}
Seja~$A$ uma matriz em~$\FF^{R\times C}$.  Podemos considerar a função
$f_A\:\FF^C\to\FF^R$ que leva $\bfv\in\FF^C$
em~$f_A(\bfv)=A\bfv\in\FF^R$ para todo~$\bfv\in\FF^C$.  Essa
aplicação é \textit{linear}, isto é,
\begin{enumerate}
\item[(L1)] $f_A(\alpha\bfv)=\alpha f_A(\bfv)$ para
  todo~$\alpha\in\FF$ e~$\bfv\in\FF^C$ e 
\item[(L2)] $f_A(\bfv+\bfw)=f_A(\bfv)+f_A(\bfw)$
  para todo~$\bfv$ e~$\bfw$ em~$\FF^C$. 
\end{enumerate}

A imagem inversa de~$\{\bfzero\}$ pela função~$f_A$ é o \textit{espaço
  nulo}~$\Null A$ de~$A$:
\begin{equation}
  \label{eq:Null_def}
  \Null A=f_A^{-1}(\{\bfzero\})=\{\bfv\in\FF^C\:f_A(\bfv)=\bfzero\}
  =\{\bfv\in\FF^C\:A\bfv=\bfzero\}.
\end{equation}
Note que~$\Null A$ nada mais é que o espaço das soluções do sistema
linear homogêneo $A\bfx=\bfzero$.  Assim, aqui estamos apenas dando um
nome para um conjunto que já ocorreu em~\S\ref{sec:espaco-das-solucoes}. 

\begin{proposicao}
  \label{prop:Null_VS}
  Seja~$A$ uma matriz em~$\FF^{R\times C}$ e~$\bfbeta$ um vetor
  em~$\FF^R$. 
  \begin{enumerate}[label=\rmlabel]
  \item O espaço nulo~$\Null A$ de~$A$ é um espaço vetorial.
  \item O conjunto das soluções do sistema linear $A\bfx=\bfbeta$ é
    vazio, ou é da forma $\bfu+\Null A$, onde~$\bfu$ é qualquer
    solução de $A\bfx=\bfbeta$.
  \end{enumerate}
\end{proposicao}

\subsection{Representação matricial de funções lineares}
\label{sec:repr-matr-de}
Sejam~$V$ e~$W$ espaços vetoriais sobre~$\FF$.  Uma função $f\:V\to W$
é \textit{linear} se
\begin{enumerate}
\item[(L1)] $f(\alpha\bfv)=\alpha f(\bfv)$ para
  todo~$\alpha\in\FF$ e~$\bfv\in V$ e 
\item[(L2)] $f(\bfv+\bfw)=f(\bfv)+f(\bfw)$
  para todo~$\bfv$ e~$\bfw$ em~$V$.
\end{enumerate}

\begin{uremark}
  Vimos em~\S\ref{sec:line-de-aplic} que se~$A\in\FF^{R\times C}$, então
  a função $f_A\:\bfv\in\FF^C\mapsto A\bfv\in\FF^R$ é uma função
  linear.  
\end{uremark}

\begin{fato}
  \label{f:0to0}
  Seja $f\:V\to W$ uma função linear.  Então $f(\bfzero)=\bfzero$. 
\end{fato}
\begin{proof}
  Como $f(\bfzero)=f(\bfzero+\bfzero)=f(\bfzero)+f(\bfzero)$, segue
  que $f(\bfzero)=\bfzero$.
\end{proof}

\begin{proposicao}
  \label{prop:lc}
  Seja $f\:V\to W$ uma função linear entre espaços vetoriais
  sobre~$\FF$.  Então, para quaisquer $\alpha_1,\dots,\alpha_n\in\FF$
  e $\bfv_1,\dots,\bfv_n\in V$, temos
  \begin{equation}
    \label{eq:8}
    f(\alpha_1\bfv_1+\dots+\alpha_n\bfv_n)
    =\alpha_1f(\bfv_1)+\dots+\alpha_nf(\bfv_n).
  \end{equation}
\end{proposicao}
\begin{proof}
  Indução em~$n$ (exercício).
\end{proof}

Seja $\bfe_s=\mathds{1}_{\{s\}}\in\FF^S$ para todo~$s\in S$.  Podemos
escrever todo~$\bfv\in\FF^S$ em função desses~$\bfe_s$:
\begin{equation}
  \label{eq:3}
  \bfv=\sum_{s\in S}\bfv(s)\bfe_s.
\end{equation}
Seja agora $f\:\FF^S\to\FF^T$ uma função linear.  Por~\eqref{eq:8}
e~\eqref{eq:3}, temos
\begin{equation}
  \label{eq:4}
  f(\bfv)=\sum_{s\in S}\bfv(s)f(\bfe_s).
\end{equation}
Seja~$\bff_t=\mathds{1}_{\{t\}}\in\FF^T$ para todo~$t\in T$ e escreva
cada~$f(\bfe_s)\in\FF^T$ em~\eqref{eq:4} em função desses~$\bff_t$:
\begin{equation}
  \label{eq:7}
  f(\bfe_s)=\sum_{t\in T}A(t, s)\bff_t.
\end{equation}
Em vista de~\eqref{eq:4} e~\eqref{eq:7}, temos
\begin{equation}
  \label{eq:9}
  f(\bfv)=\sum_{s\in S}\bfv(s)f(\bfe_s)
  =\sum_{s\in S}\bfv(s)\sum_{t\in T}A(t, s)\bff_t
  =\sum_{s\in S,\,t\in T}A(t,s)\bfv(s)\bff_t.
\end{equation}
A identidade~\eqref{eq:9} é equivalente a dizer que
\begin{equation}
  \label{eq:10}
  f(\bfv)=A\bfv, 
\end{equation}
onde~$A$ é a matriz em~$\FF^{T\times S}$ tal que $(t,s)\mapsto A(t,s)$
para todo~$(t,s)\in T\times S$.  Provamos o seguinte fato.

\begin{proposicao}
  \label{prop:L_is_matrix}
  Toda função linear $f\:\FF^S\to\FF^T$ é tal que existe uma matriz
  $A\in\FF^{T\times S}$ tal que $f(\bfv)=A\bfv$ para todo
  $\bfv\in\FF^S$.  De fato, tal matriz~$A$ é única e é tal que sua
  $s$-ésima coluna~$A_{*s}$ é~$f(\bfe_s)$ para todo~$s\in S$.
\end{proposicao}

A proposição acima tem o seguinte corolário.  Denotemos por~$I_S$ a
matriz identidade em~$\FF^{S\times S}$ e por $\id_{\FF^S}$ a função
identidade $\FF^S\to\FF^S$.

\begin{corolario}
  \label{cor:id_iff_I}
  Seja~$A\in\FF^{S\times S}$ uma matriz e $f_A\:\FF^S\to\FF^S$ a
  função linear $\bfv\in\FF^S\mapsto A\bfv\in\FF^S$ associada.  Então
  $A=I_S$ se e só sem $f_A=\id_{\FF^s}$.
\end{corolario}

\subsection{Funções lineares: injeção e sobrejeção}
\label{sec:func-line-injec}
Seja $f\:V\to W$ uma função linear.  Definimos o
\textit{núcleo}~$\Ker f$ de~$f$ como sendo a imagem inversa
de~$\{\bfzero\}$:
\begin{equation}
  \label{eq:kern_def}
  \Ker f=f^{-1}(\{\bfzero\})=\{\bfv\in V\:f(\bfv)=\bfzero\}.
\end{equation}
Se $f=f_A$ como em~\S\ref{sec:line-de-aplic}, isto é, $f$~é a
aplicação $\bfv\mapsto A\bfv$ para uma matriz~$A$, então
\begin{equation}
  \label{eq:kern_null}
  \Ker f=\Null A.
\end{equation}

\begin{proposicao}
  \label{prop:kern-inj}
  Uma função linear $f\:V\to W$ é injetora se e só se $\Ker
  f=\{\bfzero\}$. 
\end{proposicao}

No caso em que~$f=f_A$ para uma matriz~$A$, deduzimos que a aplicação
$\bfv\mapsto A\bfv$ é injetora se e só se~$\Null A=\{\bfzero\}$.  Na
verdade, já conhecemos esse fato: isso segue do
Teorema~\ref{teo:system_sols} (verifique).

O seguinte fato é simples mas importante.

\begin{proposicao}
  \label{prop:imf_vs}
  Seja $f\:V\to W$ uma função linear.  A imagem~$\Im f$ de~$f$ é um
  subespaço vetorial de~$W$.
\end{proposicao}

Veremos mais adiante métodos para decidir se~$f$ é sobrejetora, isto
é, se $\Im f=W$.

\subsection{Composição de funções lineares}
\label{sec:comp-de-func}
Sejam~$U$, $V$ e~$W$ espaços vetoriais sobre~$\FF$.  Sejam $g\:U\to V$
e $f\:V\to W$ funções lineares.  É imediato que a composta
$h=f\circ g\:U\to W$ é linear.  Suponha agora que~$U=\FF^R$, $V=\FF^S$
e~$W=\FF^T$.  Nesse caso, sabemos da Proposição~\ref{prop:L_is_matrix}
que existem matrizes $A\in\FF^{T\times S}$, $B\in\FF^{S\times R}$ e
$C\in\FF^{T\times R}$ univocamente determinadas tais que
$f(\bfv)=A\bfv$, $g(\bfu)=B\bfu$ e $h(\bfu)=C\bfu$, para todo
$\bfu\in U$ e $\bfv\in V$.  

\begin{proposicao}
  \label{prop:C=AB}
  Temos que $C=AB$.
\end{proposicao}
\begin{proof}
  Pela Proposição~\ref{prop:L_is_matrix}, sabemos que, para todo~$r\in
  R$, temos
  \begin{equation}
    \label{eq:11}
    C_{*r}=h(\bfe_r)
  \end{equation}
  e
  \begin{equation}
    \label{eq:12}
    B_{*r}=g(\bfe_r).
  \end{equation}
  Assim, 
  \begin{equation}
    \label{eq:13}
    (AB)_{*r}=AB_{*r}=Ag(\bfe_r)=f(g(\bfe_r))=(f\circ
    g)(\bfe_r)=h(\bfe_r)=C_{*r}. 
  \end{equation}
  onde a primeira igualdade vem da definição de produto de matrizes.

  O resultado segue de~\eqref{eq:13}.
\end{proof}

Usando a notação de~\S\ref{sec:line-de-aplic}, temos que $f=f_A$,
$g=f_B$ e $h=f_C$.  Lembrando que $h=f\circ g$, temos que
$f_C=f_A\circ f_B$.  A Proposição~\ref{prop:C=AB} acima diz
que~$f_C=f_{AB}$, donde temos que
\begin{equation}
  \label{eq:17}
  f_A\circ f_B=f_{AB}.  
\end{equation}
Segue de~\eqref{eq:17} que
$A(B\bfu)=f_A(f_B(\bfu))=(f_A\circ f_B)(\bfu)=f_{AB}(\bfu)=(AB)\bfu$ para
todo~$\bfu\in U$.  Isto é, 
\begin{equation}
  \label{eq:15}
  A(B\bfu)=(AB)\bfu
\end{equation}
para todo~$\bfu\in U$.  Na verdade, é um exercício simples
provar~\eqref{eq:15} diretamente, a partir da definição de produto de
matrizes (exercício).

Suponha agora que temos três matrizes~$A$, $B$ e~$C$ tais que os
produtos $A(BC)$ e~$(AB)C$ estejam bem definidos.  Usando que
$f_A\circ(f_B\circ f_C)=(f_A\circ f_B)\circ f_C$, a
Proposição~\ref{prop:C=AB} implica que
\begin{equation}
  \label{eq:assoc}
  A(BC)=(AB)C.
\end{equation}
Isto é, a multiplicação de matrizes é associativa.  Na verdade,
supondo que $A\in\FF^{P\times Q}$, $B\in\FF^{Q\times R}$ e
$C\in\FF^{R\times S}$, é fácil ver diretamente que a $(p,s)$-ésima
entrada das matrizes em~\eqref{eq:assoc} é
\begin{equation}
  \label{eq:16}
  \sum_{q\in Q,\,r\in R}A(p,q)B(q,r)C(r,s).
\end{equation}

\subsection{Inversão de matrizes}
\label{sec:inversao-de-matrizes}

Seja $A\in\FF^{R\times C}$ uma matriz.  Seja $f_A\:\FF^C\to\FF^R$ a
função linear associada a~$A$ (veja~\S\ref{sec:line-de-aplic}).
Suponha que~$f_A$ seja inversível e seja~$g=f_A^{-1}$.

\begin{proposicao}
  \label{prop:inv_is_lin}
  A função $g=f_A^{-1}\:\FF^R\to\FF^C$ é uma função linear.
\end{proposicao}
\begin{proof}
  Exercício.
\end{proof}

Sabemos que toda função linear de~$\FF^R$ em~$\FF^C$ é da forma~$f_B$
para alguma matriz $B\in\FF^{C\times R}$.  Seja~$B$ tal que
$g=f_A^{-1}=f_B$.  Essa matriz~$B$ é a \textit{inversa} de~$A$.
Denotamos a inversa de~$A$ por~$A^{-1}$.  Note que
\begin{equation}
  \label{eq:14}
  f_A^{-1}=f_{A^{-1}}.
\end{equation}
Note que definimos a inversa da matriz~$A$ somente no caso em
que~$f_A$ é uma função inversível.  É natural dizermos que~$A$ é
\textit{inversível} se~$f_A$ for inversível.

\begin{proposicao}
  \label{prop:usual_inv}
  Sejam $I_R$ a matriz identidade em~$\FF^{R\times R}$ e~$I_C$ a
  matriz identidade em~$\FF^{C\times C}$.
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$A\in\FF^{R\times C}$ uma matriz inversível.  
    Então $AA^{-1}=I_R$ e~$A^{-1}A=I_C$.
  \item Sejam $A\in\FF^{R\times C}$ e~$B\in\FF^{C\times R}$ matrizes
    tais que $AB=I_R$ e $BA=I_C$.  Então $B=A^{-1}$.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Exercício (veja~\eqref{eq:17} e Corolário~\ref{cor:id_iff_I}).
\end{proof}

\begin{proposicao}
  \label{prop:inv_prod}
  Sejam~$A\in\FF^{R\times C}$ e~$B\in\FF^{C\times D}$ matrizes
  inversíveis.  Então o produto $AB\in\FF^{R\times D}$ é inversível. 
\end{proposicao}
\begin{proof}
  Considere as funções $f_A\:\FF^C\to\FF^R$ e $f_B\:\FF^D\to\FF^C$
  associadas a~$A$ e~$B$.  Como~$A$ e~$B$ são inversíveis, por
  definição~$f_A$ e~$f_B$ são funções inversíveis e
  $f_A^{-1}=f_{A^{-1}}$ e $f_B^{-1}=f_{B^{-1}}$.  Basta agora
  verificar que $f_{B^{-1}A^{-1}}=f_{B^{-1}}\circ f_{A^{-1}}$ é a
  inversa da função~$f_{AB}$ (exercício).
\end{proof}

\begin{uremark}
  Seja~$M\in\FF^{R\times C}$ uma matriz.  Por definição, $M$~é
  inversível se e só se~$f_M\:\FF^C\to\FF^R$ é uma função inversível.
  Assim, é necessário que~$f_M$ seja injetora, que ocorre se e só se
  $\Ker f_M=\{\bfzero\}$, isto é, $\Null M=\{\bfzero\}$ (lembre-se da
  Proposição~\ref{prop:kern-inj} e de~\eqref{eq:kern_null}).  Quando
  soubermos em que condições~$f_M$ é sobrejetora, teremos uma condição
  necessária e suficiente para~$M$ ser inversível.
\end{uremark}

\section{Bases}
\label{sec:bases}
Sejam dados $\bfa_1,\dots,\bfa_n\in\FF^D$ e considere
$V=\Span\{\bfa_1,\dots,\bfa_n\}$.  Se~$\bfv\in V$, então existem
$\alpha_1,\dots,\alpha_n\in\FF$ tais que
\begin{equation}
  \label{eq:18}
  \bfv=\sum_{1\leq i\leq n}\alpha_i\bfa_i.
\end{equation}
Naturalmente, o vetor dos coeficientes
$\bfalpha=[\alpha_1\,\cdots\,\alpha_n]^\top\in\FF^n$ é uma
`representação' de~$\bfv$, no sentido que, se temos~$\bfalpha$,
podemos recuperar~$\bfv$ (basta usar~\eqref{eq:18}).

\begin{uremark}
  Veremos mais à frente que se os~$\bfa_i$ ($1\leq i\leq n$)
  satisfizeram uma certa propriedade (forem `linear independentes'),
  então o vetor dos coeficientes~$\bfalpha$ é univocamente definido.
\end{uremark}

Para termos tais representações
$\bfalpha=[\alpha_1\,\cdots\,\alpha_n]^\top$ de~$\bfv\in V$,
naturalmente, precisamos dos vetores~$\bfa_i$ ($1\leq i\leq n$) que
geram~$V$.

\subsection{Obtenção de geradores}
\label{sec:obtenc-de-gerad}
Seja~$V\subset\FF^D$ um espaço vetorial sobre~$\FF$.  Queremos um
conjunto gerador para~$V$, isto é, um conjunto $S\subset V$ tal que
$\Span S=V$.  Podemos considerar dois procedimentos:

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{Espaço vetorial~$V\subset\FF^D$ com~$D$ finito}
  \Output{$S\subset V$ finito tal que $V=\Span S$ e $|S|$ é mínimo}
  \BlankLine
  $S\gets\emptyset$\;
  \While{$\Span S\neq V$}{
    $\bfv\gets\text{algum vetor em }V\setminus\Span S$\;
    $S\gets S\cup\{\bfv\}$\;
  }
  \Return$S$\;
  \caption{\textsc{Grow}}\label{alg:grow}
\end{algorithm}
\DecMargin{1em}

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{Espaço vetorial~$V\subset\FF^D$ com~$D$ finito}
  \Output{$S\subset V$ finito tal que $V=\Span S$ e $|S|$ é mínimo}
  \BlankLine
  $S\gets\text{algum $S$ finito tal que }\Span S=V$\;
  \While{existe $\bfv$ tal que $\Span(S\setminus\{\bfv\})=V$}{
    $S\gets S\setminus\{\bfv\}$\;
  }
  \Return$S$\;
  \caption{\textsc{Shrink}}\label{alg:shrink}
\end{algorithm}
\DecMargin{1em}

\bigskip

\begin{uremark}
  Note que, no momento, não sabemos se \textsc{Grow} necessariamente
  termina.  Também não sabemos se existe um conjunto como especificado
  na linha~1 de \textsc{Shrink}.
\end{uremark}

Veremos mais à frente que os dois procedimentos acima estão corretos:
eles produzem conjuntos~$S$ como especificados.  O seguinte resultado
é fácil provar.

\begin{proposicao}
  \label{prop:S_spans_V}
  Valem as seguintes afirmações.
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:grow_simple} Suponha que \textsc{Grow} termine com
    uma saída~$S$.  Então $S\subset V$, $S$~é finito, e é tal que
    $\Span S=V$.
  \item\label{it:shrink_simple} Suponha que a linha~1 de
    \textsc{Shrink} seja executada com sucesso.  Então \textsc{Shrink}
    termina com~$S\subset V$ finito tal que $\Span S=V$.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Em \textsc{Grow}, o invariante $\Span S\subset V$ é mantido no laço.
  Isto é, toda vez que vamos executar o teste na linha~2, vale que
  $\Span S\subset V$ (exercício).  Como \textsc{Grow} termina, a
  condição $\Span S\neq V$ na linha~2 falha, donde concluímos que
  $\Span S=V$ quando \textsc{Grow} termina.  Ademais, como
  \textsc{Grow} termina, temos que~$S$ é um conjunto finito.
  Claramente $S\subset V$.  Isso prova~\ref{it:grow_simple}.

  Vamos agora provar~\ref{it:shrink_simple}.  Em \textsc{Shrink}, o
  invariante $\Span S=V$ é mantido no laço da linha~2.  Isto é, toda
  vez que vamos executar o teste na linha~2, vale que $\Span S=V$
  (exercício).  Claramente, o laço em \textsc{Shrink} termina.  Como o
  invariante $\Span S=V$ é mantido no laço, temos que $\Span S=V$
  quando o laço termina, e assim o conjunto~$S$ devolvido por
  \textsc{Shrink} é tal que $\Span S=V$.  Claramente $S\subset V$
  e~$S$ é finito.
\end{proof}

\begin{uremark}
  É importante perceber que ainda não sabemos por que \textsc{Grow} e
  \textsc{Shrink} devolvem~$S$ de cardinalidade mínima.
\end{uremark}

\subsubsection{Espaço das arestas de um grafo}
\label{sec:espaco-das-arestas}

Seja~$G=(V,E)$ um grafo.  O \textit{espaço das arestas}~$B_1(G)$
de~$G$ sobre~$\GF(2)$ é o espaço vetorial sobre~$\GF(2)$ gerado pelas
funções características das arestas de~$G$:
\begin{equation}
  \label{eq:B_1_def}
  B_1(G)=\Span\{\dsone_e\:e\in E\}\subset\GF(2)^V.
\end{equation}
Podemos executar \textsc{Grow} e \textsc{Shrink} para encontrar
conjuntos geradores de cardinalidade mínima para~$B_1(G)$.  Para
tanto, é importante entendermos quando
\begin{equation}
  \label{eq:20}
  \dsone_e\in\Span\{\dsone_f\:f\in F\},
\end{equation}
onde~$e\in E$ e~$F\subset E$.

\begin{proposicao}
  \label{prop:e_spanned_by_F}
  Seja~$G=(V,E)$ um grafo e sejam dados~$e\in E$ e~$F\subset E$.  A
  condição~\eqref{eq:20} vale se e só se o grafo~$H=(V,F)$ contém um
  $(x,y)$-caminho, onde~$e=\{x,y\}$.
\end{proposicao}
\begin{proof}
  Exercício.
\end{proof}

Dizemos que~$F\subset E$ é \textit{aresta-gerador} se toda
aresta~$e=\{x,y\}$ de~$G$ é tal que~$H=(V,F)$ contém um
$(x,y)$-caminho, isto é, existe um $(x,y)$-caminho que só usa arestas
em~$F$.  A Proposição~\ref{prop:e_spanned_by_F} implica que $F\subset
E$ é aresta-gerador se e só se
\begin{equation}
  \label{eq:F_spans_B_1}
  B_1(G)=\Span\{\dsone_f\:f\in F\}.
\end{equation}
\textsc{Grow} e \textsc{Shrink} tomam a seguinte forma quando
especializados para encontrar conjuntos geradores de~$B_1(G)$, isto é,
conjuntos aresta-geradores de~$G$.

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{Grafo $G=(V,E)$ finito}
  \Output{$F\subset E$ aresta-gerador com $|F|$ é mínimo}
  \BlankLine
  $F\gets\emptyset$\;
  \While{existe $e=\{x,y\}\in E$ tal que não há $(x,y)$-caminho em $(V,F)$}{
    $F\gets F\cup\{e\}$\;
  }
  \Return$F$\;
  \caption{\textsc{GrowSF}}\label{alg:grow_sf}
\end{algorithm}
\DecMargin{1em}

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{Grafo $G=(V,E)$ finito}
  \Output{$F\subset E$ aresta-gerador com $|F|$ é mínimo}
  \BlankLine
  $F\gets E$\;
  \While{existe $f\in F$ tal que $F\setminus\{f\}$ é aresta-gerador}{
    $F\gets F\setminus\{f\}$\;
  }
  \Return$F$\;
  \caption{\textsc{ShrinkSF}}\label{alg:shrink_sf}
\end{algorithm}
\DecMargin{1em}

\bigskip

\begin{uremark}
  Ainda não sabemos por que \textsc{GrowSF} e \textsc{ShrinkSF}
  devolvem~$F$ de cardinalidade mínima.
\end{uremark}

\subsection{Dependência e independência linear}
\label{sec:depend-e-indep}

Seja~$V\subset\FF^D$ um espaço vetorial sobre~$\FF$.  Sejam
dados~$S\subset V$ e~$\bfv\in S$.  Dizemos que~$\bfv$ é
\textit{supérfluo em~$S$} se $\Span(S\setminus\{\bfv\})=\Span S$.

\begin{proposicao}
  \label{prop:superfluo}
  São equivalentes{\/\rm:}
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:superf_i} $\bfv$ é supérfluo em~$S$;
  \item\label{it:superf_ii} $\bfv$ é uma combinação linear de vetores
    em $S\setminus\{\bfv\}$.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Suponha que~$\bfv$ seja supérfluo em~$S$.  Então
  $\bfv\in\Span S=\Span(S\setminus\{\bfv\})$, e portanto $\bfv$~é uma
  combinação linear de vetores em $S\setminus\{\bfv\}$.  Suponha agora
  que $\bfv$~seja uma combinação linear de vetores em
  $S\setminus\{\bfv\}$.  Precisamos provar
  que~$\Span S\subset\Span(S\setminus\{\bfv\})$.  Para tanto,
  seja~$\bfu\in\Span S$.  Então
  $\bfu=\sum_{1\leq i\leq n}\alpha_i\bfv_i$ para alguns
  escalares~$\alpha_i$ e vetores~$\bfv_i\in S$ ($1\leq i\leq n$).  Se
  nenhum dos~$\bfv_i$ é~$\bfv$, então
  $\bfu\in\Span\{\bfv_1,\dots,\bfv_n\}\subset\Span(S\setminus\{\bfv\})$.
  Suponha agora que~$\bfv$ seja um dos~$\bfv_i$.  Sem perda de
  generalidade, suponha que~$\bfv=\bfv_n$.  Como estamos supondo que
  $\bfv=\sum_{1\leq j\leq m}\beta_j\bfw_j$ para alguns
  escalares~$\beta_j$ e vetores~$\bfw_j\in S\setminus\{\bfv\}$, o
  vetor~$\bfu$ pode ser escrito como combinação linear dos vetores em
  $\{\bfv_i\:1\leq i<n\}\cup\{\bfw_j\:1\leq j\leq m\}\subset
  S\setminus\{\bfv\}$. 
\end{proof}

Note que no algoritmo \textsc{Shrink}, na linha~2, perguntamos se
há~$\bfv\in S$ que é supérfluo em~$S$ (e o removemos de~$S$ no corpo
do laço nesse caso).  Em \textsc{Grow}, procuramos~$\bfv$ tal
que~$\bfv$ não seja supérfluo em~$S\cup\{\bfv\}$ (e o adicionamos
a~$S$ no corpo do laço nesse caso).

Sejam~$\bfv_1,\dots,\bfv_n$ vetores em um espaço vetorial e
$\alpha_1,\dots,\alpha_n$ escalares.  A combinação linear
\begin{equation}
  \label{eq:22}
  \alpha_1\bfv_1+\dots+\alpha_n\bfv_n
\end{equation}
é uma \textit{combinação linear trivial} se os~$\alpha_i$ são
todos~$0$.  A combinação linear~\eqref{eq:22} é \textit{não-trivial}
caso contrário.  Naturalmente, uma combinação linear trivial tem
valor~$\bfzero$.  Pode acontecer de uma combinação linear não-trivial
ter valor~$\bfzero$: 
\begin{equation}
  \label{eq:19}
  \alpha_1\bfv_1+\dots+\alpha_n\bfv_n=\bfzero
\end{equation}
com os~$\alpha_i$ não todos nulos.  Nesse caso, dizemos que~$\bfzero$
é uma combinação linear não-trivial dos~$\bfv_i$ ($1\leq i\leq n$).

\begin{proposicao}
  \label{prop:*-**}
  São equivalentes{\/\rm:}
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:*-**.i} $S$~contém um vetor supérfluo;
  \item\label{it:*-**.ii} $\bfzero$ é uma combinação linear
    não-trivial de elementos de~$S$.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Exercício.
\end{proof}

\begin{definicao}[Independência linear; dependência linear]
  \label{def:LI}
  Dizemos que um conjunto~$S$ de vetores é \textit{linearmente
    independente} se toda combinação linear não-trivial de vetores
  de~$S$ é não nulo.  Caso contrário, $S$~é \textit{linearmente
    dependente}.
\end{definicao}

\begin{proposicao}
  \label{prop:LI}
  Seja~$S\subset V$ um conjunto de vetores.  São equivalentes{\/\rm:}
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:LI_i} $S$ é linearmente independente;
  \item\label{it:LI_ii} $S$ não contém elementos supérfluos;
  \item\label{it:LI_iii} se vale~\eqref{eq:19} para
    escalares~$\alpha_i$ e~$\bfv_i\in S$ $(1\leq i\leq n)$, então
    todos os~$\alpha_i$ são nulos.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Exercício.
\end{proof}

\begin{uremark}
  É comum provar que um conjunto de vetores é linearmente independente
  verificando a asserção~\ref{it:LI_iii} da Proposição~\ref{prop:LI}.
\end{uremark}

\subsubsection{Arestas linearmente independentes em um grafo}
\label{sec:arest-line-indep}
Seja~$G=(V,E)$ um grafo e seja $B_1(G)=\Span\{\dsone_e\:e\in E\}$ o
espaço das arestas de~$G$ (veja~\S\ref{sec:espaco-das-arestas}).
Definimos um conjunto de arestas $F\subset E$ como sendo
\textit{linearmente independente} se
$\{\dsone_f\:f\in F\}\subset B_1(G)$ for linearmente independente.
Dizemos que~$F\subset E$ é \textit{acíclico} se não há um circuito
em~$G$ que tem todas suas arestas em~$F$.

\begin{proposicao}
  \label{prop:li_edges}
  Um conjunto de arestas $F\subset E$ é linearmente independente se e
  só se~$F$ é acíclico.
\end{proposicao}
\begin{proof}
  Exercício.
\end{proof}

\subsection{Hereditariedade de independência linear}
\label{sec:propr-de-indep-1}
A propriedade de ser linearmente independente é uma propriedade
\textit{hereditária}, isto é, vale a afirmação a seguir.

\begin{proposicao}
  \label{prop:LI_hereditary}
  Seja~$S$ um conjunto linearmente independente de vetores e
  seja~$T\subset S$.  Então~$T$ é linearmente independente.
\end{proposicao}
\begin{proof}
  Se vale a afirmação em Proposição~\ref{prop:LI}\ref{it:LI_iii}
  para~$S$, então ela também vale para~$T$.
\end{proof}

\subsection{Análise dos algoritmos {\sc Grow} e {\sc Shrink}}
\label{sec:anal-dos-algor}
Vamos verificar que os conjuntos devolvidos por \textsc{Grow} e
\textsc{Shrink} são conjuntos independentes.

\begin{proposicao}
  \label{prop:Grow_indept}
  Suponha que \textsc{Grow} devolve o conjunto~$S$.  Então~$S$ é um
  conjunto linearmente independente.
\end{proposicao}
\begin{proof}
  Suponha que \textsc{Grow} adiciona a~$S$ os vetores
  $\bfv_1,\dots,\bfv_n$, nessa ordem.  Provamos que esses~$n$ vetores
  são linearmente independentes por indução em~$n$.  A afirmação é
  válida para~$n=0$.  Suponha agora que~$n$ seja positivo e que a
  afirmação seja válida para valores menores de~$n$.  Se os~$\bfv_i$
  ($1\leq i\leq n$) não são linearmente independentes, então há
  escalares~$\alpha_i$ ($1\leq i\leq n$) não todos nulos tais
  que~\eqref{eq:19} vale.  Pela hipótese de indução, $\bfv_i$ ($1\leq
  i<n$) são linearmente independentes.  Assim, temos~$\alpha_n\neq0$
  (por que?).  Dividindo~\eqref{eq:19} por~$\alpha_n$ e rearranjando,
  obtemos
  \begin{equation}
    \label{eq:21}
    \bfv_n=-\alpha_n^{-1}\alpha_1\bfv_1-\dots-\alpha_n^{-1}\alpha_{n-1}\bfv_{n-1}. 
  \end{equation}
  Segue que~$\bfv_n\in\Span\{\bfv_1,\dots,\bfv_{n-1}\}$, contradizendo
  a condição na linha~3 de \textsc{Grow} para a escolha de~$\bfv_n$.
\end{proof}

\begin{proposicao}
  \label{prop:Shrink_indept}
  Suponha que \textsc{Shrink} devolve o conjunto~$S$.  Então~$S$ é um
  conjunto independente.
\end{proposicao}
\begin{proof}
  Note que o laço de \textsc{Shrink} remove vetores supérfluos de~$S$
  e que o laço termina quando não há mais vetores supérfluos em~$S$.
  Assim, o conjunto~$S$ devolvido por \textsc{Shrink} satisfaz a
  afirmação~\ref{it:LI_ii} da Proposição~\ref{prop:LI}.  O resultado
  segue.
\end{proof}

As Proposições~\ref{prop:S_spans_V}, \ref{prop:Grow_indept}
e~\ref{prop:Shrink_indept} implicam que os conjuntos~$S$ devolvidos
por \textsc{Grow} e \textsc{Shrink} geram~$V$, isto é, $\Span S=V$, e
são linearmente independentes.  Tais conjuntos são chamados de ``bases''
de~$V$.

\subsection{Bases de espaços vetoriais}
\label{sec:bases-de-espacos}
A seguinte definição é muito importante.

\begin{definicao}[Base]
  \label{def:basis}
  Seja~$V$ um espaço vetorial.  Um conjunto~$S$ de vetores de~$V$ é
  uma \textit{base} de~$V$ se
  \begin{enumerate}
  \item[(B1)] $S$ gera~$V$, isto é, $\Span S=V$ e
  \item[(B2)] $S$ é linearmente independente.
  \end{enumerate}
\end{definicao}

\begin{exemplo}
  \label{ex:graph_basis}
  Seja~$G=(V,E)$ um grafo.  O conjunto $\{\dsone_f\:f\in F\}$ é uma
  base de~$B_1(G)$ se e só se (a)~$F$ é aresta-gerador e (b)~$F$ é
  acíclico.  (Exercício: prove essa asserção.)  Tais conjuntos~$F$ são
  chamados de \textit{florestas aresta-geradoras}.
\end{exemplo}

Já observamos que se o algoritmo \textsc{Grow} termina, então ele
devolve uma base da entrada~$V$.  Observamos também que se a linha~1
de \textsc{Shrink} pode ser executada, então \textsc{Shrink} devolve
uma base da entrada~$V$.  Assim, para obtermos uma base de um espaço
vetorial~$V$, basta provar que \textsc{Grow} com entrada~$V$ termina,
ou que a linha~1 de \textsc{Shrink} pode ser executada com a
entrada~$V$.

\begin{exemplo}
  \label{ex:graph_basisªlg}
  Seja~$G=(V,E)$ um grafo.  Os algoritmos \textsc{GrowSF} e
  \textsc{ShrinkSF} executados com entrada~$G$ terminam e devolvem
  uma floresta aresta-geradora.
\end{exemplo}

Seja~$V$ um espaço vetorial, $B$~uma base de~$V$ e~$\bfv$ um elemento
de~$V$.  Pelo fato de~$B$ gerar~$V$, há escalares~$\alpha_{\bfb}$
($\bfb\in B$) tais que
\begin{equation}
  \label{eq:23}
  \bfv=\sum_{\bfb\in B}\alpha_{\bfb}\bfb,
\end{equation}
isto é, podemos ``escrever~$\bfv$ na base~$B$''.  O seguinte fato
implica que há exatamente uma forma de se escrever~$\bfv$ na
base~$B$.

\begin{proposicao}
  \label{prop:unique_rep}
  Seja $S$ um conjunto de vetores linearmente independentes e suponha
  que
  \begin{equation}
    \label{eq:24a}
    \bfv=\sum_{1\leq i\leq m}\alpha_i\bfv_i,
  \end{equation}
  onde os~$\bfv_i$ são elementos distintos de~$S$ e os~$\alpha_i$ são
  todos não-nulos.  Suponha também que 
  \begin{equation}
    \label{eq:24b}
    \bfv=\sum_{1\leq j\leq n}\beta_j\bfu_j.
  \end{equation}
  onde os~$\bfu_j$ são elementos distintos de~$S$ e os~$\beta_j$ são
  todos não-nulos.  Então
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:unique_i} $\{\bfv_i\:1\leq i\leq m\}=\{\bfu_j\:1\leq j\leq n\}$, de
    forma que $m=n$ e existe uma bijeção~$\sigma\:[m]=\{1,\dots,m\}\to[m]$
    tal que $\bfu_j=\bfv_{\sigma(j)}$ para todo~$1\leq j\leq n=m$ e
  \item $\beta_j=\alpha_{\sigma(j)}$ para todo~$1\leq j\leq n=m$.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Segue do fato que~$\beta_1\neq0$ e que 
  \begin{equation}
    \label{eq:24ab}
    \sum_{1\leq i\leq m}\alpha_i\bfv_i=\sum_{1\leq j\leq
      n}\beta_j\bfu_j 
  \end{equation}
  que $\bfu_1\in\Span\{\bfv_1,\dots,\bfv_m,\bfu_2,\dots,\bfu_n\}$.
  Segue que~$\bfu_1$ é igual a algum dos~$\bfv_i$ (por quê?).  Este
  argumento mostra que de fato
  $\{\bfv_i\:1\leq i\leq m\}=\{\bfu_j\:1\leq j\leq n\}$.  Segue que
  $m=n$ e que existe a bijeção~$\sigma\:[m]\to[m]$ como especificado
  em~\ref{it:unique_i}.  A identidade~\eqref{eq:24ab} toma a forma
  \begin{equation}
    \label{eq:25}
    \sum_{1\leq i\leq m}\alpha_i\bfv_i=\sum_{1\leq j\leq
      m}\beta_j\bfv_{\sigma(j)}=\sum_{1\leq i\leq
      m}\beta_{\sigma^{-1}(i)}\bfv_i.
  \end{equation}
  Rearranjando,
  \begin{equation}
    \label{eq:25b}
    \sum_{1\leq i\leq
      m}(\alpha_i-\beta_{\sigma^{-1}(i)})\bfv_i=\bfzero. 
  \end{equation}
  Pela independência linear dos~$\bfv_i$, temos que
  $\alpha_i=\beta_{\sigma^{-1}(i)}$ para todo~$i$.  Segue que
  $\alpha_{\sigma(j)}=\beta_j$ para todo~$j$.
\end{proof}

A proposição abaixo sobre grafos é uma consequência da unicidade da
representação de vetores em uma dada base.

\begin{proposicao}
  \label{prop:unique_path}
  Seja~$G=(V,E)$ um grafo.  Sejam~$F\subset E$ uma floresta
  aresta-geradora de~$G$ e~$x$ e~$y$ vértices de~$G$ tais que existe
  um $(x,y)$-caminho em~$G$.  Então existe exatamente um
  $(x,y)$-caminho em~$G$ que usa apenas arestas em~$F$.
\end{proposicao}
\begin{proof}
  Exercício.
\end{proof}

\subsubsection{Representação em bases e mudança de base}
\label{sec:mudanca-de-base}
Seja~$V\subset\FF^D$ um espaço vetorial, $B$~uma base de~$V$ e~$\bfv$
um elemento de~$V$.  Lembre que podemos escrever~$\bfv$ na base~$B$:
\begin{equation}
  \label{eq:23b}
  \bfv=\sum_{\bfb\in B}\alpha_{\bfb}\bfb,
\end{equation}
onde os escalares~$\alpha_{\bfb}$ ($\bfb\in B$) estão univocamente
definidos.  Podemos montar o vetor de coeficientes
$\bfalpha=[\alpha_{\bfb}\:\bfb\in B]\in\FF^B$ e pensar que
$\bfalpha\in\FF^B$ representa~$\bfv$.  Note que encontrar~$\bfalpha$
dado~$\bfv$ equivale a resolver a equação
\begin{equation}
  \label{eq:24}
  M\bfx=\bfv, 
\end{equation}
onde~$M\in\FF^{D\times B}$ é tal que sua $\bfb$-ésima coluna
é~$\bfb$ ($\bfb\in B$).  Intuitivamente, se
$B=\{\bfb_1,\dots,\bfb_m\}$, então
\begin{equation}
  \label{eq:26}
  M=
  \begin{bmatrix}
    \bfb_1\,\Big|\,\dots\,\Big|\,\bfb_m
  \end{bmatrix}.
\end{equation}
Note também que a função linear~$f_M\:\FF^B\to V$ que leva~$\bfx\in\FF^B$
em~$M\bfx\in V$ é bijetora (por quê?).  

Consideramos agora o \textsl{problema de mudança de base}: se temos a
representação $\bfalpha\in\FF^B$ de~$\bfv$ na base~$B$ como acima
e~$B'$ é outra base de~$V$, como podemos obter a representação
$\bfalpha'\in\FF^{B'}$ de~$\bfv$ na base~$B'$?  Gostaríamos de
obter~$\bfalpha'$ de alguma forma simples a partir de~$\bfalpha$.

Considere a matriz~$M'\in\FF^{D\times B'}$ tal que sua $\bfb'$-ésima coluna
é~$\bfb'$ ($\bfb'\in B'$).  Intuitivamente, se
$B'=\{\bfb_1',\dots,\bfb_{m'}'\}$, então
\begin{equation}
  \label{eq:26b}
  M'=
  \begin{bmatrix}
    \bfb_1'\,\Big|\,\dots\,\Big|\,\bfb_{m'}'
  \end{bmatrix}.
\end{equation}
Considere a função linear $f_{M'}\:\FF^{B'}\to V$, que leva
$\bfx\in\FF^{B'}$ em $M'\bfx\in V$.  Lembre que~$f_{M'}$ é bijetora, e
assim é inversível.  Basta agora observar que
\begin{equation}
  \label{eq:28}
  \bfalpha'=(f_{M'}^{-1}\circ f_M)(\bfalpha)
  =f_{(M')^{-1}M}(\bfalpha)
  =(M')^{-1}M\bfalpha.
\end{equation}

\subsubsection{O caso dos espaços vetoriais finitos sobre $\GF(2)$}
\label{sec:o-caso-gf2}
Seja~$V$ um espaço vetorial sobre~$\GF(2)$ finito, isto é, com~$|V|$
finito.  O algoritmo \textsc{Shrink} encontra uma base para~$V$,
digamos~$B$.  A Proposição~\ref{prop:unique_rep} implica que se~$B$
tem~$n$ elementos, então $|V|=2^n$ (exercício).  Em particular,
se~$B'$ for outra base de~$V$, então~$B'$ também tem~$n$ elementos.
Esse valor comum~$n$ é a \textit{dimensão} de~$V$.

Novamente usando o fato que~$V$ é finito, podemos concluir que o
algoritmo \textsc{Grow} termina com entrada~$V$.  Ademais, como
\textsc{Grow} devolve uma base de~$V$, vemos que a saída de
\textsc{Grow} sempre tem~$n$ elementos.

Note que, no caso de espaços vetoriais finitos sobre~$\GF(2)$,
deduzimos que \textsc{Grow} e \textsc{Shrink} funcionam como
prometido: eles devolvem conjuntos geradores de cardinalidade mínima,
a saber, com dimensão de~$V$ elementos.

\begin{proposicao}
  \label{prop:gf2_case}
  Seja~$V$ um espaço vetorial sobre~$\GF(2)$ finito.  Valem as
  seguintes afirmações.
  \begin{enumerate}[label=\rmlabel]
  \item \textsc{Shrink} e \textsc{Grow} devolvem bases de~$V$.
  \item Todas as bases de~$V$ têm a mesma cardinalidade.
  \item A cardinalidade comum~$n$ das bases de~$V$ é tal
    que~$|V|=2^n$.
  \end{enumerate}
\end{proposicao}

Seja~$V$ como na proposição acima. Vamos denotar a dimensão~$n$ de~$V$
por~$\dim V$.

\begin{corolario}
  \label{cor:gf2_case}
  Seja~$V$ um espaço vetorial finito sobre~$\GF(2)$.  Se~$S$ é um
  conjunto com mais de~$\dim V$ vetores, então~$S$ não é linearmente
  independente. 
\end{corolario}
\begin{proof}
  Seja~$n=\dim V$.  Temos que~$|V|=2^n$.  Se temos mais de~$n$ vetores
  em~$S$, então, pelo princípio da casa dos pombos, há duas
  combinações lineares de vetores de~$S$ que tem o mesmo valor.  Isto
  é, há~$S_1$ e~$S_2$ subconjuntos distintos de~$S$ tais que
  $\sum_{\bfs\in S_1}\bfs=\sum_{\bfs\in S_2}\bfs$.  Segue que
  $\sum_{\bfs\in S_1\sdiff S_2}\bfs=\bfzero$ é uma dependência linear
  de vetores em~$S$.
\end{proof}

Vários dos fatos que pudemos deduzir nessa seção sobre espaços
vetoriais finitos sobre~$\GF(2)$ serão provados em situações gerais
mais à frente.

\subsection{Propriedades de troca de conjuntos geradores}
\label{sec:propr-de-troca}
Descrevemos agora duas propriedades que conjuntos geradores
satisfazem. 

\begin{proposicao}
  \label{prop:exchange.1}
  Sejam~$V$ um espaço vetorial e $A\subset V$.  Suponha que
  $\bfb\in(\Span A)\setminus A$ seja um vetor não-nulo.  Então existe
  $\bfa\in A$ tal que $(A\setminus\{\bfa\})\cup\{\bfb\}$
  gera~$\Span A$.
\end{proposicao}
\begin{proof}
  Escreva~$\bfb$ como combinação linear de elementos de~$A$.
  Como~$\bfb\neq\bfzero$, tal combinação linear é não-trivial.
  Suponha que~$\bfa\in A$ ocorre nessa combinação linear com
  coeficiente não-nulo.  Então
  $\bfa\in\Span\big((A\setminus\{\bfa\})\cup\{\bfb\}\big)$.  Isso
  implica que $(A\setminus\{\bfa\})\cup\{\bfb\}$ gera~$\Span A$
  (exercício). 
\end{proof}

Na proposição acima, não temos ``controle'' sobre qual~$\bfa$ é
removido de~$A$.  A proposição a seguir dá certo controle sobre esse
elemento. 

\begin{proposicao}
  \label{prop:exchange.2}
  Sejam~$V$ um espaço vetorial e~$A\subset V$.  Suponha que
  $A'\subset A$ e $\bfb\in(\Span A)\setminus A$ são tais que
  $A'\cup\{\bfb\}$ é linearmente independente.  Então existe
  $\bfa\in A\setminus A'$ tal que $(A\setminus\{\bfa\})\cup\{\bfb\}$
  gera~$\Span A$.
\end{proposicao}
\begin{proof}
  Escreva~$\bfb$ como combinação linear de elementos de~$A$.  Como
  $A'\cup\{\bfb\}$ é linearmente independente, algum
  $\bfa\in A\setminus A'$ ocorre nessa combinação linear com
  coeficiente não-nulo (por quê?).  Segue que
  $\bfa\in\Span\big((A\setminus\{\bfa\})\cup\{\bfb\}\big)$, e a prova
  segue como na prova da Proposição~\ref{prop:exchange.1}.
\end{proof}

Podemos usar a Proposição~\ref{prop:exchange.2} para provar que um
algoritmo guloso resolve o \textit{problema do conjunto gerador de
  peso mínimo}.  Neste problema, recebemos um conjunto~$X$ de vetores
de algum espaço vetorial~$V$.  Recebemos também uma função
$w\:X\to\RR$ que atribui \textit{peso}~$w(\bfx)$ a cada~$\bfx\in X$.
O objetivo é encontrar um subconjunto~$S$ de~$X$ de peso mínimo tal
que $\Span S=\Span X$.  Aqui, o peso~$w(S)$ de~$S$ é simplesmente
$\sum_{\bfs\in S}w(\bfs)$.

O algoritmo \textsc{Guloso} resolve esse problema.

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{$X\subset V$ finito e $w\:X\to\RR$}
  \Output{$S\subset X$ tal que $\Span S=\Span X$ e $w(S)$ é mínimo}
  \BlankLine
  Sejam $\bfx_1,\dots,\bfx_n$ os vetores em~$X$ em ordem
  não-decrescente de peso: isto é, $w(\bfx_1)\leq\dots\leq w(\bfx_n)$\;
  $S\gets\emptyset$\;
  \For{$i=1,\dots,n$}{
    \If{$\bfx_i\notin\Span S$}
    {$S\gets S\cup\{\bfx_i\}$\;}
  }  
  \Return$S$\;
  \caption{\textsc{Guloso}}\label{alg:guloso}
\end{algorithm}
\DecMargin{1em}

\bigskip

\begin{teorema}
  \label{teo:greedy}
  O algoritmo \textsc{Guloso} resolve o problema do conjunto gerador
  de peso mínimo.
\end{teorema}
\begin{proof}
  Seja~$S$ o conjunto devolvido por \textsc{Guloso}.  Um argumento
  simples mostra que~$\Span S=\Span X$ (exercício).  Seja~$S^*$ um
  conjunto gerador de $\Span X$ de peso mínimo.  Se $S=S^*$ então
  \textsc{Guloso} funcionou corretamente.  Suponha por contradição
  que~$S\neq S^*$ e seja~$i$ o menor índice tal que
  $\bfx_i\in S^*\sdiff S=(S^*\setminus S)\cup(S\setminus S^*)$.  Dentre
  todas as possíveis escolhas de~$S^*$, escolha uma que maximiza o
  valor de~$i$.  Vamos derivar uma contradição construindo outra
  solução~$S^{**}$ com tal índice~$i$ maior.

  Observemos inicialmente que~$S^*$ é um conjunto linearmente
  independente (por quê?).  Também é verdade que~$S$ é um conjunto
  linearmente independente (exercício).  Sejam $S_{<i}\subset S$ e
  $S_{<i}^*\subset S^*$ dados por
  \begin{equation}
    \label{eq:27}
    S_{<i}=\{\bfx_j\in S\:j<i\}
  \end{equation}
  e
  \begin{equation}
    \label{eq:27b}
    S_{<i}^*=\{\bfx_j\in S^*\:j<i\}.
  \end{equation}
  Pela definição de~$i$, temos que $S_{<i}=S_{<i}^*$.  Como
  $S_{<i}\cup\{\bfx_i\}=S_{<i}^*\cup\{\bfx_i\}$ está contido ou em~$S$
  ou em~$S^*$ e tanto~$S$ como~$S^*$ são linearmente independentes,
  segue que $\bfx_i\notin\Span S_{<i}$.  Segue que~$\bfx_i$ é
  adicionado a~$S$ na linha~5 de \textsc{Guloso}.  Deduzimos
  que~$\bfx_i\notin S^*$.  Aplicamos agora a
  Proposição~\ref{prop:exchange.2}, tomando $A=S^*$, $A'=S_{<i}^*$
  e $\bfb=\bfx_i$.  Note que tal escolha faz com que as
  hipóteses daquela proposição sejam satisfeitas (exercício).  Segue
  que existe $\bfx_k$ com~$k>i$ tal que, tomando
  $S^{**}=(S^*\setminus\{\bfx_k\})\cup\{\bfx_i\}$, temos que
  (\textit{a})~$S^{**}$ gera~$\Span X$ e
  (\textbf{b})~$w(S^{**})\leq w(S^*)$.  Podemos concluir que
  $S^{**}$~é um conjunto gerador de $\Span X$ de peso mínimo.  Basta
  agora observar que o menor índice dos elementos em $S^{**}\sdiff S$
  é maior que~$i$, e isso contradiz a escolha de~$S^*$.
\end{proof}

Podemos especializar \textsc{Guloso} para resolver o \textit{problema
  da floresta aresta-geradora de peso mínimo} (mais conhecido como o
\textit{problema da árvore geradora mínima}).  Neste problema,
recebemos um grafo~$G=(V,E)$ e uma função $w\:E\to\RR$ que atribui
\textit{peso}~$w(e)$ a cada~$e\in E$.  O objetivo é encontrar um
subconjunto~$F$ de~$E$ de peso mínimo tal que~$F$ seja aresta-geradora
em~$G$, isto é, tal que, para toda aresta~$e=\{x,y\}$ de~$G$, há um
$(x,y)$-caminho em~$G$ que usa somente arestas em~$F$.  Aqui, o
peso~$w(F)$ de~$F$ é simplesmente $\sum_{f\in F}w(f)$.

O algoritmo \textsc{Kruskal}, que é uma especialização de
\textsc{Guloso}, resolve esse problema.

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{$G=(V,E)$ grafo e $w\:E\to\RR$}
  \Output{$F\subset E$ tal que~$F$ é aresta-gerador e $w(F)$ é mínimo}
  \BlankLine
  Sejam $e_1,\dots,e_m$ as arestas de~$G$ em ordem
  não-decrescente de peso: isto é, $w(e_1)\leq\dots\leq w(e_m)$\;
  $F\gets\emptyset$\;
  \For{$i=1,\dots,m$}{
    \If{não existe $(x,y)$-caminho em $(V,F)$ onde $e_i=\{x,y\}$}
    {$F\gets F\cup\{e_i\}$\;}
  }  
  \Return$F$\;
  \caption{\textsc{Kruskal}}\label{alg:kruskal}
\end{algorithm}
\DecMargin{1em}

\bigskip

\begin{teorema}
  \label{teo:greedy_gr}
  O algoritmo \textsc{Kruskal} resolve o problema da floresta
  aresta-geradora de peso mínimo.
\end{teorema}
\begin{proof}
  Exercício.
\end{proof}

Os algoritmos \textsc{Guloso} e \textsc{Kruskal} são versões de
\textsc{Grow}.  Os algoritmos \textsc{Mesquinho} e \textsc{Kruskal
  invertido} são as versões correspondentes a \textsc{Shrink}.
A prova da correção de \textsc{Mesquinho} e \textsc{Kruskal invertido}
fica como exercício.

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{$X\subset V$ finito e $w\:X\to\RR$}
  \Output{$S\subset X$ tal que $\Span S=\Span X$ e $w(S)$ é mínimo}
  \BlankLine
  Sejam $\bfx_1,\dots,\bfx_n$ os vetores em~$X$ em ordem
  não-decrescente de peso: isto é, $w(\bfx_1)\leq\dots\leq w(\bfx_n)$\;
  $S\gets X$\;
  \For{$i=n,\dots,1$}{
    \If{$\bfx_i\in\Span(S\setminus\{\bfx_i\})$}
    {$S\gets S\setminus\{\bfx_i\}$\;}
  }  
  \Return$S$\;
  \caption{\textsc{Mesquinho}}\label{alg:mesquinho}
\end{algorithm}
\DecMargin{1em}

\bigskip

\IncMargin{1em}
\begin{algorithm}[H]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{$G=(V,E)$ grafo e $w\:E\to\RR$}
  \Output{$F\subset E$ tal que~$F$ é aresta-gerador e $w(F)$ é mínimo}
  \BlankLine
  Sejam $e_1,\dots,e_m$ as arestas de~$G$ em ordem
  não-decrescente de peso: isto é, $w(e_1)\leq\dots\leq w(e_m)$\;
  $F\gets E$\;
  \For{$i=m,\dots,1$}{
    \If{existe $(x,y)$-caminho em $(V,F\setminus\{e_i\})$ onde $e_i=\{x,y\}$}
    {$F\gets F\setminus\{e_i\}$\;}
  }  
  \Return$F$\;
  \caption{\textsc{Kruskal invertido}}\label{alg:kruskal_inv}
\end{algorithm}
\DecMargin{1em}

\bigskip

\section{Dimensão}
\label{sec:dimensao}

Em~\S\ref{sec:o-caso-gf2}, vimos que há uma noção bem definida de
`dimensão' no caso de espaços vetoriais sobre~$\GF(2)$ finitos: tais
espaços vetoriais~$V$ são tais que todas as suas bases tem um mesmo
número de elementos, e denominamos esse número de \textit{dimensão}
de~$V$.  Veremos agora que podemos definir dimensão para espaços
quaisquer.

\subsection{Dimensão de espaços vetoriais}
\label{sec:dimensao-de-espacos}
Começamos com a seguinte proposição.

\begin{proposicao}
  \label{prop:morphing}
  Seja~$S$ um conjunto de vetores em um espaço vetorial~$V$.  Suponha
  que~$T\subset\Span S$ seja um conjunto linearmente independente.
  Então $|T|\leq|S|$.
\end{proposicao}
\begin{proof}
  A prova é baseada na Proposição~\ref{prop:exchange.2} e pode ser
  formulada de forma algorítmica.  Considere o algoritmo
  \textsc{Morph}.  Verifique que \textsc{Morph} de fato devolve~$S'$
  como especificado.  Como $T\subset S'$ e~$|S'|=|S|$, vale
  que~$|T|\leq|S|$.
\end{proof}

\IncMargin{1em}
\begin{algorithm}[h]
  \LinesNumbered
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \SetKw{continue}{continue}  
  \Input{$S\subset V$ e~$T\subset\Span S$ linearmente independente, 
    onde~$V$ é um espaço vetorial}
  \Output{$S'\subset V$ tal que~$|S'|=|S|$, $T\subset S'$ e $\Span
    S'=\Span S$}
  \BlankLine
  Suponha $T=\{\bfv_1,\dots,\bfv_t\}$\;
  $S'\gets S$; $A\gets\emptyset$\;
  \For{$i=1,\dots,t$}{
    \tcc{$A\cup\{\bfv_i\}=\{\bfv_1,\dots,\bfv_i\}$ e assim
      $A\cup\{\bfv_i\}$ é linearmente independente.  Ademais, vale que
      $\Span S'=\Span S$.} 
    \If{$\bfv_i\in S'$}
    {$A\gets A\cup\{\bfv_i\}$\;
    \continue\;}
    \tcc{Como $\bfv_i\in T\setminus S'\subset(\Span S)\setminus
      S'=(\Span S')\setminus S'$, segue da
      Proposição~\ref{prop:exchange.2} que existe~$\bfw\in S'\setminus
      A$ como abaixo.}  
    Seja $\bfw\in S'\setminus A$ tal que
    $\Span\big((S'\setminus\{\bfw\})\cup\{\bfv_i\}\big)=\Span S'$\;
    $S'\gets(S'\setminus\{\bfw\})\cup\{\bfv_i\}$\;
    $A\gets A\cup\{\bfv_i\}$\;
  }  
  \Return$S'$\;
  \caption{\textsc{Morph}}\label{alg:morph}
\end{algorithm}
\DecMargin{1em}

Podemos deduzir do algoritmo~\textsc{Morph} usado na prova da
Proposição~\ref{prop:morphing} o seguinte resultado mais refinado.

\begin{lema}[Lema de substituição de Steinitz]
  Seja~$S$ um conjunto de vetores em um espaço vetorial~$V$.  Suponha
  que~$T\subset\Span S$ seja um conjunto finito linearmente
  independente.  Então existe~$S_1\subset S$ tal que
  \begin{enumerate}[label=\rmlabel]
  \item $|T\cup S_1|=|S|$
  \item $\Span(T\cup S_1)=\Span S$.
  \end{enumerate}
\end{lema}
\begin{proof}
  Segue do algoritmo \textsc{Morph}: a saída~$S'$ de \textsc{Morph} é
  da forma $T\cup S_1$ onde $S=S_0\cup S_1$ e $|S_0|=|T|$.  O
  algoritmo \textsc{Morph} iterativamente substitui os elementos
  de~$S_0$ por elementos de~$T$.
\end{proof}

\begin{teorema}
  \label{teo:any2gives3rd}
  Seja~$V$ um espaço vetorial e suponha que
  \begin{equation}
    \label{eq:n_def}
    n=\min\{|S|\:S\subset V\text{ tal que }\Span S=V\}
  \end{equation}
  seja finito.  Fixe $B\subset V$.  Quaisquer duas das afirmações
  abaixo implica a terceira{\/{\rm:}}
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:2to3.i} $V=\Span B$;
  \item\label{it:2to3.ii} $B$ é linearmente independente;
  \item\label{it:2to3.iii} $|B|=n$.
  \end{enumerate}
\end{teorema}
\begin{proof}
  Fixemos inicialmente $S\subset V$ tal que~$\Span S=V$ e~$|S|=n$.
  Suponha que agora que valham~\ref{it:2to3.i} e~\ref{it:2to3.ii}.
  Vamos provar que~\ref{it:2to3.iii} vale.  Pela
  Proposição~\ref{prop:morphing}, segue que~$|B|\leq|S|=n$.  Pela
  definição de~$n$, como $\Span B=V$, segue que~$|B|\geq n$ e
  portanto~$|B|=n$.  Suponha agora que valem~\ref{it:2to3.i}
  e~\ref{it:2to3.iii}.  Provemos que~\ref{it:2to3.ii} vale.  Suponha
  que~$B$ não seja linearmente independente.  Então, pela
  Proposição~\ref{prop:LI}, há um vetor supérfluo~$\bfv$ em~$B$.
  Considere~$B'=B\setminus\{\bfv\}$.  Temos que $\Span B'=\Span B=V$.
  Entretanto, $|B'|=|B|-1=n-1$, o que contradiz a definição de~$n$.
  Essa contradição prova que~$B$ é necessariamente linearmente
  independente, isto é, que~\ref{it:2to3.ii} vale.  Finalmente,
  suponha que~\ref{it:2to3.ii} e~\ref{it:2to3.iii} valham.  Provemos
  que~\ref{it:2to3.i} também vale.  Suponha por contradição que
  $\Span B\neq V$ e seja~$\bfv\in V\setminus\Span B$.  Segue que
  $B'=B\cup\{\bfv\}$ é linearmente independente.  Lembre que fixamos
  $S\subset V$ tal que~$\Span S=V$ e~$|S|=n$.  Pela
  Proposição~\ref{prop:morphing}, temos que $n+1=|B'|\leq|S|=n$.  Esta
  contradição mostra que $\Span B=V$.
\end{proof}

Note que se~\ref{it:2to3.i} e~\ref{it:2to3.ii} valem, então~$B$ é uma
base de~$V$.  Assim, o teorema acima implica que toda base de~$V$
tem~$n$ elementos, onde~$n$ é como definido em~\eqref{eq:n_def}.  Em
particular, todas as bases de~$V$ têm o mesmo número de elementos.  O
teorema acima também diz duas outras coisas: (1)~se~$\Span B=V$
e~$|B|=n$, então~$B$ é uma base e (2)~se~$B$ é linearmente
independente e~$|B|=n$, então~$B$ é uma base de~$V$.

\begin{definicao}[Dimensão de um espaço vetorial; $\dim V$]
  \label{def:dim_def}
  Seja~$V$ um espaço vetorial com
  \begin{equation}
    \label{eq:n_def.2}
    n=\min\{|S|\:S\subset V\text{ tal que }\Span S=V\}
  \end{equation}
  finito.  Definimos a dimensão~$\dim V$ de~$V$ como sendo o
  inteiro~$n$ em~\eqref{eq:n_def.2}.  Se um espaço vetorial~$V$ é tal
  que~$\Span S\neq V$ para qualquer~$V$ finito, dizemos que~$V$ tem
  dimensão infinita.
\end{definicao}

Devido ao Teorema~\ref{teo:any2gives3rd}, $\dim V$ é também a
cardinalidade comum das bases de~$V$.

\begin{proposicao}
  \label{prop:dim_F^n}
  Seja~$D$ um conjunto finito.  Então~$\FF^D$ tem dimensão~$|D|$.
\end{proposicao}
\begin{proof}
  Seja $B=\{\dsone_{\{d\}}\in\FF^D\:d\in D\}$.  Como~$D$ é finito,
  temos que $\Span B=\FF^D$.  Claramente, os vetores em~$B$ são
  linearmente independentes.  Assim, $B$~é uma base de~$\FF^D$, donde
  $\dim \FF^D=|B|=|D|$.
\end{proof}

\begin{proposicao}
  \label{prop:not_more_than_dim}
  Sejam $\bfv_1,\dots,\bfv_N$ vetores em um espaço vetorial~$V$ de
  dimensão~$n$.  Se~$N>n$, então $\bfv_1,\dots,\bfv_N$ não podem ser
  linearmente independentes.
\end{proposicao}
\begin{proof}
  Seja~$B$ uma base de~$V$, de forma que~$|B|=\dim V=n$.  Se os
  vetores $\bfv_i$ ($1\leq i\leq N$) fossem linearmente independentes,
  então a Proposição~\ref{prop:morphing} implicaria que~$N\leq n$.
  Assim, os $\bfv_i$ ($1\leq i\leq N$) não são linearmente
  independentes.
\end{proof}

\subsection{Alguns fatos sobre dimensão}
\label{sec:alguns-fatos-sobre}
Os seguintes fatos são úteis.

\begin{proposicao}
  \label{prop:dim at most_size}
  Seja~$V$ um espaço vetorial sobre~$\FF$ e seja~$S\subset V$ um
  conjunto finito.  Então existe~$T\subset S$ tal que~$T$ é base
  de~$\Span S$.  Em particular, $\dim\Span S=|T|\leq|S|$.
\end{proposicao}
\begin{proof}
  Seja~$T\subset S$ com~$\Span T=\Span S$ e minimal com essa
  propriedade (isto é, tal que se~$T'\subset T$ e $T'\neq T$, então
  $\Span T'\neq\Span S$).  A existência de tal~$T$ segue do fato
  que~$S$ é finito.  Então~$T$ é linearmente independente (exercício).
  Assim, $T$~é base de~$\Span S$.
\end{proof}

A seguinte proposição afirma que todo conjunto linearmente
independente de vetores em um espaço vetorial pode ser estendido a uma
base do espaço.  Em particular, todo espaço vetorial tem uma base.

\begin{proposicao}
  \label{prop:superset}
  Seja~$V\subset\FF^D$ um espaço vetorial sobre~$\FF$ com~$D$ finito,
  e seja~$S\subset V$ um conjunto linearmente independente.  Então
  existe uma base~$B$ de~$V$ com~$S\subset B$.
\end{proposicao}
\begin{proof}
  Considere um conjunto~$B\subset V$ que contém~$S$ linearmente
  independente e maximal com essa propriedade (isto é, tal que
  se~$B\subset B'$ e~$B\neq B'$, então~$B'$ não é linearmente
  independente).  A existência de tal~$B$ segue do fato que~$D$ é
  finito: se tivéssemos uma sequência
  $S=B_0\subset B_1\subset B_2\subset\dots$ de conjuntos linearmente
  independentes estritamente crescente, então teríamos um conjunto com
  mais de~$|D|$ vetores linearmente independentes em~$\FF^D$, mas isso
  é impossível, pois quaisquer~$|D|$ deles formam uma base
  (Teorema~\ref{teo:any2gives3rd}).  Confirmamos assim que~$B$ como
  especificado existe.  Afirmamos que~$B$ é uma base de~$V$.  Basta
  verificar que $\Span B=V$.  Claramente $\Span B\subset V$.  Suponha
  que~$\Span B\neq V$.  Tome~$\bfv\in V\setminus\Span B$.  Temos que
  $B'=B\cup\{\bfv\}\subset V$ é linearmente independente e $B'\neq B$.
  Tal~$B'$ contradiz a maximalidade de~$B$.  Segue que $\Span B=V$.
\end{proof}

\begin{uremark}
  É fácil verificar que qualquer $B\subset V$ linearmente independente
  maximal é base de~$V$.  Quando~$V$ tem dimensão finita, a existência
  de tal~$B$ é simples de provar (como vimos acima).  No caso em
  que~$V$ tem dimensão infinita, esse fato vale, mas a prova é mais
  sutil.  A conclusão é que todo espaço vetorial tem uma base.
\end{uremark}

\begin{proposicao}
  \label{prop:dim_principle}
  Seja~$U$ um subespaço vetorial de um espaço~$V$ com~$V$ de dimensão
  finita.  Valem as seguintes afirmações{\/\rm:}
  \begin{enumerate}[label=\rmlabel]
  \item $\dim U\leq\dim V$.
  \item\label{it:dim_principle.ii} Se $\dim U=\dim V$, então~$U=V$.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Seja~$B$ uma base de~$U$.  Pela Proposição~\ref{prop:superset},
  existe~$B'$ base de~$V$ com~$B\subset B'$.  Assim,
  $\dim U=|B|\leq|B'|=\dim V$.  Se vale que $\dim U=\dim V$, temos
  que~$B=B'$ e assim $U=\Span B=\Span B'=V$.
\end{proof}

\subsection{Dimensão e o algoritmo {\sc Grow}}
\label{sec:dimensao-e-Grow}

Considere o algoritmo \textsc{Grow} (Algoritmo~\ref{alg:grow})
executado com entrada~$V$.  Vimos que \textsc{Grow}, se ele termina,
ele devolve~$S$ linearmente independente tal que~$\Span S=V$
(Proposições~\ref{prop:S_spans_V}\ref{it:grow_simple}
e~\ref{prop:Grow_indept}).  Isto é, \textsc{Grow} devolve uma base
de~$V$.  Vamos agora ver que \textsc{Grow} de fato termina usando o
conceito de dimensão.

\begin{proposicao}
  \label{prop:grow_termina}
  Suponha que \textsc{Grow} é executado com entrada $V\subset\FF^D$,
  onde~$D$ é finito.  Então a linha~$3$ de \textsc{Grow} é executada
  no máximo~$|D|$ vezes.  Em particular, \textsc{Grow} termina. 
\end{proposicao}
\begin{proof}
  Sabemos que, ao longo da execução de \textsc{Grow}, o conjunto~$S$ é
  linearmente independente e que~$S$ cresce a cada execução da
  linha~$3$.  Basta agora aplicar a
  Proposição~\ref{prop:not_more_than_dim}. 
\end{proof}

\subsection{O posto de matrizes}
\label{sec:o-posto-de}

Dado um conjunto~$S$ de vetores de um espaço vetorial, o
\textit{posto} de~$S$ é~$\dim\Span S$.  Dada uma
matriz~$M\in\FF^{R\times C}$ o \textit{posto-linha} de~$M$ é o posto
do conjunto das linhas de~$M$, consideradas como vetores em~$\FF^C$.
O \textit{posto-coluna} de~$M$ é o posto do conjunto das colunas
de~$M$, consideradas como vetores em~$\FF^R$.

\begin{proposicao}
  \label{prop:rowr_leq_colr}
  Para toda matriz~$M\in\FF^{R\times C}$, seu posto-linha é menor ou
  igual ao seu posto-coluna.
\end{proposicao}
\begin{proof}
  Seja~$B$ uma base do espaço das colunas~$\Span\{M_{*c}\:c\in C\}$
  de~$M$.  Suponha que o posto-coluna de~$M$ seja~$r$ e suponha
  $B=\{\bfb_1,\dots,\bfb_r\}$.  Seja
  $P=[\bfb_1\mid\dots\mid\bfb_r]\in\FF^{R\times[r]}$, onde
  $[r]=\{1,\dots,r\}$.  Pelo fato de~$B$ ser base, existe
  $Q\in\FF^{[r]\times C}$ tal que
  \begin{equation}
    \label{eq:29}
    M=PQ.
  \end{equation}
  Note agora que~\eqref{eq:29} implica que as linhas de~$M$ pertencem
  ao espaço $\Span\{Q_{i*}\:i\in[r]\}\subset\FF^C$ gerado pelas~$r$
  linhas de~$Q$.  Assim, o posto-linha de~$M$ é no máximo
  $\dim\Span\{Q_{i*}\:i\in[r]\}\leq r$.  Como~$r$ é o posto-coluna
  de~$M$, obtivemos a desigualdade procurada.
\end{proof}

\begin{corolario}
  \label{cor:rowr_colr_eq}
  Para toda matriz~$M\in\FF^{R\times C}$, seu posto-linha e seu
  posto-coluna coincidem.
\end{corolario}
\begin{proof}
  Basta aplicar a Proposição~\ref{prop:rowr_leq_colr} à matriz~$M$ e à
  matriz~$M^\top$.
\end{proof}

O \textit{posto} de uma matriz~$M$ é o valor comum de seu posto-linha
e seu posto-coluna.

\subsection{Soma direta de subespaços vetoriais}
\label{sec:soma-direta-de}

Sejam~$U$ e~$W$ subespaços de um espaço vetorial~$V$.
Quando~$U\cap W=\{\bfzero\}$, definimos a \textit{soma
  direta}~$U\oplus W$ de~$U$ e~$W$ pondo
\begin{equation}
  \label{eq:30}
  U\oplus W=\{\bfu+\bfw\:\bfu\in U\text{ e }\bfw\in W\}.
\end{equation}
É fácil verificar que~$U\oplus W$ é um subespaço vetorial de~$V$
(exercício).

\begin{proposicao}
  \label{prop:dsum_dim}
  A união de uma base de~$U$ e uma base de~$W$ é uma base de $U\oplus
  W$.  Em particular, se~$U$ e~$W$ têm dimensão finita, então
  \begin{equation}
    \label{eq:31}
    \dim U\oplus W=\dim U+\dim W.
  \end{equation}
\end{proposicao}
\begin{proof}
  Sejam~$B'$ e~$B''$ bases de~$U$ e~$W$, respectivamente.
  Seja~$B=B'\cup B''$.  É simples ver que~$B$ gera $U\oplus W$.  Vamos
  agora provar que~$B$ é linearmente independente.  Para tanto,
  suponha que uma combinação linear de elementos de~$B$ seja igual
  a~$\bfzero$:
  \begin{equation}
    \label{eq:32}
    \alpha_1\bfb_1'+\dots+\alpha_r\bfb_r'
    +\beta_1\bfb_1''+\dots+\beta_s\bfb_s''=\bfzero, 
  \end{equation}
  onde os~$\bfb_i'$ pertencem a~$B'$, os~$\bfb_j''$ pertencem a~$B''$,
  e os~$\alpha_i$ e~$\beta_j$ são escalares.  Temos então
  \begin{equation}
    \label{eq:32b}
    \alpha_1\bfb_1'+\dots+\alpha_r\bfb_r'
    =-\beta_1\bfb_1''-\dots-\beta_s\bfb_s''.
  \end{equation}
  Entretanto, o lado esquerdo de~\eqref{eq:32b} pertence a~$U$,
  enquanto que o lado direito de~\eqref{eq:32b} pertence a~$W$.
  Como~$U\cap W=\{\bfzero\}$, deduzimos que ambos os lados
  de~\eqref{eq:32b} são nulos.  Da independência linear de~$B'$
  e~$B''$, segue que todos os~$\alpha_i$ e todos os~$\beta_j$ são
  nulos.  Concluímos que~$B$ é linearmente independente.

  A identidade~\eqref{eq:31} segue imediatamente.
\end{proof}

Quando $U\oplus W=V$, dizemos que~$U$ e~$W$ são subespaços
\textit{complementares} de~$V$.

\begin{proposicao}
  \label{prop:compl_subsp}
  Todo subespaço~$U$ de um espaço vetorial~$V$ admite um subespaço
  complementar~$W$ em~$V$.
\end{proposicao}
\begin{proof}
  Sejam~$U$ e~$V$ dados como no enunciado.  Seja~$B'$ uma base
  de~$U$.  Pela Proposição~\ref{prop:superset}, existe uma base~$B$
  de~$V$ que estende~$B'$ (isto é, com $B'\subset B$).  Basta tomar
  $W=\Span(B\setminus B')$ (exercício).
\end{proof}

\subsection{Funções lineares e dimensão} 
\label{sec:funcoes-lineares-e}
Seja $f\:U\to V$ uma função linear.  Veremos agora que
\begin{equation}
  \label{eq:34}
  \dim U=\dim\Ker f+\dim\Im f.
\end{equation}

\begin{proposicao}
  \label{prop:dom_dec}
  Sejam~$U$ e~$V$ espaços vetoriais e seja $f\:U\to V$ uma função
  linear.  Existe um subespaço~$U^*$ de~$U$ tal que
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:dom_dec.i} $U=U^*\oplus\Ker f$ e
  \item\label{it:dom_dec.ii} a função $f^*\:U^*\to\Im f$ dada por
    $f^*(\bfu)=f(\bfu)$ para todo~$\bfu\in U^*$ é bijetora.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Seja~$B'$ uma base de~$\Im f\subset V$ (lembre que~$\im f$ é um
  espaço vetorial).  Suponha que $B'=\{\bfb_1',\dots,\bfb_r'\}$ (o
  argumento abaixo mostra que~$B'$ é finito (exercício)).  Escolha
  $\bfb_1,\dots,\bfb_r\in U$ tais que $f(\bfb_i)=\bfb_i'$ para
  todo~$i$.  Seja $B=\{\bfb_1,\dots,\bfb_r\}$ e seja $U^*=\Span B$.

  Vamos mostrar que~$B$ é linearmente independente.  Suponha que
  $\sum_i\alpha_i\bfb_i=\bfzero$.  Então
  $\sum_i\alpha_i\bfb_i'=\sum_i\alpha_if(\bfb_i)
  =f\big(\sum_i\alpha\bfb_i\big)=\bfzero$.  Lembrando que os~$\bfb_i'$
  são linearmente independentes, obtemos que todos os~$\alpha_i$ são
  nulos.  Concluímos que os~$\bfb_i$ são linearmente independentes, e
  portanto formam uma base de~$U^*$.

  Suponha agora que~$\bfu=\sum_i\alpha_i\bfb_i$ é tal que $f(\bfu)=0$.
  O argumento acima mostra que todos os~$\alpha_i$ são nulos e
  portanto~$\bfu=\bfzero$ (exercício).
  Segue que
  $U^*\cap\Ker f=\{\bfzero\}$ e portanto podemos considerar a soma
  direta $U'=U^*\oplus\Ker f\subset U$.  Vamos mostrar agora que
  $U'=U$.  Fixe~$\bfu\in U$.  Seja $\bfv=f(\bfu)\in\Im f$.
  Escrevendo~$\bfv$ na base~$B'$, é fácil ver que
  existe~$\bfu^*\in U^*$ tal que $f(\bfu^*)=\bfv=f(\bfu)$.  Seja
  $\bfk=\bfu-\bfu^*$ então $\bfk\in\Ker f$ e
  $\bfu=\bfu^*+\bfk\in U^*\oplus\Ker f=U'$.  Isto prova que
  $U\subset U'$ e portanto $U=U'$, isto é, provamos
  que~\ref{it:dom_dec.i} vale.

  A verificação de~\ref{it:dom_dec.ii} fica como exercício.  
\end{proof}

\begin{corolario}
  \label{cor:dimf}
  Para qualquer função linear $f\:U\to V$ com~$U$ de dimensão finita,
  vale a relação~\eqref{eq:34}.
\end{corolario}
\begin{proof}
  Se dois espaços vetoriais~$A$ e~$B$ são tais que existe uma função
  linear bijetora $f\:A\to B$, então~$A$ e~$B$ tem a mesma dimensão
  (exercício).  Assim, os espaços~$U^*$ e~$\Im f$ da
  Proposição~\ref{prop:dom_dec} tem a mesma dimensão.  Basta agora
  lembrar~\eqref{eq:31} e usar~\ref{it:dom_dec.i} da
  Proposição~\ref{prop:dom_dec}.
\end{proof}

\begin{proposicao}
  \label{prop:dim_compare}
  Seja $f\:U\to V$ uma função linear injetora entre espaços de
  dimensão finita.  Então
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:dim_comp.i} $\dim U\leq\dim V$ e
  \item\label{it:dim_comp.ii} se $\dim U=\dim V$, então~$f$ é
    sobrejetora e portanto bijetora.
  \end{enumerate}
\end{proposicao}
\begin{proof}
  Seja~$B$ uma base de~$U$.  É fácil ver que a coleção de
  vetores~$f(\bfb)$ com~$\bfb\in B$ é linearmente independente
  (exercício).  Segue que~\ref{it:dim_comp.i} vale.
  Para~\ref{it:dim_comp.ii}, basta aplicar a
  Proposição~\ref{prop:dim_principle}\ref{it:dim_principle.ii} ao
  subespaço~$\Im f$ de~$V$, observando que, por~\eqref{eq:34}, temos
  que $\dim\Im f=\dim U$ pois supomos~$f$ injetora (exercício).
\end{proof}

De fato, a Proposição~\ref{prop:dim_compare}\ref{it:dim_comp.ii} acima
é apenas umas das três implicações no teorema abaixo.

\begin{teorema}
  \label{thm:invertible_f}
  Seja $f\:U\to V$ uma função linear entre espaços de dimensão finita.
  Quaisquer duas das três afirmações abaixo implica a
  terceira{\/{\rm:}}
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:inv_f.i} $f$ é injetora;
  \item\label{it:inv_f.ii} $f$ é sobrejetora;
  \item\label{it:inv_f.iii} $\dim U=\dim V$.
  \end{enumerate}
\end{teorema}
\begin{proof}
  Exercício (use~\eqref{eq:34}).
\end{proof}

Note que o Teorema~\ref{thm:invertible_f} dá critérios necessários e
suficientes para~$f$ ser inversível, pois~$f$ é inversível se e só se
valem~\ref{it:inv_f.i} e~\ref{it:inv_f.ii}.  Por exemplo, deduzimos
daquele teorema que se~$f$ é inversível, então necessariamente
$\dim U=\dim W$ (note que isso não é difícil de se provar diretamente
e isso já foi citado na prova do Corolário~\ref{cor:dimf}).  Ademais,
se~$f$ é injetora ou sobrejetora e, além disso, $\dim U=\dim V$,
então~$f$ é inversível.

\subsection{Matrizes e dimensão} 
\label{sec:matrizes-e-dimensao}
Seja~$A\in\FF^{R\times C}$ uma matriz e seja $f_A\:\FF^C\to\FF^R$ tal
que $f_A(\bfv)=A\bfv$ para todo~$\bfv\in\FF^C$.  Temos que
\begin{equation}
  \label{eq:34mx}
  \dim\FF^C=\dim\Ker f_A+\dim\Im f_A.
\end{equation}
Já sabemos que $\dim\FF^C=|C|$.  Ademais,
$\Im f_A=\{A\bfv\:\bfv\in\FF^C\}$ coincide com o espaço das colunas
$\Span\{A_{*c}\:c\in C\}$ de~$A$, e portanto $\dim\Im f_A$ é o posto
de~$A$.  Temos também que $\Ker f_A=\Null A$.  Definimos a
\textit{nulidade}~$\nullity A$ de~$A$ como sendo
$\dim\Null A=\dim\Ker f_A$.  Assim, temos
\begin{equation}
  \label{eq:34mxb}
  |C|=\nullity A+\posto A.
\end{equation}

\begin{teorema}
  \label{thm:invertible_mx}
  Seja $A\in\FF^{R\times C}$ uma matriz.  Quaisquer duas das três
  afirmações abaixo implica a terceira{\/{\rm:}}
  \begin{enumerate}[label=\rmlabel]
  \item\label{it:inv_mx.i} $\nullity A=0$;
  \item\label{it:inv_mx.ii} $\posto A=|R|$;
  \item\label{it:inv_mx.iii} $|C|=|R|$.
  \end{enumerate}
  Ademais, $A$ é inversível se e só se valem quaisquer duas das
  afirmações acima.
\end{teorema}
\begin{proof}
  Exercício.
\end{proof}

\subsection{O aniquilador} 
\label{sec:aniquilador}
Seja~$V\subset\FF^n$ um espaço vetorial.  O \textit{aniquilador}
de~$V$ é
\begin{equation}
  \label{eq:33}
  V^\circ=\{\bfu\in\FF^n\:\bfu\cdot\bfv=\bfzero\text{ para todo
  }\bfv\in V\}.
\end{equation}
É fácil ver que~$V^\circ$ é um espaço vetorial.  De fato, $V^\circ$~é
o espaço nulo de uma certa matriz.  Suponha que
$\bfa_i\dots,\bfa_r\in\FF^n$ formem uma base de~$V$.  Seja~$A$ a
matriz cujas linhas são os vetores linha $\bfa_i^\top$
($1\leq i\leq r$):
\begin{equation}
  \label{eq:35}
  A=
  \begin{bmatrix}
    \bfa_1^\top\\
    \vdots\\
    \bfa_r^\top
  \end{bmatrix}\in\FF^{r\times n}.
\end{equation}
Aqui estamos transpondo os vetores~$\bfa_i\in\FF^n$ pois estamos
pensando neles como vetores coluna (veja~\S\ref{sec:vetores-coluna}). 

\begin{proposicao}
  \label{prop:aniq=null}
  Tem-se que $V^\circ=\Null A$.
\end{proposicao}
\begin{proof}
  Isso é imediato, dado que $V=\Span\{\bfa_1,\dots,\bfa_r\}$ e
  $\bfa_i^\top\bfu=\bfu\cdot\bfa_i$ (complete os detalhes).
\end{proof}

O seguinte fato segue de~\eqref{eq:34mxb}.

\begin{teorema}
  \label{thm:aniq_dim}
  Seja~$V\subset\FF^n$ um espaço vetorial.  Então
  \begin{equation}
    \label{eq:36}
    \dim V+\dim V^\circ=n.
  \end{equation}
\end{teorema}
\begin{proof}
  Como acima, seja~$\{\bfa_i,\dots,\bfa_r\}$ uma base de~$V$, e
  seja~$A$ a matriz em~\eqref{eq:35}.  Note que $\dim V=r=\posto A$.
  Ademais, $\dim V^\circ=\dim\Null A=\nullity A$, donde vemos
  que~\eqref{eq:36} é equivalente a~\eqref{eq:34mxb}, e o resultado
  segue.
\end{proof}

Seja~$V\subset\FF^n$ um espaço vetorial.  É fácil ver que
$V\subset(V^\circ)^\circ$ (exercício).

\begin{teorema}
  \label{thm:aniqaniq}
  Seja~$V\subset\FF^n$ um espaço vetorial.  Então $V=(V^\circ)^\circ$.
\end{teorema}
\begin{proof}
  Já observamos que
  \begin{equation}
    \label{eq:37}
    V\subset(V^\circ)^\circ.    
  \end{equation}
  Para provarmos que esses dois espaços coincidem, usamos um argumento
  de dimensão.  Aplicando~\eqref{eq:36} a~$V$ e a~$V^\circ$, obtemos
  \begin{equation}
    \label{eq:36b}
    \dim V+\dim V^\circ=n
  \end{equation}
  e
  \begin{equation}
    \label{eq:36c}
    \dim V^\circ+\dim(V^\circ)^\circ=n.
  \end{equation}
  Claramente, segue de~\eqref{eq:36b} e~\eqref{eq:36c} que
  \begin{equation}
    \label{eq:38}
    \dim V=\dim(V^\circ)^\circ.
  \end{equation}
  Lembrando~\ref{it:dim_principle.ii} da
  Proposição~\ref{prop:dim_principle}, o resultado segue
  de~\eqref{eq:37} e~\eqref{eq:38}.
\end{proof}

\subsection{Representações de espaços vetoriais} 
\label{sec:rep_vsp}
Seja~$V\subset\FF^D$ um espaço vetorial sobre~$\FF$.  Podemos
representar~$V$ como $\Span B$, onde~$B$ é uma base de~$V$.  Há outra
forma de se representar~$V$: há necessariamente uma
matriz~$A\in\FF^{R\times D}$ tal que $V=\Null A$.  Vamos discutir como
obter~$A$ a partir de~$B$ e vice-versa.

Nossa discussão nessa seção será parcial, no sentido que vamos supor
que temos acesso a um algoritmo, Algoritmo~X, tal que, dado um espaço
vetorial~$V$ através de um conjunto gerador~$B$ (isto é, tal que
$V=\Span B$), devolve uma base para seu aniquilador~$V^\circ$.

\IncMargin{1em}
\begin{algorithm}[h]
  \LinesNumbered \null
  \SetKwInOut{Input}{Entrada}\SetKwInOut{Output}{\phantom{Entrada}{\llap{Saída}}}
  \Input{Vetores $\bfb_1,\dots,\bfb_s\in\FF^D$ tais que
    $V=\Span\{\bfb_1,\dots,\bfb_s\}$} 
  \Output{Uma base $\bfa_1,\dots,\bfa_r$ do aniquilador
    $V^\circ\subseteq\FF^D$} \BlankLine
  \caption{\textsc{Algoritmo X}}\label{alg:X}
\end{algorithm}
\DecMargin{1em}

\subsubsection{De bases para espaços nulos}
\label{sec:de-bases-para}
Suponha que $V=\Span\{\bfb_1,\dots,\bfb_s\}$.  Suponha que,
alimentando os~$\bfb_i$ ao Algoritmo~X, obtemos $\bfa_1,\dots,\bfa_r$,
que formam um base de~$V^\circ$.  Monte a matriz $A\in\FF^{R\times D}$
cuja $i$-ésima linha é~$\bfa_i$ (aqui, $R=\{1,\dots,r\}$).  Pela
Proposição~\ref{prop:aniq=null}, temos que $(V^\circ)^\circ=\Null A$.
Entretanto, pelo Teorema~\ref{thm:aniqaniq}, temos que
$(V^\circ)^\circ=V$ e assim $V=\Null A$.  Convertemos assim a
representação $V=\Span\{\bfb_1,\dots,\bfb_s\}$ para a representação
$V=\Null A$.

\subsubsection{De espaços nulos para bases}
\label{sec:de-espacos-nulos}
Suponha agora que $V=\Null A$ para uma matriz~$A\in\FF^{R\times D}$.
Sejam $\bfa_i$ ($i\in R$) as linhas de~$A$.  Seja
$U=\Span\{\bfa_1,\dots,\bfa_r\}$.  Alimentando esses $\bfa_i$
($i\in R$) ao Algoritmo~X, obtemos vetores $\bfb_1,\dots,\bfb_s$ que
formam uma base de~$U^\circ$.  Pela Proposição~\ref{prop:aniq=null},
$U^\circ=\Null A=V$.  Assim, os $\bfb_1,\dots,\bfb_s$ formam uma base
de~$V$, como queríamos.

\begin{uremark}
  Para implementar o Algoritmo~X, o que faremos mais à frente é, de
  fato, resolver o problema ``encontrar uma base para $\Null A$'' (o
  problema discutido em~\S\ref{sec:de-espacos-nulos}) usando
  eliminação gaussiana.
\end{uremark}

\newpage
\begingroup
\footnotesize
\tableofcontents
\endgroup

\endgroup % por causa do \onehalfspace
\end{document}


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