2_hw_cp220_A.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "view-in-github"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/AshrithSagar/CP220-M4RAS-2024/blob/main/2_hw_cp220_A.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tQL6OT5JA9ak"
      },
      "source": [
        "**Topics**\n",
        "\n",
        "* Linear Transforms representation as Matrix operation\n",
        "* Square and Rectangular, transpose, Diagonal, Lower triangular, upper triangular, sparse matrices\n",
        "* Image Space, Column Space, Row Space, Kernel or Null Space\n",
        "* Rank, Rank-nullity theorem, rank of a matrix product\n",
        "* Systems of linear equations and Gaussian Elimination\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NPDlsKfYmp-1"
      },
      "source": [
        "**Linear Transforms as Matrices**\n",
        "\n",
        "Let  $V_n \\&  W_m$ be $n \\& m$ dimensional vector spaces respectively\n",
        "\n",
        "and $T : V_n → W_m$ be a linear map.\n",
        "\n",
        "Let $v \\in V_n$ and $w \\in W_m$ and they can be represented as column vectors in their respective (arbitrary) orthonormal basis as: $v= \\begin{bmatrix} v_1 \\\\ v_2 \\\\ . \\\\ . \\\\ v_n \\end{bmatrix}$ and  $w= \\begin{bmatrix} w_1 \\\\ w_2 \\\\ . \\\\ . \\\\ w_m \\end{bmatrix}$\n",
        "\n",
        "We can represent $T$ as a 2D matrix with columns being the $T(e_i)$ with $\\{e_i\\}_{i=1..n}$ being a basis set for $V_n$ and $T = \\begin{bmatrix} t_{11} & t_{12} & .. & t_{1n} \\\\ t_{21} & t_{22} & .. & t_{2n} \\\\ ... \\\\ t_{m1} & t_{m2} & .. & t_{mn} \\end{bmatrix}$\n",
        "\n",
        "Then $T(v) = w$ for $v \\in V$ and $w \\in W$ can be computed as $w=Tv = $\n",
        "\n",
        "$w= \\begin{bmatrix} w_1 \\\\ w_2 \\\\ . \\\\ . \\\\ w_m \\end{bmatrix} =  \\begin{bmatrix} t_{11} & t_{12} & .. & t_{1n} \\\\ t_{21} & t_{22} & .. & t_{2n} \\\\ ... \\\\ t_{m1} & t_{m2} & .. & t_{mn} \\end{bmatrix} \\begin{bmatrix} v_1 \\\\ v_2 \\\\ . \\\\ . \\\\ v_n \\end{bmatrix} = v_1\\begin{bmatrix} t_{11}\\\\t_{21}\\\\.\\\\.\\\\t_{m1}\\end{bmatrix}+v_2\\begin{bmatrix} t_{12}\\\\t_{22}\\\\.\\\\.\\\\t_{m2}\\end{bmatrix} + ... + v_n \\begin{bmatrix} t_{1n}\\\\t_{2n}\\\\.\\\\.\\\\t_{mn}\\end{bmatrix}$\n",
        "\n",
        "and is a linear combination of the columns of $T$\n",
        "\n",
        "Thus $T \\subset ℝ ^{m\\times n}$\n",
        "\n",
        "Just as a confirmation, the representation of the $i^{th}$ basis vector $e_i \\in V_n$ is by the column vector $\\begin{bmatrix} 0\\\\.\\\\.\\\\1\\\\0\\\\.\\\\.\\end{bmatrix}$ with 1 in the $i^{th} row and 0's in all other rows.\n",
        "\n",
        "Thus the mapping $T(e_i)$ is computed as matrix vector multiplication $T e_i$ and picks out the $i^{th}$ column of $T$ \\begin{bmatrix} t_{1i}\\\\t_{2i}\\\\.\\\\.\\\\t_{mi}\\end{bmatrix}\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v43VlU5mcPz6"
      },
      "source": [
        "**Transpose of a matrix**\n",
        "Let $A$ be a $mxn$ matrix with $A=\\begin{bmatrix}a_{11} & a_{12} & ... & a_{1n} \\\\ ... \\\\ a_{m1} & a_{m2} & ... & a_{mn} \\end{bmatrix}$ then\n",
        "\n",
        "$A^T = \\begin{bmatrix}a_{11} & a_{21} & ... & a_{m1} \\\\ ... \\\\ a_{1n} & a_{2n} & ... & a_{mn} \\end{bmatrix}$ is a $nxm$ matrix\n",
        "\n",
        "\n",
        "If $A$ is a complex matrix then the transpose is also followed by complex conjugation and is called the Hermitian transpose or conjugate transpose\n",
        "\n",
        "$A^H = \\begin{bmatrix}\\overline{a_{11}} & \\overline{a_{21}} & ... & \\overline{a_{m1}} \\\\ ... \\\\ \\overline{a_{1n}} & \\overline{a_{2n}} & ... & \\overline{a_{mn}} \\end{bmatrix}$ is a $nxm$ Hermitian transpose matrix\n",
        "<br>\n",
        "<br>\n",
        "Fact:\n",
        "\n",
        "$(Av)^T = v^TA^T$\n",
        "\n",
        "*dot product*\n",
        "\n",
        "$v,w \\in V$ then the dot product\n",
        "\n",
        "$v \\cdot w = \\sum_{i=1}^n v_iw_i = v^Tw = w^T v$\n",
        "\n",
        "$v \\cdot w = \\sum_{i=1}^n \\bar{v_i}w_i = v^Hw$\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ymbw0lsWPwLi"
      },
      "source": [
        "**Notation**\n",
        "\n",
        "As a shorthand, the matrix $T$ is also written as $[t_{ij}]$\n",
        "\n",
        "An index range of 0,1,2,...,n-1 is also written as $:$\n",
        "\n",
        "(in python the numbering of first n elements of an array is from 0 to n-1)\n",
        "\n",
        "Thus the $i^{th}$ column of $T$ is $t_{:,i}$ and $T$ in terms of column vectors is:\n",
        "\n",
        "$T=\\begin{bmatrix}t_{:,1} & t_{:,2} & ...& t_{:,n}\\end{bmatrix}$\n",
        "\n",
        "\n",
        "When the context is clear, the matrix $T_{m \\times n}$ is represented as\n",
        "\n",
        "$T=\\begin{bmatrix} t_1 & t_2 & ... & t_n \\end{bmatrix}$\n",
        "\n",
        "where $t_1, t_2, ..., t_n$ are $m \\times 1$ column vectors\n",
        "\n",
        "Alternatively,\n",
        "$T= \\begin{bmatrix} r_1^T \\\\ r_2^T \\\\ . \\\\ . \\\\ . \\\\ r_m^T \\end{bmatrix}$\n",
        "\n",
        "where $r_i$ is a $n \\times 1$ column vector (and hence $r_i^T$ is a $1 \\times n$ row vector)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KwvPc69Jgv7J"
      },
      "source": [
        "**Matrix types**\n",
        "\n",
        "*Square matrix* is a matrix with equal number of rows and columns, e.g. $A_{n \\times n}$\n",
        "\n",
        "*Identity Matrix* is a special square matrix\n",
        "\n",
        "$I_n = \\begin{bmatrix} 1 &0 &...&0\\\\0&1&...&0\\\\...\\\\0&0&...&1\\end{bmatrix}_{n \\times n}$\n",
        "\n",
        "It has '1's only along the main diagonal and 0 everywhere else.\n",
        "\n",
        "If $v \\in V_n$ is a n-dimensional column vector then, $Iv = v$ and $v^TI = v^T$\n",
        "\n",
        "*diagonal matrix* is a square matrix with all off-diagonal entries as 0. Identity matrix is a diagonal matrix\n",
        "\n",
        "\n",
        "*lower triangular matrix* has zeros in the entries above the main diagonal. Example\n",
        "\n",
        "$L=  \\begin{bmatrix} 3.2 & 0 & 0 \\\\ 1.2 & 0 & 0 \\\\ 0 & 1 & 1 \\end{bmatrix}$\n",
        "\n",
        "Similarly *upper triangular matrix* has zeros in all entries below the main diagonal. Example\n",
        "\n",
        "$U = L^T $\n",
        "\n",
        "\n",
        "*Symmetrix Matrices*\n",
        "\n",
        "$A$ an $n \\times n$ matrix is symmetric is\n",
        "\n",
        "$A^T = A$ (for real matrices)\n",
        "\n",
        "$A^H = A$ (for complex matrices)\n",
        "\n",
        "this means that\n",
        "\n",
        "$a_{ij} = a_{ji}$ for real matrices \\\\\n",
        "$\\bar{a_{ij}} = a_{ji}$ for complex matrices\n",
        "and implies diagonal is real\n",
        "\n",
        "\n",
        "*Skew symmetrix matrix*\n",
        "\n",
        "A square matrix $A$ is skew-symmetric when:\n",
        "\n",
        "$A^T = -A$\n",
        "\n",
        "this means diagonal entries are 0 and off-diagonal are negatives $a_{ij} = -a_{ji}$ and $a_{ii}=0$\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "*Sparse Matrices* Certain computational problems can have matrices of dimensions $10^6 x 10^6$ i.e a million by million. However many such problems will also have sparse matrices - ie. only a fraction of the trillion entries will be non-zero. For example - only 10 to 20 million entries will be non-zero and others will be zero.\n",
        "\n",
        "This fact can be taken advantage of to reduce storage and compute."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sgRg4Ater6BG"
      },
      "source": [
        "**Pictorial View of a matrix transform**\n",
        "\n",
        "\n",
        "![Matrix_Transforms_Picture_1.jpg](data:image/jpeg;base64,/9j/4AAQSkZJRgABAgAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAExAhkDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD3+iiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACisjxL4l03wno7anqkki24cIBGhdmY9gB14BP0BrTgniureK4gcSQyoHR16MpGQR+FAElFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUVmaVr1jrEd+9s7AWF1JaXHmLt2SJjd+GCDn0NVvDni3SPFWiyatpkzm0jdkdpUKFSoBOQfYg/Q0AblFUNF1e11/RrXVbISfZrpPMi8xdrFexxV+gAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKAOJtZJtD+K91ZyyubHX7QXNsHYlUuIflkVR2yhVvwNP0WWXXfiLrepiV/7P0mNdLt0DHY83DzNj1GUT8DVzxvo9/qOnWV9o0SSaxpd3Hd2qO4QSY+V4y3YMjMPyq14O0OTw94WsrC4YPebTNdydd87kvIc9/mJ/DFAG7RRRQAUUUUAFFUdT1rStFjjk1XU7OwSQ7Ua6nWIMfQFiM1m/wDCdeE/+hl0k/S7T/GgDoKK5/8A4Tnwt216wPuJgRR/wm/hntrFuR6jJH8qAOgorn/+E28O9tSBHqsTkfmFo/4TXQO13Kw9VtJiPzCUAdBRXP8A/CaaH2lvGHqun3BH5hKP+Ez0fsNTYeq6TdMP0joA6Ciuf/4TLSu1vrTD1XRLxh+kVH/CY6cfu2WuN/3BLsfziFAHQUVz/wDwl9mfu6brjf8AcIuB/NBR/wAJbAfu6Rrjf9w2UfzAoA5DxfrMN58SLDTptL1LUtP0e2e4uYrG1af9/MpSNXA6YTew/wB6r/wm1V5vD91oFxHcxXOiTm3WO7jMcv2dvmhZlPT5OP8AgNW9Iu7HR7vVLq20bxFNcalcm5uJJrM5zgAKOnyqBgDmkjntY/Fc3iKDQvEQvJrVbWaNbdVjkVWyrEE/eHTOelAHbUVz/wDwk85+74a1xj6eTEP5yCj/AISW7P3fCuuE+mLcfzlFAHQUVz//AAkeoH7vhDXCfTfaD+c9H/CQ6qeB4N1sH/amssfpcGgDoKK5/wDt7WDwPCGqA/7Vza4/Saj+29bPTwneg+93b4/9DoA6Ciuf/tnXj08Kzfjew4/nR/a3iL/oWB+OoR/4UAdBRXP/ANqeJf8AoW4P/BkP/iKP7R8U/wDQu2P/AIND/wDGqAOgorn/ALd4s/6AGlf+Dd//AJHrLg1L4gN4p8iTQNIGkbVLzC/clG7hWMYLcYONmM/xegB2lFFFABRRRQB5J4oupvD+r+M9KtTtn8QW9rJYqP8AntK32aTHv91qr6+p8Gy+JvD+nDamr6XajT0HGJSVs2A98NE1ejav4T0zWtf0jWrsS/atKZmgCMArbsffGOcEAjpzS6z4U0zXdZ0fVLwS/aNJlaW32MApJxwwxyAVUjpyKANLTLCLS9KtNPtxiG1hSFP91VAH8qtUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAVh3XivTbTXotIfzjI7LHJOqZhhkYZSN3zwzdh9Om5cpreq3P2pNF0cqdVnTe0jDclpFnBlcdz1Cr/ER6BiLFv4c02DQn0d4PPtZg3n+cdzTs3LO7dSxPOfXpjAoA0YLiK5hjmhcNHIu5D0yPWpK5jTZX0zVYtG1hvOmMbppupOPnniOC0TN2kG0E/3wobqDjd8m4gjIt5BKI4NkcczH5nHQs/J54BOD680AWqKrSXiQea1wrRRxRq7TH7nOcgHrkY547j8LNABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABWRrmsvp4hs7GJbnVrvK2sBOAMfekcjoi5BJ+gHJFS61rEej2iP5TXF1M/lWtrGfnnkPRR6Dgkk8AAk9Kh0PR5LEzX+oSrcavd4NxMo+VQPuxR56IuTj1JJPJoAl0TRk0i1cNK1zeXD+bd3TjDTyY6+wA4C9AABWnRRQBS1XSrbWdPezulbYxDK6Ha8bg5V1PZgeQaz9F1W5W7fRNYZf7ThTekyjat5EOPMUdiMgMv8JPoRW7WbrWjx6xaIvmtb3cD+ba3UY+eCQdGHqOoIPBBIPWgDSqvJZQuZGVfKklZGkki+Vn2kYyRyemPpxWfoesSX3nWN/Etvq1pgXMKn5WB+7JGT1RsHB7EEHkGtigCuftcbOV8qYNKu1TlPLjwAeedxzuPbqBxjNAvIgyrLmFnlMMYl+XzGAJ+X14BP4VYooAKKrpZxRGPycwojvIY4/lV2bJYsO+SxP15oiN2hiSXypRtYySplMHI2gJz1Ge/b34ALFFV4byGbyV3eXNLF5wgk+WQLxkleowSAfQmrFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFUtV1S10fT5Ly7ZtikKqINzyOThUUd2JwAKmvb2206ymvLyZYbeFC8kjnhQKw9KsrnWNQj17VoWh2A/2fZSDm3UjHmOP+erD/AL5B29S2QCXRdLunu21vWFX+05k2Rwg7ls4jz5anuxwCzdyPQCt6iigAooooAKKKKAMfXNGkv/JvbCVbbVrTJtp2GVIP3o3A6o2BkdsAjkCpdF1mPWLVyYmt7yB/KurVzloJMdD6gjBDDggg1p1ha3pVyLpNa0cKNUgTY8THal5FnPlOex6lW/hJ9CQQDdoqlpOq22s6el5algpJV43G14nBwyOOzA8EVdoAKKKKAGyRpLE8cihkdSrKe4PUVXe2lRJPsk3lv5IjiWRd0UZGcNtBBPUZG4cAdOtWqKAK8lw8JlaSBzEgXa0eXZiTg/KBnjj/ACKkSeKWSWOOVHeJgsiqwJQkAgEdjgg/QipKjmginQJKgZQ6vj/aUgg/gQKAJKKr+VcIxMdxuDS72Eq52pjBVcYx65Oep/AW5YFFmgkRpJWjQKC4wMkMxAwoIXv3IHU0AWKKZFNFPGJIZEkQkjcjAjIODyPcEU+gAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKbJIkMTyyuqRopZmY4CgdST2FOrlW/4rO8KDnw5byYc9tQkU9B6wqRz/fIx90HcAOso38V30Oq3KMujW7h7C3cYNw46TuPT+4p/wB487cdRR0ooAKKKKACiiigAooooAKKKKAOd1axudK1B9f0iFpWYAahZJ1uUAwHQf8APVR0/vAbT/CRtWN9balYw3tnMs1vMoeORehH9Pp2qxXL30Unha+m1e0Rn0i4YvqNsgyYWPW4QD/x9R1+8OQdwB1FFMiljnhSaGRZIpFDI6HIYHkEHuKfQAUUUUAFFFFABRRRQBEbeIyxybMNHu24JAGevHQ1HHHcwLEvnfaESIh2kAEkj8YORhR/FnjqR0qzRQBWW8RV/fq0DCETSbwdiDuC/wB3I+vv0qyCCAQcg96R0WRGR1DKwwVIyCKgltA5meKaWGaVFTzEOdoBJGFbK5+Y9ufwFAFiiq7yXMRkbyRMm5BGkZAbBIDE7iBxyfoO5py3ULNIu4qY5BGd6lQWIBABP3vvDkZ546g0ATUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFYmt6xPBPHpWlIk2r3C7kV+Ut4+hlkx/COw6seB3IfresvYNDY2EK3OrXQP2eAnCqB1kkI+6i5GT3OAOSKk0TRk0iCRnma5vrlvMu7txhpn+nZR0VRwB+JIBjpLe+D5U/tK/uNQ0eYjzLy4IMlpKepfAx5TH/AL4Jx937vWA5GR0pskaSxtHIivG4KsrDIYHqCK5eCR/B1zHZ3Ds/h+VgltO5ybFicCJz/wA8yeFY/d+6eMGgDqqKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiud1e/utSv20DSJmimABvr1P+XSM9FX/pqw6D+EfMewYAiv5pfE9/No1lI8emQNs1G6jODI3e3jI7/32HQfKOSSvSQwxW8EcEEaRxRqEREGFVRwAB2FQ2Fha6XYQ2VlCsNvCu1EHYf1J6knknmrNABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFAHK/wDImXnp4cuJPw0+Rj+kLE/8AJ/un5eqpksUc8LwzRrJFIpV0cZDA8EEdxXNWMsnha+h0i7kZ9JnbZp1y5yYW7W7k/8AjjHr908gbgDqKKKKACiiigAooooAKKKKACiiigAprxpIAHRWCkMNwzgjofrTqKAK4tSjKYZpUHmmWQFt+/IPy/NnaMkHAx0+tCSXCmNZYNxd3BeIjaigkqTkg8jA4B5PpzViigCKG5iuI0eNuHBKhgVJA68HmpaY0MbSrK0amRVKq+PmUHGQD2zgfkKgW3lt40W3lZkig8tI5mLbmGMFnOWPTknOc55NAFqiqr3f2dJXuYmjjihEryjDJ3yB/ESMZ6dxjuBZyCSMjI6igBaKKKACiiigAooooAKytb1oaXHFDbw/atSuiUtLVWwZGHVmP8KL1Zu3uSAXa1rMWj2yHynuLudvLtbSM/PPJjoPQDqWPAAJNQ6Jo0tnJLqOpSpc6vdACaVR8kajkRRg9EH5k5J5PAA/RNFOmrNc3U32rVLohrq6K43EdEUfwouSAv1JySSdaiigAqOeCG6t5Le4iSWGVSjxuuVZTwQR3FSUUAcvaTzeFLuHTL6V5dHmYR2N3I2TAx6QSk9uyOev3Tzgt1FQ3dpb39pLaXcKTW8yFJI3GVZT1BFc/YXdx4dvodH1OZ5rKZtmn38hySe0Ep/v/wB1j94cH5h8wB01FFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUVka5rL6csNpZQrc6rdkra25OBx1dz2Rcgk/QDkgUARa3q1ytzHo2kbG1W4XcXYbktIs4Mrj8wq/xH2DEXtJ0m20awW0tt7cl5JZDueaQ8s7nuxPJP9Ki0TRk0i2kLzNc31w3m3d24w00mMZx2UDhV6AACtOgAooooAKKKKACiiigAooooAKKKKACiiigAooooAKr31jbanYzWV5Cs1vMpSRG6Ef0Pv2qxRQBzuk31zpWoJoGrzNK7AmwvX63SDkox/56qOv94fMP4gOiqlq2lW2s6e9ndBgpIZJIzteJxyroezA8g1n6Jqtz9qfRdYKjVIE3rKo2pdxZx5qDsegZf4SfQqSAbtFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABUEtnBL5h2mN5du+SIlHbacgFhz6/mfWp6KAK7C6QyNG0cu6VNqOdgROA3IByfvEepwMjrR9sRWxMrw5l8pN+P3hxkEYJ469cdKsUUAFFV1soIzGYV8kJK0pWL5FdmzuLAdcliee/PWiMXcZiRzFMp3eZJkoRz8oC4OfQ8jp70AWKz9Y1e30ay8+ZXkkdhHBbxDMk8h6Io7k/kACTgAmor/wAQ2Gl2MdzeGSKSWPfHalczSHIARUHVssowO5qto+lXU17/AG5rSr/aLqVgtw25LKM/wKe7njc3foOAKAHaLpFxHcyavq7JLq067cIcpax5z5Uft0LN1Y89AANyiigAooooAKKKKACq99Y2up2M1lewrNbzLtdG6Ef0PcHtViigDm9NvrrRb+LQ9YmaZJTt0+/f/luAM+VIf+eoHf8AjAz1BFdJVXUtOtdWsJbK9i8yCQcjOCCOQwI5BBwQRyCAayNK1G606/TQtal8ydgfsV6QALtBztbsJVHUfxD5h3CgHQ0UUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUVT1TVLXR9PkvbtiI0wAqDczsThUUd2JwAO5NAEOtaxFo1mshjee5mcRW1rH9+eQ9FH5EkngAEngVBoejy2TTahqMiXGr3YH2iVfuoo+7FHnoi5PuSSTyai0XS7qW8bXNZUDUpU2RQA7lsojz5anuxwCzdyABwBW9QAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAVma3o0esWqBZWtryB/NtbpBloJMdR6gjgqeCCRWnRQBj6HrMmoCayvolttWtMC5gBypz92RCeqNg4PbkHkGtisfXNHkvjDfafKtvq1pk20zD5WB+9HJjqjYGfQgEcgVNousR6xaO/lNb3UD+VdWsh+eCQdVPqOQQRwQQR1oA0qKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAqrqWo2uk2Et7ey+XBGOTjJJPAAA5JJwABySQKdfX1tptlNe3kyQ20Kl5JHPCisPTbK51u/i1zV4XhiiO7TrCQcwg8ebIP+epHQfwA46k0ALpml3GqXg1rXIAsu0rZ2L4ZbSNhgluxlYfePQD5RxktsmzMUbC0k8grB5UKFcxx4+6dgIzjjuOBirVFAFeSeaDzWeAvEiKVMRLO7c7htxxjjuc5PTHMiTwySyxJKjSRECRA2SmRkZHbipKjmgiuY/LmjWRNyttYZGVIYH8CAfwoAkoquYZkZmiuOXlDsJV3ALgAquCMdM555J69KBcSKyrNAyl5TGmzLjGCQzHHyggd+5A70AWKKKKACiiigAqlqul2usWD2d2hMbEMrI2143Byrqw5VgeQRV2igDA0jVLq2vhoetODfhS1tdBdqXsY6sB0Eg/iX8RweN+qGr6TbazYm2uN6lWEkU0Z2yQyD7roezD/EHIJFUdG1a5F22i6zsTVIk3pIo2peRjjzEHY9Ny/wk+hBIBu0UUUAFFFFABRRRQAUUUUAFFFFABWdrWkRazYiBpXgmikE1tcR/eglX7rj16kEHggkHg1o0UAY2h6xLeNNp+oxpBq9oB9oiX7sin7sseeqNg+4OQeRWzWRrmjPqKw3dlMttqtoS1rcEZAz1Rx3RsAEfQjkA1Jomspq9tIHha2vrdvKu7RzloZMZxnupHKt0IINAGnRRRQAUUUUAc1401bVNGstOu9KiE7/AG+NJ7fAzNEVfKKT0Ynbj3wDwTW7YX1tqdhBfWkolt50EkbjuD/L6Vj+NPk8O/ae9rd2tzn0CTxs3/joNQxf8U14i+zn5dJ1aUtD6W90eWT2WTlh/t7h/EKAOmooooAKKKKACiiigAooooAKKKKACiiigAooqlq2q22jae95dFioIRI4xueVzwqIO7E8AUAQ63rKaPaoVia5vLh/KtbVDhp5MdB6ADkseAATUehaPJpyz3d7Mtxql6Q93MowuQPlRB2RQSAPqTyTUOiaVc/an1rWAp1SdNixqdyWkWc+Uh7noWb+Ij0CgbtABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAVFc3MFnay3NzKkMESF5JHbCqo5JJ9KfJJHDE8srqkaKWZ2OAoHUk9hXMW0cni+6iv7lGTQYXD2du4wbxgciZx/cB5RT1+8f4QAB1jbT+Jr2HV9RieLTYGEmn2Ui4LntPKD3/uqfu9T83C9PRRQAVyfivxDfeH9b0WWNRJpbrOb9AuWCKEIkXv8g3MR3Xd1IFdZXPeIgE1jw1OQCo1Fonz/AHXt5hj/AL620Ab6OsiK6MGRhlWU5BHqKdXNaKToGqnw5KT9jdWm0pz2jH3oPqmcr/sEf3TXS0AFFFFABRRRQAUUUUAFFFFABWdrOjwazaLFI7wzxP5tvcxcSQSDoyn9CDwQSDkE1o0UAYmi6xPNcSaTqqJDq9uu5gnCXEfQSx5/hPcdVPB7E7dZmtaNHq9vHtla2vbdvMtbuMfPA/qPUHoVPBHFQ6JrMl7JLp+oxLbavagGeFT8singSxk9UP5g5B5FAGzRRRQAUUUUAFFFFABRRRQAUUUUAFYet6Tctcx6zpGxdVt127GO1LqLOTE5/Mq38J9iwO5RQBR0jVrbWbBbu23ryUkikG14ZBwyOOzA9f8ACr1c7q9hdabftr+kQtLMQBfWaf8AL3GOjL/01UdD/EPlPYrs2F/a6pYQ3tlMstvMu5HHf8OxHQg8gjFAFmiiigDH8W2zXvg7WrZPvyWMyoR2bYcH88VLNbWviTw6sdwCbe9gV8ocMuQGVlPZgcEHsQDWi6LIjIwyrAgj1FYfgl2bwToyOcvDapA5PdoxsP6qaAH+HdSuLiKfTtSK/wBq2DCO4IGBKp+5Mo9HAz7MGHatusDxFZ3EEsGvadE0l9YqRJCnW5tzy8fuwxuX/aGOjGtiyvLfULKC8tJVlt50Ekci9GUjINAE9FFFABRRRQAUUUUAFFFFABRRTJZY4IXmmkWOKNSzu5wFA5JJ7CgCK+vrbTLGa9vJlht4V3SO3QD+p9u9Yuk2NzqmoJr+rwtE6giwsn/5dUPBdh/z1Ydf7o+UfxEw2MUnim+h1e7jZNJgbfp1s4wZm7XDg/8Ajinp948kbeooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigDlGz4v1e7tJvk0bTbjyprc/eu5lwcOO0QyCAfv9fu43dXWFrOk3K3i61owRdUiQJJEx2peRDny3PYjJ2t/CT6Eir+k6tbazYLdWxcYYpJFINskMg+8jjswPb+lAF6iiigArn/ABf+70uyuf8Anhqdm/0BnRG/8dY10FYHjgEeCNYlAybe2a4H1j+f/wBloAua7pP9sacYUl8i7icTWtwBkwzL91vcdiO4JHejQdW/tfTvMli8i8hcwXdvnPkzL95fcdCD3Ug960wQQCDkGua1tToOpr4khB+ylRDqiD/nkPuzY9Y8nPqhP90UAdLRSKwZQykFSMgjoaWgAooooAKKKKACiiigAooooAKytb0UapHFNBMbXUrUl7S7VcmNj1Uj+JG6Mvf2IBGrXM393ceIr6bR9LmeGyhbZqF/GcEHvBEf7/8AeYfdHA+Y/KAaHh3WTremvNJCIriCZ7adUbcnmIcNsb+Jc9D+BwQQNaobS0t7C0itLSFIbeFAkcaDCqo6AVNQAUUUUAFFFFABRRRQAUUUUAFFFFABXMX8Mvhi/m1myjeTTJ236laxjJjPe4jA7/31HUfMOQQ3T0UAMhmiuYI54JEkikUOjocqykZBB7in1yrf8UZeGQceHLiTLjtp8jH7w9IWJ5/uE5+6Tt6rqMigArn/AAh+706/tP8An21O7THoGmaRR/3y4roK5/Qv3PiLxNbdmu4rlR6B4I1/9CjagDoK5m2/4prxB9hPy6TqkjPantBcnLPH7K/Lr/tbx3UV01UtW0y31jTJ7G53BJQMOhw0bA5V1PZlIBB9QKALtFY3h7U7i8gmstR2jVbBhFdBRgPxlZVH91xyPQ5HVTWzQAVj6d4lsNUfVBaid49Nu/sU0ix7g0oClgoXJIG8AkgY57DNHiXUp9P0krZYOoXbra2YIyPNfoxHcKMufZTWX4J02DSJ/Een2+fKt9RiQFjlm/0K1yxPck5JPck0AdQk8MsksccqO8RCyKrAlCQCAR2OCD9DUlRzW8NxH5c8SSpuV9rqCNykMp57ggEehAqNrXlzHPPG0kqysQ+7ONoKgNkKpC4IXHUkYJzQBYoqv/piE4MEoaUYBzHsj4z/AHtzdfQH260C6IIElvMhaUxL8u/PUhjtzhTjqcUAWK5X/kc7zPXw5byfhqEin9YVI/4GR/dHzF7cnxXfTaRaSlNIgkMWoXKNgzuOtvGf/Q2HQfKOSdvTxRRwQpDEixxooVEQYCgcAAdhQA+iiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACuf1bTLqzv213RY915tAu7TO1b2MdB6CRR91u/3TxgjoKKAKmmana6vYR3tnJvifI5BDKwOCrA8qwOQQeQRVuuc1OwutIv5Nd0eFpfMwdQsE/5eVAx5iDtKB/30Bg8hSNqwv7XVLGG9splmt5l3I69/wDAjoQeQeKALNUtYtft2iX9njPn20kWPXcpH9au0UAZnhy6+3eGNJvM58+yhlz67kB/rWkyq6FHUMrDBBGQRWB4I+Xwdp0H/PsrWv08p2jx/wCO10FAHNaGzaFqTeGp2P2fYZtLkY/ehH3oc+seRj1Qr6GulrL17STq2nhIZRBfQOJ7O4xnypV6E+qnJVh3ViO9O0PVhrGmidojBcxsYbq3JyYZV4ZT6+oPcEHvQBpUUUUAFFFFABRRRQAUUVz2q6ldajfvoWiy+XOoH229ABFoh5wOxlYdB/CPmPYMAM1K/utav5dD0eZoUiO3UL9P+WAIz5UZ/wCepHf+AHJ5IFblhYWumWMNlZQrDbwrtRF6Af1PcnqTTdN0210mwisrKLy4IxwMkkknJYk8lickk8kkmrVABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQA2SNJonilRXjcFWVhkMD1BHcVzNlI/hO+h0q5dm0a4cJYXDnP2dz0gc+n9xj/unnbnqKgvbK21Gyms7yFJreZCkkbjhgaAJ65+D9x8Qb5e11pkDge8ckoJ/KRfypmlXtzo+oR6Dq0zzB8/2deyHm4UDPluf+eqj/voDd1DYPEZfSr+y8SKC8FnHJBeoByLeQoTIP9worH/Z398UAdHRUFze2tnZteXE8cdsi7mmZvkVfUnoB79Kfb3EF3Ak9tNHNC4yskbBlYexHWgDC1BRb+OtFuFG03Nrc2shH8eNki59cbXx6bj610Nc/wCI/wB3qnhq5/556nsb6PBMn/oTL+VW/EWpy6Vo8klqqvfTMtvaRt0eZzhc+wPJ9ACe1AFGz/4nXi25vzzZ6SGtLb0adsGZ/wDgI2oPfzBT/D3/ACHPFn/YVj/9IrWtLR9Mi0bSLbT4mZxCmGkb70jHlnPuzEk+5NZvh7/kOeLP+wrH/wCkVrQB0FFFFABXO6tfXOq6g+gaTM0TKAdQvU62yEZCIf8Anqw6f3Qdx/hBl1rVbk3SaLo5U6pOm95WG5LOLOPNcdz1Cr/ER6AkaGk6VbaNp6WdqG2glnkc7nlcnLO57sTyTQA600uxsbS1tbe1iSG0/wBQu3PlnBGQT3wWBPU5PqaelosRj8qWVFSR5Cu/cHLZJBJycZbIAIxgduKsUUAV41u0MSu8Uoy3mvgqf9nA5+h5oiuXYwrLbyxySKzEfeCYxwWHGeePxqxRQBDBdQXEcMkUqssyeZHzyy8cgenI/MVNTGijZw7IpcKVDY5AOMjP4D8hUK2axKiwSSRrHD5MaZyqjjBwepGKALNFVj9riU48ucLDwD8rPIPfoAaJLxYFlaeKREhhEruF3LjnIGOSRjpjuKALNFMEsbStEJFMiqGZAeQDnBI9Dg/kafQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAVzN/aXHh2+m1nTIXmspm36jYxjJJ7zxD++P4lH3hyPmHPTUUAQ2l3b31pFd2syTW8yB45EOVZT0INTVy93DL4Tu5dSs43k0WZzJfWsYybdjyZ4wO3d1H+8OchulhmiuII54JEkikUOjocqynkEHuKAMLwl+7tNTtv+eGq3fHpvlMv/tSugrm4XOheLLiGb/jy1uUSwy/887lY1Voz/vJGGX3Dj0rpKACuet1Ft8Qb5VG1bzToZWA6M8bupb67XQZ9FHpXQ1z99+68eaLL2lsbuA+53QuP0VvzoA6CiiigAooooAKKKwtZ1a5N2ui6NsfVJU3vIw3JZxnjzHHc9dq/wARHoCQAN1fVLq4vjoeiuBflQ1zcldyWUZ6MR0Ln+FfxPA50tK0u10ewSztEYIpLMztueRycs7MeWYnkk03SNIttGsRbW+9yzGSWaQ7pJpD953Pdj/gBgACr9ABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFQ3d5bWFpLd3c8cFvEpaSSRsKo9Sa54f2r4p+bdcaTordAMx3d0PXPWFD/wB9n/Y7gC+JNS0i9im0RobnUb7hhbWAzLAw5Vy+QsRBwQzEdO9ZOm3fivULo6FrN9aaXdJCHDRW4lkvI+hdWY+WCMgMu1sE56EZ7LT9NstJtFtLC1itoFOQka4BJ6k+pPcnk1X1rR4tYtFTzWt7qF/NtbqMfPBIOjD1HJBB4IJB60AcRbeDbSOe58Kanf6lNG9uW0yaa6cp5OArIIwRGXjJ4yuNrLxwRXZ+HfDWk+FNKTTdHtFt7dTubByzt3ZmPJP+elY7vceIrGSxnEdj4n0p1njIyUEgyFkTu0Tjcp74LKeRW9omrJrOlx3axtDLkxzwOfmhlU4dD7gg/Xgjg0AZ/jH5NGt7jvb6jZSZ9F+0Rhv/AB0tTIgdY8aTSuP9F0QCGNT3uZEDM3/AYnUA/wDTR/SpPG6s3gfW3UZeKzkmUerIN4/VRTfDzK2veKCpyr30MgPqDawD+lAHQ1z/AIe/5Dniz/sKx/8ApFa1vsyojO7BVUZJJwAK5/wiHubK91l1KDWLs3kaEYxFsSKM/UxxIx9CxFAHQ1j65rMlh5NlYRLcatd5FtAxwoA+9I5HRFyMnvwByRU2taxHo9qjCJri7nfyrW1jPzzyHoo9B1JJ4ABJ6VDoejyWHnX1/Ktxq13g3M6j5VA+7GgPRFycDuSSeSaAJdE0aPR7V1MrXF5O/m3V1IMPPIepPoBwAo4AAArToooAKKKKACiiigAooooAKKKKAIpraC5ikjmiR0lXa4I+8PQ/maZJbMxmaK4likkCjcDuC49FOQM9+KsUUAV3N2hlZFhlBZfLQkoQvG7J5yepHA7D3oa7EZk82GZFWVIlYJu37tuCAuTty2CSBjBJ4GasUUARxzwzNIsUqO0TbJArAlGwDg+hwQce4qSo5beGcKJokkCuJFDqDhgcgj3HrUf2XacxTzx5l81vn37vVfmzhfZce2KALFFVx9sQqCYJQZTuPMeyPnGB825h8o7A8njpQt0cxiW3mjaSV41BXd03YYlchVIXIyR1AOCcUAWKKihuIbiMPDKkiFmUFWyCQSCPwII/CpaACiiigAooooAKKKKACuVlVvBlw9xEpPhyZy00SjP9nuTy6j/nkTyw/hPI4zjqqQgMpVgCCMEHvQBR1XTbbXNJltJXPlygNHLGfmjYEMjqfUEAg+oqt4e1Se+tprTUAqarYv5N2qjAY4ysij+64+YenI6g1mKT4LuBGxJ8NythGP8AzDnJ+6f+mJPQ/wAB4+7jba8Q281jcQ+I7CNpJ7RNl1Cgybi2zlgB3Zfvr/wJf4qAOhrn/EP7rW/DFx2GoPEx/wBl7eb/ANmC1neI4fF2rx2V14S1vTIdOlCSOJLcs8kZwflfdggjoBsP+0OoqeKbXxVFp1nczazoziDUbQjZpMqlS0yx5JNycgbySO4BGR1oA7yiuf8Asfi8dNd0Q/72jy//ACTRt8YQ8+bod3/s+VNb/ruk/lQB0FFc8fEOo2POseH7qKMfeuLBxdxr+AAk/wDHKbd+LLW5ggh8Py2+pahd5ECI+UjA4Z5SOVVc8jqThRyaALGtaxPBcR6TpSJNq9wu5Q/KW8fQyyY/hHYdWPA7kWtG0eDRrRoo3eaeV/NuLmXmSeQ9WY/oAOAAAMAU3RdGj0i3kLStc3tw3mXV3IPnmf19lHQKOAOK06ACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKgvb2206ymvLyZIbeFS8kjnhQKnrl4F/4SrWPtb86Lp0xFsna6uFODKfVEOQvqwLdlNADrHT7nxBdxavrULRW0bB7DTZB/q/SWUd5O4Xon+9kjpqKKACiiigDI1zRn1AQ3ljKttqtplrW4IyOfvRuB1RsAEfQjkCudttZS01RtZ8prWKeRLTW7NzzaXGAI5j6qRhS3QqUboprua53xJoL3u7ULCKJ74QmGa3kOI72A53Qyfmdrfwk+hYEA2NStft2lXloRnz4Hi/76Uj+tcl4AnGoQX0zFv9JtbGUkMQfmtUzyOQeKs+B9eS9tpNIllle4sx+6acYleEHaA4/56IRsf3Abo4rN+Gn7uXVbb/n3EUGPTy2li/8AadAGVrvg7VLDVls9L8Sarf8A9rF0OnalfzPHFbquZcPuOM5VAxViPMHfmutfxpYaXb+Vq9ldaZdKAsVq8e4Tt0CQuuVcngBQQ3qBTdNvbZ7jV/Ft9MsVkgNtayP0W3iJ3OP9+Td06hUpbTRj4lmOq+IbJWgZStnptwgYQRkYLyKeDKw6/wB0fKOdxIBc0XSrlrt9b1gL/akybEiU7ks4jz5SnuehZv4iPQADdrmTZ6p4Z+fTTNqelD71jI+6eAf9MXb74H9xjn0botbem6nZ6vZLd2M6zQsSuQCCrDqrA8qw6EHBFAFuiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKAGPDFJJHI8aM8ZJRioJXIwcHtxUUdosJhEUsyxxBhsL7g2fUnJOO3NWKKAK8Qu08hJXilAjPmyAFSX4xheRj72eeOOtJHdtti8+CSF3hMrgjcseMZUsOM8/jg1ZooAjiuIZ1Ro5FYSIJFweSp6HHpUlRyW8Mu4vGpLIYy2MHaeoz1qJrVgr+RPJExh8qP+JUIzhsHqefxxQBZoqvK13GJmjjjmCxAxJu2s8nOQT0APy4/GiW8SAzGVJVjiVWMmzIbOeBjkkY547igCxRTFljeR41kUumN6g5K56ZHan0ANkjjmieKVFeN1KsjDIYHqCO4rmLaSTwhdRWFy7PoMzhLO4c5NmxOBC5/uE8Ix6fdP8JPU1Fc20F5ay21zEk0EqFJI3XKsp4II9KAOesP+Kb13+yW+XTNQdpbA9oZeWkg9geXX/gY6AVN44GPBOrzDrb25uR/2z/ef+y1lXdmbOEeG9WuJTp1wyjS9TLZkt5Qcxxux/jUgFGP3sbTz96/DdTa/4W1XTL5FTU4oZLO8iXpvKHDr/sOCGHscdQaAOmByMiis3w9dfbvDWlXmc+fZwy59dyA/1put60ukxRRxQm61C5YpaWiHDSt3JP8ACo6sx4A98AgDNb1o6aIbW0hF1ql1lbW23Yzjq7n+FFyMt9AMkgHKh8Fm2D6jb6lLF4ilbzJ9QUfJM2PuPFnBjGAAvUDkMCSTq6JoraeZr2+mF1q11g3NwBgADpGg/hjXJwPqTkkmtegDG0fW3vJ5NO1GAWerQLukg3ZSROnmRN/EhP4g8EDvs1m6zo0WrwR/vHt7uBvMtbuLG+B/UeoPQqeCODVfR9ZlnuH0vVY0t9XhXcyLnZOnTzYieq+o6qTg9iQDaooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKAMDxNczzC20KxlaO81IsrSocNBAuPNkHocEKD/AHnU9jWza2sFjaQ2lrEsVvCgjjjUYCqBgAfhVaDS0i1u71V5GkmnjSFARxFGuTtH1ZiSe/HoKv0AFFFFABRRRQAUUUUAcR4x8O30F9D4r8OR7tWszvntRwLyPGGX/f28Z74XqVXHG+HPEtvdSeJxpN0I31KaNLeVjtMIlkuZZJD6GNC7HPdcV7TXBXfwt0yfxrc+IIZlhhuYv9IsRETHNNuJ3v8AMMqflyoA3Y5OGYEAvaLp6a19huTAYPD9gqDSrRhjzdows7g9gB8in/ePJG3r6r7LzHE8H+qwP3J/1n97733f9nr/ALVBS85xPB/qsD9yf9Z/e+993/Z6/wC1QBYrC1PQZftjatosqWeqEDzAwPk3YHRZVH5Bx8y+4yp1Sl5zieAfusDMJ4k/vfe+7/s9f9qgpefNieAfusDMJOJP733uV6fL1/2qAKWj65Fqplt5IXtNRt8fabKUjfHnoQejIezDg+xBA1axNX0KbVHhuY7uO1v7aP8A0a6ihO9JP4s/Nho24BjPpnOcERaTq99fTXOn3n2ez1W3hG+3MbMrMcgTI24b4jxxwQQQSDQB0FFV2S8O/ZPAMxYTMJOJOfmPzcr0+Xg8H5ueB0vDv2TwDMWEzCTiTn5j83K9Pl4PB+bngAsUVXdLw+ZsngXMWE3Qk7ZOfmPzDK9Pl4PB+bngdLw+Z5c8C5ixHuhJ2yc/MfmGV6fLweD83PABYoqvIl4fN8ueBcxYj3Qk7ZOfmPzDK9Pl4PB+bngkS8Pm+XPAuYsR7oSdsnPzH5hlfu/LweD83PABYoqvIl4fN8qeBcxYi3QltsnPzN8w3L935Rg8H5ueCRLw+d5U8C5ixFuhLbZOfmb5huX7vyjB4Pzc8AFiiq8qXh87yp4EzFiHfCW2Sc/M3zDcv3flGDwfm54JUvD5/kzwJmICHfCW2Sc/M2GG5fu/KNp4Pzc8AFiiq8qXh8/yZ4E3RAQ74S2yT5ss2GG5fu/KNp4PzcjBMl432jyZ4E3RAQb4S2yT5ss2GG5eV+UbTwfm5GACxRVeZLxvtHkTwJuiAg3wltknzZZsMNy8r8o2ng/NyMEyXjfaPJngTdEBBvhLbJPmyzYYbl+78o2ng88jABYoqvMl432jyZ4E3RAQb4S2yTnLNhhuX7vyjaeDzzwTJeN5/kzwJujAh3wltj85ZsMNy/d4G08HnngAsUVXlS8bz/JngTdGBDvhLbH5yWww3D7vA29Dyc8EqXh8/wAmeBN0YEO+EtsfnJbDDcPu8Db0PJzwAWKKrypeHz/JngTcgEO+EtsfnJbDDcPu8Db0PJzwSpeHz/JngTcgEO+EtsbnJbDDcOnA29Dyc8AFiiq8qXh8/wAmeBNyAQ74S2xuclsMNw6cDbjB5OeCVLw+f5U8CbkAh3wltjc5LfMNw6cDbjB5OeACxRVeVLw+f5U8CZUCHfCW2Nzkt8w3DpwNuMHk54JUvD5/lTwLlQId8JbY3OS3zDcOnA249TQA+a2guEZJYkdXILAjrg5GfpimPbNmRoriWNpJEcnO4ADGVAOQAQMHHqT1olS8Pn+VPAuVHk74S2w9y3zDcOnAxj1NEiXh87yp4FyB5O6EtsPct8w3dsYxj3oAGN2hchYZQZVCLkptj+UMSecsPmI4GeBx1oN2FJ8yGaMeaIlOzduzjDfLnC84ycdKJEvD53lTwLkDyd0JbYe+75huz2xjHvRIl4fO8qeBcgeVuhLbD33fMN2e2MY96AGXMFhrNjc2c4hurZ90M0eQwyOoOOhH5g1wl/PfeEdatbm6aW5Ea+SlyeWvbUZYxP6zxcup/jXeByTXdXNpNOzHdakoyvbGS3L+U4BBY/MMnBIGNuM96o6poDapY3FlJdAW0knmKjoznJyTli27hiGXYUKlVwcDFAGJ4b1+1034eaK0IN5K0f2Syt4CC1wyEoAvbGFyW6AAk1t6Jo0trNLqepyJcaxcqBLIv3Ik6iKPPRB+bHk9gKfhTwZa+F4yTcNeXA3pFK6BRFGzlyiKOFyxyxHU+gCqOmoAKKyPFOsP4e8LanrEcKzPZ27zCNjgMQM4zUi69p8WnQXV/fWlmZLdLhxNOqBVOOeSOMnGaANOs7WNGttZt0SVpIZ4W8y3uYTtkgf+8p/Qg5BHBBFI/iHRIxal9Y09Rd/8exNyg87t8nPzfhUuo6xpmkRpJqeo2lkjnCtczrGGPsWIzQBHpDasIZINXjgaWJgqXMBwlwv97YeUPqMkehPbRqsNQsjYfbxeW/2Pbv8AtHmr5e313Zxj3qKy1nS9T2/YNSs7repZfInWTIBAJGD0BI/MUAXqKoRa3pM+ovp0OqWUl8md1slwhlXHXKg5FWrq5hsrSa6uZBHBBG0kjt0VVGST+AoAlorg7TxN401zT11nRfD+mrpki+Zbw3126XNzH1DAKpVNw6Ak9a0pPGaN4LtdcgsZku71kt7axuAUc3DNsCN7Bskn+6CaAOqornvFniG48OaHDNBbR3mp3NxFaWtvu2LLM5xjPOABuP0FT6Brn/CS+E7TWLFUjlurfcscmSI5RkFWxzwwIP0oA2qKyvDmtp4g0SG+ERhm3NFcQE5MMyMVdD9GB+owe9atABRRRQAUUUUAFFFeM+EJrTWfCdrqWs/EnU7LUJDKZYv7UhjEe2RlHyspI+UA80AezUV5lpHjPVo/hhcalNML2+N6+n6XdPHsF5ukEcMpUcY5yfUKa3fFt7d+GvAsdlZXc0+rXJi06znlbdI88h27yT3HzP8AhQB2FFcl4D1O8ms9R0TVLl7jU9Gu3tpZZPvzRn5opD/vIR+INTeEtRuPtms+H72Z57nSLhQk0jbmkt5F3xFierAblJ77M96AOnooooAKKKKAEZgqlmIAAySe1ebDxv4k/wCEc/4TT7Np3/COeZu+x7H+1fZt+3zd+7bux823b075r0W5h+0Ws0OceYjJn0yMV42dcs/+FK/8Ih50f/CS+T/ZP9l7v3/nbtv3Ou3HzbumO9AHtCsHUMpBUjII70tRW0P2e0hgzny0VM+uBipaACiqianZS6pNpqXCNewxrLJCPvKjEgE+xwaZFrOnT6vPpUN3HJf26CSaFDkxqem7sM+h5oAvVla3oo1SOKaCY2upWpL2l0oyY2PUEfxI3Rl7j0IBGrRQBlaHrB1SKaG5hFtqVowju7bdnY3ZlP8AEjDlW7jjgggatZt5o8dzqtnqcUrW95b/ACM6DPnRHrG47jPI7gjI6kHSoAKKqz6jZ21/a2M1wiXV2HMER6ybAC2PoCKTUNTstKgSe+uEgieRYlZ+hdjhR9SaALdFUdU1jTtFgjm1G7jt0lkWKPeeXc9FUDkk+gqWa/tYLy1tJZgtxdbvJjwSW2jLH2AGOT6gdSKALNFULjWtNtNWtNKuL2GO/uwzW8DN80gUZOB+Bqa5v7W0uLWC4mEcl05jhDA4dwpbbnpnAJx3waALNFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFAFPVtSg0bR73U7nPkWkDzyY6lVUk49+K4uDxT4osItE1bXYNLGlatPFCYLZXE1mZf9WWYsQ4yQG4XBPFdJ4z02fV/BOt6fbKWuLiylSJR/E5U4H4nArhNU8RaZ4s8M+F9E0q6jn1O4vLNprRDmW1WJg0pkXqm3aRzjJ6UAer0UUUAcr8Sv8AkmniP/rwl/lXOW+m2Wp/E3w+t7bRXCQeFzMiSoGUP5ka5we+Gb869IuLeC7t5Le5hjmgkUq8cihlYehB4Ipq2VolylylrCs6ReSsojAZY8g7AeoXIBx04oA8aXQNIX4b/EeUadbGSHUNQWFjGCYlQ5RVP8IBJIA7k1rzXg1DxYIrOx0c6laaPbm5v9amdl8twWxHH09SzZHUA16X/Zth9nuLf7FbeRcszzxeUu2Vm+8WGMMT3z1qtfeHND1SSCS/0bT7p7cBYWntkcxgdAuRwPagDxbRpbaTwvpn26W1k8PL4unF20SbLbYdxi+UkhYt5U4JIGRmt7Un00fEvV38Jm2OpDwpdE/YsY87enl/d439PfG32rvtd0C4n0todBaxspmuBPPFLaq0N2MYZJQBnDDHzDn5RWb4Y8IXWm6/LrWoLpdvKLT7Hb2elQGOGKMuHZjnBLMQOwwB3oA81trRn8AaBJHqnhazj8y2a1uLa1la9FxuXj5WJMhOQ3Hc17F4v02fWPButaba/wDHxc2UsUQz1YoQB+J4qaLw3oUGqHVIdG0+PUGJJuktkEhJ6ndjOa1KAON8J+MtAfwPYXM2pWlp9jtUiuoZpQj27ooVlZTyCCD25rGvNdbxHqPw+1WSymtLG51Kdkjn6kiGQQsfTdyR7Gu0uvCvh6+vxf3ehaZcXmc+fLaoz59ckZpnifQjr2jfZ4JVgvbeVLqymYZEU0ZyhPt2PsTQBx/iB9b8QfE63g0FNPlXw3B5swvndY/tE6kKPkBJKoMj03U7wDJqWgeLdb8L60tpHLdk6vaLaMzRbXbEqqWAPDAHH+0a7+0tIbfzJUtbeC4uCHuDCoG98YyTgFvTJpt3ZxyP9sitLWTUYY3W2lmXlSR03YJVScZxQBy3gMn+1vGYj/49hrkmz03+VHv/APHv1zXaVkeGdDHh/Q4bIy+dcFmmuZ8YM0zsWd/xYnHtgVr0AFFFFABRRRQAV5d4S+HGm6n8LrTTtb0aO01NhNm4aAJcwv5rlHDY3ZA2keo9q9RooA8l1S51s+BLCTxBZyRXnhvWrSS6mEe2O5hjkA85O2NpyfTB4FbviPQLzxd48sbeWTULHSdJtTcpd2reWZLlztAViDnagPI/vYruLm2hvbWa1uYllgmQxyRsMhlIwQfqKj0+yTTdOtrGKSV47eNYkaVtzFQMDJ7nHegDg7TwzfeEfiJY6hZT6rqljq0L2uoy3UnnNCyYaJyQBx95eema0fDatdfEfxhqMfNsn2SxVx0aSNGZ/wAvMUfnXaVR0nSbXRbAWdoG2b2kd3O55HZizOx7kkk0AXqKKKACiiigAqP7PD5/n+TH52NvmbRux6Z61JRQAUUUUAeP+JtQ8R2fxO8QQ+FtON1qc+jQbZWICQKpck89WPAUdyeeAa2tF1fQ/DPwlu/EmiI9ziB7id7hszTXPRvOPXdu4PoOnGK6u28Oi38ZX/iH7SWN3aRW3kbMbdhY7t2ec7umKyn8AWjanrrLdMuka5CVvdOEfy+cRgzI2flYjrwcnn0oA5ew8Y6va32kStrl1rJu7iOG9sToskCQK/BeOTywcISPvE5GelaGn6n4q1O68Tal/bkdvp2jXt3bRWa2aMZgiZUs55GCVxjrg568a9l4R11Z9Oj1HxdcXWn6fIskcMNsIJJiowolkDHeB3AADd81oad4WWw0/wAQWgvC/wDa93cXJby8eV5qhduM84x14zQBxcOt+L7Twx4b8V3muxXEV/LaJcacLNFj8uYquQ4+bf8AMD1xntilv/Gl7qPiPWraLxDcaLb6bcG0gjt9Ia7MzqoLNI2xgBk4CqQcDOa6qfwWs/gzR/Dv28gaa1oRP5X+s8gqfu54zt9TjPeornwhqltq+o33h3xD/ZaakwluoJbNbhfNwFMkeWXaxAGc5BI6UAc7Ya1deIPEvw61K+tTa3csOpLNEUZMMqqpIDcgHGRnsRWn8X5zbeDra4EUkxi1S0cRxjLPiQHAHqela1t4NW2v/DdyNTupzosVwm65JkkuDKoBZnJ4wRnoeuOMVd8U+HR4m023szcm38m7hutwTdny3DbcZHXGM0AcX4Ukn1X4iXkvjG1Nv4gghWbSrNnDwwWzAZMZ6NIDlXbrxxxW7oEp1P4j+KbyXn+z1t9Pth/cUp5sn5sy/wDfArQ8VeFV8RfYLq3vG0/VdOnE1pepHvKdmUrkblYcEZrJ/s+703xxrUEU5t18R2Svb3ax5EN1EhRhjPUptcAnnY1AHnXiHxFpWq6h4m8QDUUTVtOu4U0WMoxytsSWwQMYkZpB19K9I8WXkHiD4U3Wt6fJtKWQ1S0k7xvGBKv0IK4P4iuh8OaFb+G/Ddhotud8VpCI95GN56sxHqSSfxrjNT8NT6B4DuPB+nXbXB1i8ktrJfKx9lglYtIDycqieYc8ZyBjkUAd7pl4NR0qzvQu0XECTY9Nyg/1q1UVtbx2lrDbQjbFCixoPQAYFS0AFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFRpbwxyvKkMayP8AfdVALfU96kooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigD/9k=)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IgOdYRVDsSO3"
      },
      "source": [
        "**Column Space, Row Space, Kernel**\n",
        "\n",
        "*Column space* (or range) of A is the set of all images of applying $A$ to all vectors of the domain $V$\n",
        "\n",
        "$C(A)=\\{w \\in W \\& w=Av\\ \\forall\\ v \\in V\\}$\n",
        "\n",
        "*Kernel* of A is the set of vectors in $V$ which image to 0 under A\n",
        "\n",
        "$K(A)= \\{v \\in V\\ \\& \\ Av=0\\}$\n",
        "\n",
        "*Row space* of A is\n",
        "$R(A) = \\{v \\in V\\ \\&\\  v^T=w^TA\\ or\\ v=A^T w\\  \\forall w\\in W\\}$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0uur0cNUY5iJ"
      },
      "source": [
        "---\n",
        "**Q1**\n",
        "a) For a $mxn$ real matrix, the number of multiplications and additions to obtain a matrix vector multiply $Tv$ where $v \\in V_n$ a real vector space, is:\n",
        "\n",
        "Ans:\n",
        "\n",
        "Number of multiplications = $mn$\n",
        "Number of additions = $m(n-1)$\n",
        "\n",
        "b) For a $mxn$ complex matrix, the  number of multiplications and additions to obtain a matrix vector multiply $Tv$ where $v \\in V_n$ a complex vector space, is:\n",
        "\n",
        "Ans:\n",
        "Each row $i$ has $\\sum_{j=1}^n T_{ij}*v_j$. Each term within the summation requires multiplying two complex numbers => 4 multiplications and 2 additions. Also summation has $n-1$ complex additions => $2n-2$ real additions.\n",
        "\n",
        "So Number of multiplications = $m4n$\n",
        "\n",
        "Number of additions = $m(2n+2n-2) = m(4n-2)$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s1T9jGeBbMeD"
      },
      "source": [
        "---\n",
        "We will use the popular numerical linear algebra package numpy\n",
        "https://numpy.org/doc/stable/user/index.html\n",
        "The above website has documentation, tutorials etc.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "fJZykwE8aNrm"
      },
      "outputs": [],
      "source": [
        "#import the package for numerical linear algebra computations in Python\n",
        "import numpy as np"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lnc-7lxwaWcU",
        "outputId": "fbda72e7-cc2a-4416-f96f-9f5cbddda210"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "T=\n",
            "[[2 3 4]\n",
            " [5 6 7]], v=[1 2 3] Tv = [20 38]\n"
          ]
        }
      ],
      "source": [
        "T = np.array([[2, 3, 4],[5,6,7]])\n",
        "v = np.array([1,2,3])\n",
        "print(f\"T=\\n{T}, v={v} Tv = {T@v}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "p-KaUEqAb5YL"
      },
      "source": [
        "Note that $v$ and $Tv$ are column vectors - but printing makes them appear as row vectors\n",
        "\n",
        "---"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KyTagQwKOlDD"
      },
      "source": [
        "**Matrix-Matrix Multiplication**\n",
        "\n",
        "Let $f:Z → W$ and $g:V → Z$ be two linear transforms between vector spaces $V, W, Z$ of dimensions $N,M,K$ respectively.\n",
        "\n",
        "Let the corresponding matrices be $A_f$ of size $M\\times K$ and $B_g$ of size $K \\times N$ respectively\n",
        "\n",
        "\n",
        "Then we can define $f\\circ g :V → W$ as $(f∘g) (v) = f(g(v))$\n",
        "\n",
        "and\n",
        "\n",
        "$C_{f\\circ g} = A_fB_g$ of size $M \\times N$\n",
        "\n",
        "We will drop the subscript notation.\n",
        "\n",
        "Let $A = [a_{ij}]$ be a $M \\times K$ matrix and $B=[b_{jk}]$ be a $K \\times N$ matrix.\n",
        "\n",
        "then by using considering the calculation of the linear transforms on the respective basis vectors of $V, W, Z$, we will find that\n",
        "\n",
        "$C=[c_{ij}]$ where $c_{ij} = \\sum_{k=1}^K a_{ik}b_{kj}$ is a $M \\times N$ matrix\n",
        "\n",
        "\n",
        "We can rewrite $B$ as $B = \\begin{bmatrix}b_{:1} & b_{:2} & .. & b_{:n}\\end{bmatrix}$ i,e as an array of $n$ column vectors.\n",
        "\n",
        "Then we can also represent  $AB = \\begin{bmatrix} Ab_{:1} & Ab_{:2} & ... Ab_{:n}\\end{bmatrix}$ which has $m$ rows and $n$ columns.\n",
        "\n",
        "i.e each column $k$ of the product matrix is derived by performing a matrix vector multiply of $A$ with the $k^{th}$ column of $B$. Note that for this to be well defined, the number of columns of $A$ need to be equal to number of rows of $B$.\n",
        "\n",
        "\n",
        "Example:\n",
        "Let $A \\in \\Re^{mxn}$\n",
        "\n",
        "$AI_n = I_mA = A$\n",
        "\n",
        "where $I_m$ and $I_n$ and $mxm$ and $nxn$ identity matrices"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "SZ9WdqZ7kdC_",
        "outputId": "eab2cd99-f543-4d75-aeb2-f581ca5153ec"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "4x4 identity matrix = \n",
            "[[1. 0. 0. 0.]\n",
            " [0. 1. 0. 0.]\n",
            " [0. 0. 1. 0.]\n",
            " [0. 0. 0. 1.]]\n",
            "4x4 diagonal matrix = \n",
            "[[1 0 0 0]\n",
            " [0 2 0 0]\n",
            " [0 0 3 0]\n",
            " [0 0 0 4]]\n"
          ]
        }
      ],
      "source": [
        "# 4x4 identity matrix\n",
        "print (f\"4x4 identity matrix = \\n{np.eye(4)}\")\n",
        "print(f\"4x4 diagonal matrix = \\n{np.diag([1,2,3,4])}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L0_bnIoOD3Xr"
      },
      "source": [
        "**Rank of a Matrix**\n",
        "\n",
        "Equivalent Definitions:\n",
        "\n",
        "Largest number of independent columns (column rank)\n",
        "\n",
        "Dimension of Column space\n",
        "\n",
        "Largest numnber of independent rows (row rank)\n",
        "\n",
        "Dimension of Row Space\n",
        "\n",
        "For a matrix of $A$ size $m \\times n$, rank($A$) $\\leq\\ min(m,n)$\n",
        "\n",
        "---"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgFdDDX4D_8j"
      },
      "source": [
        "*Notation*\n",
        "\n",
        "$d(V)$: Dimension of vector space\n",
        "\n",
        "$r_c(A)$: Column rank of A\n",
        "\n",
        "$r_r(A)$: Row rank of A\n",
        "\n",
        "$r(A)$: rank of A\n",
        "\n",
        "$C(A)$: Column space of A\n",
        "\n",
        "$R(A)$: Row space of A\n",
        "\n",
        "---\n",
        "\n",
        "Let B be a square $m \\times m$ matrix with column rank $m$ and let $B: V → V$ be the corresponding linear transform, where $d(V) = m$\n",
        "\n",
        "So $C(B) \\subset V$ is the columnspace of B and since it has dimension of m: hence C(B)=V\n",
        "\n",
        "---\n",
        "Lemma:\n",
        "\n",
        "If $v_1, v_2, ..., v_k$ are linearly independent, and B has a full column rank, then $Bv_1, Bv_2, ... , Bv_k$ are linearly independent.\n",
        "\n",
        "Proof:\n",
        "\n",
        "Assume otherwise\n",
        "\n",
        "let $a_1, a_2, ..., a_k$ be scalars. not all zero such that $\\sum_{i=1}^k a_iBv_i = 0$ then by linearity, $B(\\sum_{i=1}^k a_iv_i) = 0 \\implies \\sum_{i=1}^ka_iv_i =0 \\implies\\ v_1, v_2,..., v_k$ are linearly dependent.\n",
        "\n",
        "A contradiction\n",
        "\n",
        "---\n",
        "\n",
        "Lemma:\n",
        "\n",
        "$A \\subset ℜ^{m \\times n}$ and $B \\subset ℜ^{m\\times m}$ is a full column rank matrix, then column rank of $BA$ is same as column rank of A\n",
        "\n",
        "Proof:\n",
        "Let $k = r_c(A)$, the column rank of A. Let $v_1, ... v_k$ be the basis of column space of A. Then from above lemma, $Bv_1, Bv_2, ..., Bv_k$ are linearly independent and hence column rank of BA\n",
        "\n",
        "---\n",
        "Lemma: Column Rank = Row Rank\n",
        "\n",
        "Proof:\n",
        "\n",
        "Let $A_{m\\times n}=\\begin{bmatrix} a_1 & a_2 & ... & a_k & a_{k+1} & .. a_{n}\\end{bmatrix}= \\begin{bmatrix} r_1^T \\\\ r_2^T \\\\ ... \\\\ r_m^T \\end{bmatrix}$ have column and row ranks $r_c(A),r_r(A)$ respectively.\n",
        "\n",
        "We will first show that $r_c(A) \\leq r_r(A)$ and then the other way - thus proving both are equal.\n",
        "\n",
        "The column rank of $A^T$ is equal to row rank of A.\n",
        "\n",
        "Let row rank of A,  $r_r(A)=k$\n",
        "\n",
        "Let $f_1^T, f_2^T, ... f_k^T$ be the basis for rows of $A$ and let $F=\\begin{bmatrix} f_1^T \\\\ f_2^T \\\\ ...\\\\ f_k^T \\end{bmatrix}$\n",
        "\n",
        "then every row of A is a linear combination of above set.\n",
        "\n",
        "i.e. $r_i^T = \\sum_{j=1}^k c_{ij}f_j^T$\n",
        "\n",
        "In matrix form:\n",
        "\n",
        "$A = CF$ where $C$ is a $m \\times k$ matrix\n",
        "\n",
        "This also means that each column of A is a linear combination of the $k$ columns of C,\n",
        "\n",
        "Hence $r_c(A) \\leq k=r_R(A)$\n",
        "\n",
        "Applying the same argument to columns of $A^T$,\n",
        "\n",
        "$r_c(A^T)=r_r(A) \\leq r_c((A^T)^T)=r_c(A)$\n",
        "\n",
        "Hence $r_r(A) = r_c(A) = r(A)$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5rJrm1KuIyZI"
      },
      "source": [
        "**A Factorization of A**\n",
        "\n",
        "From the above - we can see that $A_{m \\times n}$ can be factorized as a product of two matrices  $C_{m \\times r}$, $F_{r \\times n}$, with $C$, $F$, $A$ all having rank $r$.\n",
        "\n",
        "\n",
        "There are other factorizations of $A$ which we will come across in subsequant lectures like $QR$, SVD etc.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ldGUNH4hlIdV"
      },
      "source": [
        "**Matrices as Vector Spaces**\n",
        "\n",
        "The set of all matrices of dimension $mxn$ forms a vector space over the scalar field (either ℜ or ℂ ) with vector addition and scalar multiplication defined as follows:\n",
        "\n",
        "Let $A = [a_{ij}]$ and B=[b_{ij}] \\in \\Re^{mxn}$.\n",
        "\n",
        "We are using a short form notation. It is understood that $i=1..m$ and $j=1..n$\n",
        "\n",
        "Then,\n",
        "\n",
        "$A + B = [a_{ij} + b_{ij}]$ is the element wise addition.\n",
        "\n",
        "$λA = [\\lambda a_{ij}]$ . The scalar multiplies with all elements\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z7Zwu3A1mcMT"
      },
      "source": [
        "---\n",
        "**Q2**\n",
        "a) What is the **0** matrix?\n",
        "\n",
        "Ans: Matrix with all elements 0\n",
        "\n",
        "b) What is the dimension of the vector space\n",
        "\n",
        "Ans: $mn$\n",
        "\n",
        "c) Give one example basis set\n",
        "\n",
        "Ans:\n",
        "$E_{ij} $ is a basis matrix with $e_{kl}=1$ for $k=i and l=j$ and 0 at all other entries."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vbfksv8yo6Ov",
        "outputId": "895b2b2f-4eba-4f82-a62d-b22a47767c74"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A=\n",
            "[[1 2 3]\n",
            " [2 3 4]\n",
            " [5 6 7]]\n",
            "B=\n",
            "[[10 11]\n",
            " [12 13]\n",
            " [14 15]]\n",
            "C=AB=\n",
            "[[ 76  82]\n",
            " [112 121]\n",
            " [220 238]]\n"
          ]
        }
      ],
      "source": [
        "A = np.array([[1,2,3], [2,3,4], [5,6,7]])\n",
        "B = np.array([[10, 11],[12,13],[14,15]])\n",
        "C = A @ B\n",
        "print(f\"A=\\n{A}\\nB=\\n{B}\\nC=AB=\\n{C}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HIIRLHPIxUJs"
      },
      "source": [
        "**Q3**\n",
        "\n",
        "Let $\\Lambda = Diag(d_1, d_2, .. d_n) = = \\begin{bmatrix} d_1 & 0 & .. & 0 \\\\ 0 & d_2 & .. & 0 \\\\ ... \\\\ 0 &0 & .. & d_n \\end{bmatrix}$ be a $nxn$ diagonal matrix. Let $A=[a_{ij}]$ be a $nxn$ matrix.\n",
        "\n",
        "a) What is $\\Lambda A$\n",
        "\n",
        "Ans:\n",
        "$\\Lambda A = \\Lambda \\begin{bmatrix} a_{1:} \\\\ a_{2:} \\\\...\\\\a_{n:}\\end{bmatrix} = \\begin{bmatrix} d_1 a_{1:} \\\\ d_2 a_{2:} \\\\...\\\\ d_n a_{n:}\\end{bmatrix}$\n",
        "\n",
        "\n",
        "b) What is $A \\Lambda $\n",
        "\n",
        "Ans:\n",
        "$ A \\Lambda = \\begin{bmatrix} a_{:1} & a_{:2} &...&a_{:n}\\end{bmatrix} \\Lambda = \\begin{bmatrix} d_1 a_{:1} & d_2 a_{:2} &..& d_n a_{:n}\\end{bmatrix}$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZXJDJNo40J43"
      },
      "source": [
        "**Q4**\n",
        "\n",
        "a) What is the rank of a $nxn$ diagonal matrix with all non-zero diagonal entries?\n",
        "\n",
        "Ans:\n",
        "$n$\n",
        "\n",
        "b) What is the rank of a $nxn$ diagonal matrix with $k$ non-zero diagonal entries?\n",
        "\n",
        "Ans:\n",
        "$k$\n",
        "\n",
        "c) What is the rank of a $nxn$ lower triangular matrix with $k$ non-zero diagonal entries?\n",
        "\n",
        "Ans:\n",
        "Atleast $k$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Zx7yV4n177DG"
      },
      "source": [
        "**Q5**\n",
        "\n",
        "Let $A$ be $mxk$ and $B$ be $kxn$ matrices.\n",
        "\n",
        "What is $Rank(AB)$?\n",
        "\n",
        "Ans:\n",
        "\n",
        "Let $D=AB$\n",
        "\n",
        "then rows of D are linear combination of rows of B, hence $rank(D) \\leq rank(B)$\n",
        "\n",
        "Similarly, columns of D are linear combination of columns of A, hence $rank(D) \\leq rank(A)$\n",
        "\n",
        "Hence $rank(D) \\leq min(rank(A), rank(B))$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nWBrDIT1vE1o",
        "outputId": "52d62782-2226-458f-ec3a-1d4871488639"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A=\n",
            "[[1 2]\n",
            " [2 4]]\n",
            "rank(A) = 1\n"
          ]
        }
      ],
      "source": [
        "A = np.array([[1,2],[2,4]])\n",
        "print(f\"A=\\n{A}\")\n",
        "print(f\"rank(A) = {np.linalg.matrix_rank(A)}\")\n",
        "\n",
        "\n",
        "# Rank of random matrices\n",
        "n = 6\n",
        "for i in range(1000):\n",
        "  # generate a random nxn matrix\n",
        "  A = np.random.rand(n,n)\n",
        "  #check if its rank is < n\n",
        "  if np.linalg.matrix_rank(A) != n:\n",
        "    print(\"Found a singular matrix\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ISDMc1U_QQD-"
      },
      "source": [
        "**Q6**\n",
        "\n",
        "What is your conclusion from above in terms of how many\n",
        "square matrices are there which are singular?\n",
        "\n",
        "Ans:\n",
        "\n",
        "The set of singular matrices seem to be very small compared to non-singular matrices (analogous to picking points from a surface of an object versus the interiors)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WO8smI60RVGA"
      },
      "source": [
        "**System of Linear Equations**\n",
        "\n",
        "Consider the following system of $m$ linear equations with $n$ unknowns $x_1, x_2, ... , x_n$ and we would like to solve it:\n",
        "\n",
        "$a_{11} x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1$\n",
        "\n",
        "$a_{21} x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2$\n",
        "\n",
        "$ ... $\n",
        "\n",
        "$a_{m1} x_1 + a_{m2}x_2 + ... + a_{mn}x_n = b_m$\n",
        "\n",
        "We can write this in a concise matrix form as ?\n",
        "\n",
        "$Ax=b$\n",
        "\n",
        "Here $x$ is the unkown vector.\n",
        "\n",
        "What can we say about the existence and uniqueness of the solutions?\n",
        "\n",
        "Another way of asking the question is: Is $b$ in the column space $C(A)$\n",
        "\n",
        "Case I:\n",
        "\n",
        "Suppose $rank(A) < m$. Note that $b$ belongs to the vector space with dimension $m$.\n",
        "\n",
        "In this case, $C(A)$ is a proper subset of the Range and hence it is possible that $b$ might fall outside the $C(A)$. So we might not be able to solve this. Note this kind of situation naturally arises when $m > n$ i.e $A$ is a tall thin matrix.\n",
        "\n",
        "All hope is not lost for this case - there is a related question - what value of $x$ will bring $Ax$ closest to $b$. Closest means smallest distance in a suitable norm. We will study this later and in the case of $L_2$ norm, this is called the least squares problem.\n",
        "\n",
        "Case II:\n",
        "\n",
        "Suppose $rank(A) = m$, in this case $C(A)$ is the same as the range space. This means that every $v$ should be linearly expressible as the linear combination of columns of $A$ and hence a solution exists. If nullspace has a dimension 0 i.e. $m=n$ then we will have a unique solution, otherwise the there will be infintely many solutions since (if $x$ is a solution, then $x+v$ is also a solution if $v \\in NullSpace(A)$ as $Av = 0$ by definition).\n",
        "\n",
        "Case III:\n",
        "\n",
        "$b = 0$. In this case, this is called a homogenous system. Clearly $x=0$ is a trivial solution. But are there other non-trivial solutions?\n",
        "\n",
        "I.e. we are equivalently asking if $dim(NullSpace(A))$ > 0.\n",
        "\n",
        "Note that $dim(NullSpace(A)) + rank(A) = n$ by Rank-Nullity Theorem.\n",
        "\n",
        "Thus if $rank(A) < n$ then we will have infinitely many non-trivial solutions which is nothing but the $NullSpace(A)$ also called as $kernel(A)$ ."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LVNawKAcXhTa"
      },
      "source": [
        "**Gassian Elimination to solve set of simultaneous systems of equations**\n",
        "\n",
        "If we can convert the above system of linear equations into the following form (such that the solution set remains the same),\n",
        "\n",
        "$a_{11} x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1$\n",
        "\n",
        "$\\ \\ \\ \\ \\ \\ \\ \\   a_{22}^{'}x_2 + ... + a_{2n}^{'}x_n = b_2^{'}$\n",
        "\n",
        "$ ... $\n",
        "\n",
        "$\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ a_{mn}^{'}x_n = b_m^{'}$\n",
        "\n",
        "\n",
        "then this is easy to solve.\n",
        "\n",
        "Start from the last equation, finding $x_n = \\frac{b_m^{'}}{a_{mn}^{'}}$, substituting it in the equation above and solving for $x_{n-1}$ and so on to get all values.\n",
        "\n",
        "Note that we can only do this if the $a_{ii}$ are all non-zero.\n",
        "\n",
        "\n",
        "Gaussian elimination is the process by which we can convert the original system into the triangular form above.\n",
        "\n",
        "It works by adding some scaled values  of rows to each other to null out certain entries. Since we are only adding scaled values of the rows, the solution set to the original system and the modified system doesnt change.\n",
        "\n",
        "The systematic way this is done is as follows:\n",
        "\n",
        "Lets null out $a_{21}$ of the second equation. We can do this by adding $-\\frac{a_{21}}{a_{11}}\\ times \\ equation\\ 1\\ to\\ equation\\ 2$.\n",
        "\n",
        "In matrix form, this is equivalent to multiplying on the left by the following $mxm$ matrix:\n",
        "\n",
        "$L_1 = \\begin{bmatrix} 1 & 0 & 0 &... & 0 \\\\ -\\frac{a_{21}}{a_{11}} & 1 & 0 & ... & 0 \\\\ -\\frac{a_{31}}{a_{11}} & 0 & 1 & ... & 0 \\\\ ... \\\\ -\\frac{a_{m1}}{a_{11}} & 0 & 0 & ... & 1 \\end{bmatrix}$\n",
        "\n",
        "i.e.\n",
        "\n",
        "$L_1 A x = L_1 v$\n",
        "\n",
        "Note that $rank(L_1) = m$ therefore $rank(L_1 A) = rank (A)$\n",
        "\n",
        "This matrix is called an  row transformation and is lower triangular.\n",
        "\n",
        "Applying this $m$ times leads to ⁉\n",
        "\n",
        "$L_m L_{m-1} .. L_1 A x = L A x = U x = Lv$\n",
        "\n",
        "Where $L = L_m L_{m-1} .. L_1$ and $U$ is the upper triangular matrix.\n",
        "\n",
        "Now $Ux = Lv$ can be solved by back substitution.\n",
        "\n",
        "\n",
        "The elements $a_{ii}^{'}$ used to form divisors are called the *pivots* and form the diagonal of the $U$ matrix. If during the process of elimination, one happens to be zero, then you can try to swap the column which has a non-zero (or the largest non-zero magnitude). Note that this doesnt change the solution set - but only changes the order of the variables (permutes them).\n",
        "\n",
        "If you cannot find as non-zero pivot - then the process has to stop and no solution exists."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MReNgwUSgNtb"
      },
      "source": [
        "**Q7**\n",
        "\n",
        "Find the matrices L1, L2, L3, U and the solution vector x\n",
        "by filling in the correct values to the matrices below in the next sequence of cells"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NtiVTRGofQQV",
        "outputId": "0be90c80-eb0f-45a0-863e-fc646dfc3cac"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A1=\n",
            "[[ 1  2  3  4]\n",
            " [ 0 -2 -4 -6]\n",
            " [ 0 -3 -6 -9]]\n",
            "v1 =\n",
            " [  6 -12 -18]\n"
          ]
        }
      ],
      "source": [
        "#Ans - Step 1\n",
        "\n",
        "A = np.array([[1,2,3,4], [3,4,5,6],[4,5,6,7]])\n",
        "v = np.array([6,6,6])\n",
        "\n",
        "L1 = np.array([[1,0,0],[-3, 1, 0],[-4, 0, 1]])\n",
        "\n",
        "A1 = L1 @ A\n",
        "v1 = L1 @ v\n",
        "\n",
        "print(f\"A1=\\n{A1}\\nv1 =\\n {v1}\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t_Ek6LvygdZ-",
        "outputId": "6839f232-694f-48a5-b841-e3e62a47d5f8"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A2=\n",
            "[[ 1.  2.  3.  4.]\n",
            " [ 0. -2. -4. -6.]\n",
            " [ 0.  0.  0.  0.]]\n",
            "v2=\n",
            "[  6. -12.   0.]\n"
          ]
        }
      ],
      "source": [
        "#Ans - step 2\n",
        "L2 = np.array([[1, 0, 0],[0,1,0],[0,-3/2, 1]])\n",
        "A2 = L2 @ A1\n",
        "v2 = L2 @ v1\n",
        "print(f\"A2=\\n{A2}\\nv2=\\n{v2}\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "i79NRsgzi8cX",
        "outputId": "257f0cc5-5847-47cf-b414-dff201ff6b7f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "L=\n",
            "[[ 1.   0.   0. ]\n",
            " [-3.   1.   0. ]\n",
            " [ 0.5 -1.5  1. ]]\n",
            "U=\n",
            "[[ 1.  2.  3.  4.]\n",
            " [ 0. -2. -4. -6.]\n",
            " [ 0.  0.  0.  0.]]\n",
            "Lv = [  6. -12.   0.]\n"
          ]
        }
      ],
      "source": [
        "L = L2 @ L1\n",
        "U = L @ A\n",
        "\n",
        "Lv = L @ v\n",
        "\n",
        "print(f\"L=\\n{L}\\nU=\\n{U}\\nLv = {Lv}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "P-iH_3aXipup"
      },
      "source": [
        "Ans:\n",
        "\n",
        "One solution is:\n",
        "\n",
        "x1 = -6, x2 = 6, x3=0, x4=0"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xLot_90rpnME"
      },
      "source": [
        "**Matrix Product and Matrix Group**\n",
        "\n",
        "Associativity: $A(BC) = (AB)C$ provided the multiplication is possible in terms of the matrix dimensions.\n",
        "\n",
        "Not commutative: $AB \\ne BA$ in general (even when A & B are square)\n",
        "\n",
        "Consider the set of $nxn$ non-singular matrices $GL(n) = \\{A \\in ℜ^{nxn}\\}$ along with the matrix product '·'. This is a \"Group\" and called the General linear group:\n",
        "\n",
        "1. Closure under multipication: $A, B \\in GL(n)$ then $A·B \\in GL(n)$\n",
        "2. Associative: $A, B, C \\in GL(n)$ then $(A·B)·C = A·(B · C)$\n",
        "3. Identity: $I_n \\in GL(n)$ such that $A · I_n = I_n · A = A$\n",
        "4. Inverse: $∀\\ A \\in GL(n)$ then $∃\\ A^{-1}$ such that $A · A^{-1} =I_n = A^{-1}A$\n"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "include_colab_link": true,
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}