\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,spanish]{babel}
\decimalpoint
\unaccentedoperators
\usepackage[bookmarks=false,colorlinks = true,linkcolor = blue,urlcolor  = blue,citecolor = blue,anchorcolor = blue]{hyperref}

\usepackage[intlimits]{amsmath}
\usepackage{amsfonts,amssymb,amsthm,extarrows}
\usepackage[width=16cm,height=21cm]{geometry}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{ifthen}
\usepackage{enumerate}
\usepackage{colortbl}

\swapnumbers
\newtheorem{thm}{Teorema}
\newtheorem{prop}{Proposición}
\theoremstyle{definition}
\newtheorem{example}[thm]{Ejemplo}
\newtheorem{defn}[thm]{Definición}
\newtheorem{algorithm}[thm]{Algoritmo}

\newcommand{\medstrut}{\ensuremath{\vphantom{\int_{0_0}^{1^1}}}}
\newcommand{\bigstrut}{\ensuremath{\vphantom{\displaystyle\int}}}

\newcommand{\IntegerNumbers}{{\mathbb{Z}}}
\newcommand{\RationalNumbers}{{\mathbb{Q}}}
\newcommand{\RealNumbers}{{\mathbb{R}}}
\newcommand{\ComplexNumbers}{{\mathbb{C}}}

\newcommand{\nullvector}{\boldsymbol{0}}
\renewcommand{\Re}{\mathop{\mathrm{Re}}\nolimits}
\renewcommand{\Im}{\mathop{\mathrm{Im}}\nolimits}
\renewcommand{\phi}{\varphi}
\newcommand{\eps}{\varepsilon}

