gistfile1.txt

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{enumitem}
\usepackage{amsmath}

\title{Advanced Algo ex 1}
\author{zozosuper6281 }
\date{January 2020}

\begin{document}

\maketitle

\section{}

\begin{enumerate}[label=(\alph*)]
\item $(x + x^2) * (1 + x + x^3)  =  x^5 + x^4 + x^ 3 + x \in Z_{2}[x]$
\item $q = x^2 + x$,  $r = x^3 + x +1 \in Z_{2}[x]$
\end{enumerate}

\section{}

\begin{enumerate}[label=(\alph*)]
\item 
\begin{tabular}{ |c|c|c|c|c| } 
\hline
i & $r_{i}$ & $s_{i}$ & $t_{i}$ & $q_{i}$ \\
\hline
0 & 1234567 & 1 & 0 &\\
\hline
1 & 123 & 0 & 1 & 10037\\
\hline
2 & 16 & 1 & -10037 & 7\\
\hline
3 & 11 & -7 & 70260 & 1\\
\hline
4 & 5 & 8 & -80297 & 2\\
\hline
5 & 1 & -23 & 230854 & 5\\
\hline
6 & 0 & 123 & -1234567 &\\
\hline
\end{tabular}

$l=5$, $gcd(f, g) = r_{5}= 1$

We have
$s_{l}*f + t_{l} * g = r_{l}$. This means that: $t_{l} * g \equiv 1$ $\pmod f$.

Hence, $t_{l} = g^{-1} = 230854 \in Z_{f}$

\item 
\begin{tabular}{ |c|c|c|c|c| } 
\hline
i & $r_{i}$ & $s_{i}$ & $t_{i}$ & $q_{i}$ \\
\hline
0 & $x^4 + x^3 + x + 1$ & 1 & 0 &\\
\hline
1 & $x^4 + 1$ & 0 & 1 & 1\\
\hline
2 & $x^3 + x$ & 1 & 1 & x\\
\hline
3 & $x^2 + 1$ & x & 1 + x & x\\
\hline
4 & 0 & $1 + x^2$ & $x^2 + x + 1$ &\\
\hline
\end{tabular}

$l=3$, $gcd(f, g) = r_{3}= x^2 +1 \in Z_{2}[x]$
\end{enumerate}

\section{}

Assume that Lagrange polynomial is already proven:
$f(x) = \sum_{i=0}^d l_{i}\eta_{i}$. Where, $\eta_{i} = f(\xi_{i})$ with $i = 0...d$. Thus,

$\alpha_0x^0 + \alpha_1x^1 + \alpha_2x^2 +...+\alpha_d x^d = \sum_{i=0}^d l_{i}\eta_{i}$
with $\alpha_0$, $\alpha_1$,..., $\alpha_d$ are the coefficients of function f(x).

We have:
$l_i = \sum_{k=0}^d \lambda_{i, k} x^k$. Hence,

$l_0 = \lambda_{00} x^0 + \lambda_{01} x^1 +...+ \lambda_{0d} x^d$

$l_1 = \lambda_{10} x^0 + \lambda_{11} x^1 +...+ \lambda_{1d} x^d$

...

$l_d = \lambda_{d0} x^0 + \lambda_{d1} x^1 +...+ \lambda_{dd} x^d$

Therefore, 

$\alpha_0x^0 + \alpha_1x^1 +...+\alpha_d x^d = \sum_{i=0}^d l_{i}\eta_{i}$

$=(\lambda_{00} \eta_0 + \lambda_{10} \eta_1 + .... + \lambda_{d0} \eta_d) x^0 +(\lambda_{01} \eta_0 + \lambda_{11} \eta_1 + .... + \lambda_{d1} \eta_d) x^1 + ... + (\lambda_{0d} \eta_0 + \lambda_{1d} \eta_1 + .... + \lambda_{dd} \eta_d) x^d$

We see the pattern: $\alpha_i = \sum_{m=0}^d \lambda_{mi} * \eta_m$. Hence,

$\begin{bmatrix}
\lambda_{00} & \lambda_{10} & ... & \lambda_{d0}\\
\lambda_{01} & \lambda_{11} & ... & \lambda_{d1}\\
... & ... & ... & ...\\
\lambda_{0d} & \lambda_{1d} & ... & \lambda_{dd}\\
\end{bmatrix} * 
\begin{bmatrix}
\eta_0\\
\eta_1\\
... \\
\eta_d\\
\end{bmatrix} =
\begin{bmatrix}
\alpha_0\\
\alpha_1\\
... \\
\alpha_d\\
\end{bmatrix}$

In addition, we have:

$\begin{bmatrix}
\xi_{0}^0 & \xi_{0}^1 & ... &\xi_{0}^d\\
\xi_{1}^0 & \xi_{1}^1 & ... &\xi_{1}^d\\
... & ... & ... & ...\\
\xi_{d}^0 & \xi_{d}^1 & ... &\xi_{d}^d\\
\end{bmatrix} * 
\begin{bmatrix}
\alpha_0\\
\alpha_1\\
... \\
\alpha_d\\
\end{bmatrix} =
\begin{bmatrix}
\eta_0\\
\eta_1\\
... \\
\eta_d\\
\end{bmatrix}$

