Question3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3) Product of matrices of special shape\n",
    "\n",
    "---\n",
    "\n",
    "## 1. Sum and product of two $T$-matrices\n",
    "\n",
    "### Let's prove that the sum of two $T$-matrices is a $T$-matrix\n",
    "\n",
    "Let $A$ and $B$ be two $T$-matrices of size $(n+1)\\times(n+1)$, with $a_{i, j}$ and $b_{i, j}$ the factors of these matrices, $T$-matrices are defined so that $a_{i+1, j+1} = a_{i, j}$ and similarly for the matrix $B$, finally if we sum $A$ and $B$ to obtain the matrix $C$, let's define $c_{i, j}$ the factors of $C$.\n",
    "\n",
    "We obtain that $$c_{i, j} = a_{i, j} + b_{i, j}$$ and in particular for $i+1$ and $j+1$ we obtain $$c_{i+1, j+1} = a_{i+1, j+1} + b_{i+1, j+1}\\\\\n",
    "\\Leftrightarrow c_{i+1, j+1} = a_{i, j} + b_{i,j}$$ by definition of $A$ and $B$.\n",
    "\n",
    "Thus, $$c_{i+1, j+1} = c_{i, j}$$ then we can conclude that $C$ is a $T$-matrix and that a sum of two $T$-matrices is a $T$-Matrix.\n",
    "\n",
    "Concerning the multiplication of $T$-matrices, there's nothing that we can apparently say about the multiplication of two matrices, for example if we take two $T$-matrices \n",
    "\n",
    "$$\n",
    "\\left( \\begin{array}{ccc}\n",
    "    1 & 4 & 5 \\\\\n",
    "    2 & 1 & 4 \\\\\n",
    "    3 & 2 & 1 \\\\\n",
    "\\end{array} \\right) and\n",
    "\\left( \\begin{array}{ccc}\n",
    "  7 & 9 & 5 \\\\\n",
    "  8 & 7 & 9 \\\\\n",
    "  12 & 8 & 7 \\\\\n",
    "\\end{array} \\right)\n",
    "$$\n",
    "\n",
    "We can compute the product,that gives us\n",
    "\n",
    "$$\n",
    "\\left( \\begin{array}{ccc}\n",
    "    99 & 77 & 76\\\\\n",
    "    70 & 57 & 47\\\\\n",
    "    49 & 49 & 40\\\\\n",
    "\\end{array} \\right)\n",
    "$$\n",
    "\n",
    "Then we can't say anything about this product."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Representation of $T$-matrices\n",
    "\n",
    "To compute the sum of $T$-matrices, an easier way to represent them is to use a list that we can construct by putting in first position, the factor of the diagonal, then all the remaining factors of the first row and all the remaining factors of the first column. For the matrix $A$ of factors $a_{i, j}$ for example we obtain the following list that we will call $L_{A}$ :\n",
    "$$L_{A} = \\left( a_{1, 1}, a_{1, 2}, ... , a_{1, n+1}, a_{2, 1}, ... , a_{n, 1}, a_{n+1, 1} \\right)$$\n",
    "\n",
    "Then the algorithm to compute the sum of two $T$-matrices is easy to deduce from this representation,\n",
    "\n",
    "Function sumOfTmatrices($L_a$,$L_b$) <br><br>\n",
    "&emsp;&emsp;for $i$ from $1$ to $2n + 1$ do <br>\n",
    "&emsp;&emsp;&emsp;&emsp;$L_c$\\[i\\] $\\leftarrow$ $L_a$\\[i\\] + $L_b$\\[i\\] <br>\n",
    "&emsp;&emsp;end for <br>\n",
    "&emsp;&emsp;return $L_c$\n",
    "\n",
    "And this algorithm is in $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Product of $T$-Matrices\n",
    "\n",
    "#### a) Product of a $T$-Matrix and a vector\n",
    "\n",
    "We consider here $A$ a $T$-Matrix of size $(n+1)\\times(n+1)$ with the following shape:\n",
    "$$\n",
    "\\left( \\begin{array}{cccccc}\n",
    "    a & b_1 & b_2 & ... & ... & b_n\\\\\n",
    "    c_1 & a & b_1 & b_2 & ... & b_{n-1}\\\\\n",
    "    c_2 & c_1 & a & b_1 & ... & b_{n-2}\\\\\n",
    "    c_3 & c_2 & c_1 & a & ... & b_{n-3}\\\\\n",
    "    \\vdots & \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    c_n & c_{n-1} & c_{n-2} & ... & ... & a\\\\\n",
    "\\end{array} \\right)\n",
    "$$\n",
    "\n",
    "And let $V = \\left( \\begin{array}{c} v_0 \\\\ v_1 \\\\ \\vdots \\\\ v_n \\\\ \\end{array} \\right)$ be a vector of dimension $n+1$.\n",
    "\n",
    "We consider $$p_A(x) = c_n + c_{n-1}x + c_{n-2}x^2 + ... + c_1x^{n-1} + ax^n + b_1x^{n+1} + b_2x^{n+2} + ... + b_nx^{2n}$$ the polynomial representation of $A$ and $$p_V(x) = v_n + v_{n-1}x + v_{n-2}x^2 + ... + v_0x^n$$ the polynomial representation of $V$.\n",
    "\n",
    "If we perform $p_A(x).p_V(x)$ we can see that the terms with degree in between $n$ and $2n$ are\n",
    "$$ \n",
    "(c_nv_0 + c_{n-1}v_1 + c_{n-2}v_2 + ... + c_2v_{n-2} + c_1v_{n-1} + av_n)x^n \\\\\n",
    "+ (c_{n-1}v_0 + c_{n-2}v_1 + c_{n-3}v_2 + ... + c_1v_{n-2} + av_{n-1} + b_1v_n)x^{n+1}\\\\\n",
    "\\vdots \\\\\n",
    "+ (c_1v_0 + av_1 + b_1v_2 + ... + b_{n-3}v_{n-2} + b_{n-2}v_{n-1} + b_{n-1}v_n)x^{2n-1}\\\\\n",
    "+ (av_0 + b_1v_1 + b_2v_2 + ... + b_{n-2}v_{n-2}+ b_{n-1}v_{n-1} + b_nv_n)x^{2n}\\\\\n",
    "$$\n",
    "And it's easy to see that all the coefficient of this polynom between the degree $n$ and the degree $2_n$ are the coefficient of the vector $AV$ by computing the vector.\n",
    "$$\n",
    "AV = \\left( \\begin{array}{c}\n",
    "    av_0 + b_1v_1 + b_2v_2 + ... + b_{n-2}v_{n-2}+ b_{n-1}v_{n-1} + b_nv_n\\\\\n",
    "    c_1v_0 + av_1 + b_1v_2 + ... + b_{n-3}v_{n-2} + b_{n-2}v_{n-1} + b_{n-1}v_n\\\\\n",
    "    \\vdots \\\\\n",
    "    c_{n-1}v_0 + c_{n-2}v_1 + c_{n-3}v_2 + ... + c_1v_{n-2} + av_{n-1} + b_1v_n\\\\\n",
    "    c_nv_0 + c_{n-1}v_1 + c_{n-2}v_2 + ... + c_2v_{n-2} + c_1v_{n-1} + av_n\\\\\n",
    "    \\end{array} \\right)\n",
    "$$\n",
    "All the coefficients of the vector correspond to a coefficient of the polynom.\n",
    "\n",
    "Thus, we can deduce that computing $AV$ is equivalent to calculate $p_A(x).p_V(x)$ and more precisely, it's equivalent to compute the coefficient of $p_A(x).p_V(x)$ that correspond to a degree which is in $[n;2n]$.\n",
    "\n",
    "And we know to calculate a product of polynom with an algorithm of complexity $O(n$ln$(n))$ with the Karatsuba's algorithm, then we can compute $AV$ with a complexity in $O(n$ln$(n))$ by computing $p_A(x).p_V(x)$.\n",
    "\n",
    "This is more efficient that the naïve matrix-vector multiplication that must compute, if we only consider products, $n$ iterations for each terms, and then to compute the $n$ terms we have a complexity in $O(n^2)$.\n",
    "\n",
    "#### b) Product of 2 $T$-Matrices\n",
    "\n",
    "To compute efficiently two $T$-Matrices we can consider that the second $T$-Matrix have the following representation:\n",
    "$$\n",
    "B = (\\begin{array}{cccccc}V_0 & V_1 & V_2 & ... & V_{n-1} & V_{n}\\end{array})\n",
    "$$\n",
    "with $V_k, k$ in $[0;n]$ some vectors of dimention $n+1$ with the coefficients of $B$.\n",
    "\n",
    "Then instead of doing the naïve calculation of $AB$ wich have a complexity in $O(n^3)$ we can compute\n",
    "$$\n",
    "AB = (\\begin{array}{cccccc}AV_0 & AV_1 & AV_2 & ... & AV_{n-1} & AV_{n}\\end{array})\n",
    "$$\n",
    "and with the polynomial representation that we have seen previously, this computation have a complexity in $O(n^2ln(n))$, wich is way more efficient."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}