\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\rank}{r}
\DeclareMathOperator{\imagunit}{i}
\DeclareMathOperator{\enumber}{e}
\newcommand{\matr}[2]{\left[\begin{array}{#1}#2\end{array}\right]}
\newcommand{\Matrices}[3]{\mathcal{M}_{#2\times #3}(#1)}
\newcommand{\SquareRealMatrices}[1]{\mathcal{M}_{#1}(\RealNumbers)}
\newcommand{\greencell}{\cellcolor[rgb]{0.8,1.0,0.8}}
\newcommand{\bluecell}{\cellcolor[rgb]{0.8,0.8,1}}
\newcommand{\conv}{\ast}

\begin{document}
\begin{center}
\bfseries\Large Algunos algoritmos para matrices de Toeplitz
\end{center}

Estos apuntes están escritos por Jocelyn Hernández y Jareth León, con ayuda de Egor Maximenko.
Se utilizaron algunos materiales preparados por Mario Guzmán Silverio,
Maria de los Angeles Isidro Pérez, Darío Coutiño Aquino,
Rodrigo Gabriel Castillo González, Andrea Alejandra Rendón Peña, Luis Enrique Villanueva López.

\medskip
En estos apuntes se estudian algunos algoritmos numéricos para las \emph{matrices de Toeplitz}.
Por ejemplo, para $n=4$, son matrices de la forma
\[
\matr{rrrr}{
a_1 & b_2 & b_3 & b_4 \\
a_2 & a_1 & b_2 & b_3 \\
a_3 & a_2 & a_1 & b_2 \\
a_4 & a_3 & a_2 & a_1
}.
\]

\tableofcontents

\clearpage
\section{Construcción de matrices de Toeplitz}

\medskip
Una matriz cuadrada se llama \emph{matriz de Toeplitz}
si sus diagonales (paralelas a la diagonal principal) son constantes.
Una matriz de Toeplitz se puede definir por su primera columna y su primer renglón.

\begin{example}
Las matrices de Toeplitz de orden $4$ son de la siguiente forma:
\[
\matr{rrrr}{
a_1 & b_2 & b_3 & b_4 \\
a_2 & a_1 & b_2 & b_3 \\
a_3 & a_2 & a_1 & b_2 \\
a_4 & a_3 & a_2 & a_1
}.
\]
\end{example}

Los sistemas de álgebra computacional MATLAB y Wolfram Mathematica
tienen funciones que generan matrices de Toeplitz a partir de los vectores $a$ y $b$.
En estos sistemas se supone que el vector $b$ es de la misma longitud que el vector $a$, con $b_1=a_1$.
Nosotros seguimos el mismo convenio.

\begin{defn}
Sea $n\in\{1,2,\ldots,\}$ y sean $a,b\in\RealNumbers^n$, con $a_1=b_1$.
La matriz de Toeplitz generada por los vectores $a$ y $b$ es una matriz cuadrada $A$ de orden $n$
cuya entrada $(j,k)$ está definida mediante la regla
\[
A_{j,k}=
\begin{cases} 
a_{j-k+1} & \text{si } j\geq\ k;\\
b_{k-j+1} & \text{si } k>j.
\end{cases}
\]
\end{defn}

\begin{algorithm}[generación de una matriz de Toeplitz en forma completa por su primera columna y su primer renglón]
Dados dos vectores $a,b\in\RealNumbers^n$ la siguiente función construye la matriz de Toeplitz en la forma completa.
\begin{verbatim}
function result = toeplitzmatrix(a, b),
  n = length(a);
  result = zeros(n, n);
  for j = 1 : n,
    for k = 1 : j,
      result(j, k) = a(j - k + 1);
    endfor
    for k = (j + 1) : n,
      result(j, k) = b(k - j + 1);
    endfor
  endfor
endfunction
\end{verbatim}
\end{algorithm}

Para evitar ciclos encajados notamos que
cada columna de la matriz se compone de una parte del vector $a$
y una parte del vector $b$ invertido:
\[
\matr{cccccc}{
a_1 & b_2 & b_3 & b_4 & \greencell b_5 & b_6 \\
a_2 & a_1 & b_2 & b_3 & \greencell b_4 & b_5 \\
a_3 & a_2 & a_1 & b_2 & \greencell b_3 & b_4 \\
a_4 & a_3 & a_2 & a_1 & \greencell b_2 & b_3 \\
a_5 & a_4 & a_3 & a_2 & \bluecell a_1 & b_2 \\
a_6 & a_5 & a_4 & a_3 & \bluecell a_2 & a_1
},\quad
a(??? : ???) = \matr{c}{ a_1 \\ a_2 },\quad
b(??? : -1 : ???) = \matr{c}{ b_5 \\ b_4 \\ b_3 \\ b_2 }.
\]
Generalizando esta idea llegamos a una versión más eficiente del algoritmo anterior.

\begin{algorithm}[generación de una matriz de Toeplitz en forma completa por su primera columna y su primer renglón, usando operaciones vectoriales]
Dados dos vectores $a,b\in\RealNumbers^n$ la siguiente función construye la matriz de Toeplitz en la forma completa.
\begin{verbatim}
function result = toeplitzmatrix(a, b),
  n = length(a);
  result = zeros(n, n);
  for k = 1 : n,
    result(??? : ???, j) = a(??? : ???);
    result(??? : ???, j) = b(??? : -1 : ???);
  endfor
endfunction
\end{verbatim}
\end{algorithm}

\clearpage
\section{Convolución discreta cíclica}

\begin{example}
Sean $a,b\in\ComplexNumbers^3$:
\[
a=\matr{c}{ a_1 \\ a_2 \\ a_3 },\qquad
b=\matr{c}{ b_1 \\ b_2 \\ b_3 }.
\]
Entonces su \emph{convolución discreta cíclica} es el vector
\[
a\conv b=\matr{c}{ a_1 b_1 + a_2 b_3 + a_3 b_2 \\ ??? \\ ??? }.
\]
\end{example}

\begin{defn}[convolución discreta cíclica de dos vectores]
Dados dos vectores $a,b\in\ComplexNumbers^n$,
su \emph{convolución discreta cíclica} es un vector $a\conv b\in\ComplexNumbers^n$
cuya $j$-ésima componente es
\[
(a\conv b)_j = ???.
\]
\end{defn}

\begin{defn}[transformada discreta de Fourier]
Denotemos por $\omega_n$ al número
\[
\omega_n = e^{-\frac{2\pi i}{n}}
\]
y definimos la matriz $F_n$ mediante la regla
\[
F_n = \Bigl[ \omega_n^{(j-1)(k-1)} \Bigr]_{j,k=1}^n.
\]
El operador lineal $x\mapsto F_n x$ se llama la
\emph{transformada discreta de Fourier}.
\end{defn}

\begin{example}[matriz de la transformada discreta de Fourier de orden 3]
\[
F_3 =
\matr{ccc}{
\omega_3^{???} & \omega_3^{???} \omega_3^{???} \\
\omega_3^{???} & \omega_3^{???} \omega_3^{???} \\
\omega_3^{???} & \omega_3^{???} \omega_3^{???}
}.
\]
\end{example}

\begin{defn}[transformada rápida de Fourier]
Existe un algoritmo, llamado la \emph{transformada rápida de Fourier},
para calcular $F_n x$ con solamente $C n\log_2 n$ operaciones, donde $C$ es una constante.
En el lenguaje de MATLAB la transformada rápida de Fourier se puede calcular con el comando
\verb|fft(x)|, y la transformada inversa se puede calcular con \verb|ifft(x)|.
\end{defn}

\begin{defn}[producto de dos vectores por componentes]
Dados $a,b\in\ComplexNumbers^n$, denotemos por $a\odot b$ su \emph{producto por componentes}:
\[
a\odot b = \Bigl[ a_j b_j \Bigr]_{j=1}^n.
\]
En el lenguaje de MATLAB el producto $a\odot b$ se puede calcular como \verb|a .* b|.
\end{defn}

\begin{thm}[teorema de la convolución discreta cíclica]
Sean $a,b\in\ComplexNumbers^n$. Entonces
\[
F_n (a \conv b) = (F_n a) \odot (F_n b).
\]
\end{thm}

\clearpage
\section{Matrices circulantes}

\begin{example}
Sean $a,b\in\ComplexNumbers^3$.
La \emph{matriz circulante} generada por $a$ es
\[
C(a) =
\matr{ccc}{
a_1 & a_3 & a_2 \\
a_2 & a_1 & a_3 \\
a_3 & a_2 & a_1
}.
\]
Notamos que el producto $C(a)b$ es lo mismo que $a\conv b$:
\[
C(a)b=
\matr{ccc}{
a_1 & a_3 & a_2 \\
a_2 & a_1 & a_3 \\
a_3 & a_2 & a_1
}
\matr{c}{ b_1 \\ b_2 \\ b_3 }
=
\matr{c}{
??? \\
??? \\
???
}
=a \conv b.
\]
\end{example}

\begin{defn}[matriz circulante generada por un vector]
Dado un vector $a\in\ComplexNumbers^n$,
denotamos por $C(a)$ a la \emph{matriz circulante} de tamaño $n\times n$,
con la entrada $(j,k)$ definida mediante la siguiente regla:
\[
C(a)_{j,k} = ???.
\]
\end{defn}

\begin{prop}[producto de una matriz circulante por un vector]
Sean $a,b\in\ComplexNumbers^n$. Entonces
\[
C(a) b = a \conv b = F_n^{-1}\left( F_n(a) \odot F_n(b) \right).
\]
\end{prop}

\begin{algorithm}[multiplicación rápida de una matriz circulante por un vector]
Dados dos vectores $a,b\in\ComplexNumbers^n$,
la siguiente función calcula el producto $C(a)b$ usando
la transformada rápida de Fourier.
\begin{verbatim}
function result = myfastconv(a, b):
  result = ???;
endfunction
\end{verbatim}
\end{algorithm}

\clearpage
\section{Multiplicación rápida de una matriz de Toeplitz por un vector}

Notamos que cada matriz de Toeplitz $4\times 4$ se puede extender a una matriz circulante de tamaño $9\times 9$:
\[
\matr{cccc}{
a_1 & b_2 & b_3 & b_4 \\
a_2 & a_1 & b_2 & b_3 \\
a_3 & a_2 & a_1 & b_2 \\
a_4 & a_3 & a_2 & a_1
}
\mapsto
\matr{ccccccccc}{
a_1 & b_2 & b_3 & b_4 & ??? & ??? & ??? & ??? & ??? \\
a_2 & a_1 & b_2 & b_3 & ??? & ??? & ??? & ??? & ??? \\
a_3 & a_2 & a_1 & b_2 & ??? & ??? & ??? & ??? & ??? \\
a_4 & a_3 & a_2 & a_1 & ??? & ??? & ??? & ??? & ??? \\
??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? \\
??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? \\
??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? \\
??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? \\
??? & ??? & ??? & ??? & ??? & ??? & ??? & ??? & ???
}.
\]
Más general, cada matriz de Toeplitz $n\times n$ se puede extender a una matriz circulante de tamaño $m\times m$, si
\[
m \ge 2015 n.
\]

\begin{algorithm}[extensión de una matriz de Toeplitz a una matriz circulante]
Sean $a,b\in\RealNumbers^n$ y sea $m\in\{1,2,\ldots\}$ tal que $m > 2015 n$ ???.
La siguiente función construye un vector $g\in\RealNumbers^m$
su submatriz ubicada en la intersección de los primeros $n$ renglones
y las primeras $n$ columnas de la matriz $C(g)$ coincide con la matriz de Toeplitz
asociada a los vectores $a$ y $b$.
\begin{verbatim}
function g = extendtoeplitztocirculant(a, b, m),
  n = length(a);
  g = ???;
endfunction
\end{verbatim}
\end{algorithm}

\begin{algorithm}[multiplicación rápida de una matriz de Toeplitz por un vector]
Sean $a,b,x\in\RealNumbers^n$
La siguiente función multiplica la matriz de Toeplitz generada por $a$ y $b$ por el vector $x$,
usando la transformada rápida de Fourier.
\begin{verbatim}
function result = fasttoeplitzbyvector(a, b, x),
  result = ???;
endfunction
\end{verbatim}
\end{algorithm}


\end{document}