Therefore,

$\begin{bmatrix}
\xi_{0}^0 & \xi_{0}^1 & ... &\xi_{0}^d\\
\xi_{1}^0 & \xi_{1}^1 & ... &\xi_{1}^d\\
... & ... & ... & ...\\
\xi_{d}^0 & \xi_{d}^1 & ... &\xi_{d}^d\\
\end{bmatrix} * 
\begin{bmatrix}
\lambda_{00} & \lambda_{10} & ... & \lambda_{d0}\\
\lambda_{01} & \lambda_{11} & ... & \lambda_{d1}\\
... & ... & ... & ...\\
\lambda_{0d} & \lambda_{1d} & ... & \lambda_{dd}\\
\end{bmatrix} * 
\begin{bmatrix}
\eta_0\\
\eta_1\\
... \\
\eta_d\\
\end{bmatrix} =
\begin{bmatrix}
\eta_0\\
\eta_1\\
... \\
\eta_d\\
\end{bmatrix}$

Hence,

$\begin{bmatrix}
\xi_{0}^0 & \xi_{0}^1 & ... &\xi_{0}^d\\
\xi_{1}^0 & \xi_{1}^1 & ... &\xi_{1}^d\\
... & ... & ... & ...\\
\xi_{d}^0 & \xi_{d}^1 & ... &\xi_{d}^d\\
\end{bmatrix} * 
\begin{bmatrix}
\lambda_{00} & \lambda_{10} & ... & \lambda_{d0}\\
\lambda_{01} & \lambda_{11} & ... & \lambda_{d1}\\
... & ... & ... & ...\\
\lambda_{0d} & \lambda_{1d} & ... & \lambda_{dd}\\
\end{bmatrix} = 1$

As a result, the Vandermonde matrix is invertible and its invert matrix is

$\begin{bmatrix}
\lambda_{00} & \lambda_{10} & ... & \lambda_{d0}\\
\lambda_{01} & \lambda_{11} & ... & \lambda_{d1}\\
... & ... & ... & ...\\
\lambda_{0d} & \lambda_{1d} & ... & \lambda_{dd}\\
\end{bmatrix}$

\section{}
\begin{enumerate}[label=(\alph*)]
\item 
Induction base case:
$i = 0$

$R_0 = \begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}$

$R_0 \begin{bmatrix}
f \\
g
\end{bmatrix} = 
\begin{bmatrix}
f \\
g
\end{bmatrix} =
\begin{bmatrix}
r_0 \\
r_1
\end{bmatrix}$

The hypothesis is true for base case. Let's assume that the hypothesis is true for $k > 0$:

$R_k \begin{bmatrix}
f \\
g
\end{bmatrix} = 
\begin{bmatrix}
r_k \\
r_{k+1}
\end{bmatrix}$

We have:
$R_{k+1} = Q_{k+1}Q_k....Q_1R_0 = Q_{k+1}R_k$

Therefore:
$R_{k+1} = 
\begin{bmatrix}
0 & 1 \\
1 & -q_{k+1}
\end{bmatrix} R_k
$

$\Longrightarrow R_{k+1}
\begin{bmatrix}
f \\
g
\end{bmatrix} = 
\begin{bmatrix}
0 & 1 \\
1 & -q_{k+1}
\end{bmatrix} R_k
\begin{bmatrix}
f \\
g
\end{bmatrix} =
\begin{bmatrix}
0 & 1 \\
1 & -q_{k+1}
\end{bmatrix}
\begin{bmatrix}
r_k \\
r_{k+1}
\end{bmatrix} = 
\begin{bmatrix}
r_{k+1} \\
r_k - q_{k+1}r_{k+1}
\end{bmatrix}
$

$\Longrightarrow R_{k+1}\begin{bmatrix}
f \\
g
\end{bmatrix} = \begin{bmatrix}
r_{k+1} \\
r_{k+2}
\end{bmatrix}$
Therefore, (a) is true

\item 
Induction base case:
$i = 0$

$R_0 = \begin{bmatrix}
s_0 & t_0\\
s_1 & t_1
\end{bmatrix}$ as shown by definition of $R_0$

The hypothesis is true for base case. Let's assume that the hypothesis is true for $k > 0$:

$R_k = \begin{bmatrix}
s_k & t_k\\
s_{k+1} & t_{k+1}
\end{bmatrix}$

We have:
$R_{k+1} = Q_{k+1}R_k = \begin{bmatrix}
0 & 1 \\
1 & -q_{k+1}
\end{bmatrix}
\begin{bmatrix}
s_k & t_k\\
s_{k+1} & t_{k+1}
\end{bmatrix} =
\begin{bmatrix}
s_{k+1} & t_{k+1}\\
s_k - q_{k+1}s_{k+1} & t_k -q_{k+1}t_{k+1}
\end{bmatrix}$

Therefore,
$R_{k+1} = 
\begin{bmatrix}
s_{k+1} & t_{k+1}\\
s_{k+2} & t_{k+2}
\end{bmatrix}$ which means that (b) is also true

\end{enumerate}

\end{document}