tutorials/LinearAlgebra/Workbook_LinearAlgebra.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Algebra Tutorial Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Linear Algebra tutorial](./LinearAlgebra.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Python that might be non-obvious for a first-time user.\n",
    "\n",
    "**What you should know for this workbook**\n",
    "\n",
    "1. Complex arithmetic.\n",
    "2. Basic Python knowledge is helpful but not necessary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Click the cell with code below this block of text and press `Ctrl+Enter` (`⌘+Enter` on Mac). **Do not skip this step**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this cell using Ctrl+Enter (⌘+Enter on Mac).\n",
    "from testing import exercise, create_empty_matrix\n",
    "from typing import List\n",
    "\n",
    "import math, cmath\n",
    "\n",
    "Matrix = List[List[complex]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 1</span>: Matrix addition.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. An $n \\times m$ matrix $A$, represented as a two-dimensional list.\n",
    "2. An $n \\times m$ matrix $B$, represented as a two-dimensional list.\n",
    "\n",
    "**Output:** Return the sum of the matrices $A + B$ - an $n \\times m$ matrix, represented as a two-dimensional list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Following the definition given in the tutorial, the sum of two matrices is a matrix of element-wise sums of matrix elements; for example, for $2 \\times 2$ matrices\n",
    "\n",
    "$$ A + B =\\begin{bmatrix} a & b \\\\ c & d \\end{bmatrix} + \\begin{bmatrix} e & f \\\\ g & h \\end{bmatrix} = \\begin{bmatrix} a + e & b + f \\\\ c + g & d + h \\end{bmatrix}$$\n",
    "\n",
    "> *Python note:* This tutorial uses a lot of lists and loops, so let's walk through some Python syntax details first. If you're familiar with Python syntax, feel free to skip this note!\n",
    ">\n",
    "> * [`range(x)`](https://docs.python.org/3/tutorial/controlflow.html#the-range-function) will create \n",
    "a [list](https://docs.python.org/3/tutorial/introduction.html#lists) of numbers from 0 to `x - 1`, inclusive; \n",
    "for example, `range(3)` will create a list `[0, 1, 2]`.  \n",
    "> * [`for`](https://docs.python.org/3/tutorial/controlflow.html#for-statements) statement iterates over the items of a sequence; for example, the following code\n",
    "> ```python\n",
    "> for i in range(3):\n",
    ">     print(i)\n",
    "> ```\n",
    ">\n",
    ">   will print:\n",
    "> ```\n",
    "> 0\n",
    "> 1\n",
    "> 2\n",
    "> ```\n",
    ">\n",
    "> * Matrices are described as two-dimensional lists, \n",
    ">   which are represented as lists of lists. For example, the following matrix:\n",
    ">\n",
    ">   $$\\begin{bmatrix} 1 & 2 & 3 \\\\ 4 & 5 & 6 \\end{bmatrix} $$\n",
    ">\n",
    ">   is represented as a list of lists `[[1, 2, 3], [4, 5, 6]]`. \n",
    ">\n",
    "> * You can access a specific element of the list using the index of that element in the list (note that indices start with 0): the first element of `array` is `array[0]`, the second - `array[1]`, etc.\n",
    "> * Similarly, you can access an element of a matrix using the row and column indices of that element:  `matrix[0][2]` would access the element in the first row and 3rd column.\n",
    "> * `len(array)` returns the number of elements in a list; for example, `len([0, 1, 2])` will return 3.\n",
    "> * Here is an example of creating a matrix from the example above and looping through its elements to print them:\n",
    ">\n",
    ">```Python\n",
    ">matrix = [[1, 2, 3], [4, 5, 6]]\n",
    ">numberOfRows = len(matrix)              # will return 2\n",
    ">numberOfColumns = len(matrix[0])        # will return 3\n",
    ">for row in range(numberOfRows):\n",
    ">    for column in range(numberOfColumns):\n",
    ">        print(matrix[row][column])\n",
    ">\n",
    ">```\n",
    ">\n",
    "> * Finally, the first exercise offers you a template of a solution that uses a function `create_empty_matrix(n, m)`; this function creates an $n \\times m$ matrix filled with 0's as values. This function is not a built-in Python function, this notebook defines it for you to use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def matrix_add(a : Matrix, b : Matrix) -> Matrix:\n",
    "    # You can get the size of a matrix like this:\n",
    "    rows = len(a)\n",
    "    columns = len(a[0])\n",
    "    \n",
    "    # You can use the following function to initialize a rows×columns matrix filled with 0s to store your answer\n",
    "    c = create_empty_matrix(rows, columns)\n",
    "        \n",
    "    for i in range(rows):\n",
    "        for j in range(columns):\n",
    "            # You can access elements of a matrix like this:\n",
    "            x = a[i][j]\n",
    "            y = b[i][j]\n",
    "            \n",
    "            # You can modify the elements of a matrix like this:\n",
    "            c[i][j] = a[i][j] + b[i][j]\n",
    "    \n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-1:-Matrix-addition.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 2</span>: Scalar multiplication.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. A scalar $x$.\n",
    "2. An $n \\times m$ matrix $A$.\n",
    "\n",
    "**Output:** Return the $n \\times m$ matrix $x \\cdot A$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We can again follow the definition given in the tutorial: to calculate the product of a number and a matrix, multiply each matrix element by that number. For example, for a $2 \\times 2$ matrix:\n",
    "\n",
    "$$x \\cdot A = x \\cdot \\begin{bmatrix} a & b \\\\ c & d \\end{bmatrix} = \\begin{bmatrix} x \\cdot a & x \\cdot b \\\\ x \\cdot c & x \\cdot d \\end{bmatrix}  $$ \n",
    "\n",
    "> *Python note:* We have to multiply each element in the matrix by the given number $x$. To do so, we will again loop trough each matrix element with 2 `for` loops, do the multiplication and store its result in the corresponding element of the newly created matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def scalar_mult(x : complex, a : Matrix) -> Matrix:\n",
    "    rows = len(a)\n",
    "    columns = len(a[0])\n",
    "    \n",
    "    c = create_empty_matrix(rows, columns)\n",
    "    \n",
    "    for i in range(rows):\n",
    "        for j in range(columns):\n",
    "            c[i][j] = a[i][j] * x\n",
    "    \n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-2:-Scalar-multiplication.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 3</span>: Matrix multiplication.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. An $n \\times m$ matrix $A$.\n",
    "2. An $m \\times k$ matrix $B$.\n",
    "\n",
    "**Output:** Return the $n \\times k$ matrix equal to the matrix product $AB$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Again, the tutorial gives us the definition of how multiplication works, and we just need to implement it in code. Here is an example of multiplying a $2 \\times 3$ matrix by a $3 \\times 2$ matrix:\n",
    "\n",
    "$$ A \\cdot B =\\begin{bmatrix} a & b & c \\\\ d & e & f \\end{bmatrix} \\cdot \\begin{bmatrix} h & i \\\\ j & k \\\\ l & m \\end{bmatrix} = \\begin{bmatrix} a \\cdot h + b \\cdot j + c \\cdot l & a \\cdot i + b \\cdot k + c \\cdot m \\\\ \n",
    "d \\cdot h + e \\cdot j + f \\cdot l & d \\cdot i + e \\cdot k + f \\cdot m \\end{bmatrix} $$\n",
    "\n",
    "> *Python note*: In this exercise we'll need an extra nested loop. \n",
    "We will iterate trough the rows and columns of the resulting matrix, similar to the previous exercises, \n",
    "but for each element of the result we'll need to iterate through the row of the left matrix and the column of the right matrix that contribute to that element. \n",
    "In the example above, to get the element in the first row and the first column of the resulting matrix product \n",
    "we'll need to iterate through the first row of the left matrix $\\begin{bmatrix} a & b & c \\end{bmatrix}$ \n",
    "and the first column of the right matrix $\\begin{bmatrix} h \\\\ j \\\\ l \\end{bmatrix}$ and add up pairwise products of their elements.\n",
    ">\n",
    "> Note that the empty matrix we create for storing the result differs in dimensions from the previous exercises: its number of rows equals the number of rows of the left matrix, and its number of columns equals to the number of columns of the right matrix.  \n",
    ">\n",
    "> Python `+=` operator is a convenient shorthand for assignment `variable = variable + increment`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def matrix_mult(a : Matrix, b : Matrix) -> Matrix:\n",
    "    rows = len(a)        # the number of rows of the left matrix\n",
    "    common = len(a[0])   # = len(b) - the common dimension of the matrices\n",
    "    columns = len(b[0])  # the number of columns of the right matrix\n",
    "    \n",
    "    ans = create_empty_matrix(rows, columns)\n",
    "    \n",
    "    for currentRow in range(rows):\n",
    "        for currentColumn in range(columns):\n",
    "            for k in range(common):\n",
    "                ans[currentRow][currentColumn] += a[currentRow][k] * b[k][currentColumn]\n",
    "                \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-3:-Matrix-multiplication.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 4</span>: Matrix Inversion.\n",
    "\n",
    "**Input:** An invertible $2 \\times 2$ matrix $A$.\n",
    "\n",
    "**Output:** Return the inverse of $A$, a $2 \\times 2$ matrix $A^{-1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Since we only need to invert a $2 \\times 2$ matrix, we will not consider a solution which can be used for arbitrary-sized matrices. \n",
    "We will follow the algorithm described in the [Wikipedia article](https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of_2_%C3%97_2_matrices).\n",
    "\n",
    "$$ A = \\begin{bmatrix} a & b \\\\ c & d \\end{bmatrix} $$\n",
    "\n",
    "The determinant of the matrix is defined as \n",
    "$$ |A| = a \\cdot d - b \\cdot c $$\n",
    "\n",
    "$$A^{-1} = \\frac{1}{|A|} \\cdot \\begin{bmatrix} d & -b \\\\ -c & a \\end{bmatrix} = \\begin{bmatrix} \\frac{d}{|A|} & \\frac{-b}{|A|} \\\\ \\frac{-c}{|A|} & \\frac{a}{|A|} \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def matrix_inverse(m : Matrix) -> Matrix:\n",
    "    # Extract each element of the array into a named variable\n",
    "    a = m[0][0]\n",
    "    b = m[0][1]\n",
    "    c = m[1][0]\n",
    "    d = m[1][1]\n",
    "    \n",
    "    # Calculate the determinant\n",
    "    determinant = (a * d) - (b * c)\n",
    "    \n",
    "    # Create the inverse of the matrix following the formula above\n",
    "    ans = [[d / determinant, -b / determinant], [-c / determinant, a / determinant]]\n",
    "\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 4 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-4:-Matrix-Inversion.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 5</span>: Transpose.\n",
    "\n",
    "**Input:** An $n \\times m$ matrix $A$.\n",
    "\n",
    "**Output:** Return an $m \\times n$ matrix $A^T$, the transpose of $A$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Again, the tutorial gives us the definition of matrix transpose, so we just need to fill the resulting matrix with the elements of the original matrix in the right order. For example, for a $3 \\times 2$ matrix\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    a & b \\\\\n",
    "    c & d \\\\\n",
    "    e & f\n",
    "\\end{bmatrix}^T\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    a & c & e \\\\\n",
    "    b & d & f\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def transpose(a : Matrix) -> Matrix:\n",
    "    rows = len(a)\n",
    "    columns = len(a[0])\n",
    "    \n",
    "    # Note that the resulting matrix dimensions are swapped compared to the original ones\n",
    "    ans = create_empty_matrix(columns, rows)\n",
    "    \n",
    "    for i in range(rows):\n",
    "        for j in range(columns):\n",
    "            ans[j][i] = a[i][j]\n",
    "                \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 5 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-5:-Transpose.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 6</span>: Conjugate.\n",
    "\n",
    "**Input:** An $n \\times m$ matrix $A$.\n",
    "\n",
    "**Output:** Return an $n \\times m$ matrix $\\overline{A}$, the conjugate of $A$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solutions\n",
    "\n",
    "To get the conjugate of a matrix you take the conjugate of each individual element \n",
    "(check the [Complex Arithmetic tutorial](../ComplexArithmetic/ComplexArithmetic.ipynb#Complex-Conjugate) for the definition.\n",
    "\n",
    "> *Python note*: In the complex arithmetic tutorial complex numbers were represented as tuples of real and imaginary components. \n",
    "However, this tutorial relies on Python's built-in [`complex`](https://docs.python.org/3.8/library/functions.html#complex) data type. \n",
    "Python's [cmath library](https://docs.python.org/3.8/library/cmath.html) offers a lot of useful functions that deal with the `complex` data type.\n",
    ">\n",
    "> Here is an example of using the `complex` data type:\n",
    ">\n",
    "> ```Python\n",
    "> # Import the cmath library\n",
    "> import cmath\n",
    ">\n",
    "> # Create a new complex number 5 + 3i; the two arguments are the real and the imaginary parts of the number\n",
    "> complexNumber = complex(5, 3)\n",
    ">\n",
    "> # Print the real and the imaginary parts of the number\n",
    "> print(complexNumber.real) \n",
    "> print(complexNumber.imag)\n",
    ">\n",
    "> # Convert the complex number to its polar representation using the cmath library\n",
    "> polar = cmath.polar(complexNumber)\n",
    "> print(polar) # This prints: (5.830951894845301, 0.5404195002705842)\n",
    "> ```\n",
    ">\n",
    "> To get the complex conjugate of a matrix, we loop trough each element of the matrix, extract real and imaginary parts of the number and flip the sign for the imaginary part."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def conjugate(a : Matrix) -> Matrix:\n",
    "    rows = len(a)\n",
    "    columns = len(a[0])\n",
    "    \n",
    "    ans = create_empty_matrix(rows, columns)\n",
    "    \n",
    "    for i in range(rows):\n",
    "        for j in range(columns):\n",
    "            ans[i][j] = complex(a[i][j].real, -a[i][j].imag)\n",
    "            \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 6 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-6:-Conjugate.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 7</span>: Adjoint.\n",
    "\n",
    "**Input:** An $n \\times m$ matrix $A$.\n",
    "\n",
    "**Output:** Return an $m \\times n$ matrix $A^\\dagger$, the adjoint of $A$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "To get the adjoint we perform both **transpose** and **conjugate** operations on the input matrix.  \n",
    "We can write out the whole procedure manually, like we have done above, but we can also leverage the code we have written above.\n",
    "> In Python the `def` word defines a function, which could be reused later in the code.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def adjoint(a : Matrix) -> Matrix:\n",
    "    \n",
    "    # Call the transpose function with the input matrix a\n",
    "    transp = transpose(a)\n",
    "    \n",
    "    # Call the conjugate function with the transposed matrix as input\n",
    "    ans = conjugate(transp)\n",
    "    \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 7 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-7:-Adjoint.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 8</span>: Unitary Verification.\n",
    "\n",
    "**Input:** An $n \\times n$ matrix $A$.\n",
    "\n",
    "**Output:** Check if the matrix is unitary and return `True` if it is, or `False` if it isn't."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "A matrix is unitary if this holds true:  $UU^\\dagger = U^\\dagger U = I$.\n",
    "(As a reminder, an identity matrix is a matrix with 1s on the main diagonal and 0s everywhere else.)\n",
    "\n",
    "Thus, to check if the input matrix is unitary we will need to perform the following steps:\n",
    "1. Calculate the adjoint of the input matrix.\n",
    "2. Multiply it by the input matrix.\n",
    "3. Check if the multiplication result is equal to an identity matrix.  \n",
    "\n",
    "> *Python note:* We will leverage the `adjoint` and the `matrix_mult` functions what we have created above.\n",
    ">\n",
    "> When we check each element of $UU^\\dagger$ to see whether it equals the respective element of the identity matrix, we'll use Python function `approx` to perform this comparison approximately."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pytest import approx\n",
    "\n",
    "@exercise\n",
    "def is_matrix_unitary(a : Matrix) -> bool:\n",
    "    n = len(a)\n",
    "    \n",
    "    # Calculate the adjoint matrix\n",
    "    adjointA = adjoint(a)\n",
    "    \n",
    "    # Multiply the adjoint matrix by the input matrix\n",
    "    multipliedMatrix = matrix_mult(a, adjointA)\n",
    "    \n",
    "    # Check whether the multiplication result is (approximately) identity matrix\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            # An identity matrix has 1's in all the places where the row index and column index are equal...\n",
    "            if i == j:\n",
    "                if multipliedMatrix[i][j] != approx(1): \n",
    "                    return False\n",
    "            # ... and 0's in all the places where the row index and column index are different\n",
    "            else:\n",
    "                if multipliedMatrix[i][j] != approx(0):\n",
    "                    return False\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 8 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-8:-Unitary-Verification.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 9</span>: Inner product.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. An $n \\times 1$ vector $V$.\n",
    "2. An $n \\times 1$ vector $W$.\n",
    "\n",
    "**Output:** Return a complex number - the inner product $\\langle V , W \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Following the definition of the inner product, $\\langle V , W \\rangle = V^\\dagger W$. For example, for vectors of length 2:\n",
    "\n",
    "$$\\langle\n",
    "\\begin{bmatrix}\n",
    "    a \\\\\n",
    "    b\n",
    "\\end{bmatrix}\n",
    ",\n",
    "\\begin{bmatrix}\n",
    "    c \\\\\n",
    "    d\n",
    "\\end{bmatrix}\n",
    "\\rangle =\n",
    "\\begin{bmatrix}\n",
    "    a \\\\\n",
    "    b\n",
    "\\end{bmatrix}^\\dagger\n",
    "\\begin{bmatrix}\n",
    "    c \\\\\n",
    "    d\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix} \\overline{a} & \\overline{b} \\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "    c \\\\\n",
    "    d\n",
    "\\end{bmatrix}\n",
    "= \\overline{a} \\cdot c + \\overline{b} \\cdot d$$\n",
    "\n",
    "> *Python note:* We will again use previously defined functions to calculate adjoint of a vector and a product of two vectors. \n",
    "> We need to keep in mind that the task asks us to return a complex number and not a $1 \\times 1$ matrix which is the result of the multiplication. \n",
    "> Therefore at the end we'll extract the top left element of the `resultMatrix` and return it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def inner_prod(v : Matrix, w : Matrix) -> complex:\n",
    "    \n",
    "    # Calculate the adjoint of the v vector\n",
    "    adjointV = adjoint(v)\n",
    "    \n",
    "    # Multiply the adjoint v and w. The result will be a matrix with only one element.\n",
    "    resultMatrix = matrix_mult(adjointV, w)\n",
    "    \n",
    "    # To get the actual complex number, we have to take one element from the multiplication result.\n",
    "    return resultMatrix[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 9 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-9:-Inner-product.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 10</span>: Normalized vectors.\n",
    "\n",
    "**Input:** A non-zero $n \\times 1$ vector $V$.\n",
    "\n",
    "**Output:** Return an $n \\times 1$ vector $\\frac{V}{||V||}$ - the normalized version of the vector $V$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution \n",
    "\n",
    "If the vector $V = \\begin{bmatrix}a & b & c \\end{bmatrix}$, its norm $ ||V|| = \\sqrt{|a|^2 + |b|^2 + |c|^2} $,\n",
    "and its normalized version is\n",
    "$ \\begin{bmatrix}\\frac{a}{||V||} & \\frac{b}{||V||} & \\frac{c}{||V||}  \\end{bmatrix} $.\n",
    "\n",
    "Thus, we need to calculate the norm of the vector and to divide each element of the vector by it. We will calculate the norm as a square root of an inner product of the vector with itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def normalize(v : Matrix) -> Matrix:\n",
    "    norm = math.sqrt(inner_prod(v, v).real)\n",
    "    \n",
    "    n = len(v)\n",
    "    ans = create_empty_matrix(n, 1)\n",
    "    \n",
    "    # Divide each element of the vector by the norm\n",
    "    for i in range(n):\n",
    "        ans[i][0] = v[i][0] / norm\n",
    "        \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 10 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-10:-Normalized-vectors.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 11</span>: Outer product.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. An $n \\times 1$ vector $V$.\n",
    "2. An $m \\times 1$ vector $W$.\n",
    "\n",
    "**Output:** Return an $n \\times m$ matrix that represents the outer product of $V$ and $W$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "By definition, the outer product of $V$ and $W$ is $VW^\\dagger$. \n",
    "We can use a similar approach to calculating the inner product, except here we will return the whole multiplication result rather than a specific number. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def outer_prod(v : Matrix, w : Matrix) -> Matrix:\n",
    "    # Calculate adjoint of the W\n",
    "    adjointW = adjoint(w)\n",
    "    \n",
    "    # Multiply V by W adjoint\n",
    "    return matrix_mult(v, adjointW)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 11 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-11:-Outer-product.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 12</span>*: Tensor Product.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. An $n \\times m$ matrix $A$.\n",
    "2. A $k \\times l$ matrix $B$.\n",
    "\n",
    "**Output:** Return an $(n \\cdot k) \\times (m \\cdot l)$ matrix $A \\otimes B$, the tensor product of $A$ and $B$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We will follow the definition of the tensor product. For example, tensor product of $2 \\times 2$ matrices look as follows:\n",
    "\n",
    "$$\\begin{bmatrix} a & b \\\\ c & d \\end{bmatrix} \\otimes \\begin{bmatrix} e & f \\\\ g & h \\end{bmatrix} =\n",
    "\\begin{bmatrix}\n",
    "    a \\cdot \\begin{bmatrix} e & f \\\\ g & h \\end{bmatrix} & b \\cdot \\begin{bmatrix} e & f \\\\ g & h \\end{bmatrix} \\\\\n",
    "    c \\cdot \\begin{bmatrix} e & f \\\\ g & h \\end{bmatrix} & d \\cdot \\begin{bmatrix} e & f \\\\ g & h \\end{bmatrix}\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    a \\cdot e & a \\cdot f & b \\cdot e & b \\cdot f \\\\\n",
    "    a \\cdot g & a \\cdot h & b \\cdot g & b \\cdot h \\\\\n",
    "    c \\cdot e & c \\cdot f & d \\cdot e & d \\cdot f \\\\\n",
    "    c \\cdot g & c \\cdot h & d \\cdot g & d \\cdot h\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "> *Python note:* We need to calculate pairwise products of all elements of the left matrix and all elements of the right matrix; this means we have to use 4 nested loops."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def tensor_product(a : Matrix, b : Matrix) -> Matrix:\n",
    "    aRows = len(a)       # the number of rows for matrix a\n",
    "    aColumns = len(a[0]) # the number of columns for matrix a\n",
    "    bRows = len(b)       # the number of rows for matrix b\n",
    "    bColumns = len(b[0]) # the number of columns for matrix b\n",
    "    \n",
    "    ans = create_empty_matrix(aRows * bRows, aColumns *  bColumns)\n",
    "    \n",
    "    # Outer pair of loops, iterating trough the elements of the left matrix\n",
    "    for i in range(aRows):\n",
    "        for j in range(aColumns):\n",
    "            # Inner pair of loops, iterating through the elements of the right matrix\n",
    "            for k in range(bRows):\n",
    "                for l in range(bColumns):\n",
    "                    ans[i * bRows + k][j * bColumns + l] = a[i][j] * b[k][l]\n",
    "    \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 12 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-12*:-Tensor-Product.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 13</span>: Finding an eigenvalue.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. A real-valued $n \\times n$ matrix $A$.\n",
    "2. An eigenvector $V$ of matrix $A$.\n",
    "\n",
    "**Output:** Return a real number - the eigenvalue of $A$ that is associated with the given eigenvector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's consider what happens when we multiply the matrix by its eigenvector for a $3 \\times 3$ example:\n",
    "\n",
    "$$ A \\cdot V = \\begin{bmatrix} a & b & c \\\\ d & e & f \\\\ g & h & i \\end{bmatrix} \\cdot \\begin{bmatrix}j \\\\ k \\\\ l \\end{bmatrix} = \\begin{bmatrix} m \\\\ n \\\\ o \\end{bmatrix} = \\alpha \\begin{bmatrix}j \\\\ k \\\\ l \\end{bmatrix} = \\alpha V$$\n",
    "This means you can find the eigenvalue $\\alpha$ from the equations \n",
    "$$ \\begin{cases} \\alpha j = m \\\\ \\alpha k = n \\\\ \\alpha l = o \\end{cases}$$\n",
    "\n",
    "We can use any of them, keeping in mind that we need an equation in which the element of the eigenvector is not zero (otherwise we get an equation $0 \\alpha = 0$ which doesn't help us find $\\alpha$).\n",
    "Since eigenvectors are defined as non-zero vectors, we are guaranteed that at least one element of the vector will not be zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pytest import approx\n",
    "\n",
    "@exercise\n",
    "def find_eigenvalue(a : Matrix, v : Matrix) -> float:\n",
    "    n = len(v)\n",
    "    multiplied = matrix_mult(a, v)\n",
    "\n",
    "    for i in range(n):\n",
    "        if (v[i][0] != approx(0)):\n",
    "            return multiplied[i][0] / v[i][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 13 of the Linear Algebra tutorial.](/LinearAlgebra.ipynb#Exercise-13:-Finding-an-eigenvalue.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 14</span>**: Finding an eigenvector.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. A $2 \\times 2$ matrix $A$.\n",
    "2. An eigenvalue $x$ of matrix $A$.\n",
    "\n",
    "**Output:** Return any non-zero eigenvector of $A$ that is associated with $x$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Searching for an eigenvector $V$ associated with a specific eigenvalue $x$ asks for solving the following equation:\n",
    "\n",
    "$$ AV = xV $$\n",
    "or, equivalently, $$(A - xI_n)V = 0$$\n",
    "\n",
    "In other words, for a $2 \\times 2$ matrix the following happens: \n",
    "1. Multiply the identity matrix $I_2$ by the eigenvalue:\n",
    "$$ x \\cdot \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} = \\begin{bmatrix} x & 0 \\\\ 0 & x \\end{bmatrix} $$\n",
    "2. Subtract this new matrix from the given matrix $A$:\n",
    "$$ \\begin{bmatrix} a & b \\\\ c & d \\end{bmatrix} - \\begin{bmatrix} x & 0 \\\\ 0 & x \\end{bmatrix} = \\begin{bmatrix} a -x & b \\\\ c & d -x \\end{bmatrix} $$ \n",
    "\n",
    "3. Find a vector that, when multiplied by the resulting matrix, will produce a 0 vector:\n",
    "$$ \\begin{bmatrix} a - x & b \\\\ c & d - x \\end{bmatrix} \\cdot \\begin{bmatrix} v_0 \\\\ v_1 \\end{bmatrix} = \\begin{bmatrix} 0 \\\\ 0 \\end{bmatrix}$$\n",
    "\n",
    "This can be rewritten as the following system of equations:\n",
    "\n",
    "$$\\begin{cases}\n",
    "(a - x) \\cdot v_0 + b \\cdot v_1 = 0  \\\\\n",
    "c \\cdot v_0 + (d - x) \\cdot v_1 = 0  \n",
    "\\end{cases}$$\n",
    "\n",
    "Each eigenvalue has infinitely many eigenvectors associated with it (since multiplying an eigenvector by a number gives another valid eigenvector). We can limit our search and say that $v_0 = 1$, if possible. In this case, the system of equations becomes\n",
    "\n",
    "$$\\begin{cases}\n",
    "(a - x) + b \\cdot v_1 = 0  \\\\\n",
    "c + (d - x) \\cdot v_1 = 0  \n",
    "\\end{cases}$$\n",
    "\n",
    "and finally we get $v_1 = \\frac{a-x}{-b}$.\n",
    "\n",
    "If $b = 0$, we can not perform this division, so we need to reconsider our choices. The first equation becomes $(a-x)v_0 = 0$, which is possible in two cases:\n",
    "* If $a - x \\neq 0$, we get $v_0 = 0$ and thus $v_1$ has to be non-zero (we can pick $v_1 = 1$).\n",
    "* If $a - x = 0$, we can not get any information from the first equation and have to fall back to the second one:\n",
    "$c \\cdot v_0 + (d - x) \\cdot v_1 = 0$. Following a similar logic:\n",
    "  * If $c = 0$, we get $(d - x) \\cdot v_1 = 0$, so $v_0 = 1, v_1 = 0$.\n",
    "  * If $c \\neq 0$, we get $v_1 = 1, v_0 = \\frac{d-x}{-c}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def find_eigenvector(a : Matrix, x : float) -> Matrix:\n",
    "    # Check for possible edge cases\n",
    "    if (a[0][1] == 0):\n",
    "        if (a[0][0] - x == 0):\n",
    "            if (a[1][0] == 0):\n",
    "                return [[1], [0]]\n",
    "            else:\n",
    "                return [[(a[1][1] - x) / (-a[1][0])], [1]]\n",
    "        else:\n",
    "            return [[0], [1]]\n",
    "    \n",
    "    v0 = 1\n",
    "    v1 = (a[0][0] - x) / (-a[0][1])\n",
    "    return [[v0], [v1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 14 of the Linear Algebra tutorial.](./LinearAlgebra.ipynb#Exercise-14**:-Finding-an-eigenvector.)"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}