tutorials/LinearAlgebra/LinearAlgebra.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Linear Algebra\n",
    "\n",
    "This is a tutorial designed to introduce you to the basics of linear algebra.\n",
    "Linear algebra is a branch of mathematics dedicated to studying the properties of matrices and vectors,\n",
    "which are used extensively in quantum computing to represent quantum states and operations on them.\n",
    "This tutorial doesn't come close to covering the full breadth of the topic, but it should be enough to get you comfortable with the main concepts of linear algebra used in quantum computing.\n",
    "\n",
    "This tutorial assumes familiarity with complex numbers; if you need a review of this topic, we recommend that you complete the [Complex Arithmetic](../ComplexArithmetic/ComplexArithmetic.ipynb) tutorial before tackling this one.\n",
    "\n",
    "This tutorial covers the following topics:\n",
    "* Matrices and vectors\n",
    "* Basic matrix operations\n",
    "* Operations and properties of complex matrices\n",
    "* Inner and outer vector products\n",
    "* Tensor product\n",
    "* Eigenvalues and eigenvectors\n",
    "\n",
    "If you need to look up some formulas quickly, you can find them in [this cheatsheet](https://github.com/microsoft/QuantumKatas/blob/master/quickref/qsharp-quick-reference.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook has several tasks that require you to write Python code to test your understanding of the concepts. If you are not familiar with Python, [here](https://docs.python.org/3/tutorial/index.html) is a good introductory tutorial for it.\n",
    "\n",
    "> The exercises use Python's built-in representation of complex numbers. Most of the operations (addition, multiplication, etc.) work as you expect them to. Here are a few notes on Python-specific syntax:\n",
    ">\n",
    "> * If `z` is a complex number, `z.real` is the real component, and `z.imag` is the coefficient of the imaginary component.\n",
    "> * To represent an imaginary number, put `j` after a real number: $3.14i$ would be `3.14j`.\n",
    "> * To represent a complex number, simply add a real number and an imaginary number.\n",
    "> * The built-in function `abs` computes the modulus of a complex number.\n",
    ">\n",
    "> You can find more information in the [official documentation](https://docs.python.org/3/library/cmath.html).\n",
    "\n",
    "Let's start by importing some useful mathematical functions and constants, and setting up a few things necessary for testing the exercises. **Do not skip this step.**\n",
    "\n",
    "Click the cell with code below this block of text and press `Ctrl+Enter` (`⌘+Enter` on Mac)."
   ]
  },
  {
   "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": [
    "# Part I. Matrices and Basic Operations\n",
    "\n",
    "## Matrices and Vectors\n",
    "\n",
    "A **matrix** is set of numbers arranged in a rectangular grid. Here is a $2$ by $2$ matrix:\n",
    "\n",
    "$$A =\n",
    "\\begin{bmatrix} 1 & 2 \\\\ 3 & 4 \\end{bmatrix}$$\n",
    "\n",
    "$A_{i,j}$ refers to the element in row $i$ and column $j$ of matrix $A$ (all indices are 0-based). In the above example, $A_{0,1} = 2$.\n",
    "\n",
    "An $n \\times m$ matrix will have $n$ rows and $m$ columns, like so:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    x_{0,0} & x_{0,1} & \\dotsb & x_{0,m-1} \\\\\n",
    "    x_{1,0} & x_{1,1} & \\dotsb & x_{1,m-1} \\\\\n",
    "    \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "    x_{n-1,0} & x_{n-1,1} & \\dotsb & x_{n-1,m-1}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "A $1 \\times 1$ matrix is equivalent to a scalar:\n",
    "\n",
    "$$\\begin{bmatrix} 3 \\end{bmatrix} = 3$$\n",
    "\n",
    "Quantum computing uses complex-valued matrices: the elements of a matrix can be complex numbers. This, for example, is a valid complex-valued matrix:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    1 & i \\\\\n",
    "    -2i & 3 + 4i\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Finally, a **vector** is an $n \\times 1$ matrix. Here, for example, is a $3 \\times 1$ vector:\n",
    "\n",
    "$$V = \\begin{bmatrix} 1 \\\\ 2i \\\\ 3 + 4i \\end{bmatrix}$$\n",
    "\n",
    "Since vectors always have a width of $1$, vector elements are sometimes written using only one index. In the above example, $V_0 = 1$ and $V_1 = 2i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix Addition\n",
    "\n",
    "The easiest matrix operation is **matrix addition**. Matrix addition works between two matrices of the same size, and adds each number from the first matrix to the number in the same position in the second matrix:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    x_{0,0} & x_{0,1} & \\dotsb & x_{0,m-1} \\\\\n",
    "    x_{1,0} & x_{1,1} & \\dotsb & x_{1,m-1} \\\\\n",
    "    \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "    x_{n-1,0} & x_{n-1,1} & \\dotsb & x_{n-1,m-1}\n",
    "\\end{bmatrix}\n",
    "+\n",
    "\\begin{bmatrix}\n",
    "    y_{0,0} & y_{0,1} & \\dotsb & y_{0,m-1} \\\\\n",
    "    y_{1,0} & y_{1,1} & \\dotsb & y_{1,m-1} \\\\\n",
    "    \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "    y_{n-1,0} & y_{n-1,1} & \\dotsb & y_{n-1,m-1}\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    x_{0,0} + y_{0,0} & x_{0,1} + y_{0,1} & \\dotsb & x_{0,m-1} + y_{0,m-1} \\\\\n",
    "    x_{1,0} + y_{1,0} & x_{1,1} + y_{1,1} & \\dotsb & x_{1,m-1} + y_{1,m-1} \\\\\n",
    "    \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "    x_{n-1,0} + y_{n-1,0} & x_{n-1,1} + y_{n-1,1} & \\dotsb & x_{n-1,m-1} + y_{n-1,m-1}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Similarly, we can compute $A - B$ by subtracting elements of $B$ from corresponding elements of $A$.\n",
    "\n",
    "Matrix addition has the following properties:\n",
    "\n",
    "* Commutativity: $A + B = B + A$\n",
    "* Associativity: $(A + B) + C = A + (B + C)$"
   ]
  },
  {
   "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.\n",
    "\n",
    "> When representing matrices as lists, each sub-list represents a row.\n",
    ">\n",
    "> For example, list `[[1, 2], [3, 4]]` represents the following matrix:\n",
    ">\n",
    "> $$\\begin{bmatrix}\n",
    "    1 & 2 \\\\\n",
    "    3 & 4\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Fill in the missing code and run the cell below to test your work.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    A video explanation can be found <a href=\"https://www.youtube.com/watch?v=WR9qCSXJlyY\">here</a>.\n",
    "</details>"
   ]
  },
  {
   "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",
    "    # You can use a for loop to execute its body several times;\n",
    "    # in this loop variable i will take on each value from 0 to n-1, inclusive\n",
    "    for i in range(rows):\n",
    "        # Loops can be nested\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] = ...\n",
    "    \n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-1:-Matrix-addition.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scalar Multiplication\n",
    "\n",
    "The next matrix operation is **scalar multiplication** - multiplying the entire matrix by a scalar (real or complex number):\n",
    "\n",
    "$$a \\cdot\n",
    "\\begin{bmatrix}\n",
    "    x_{0,0} & x_{0,1} & \\dotsb & x_{0,m-1} \\\\\n",
    "    x_{1,0} & x_{1,1} & \\dotsb & x_{1,m-1} \\\\\n",
    "    \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "    x_{n-1,0} & x_{n-1,1} & \\dotsb & x_{n-1,m-1}\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    a \\cdot x_{0,0} & a \\cdot x_{0,1} & \\dotsb & a \\cdot x_{0,m-1} \\\\\n",
    "    a \\cdot x_{1,0} & a \\cdot x_{1,1} & \\dotsb & a \\cdot x_{1,m-1} \\\\\n",
    "    \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "    a \\cdot x_{n-1,0} & a \\cdot x_{n-1,1} & \\dotsb & a \\cdot x_{n-1,m-1}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Scalar multiplication has the following properties:\n",
    "\n",
    "* Associativity: $x \\cdot (yA) = (x \\cdot y)A$\n",
    "* Distributivity over matrix addition: $x(A + B) = xA + xB$\n",
    "* Distributivity over scalar addition: $(x + y)A = xA + yA$"
   ]
  },
  {
   "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$.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    A video explanation can be found <a href=\"https://www.youtube.com/watch?v=TbaltFbJ3wE\">here</a>.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def scalar_mult(x : complex, a : Matrix) -> Matrix:\n",
    "    # Fill in the missing code and run the cell to check your work.\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-2:-Scalar-multiplication.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix Multiplication\n",
    "\n",
    "**Matrix multiplication** is a very important and somewhat unusual operation. The unusual thing about it is that neither its operands nor its output are the same size: an $n \\times m$ matrix multiplied by an $m \\times k$ matrix results in an $n \\times k$ matrix. \n",
    "That is, for matrix multiplication to be applicable, the number of columns in the first matrix must equal the number of rows in the second matrix.\n",
    "\n",
    "Here is how matrix product is calculated: if we are calculating $AB = C$, then\n",
    "\n",
    "$$C_{i,j} = A_{i,0} \\cdot B_{0,j} + A_{i,1} \\cdot B_{1,j} + \\dotsb + A_{i,m-1} \\cdot B_{m-1,j} = \\sum_{t = 0}^{m-1} A_{i,t} \\cdot B_{t,j}$$\n",
    "\n",
    "Here is a small example:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    \\color{blue} 1 & \\color{blue} 2 & \\color{blue} 3 \\\\\n",
    "    \\color{red}  4 & \\color{red}  5 & \\color{red}  6\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "    1 \\\\\n",
    "    2 \\\\\n",
    "    3\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    (\\color{blue} 1 \\cdot 1) + (\\color{blue} 2 \\cdot 2) + (\\color{blue} 3 \\cdot 3) \\\\\n",
    "    (\\color{red}  4 \\cdot 1) + (\\color{red}  5 \\cdot 2) + (\\color{red}  6 \\cdot 3)\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    14 \\\\\n",
    "    32\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Matrix multiplication has the following properties:\n",
    "\n",
    "* Associativity: $A(BC) = (AB)C$\n",
    "* Distributivity over matrix addition: $A(B + C) = AB + AC$ and $(A + B)C = AC + BC$\n",
    "* Associativity with scalar multiplication: $xAB = x(AB) = A(xB)$\n",
    "\n",
    "> Note that matrix multiplication is **not commutative:** $AB$ rarely equals $BA$.\n",
    "\n",
    "Another very important property of matrix multiplication is that a matrix multiplied by a vector produces another vector.\n",
    "\n",
    "An **identity matrix** $I_n$ is a special $n \\times n$ matrix which has $1$s on the main diagonal, and $0$s everywhere else:\n",
    "\n",
    "$$I_n =\n",
    "\\begin{bmatrix}\n",
    "    1 & 0 & \\dotsb & 0 \\\\\n",
    "    0 & 1 & \\dotsb & 0 \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    0 & 0 & \\dotsb & 1\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "What makes it special is that multiplying any matrix (of compatible size) by $I_n$ returns the original matrix. To put it another way, if $A$ is an $n \\times m$ matrix:\n",
    "\n",
    "$$AI_m = I_nA = A$$\n",
    "\n",
    "This is why $I_n$ is called an identity matrix - it acts as a **multiplicative identity**. In other words, it is the matrix equivalent of the number $1$."
   ]
  },
  {
   "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$.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    To solve this exercise, you will need 3 <code>for</code> loops: one to go over $n$ rows of the output matrix, one to go over $k$ columns, and one to add up $m$ products that form each element of the output:\n",
    "    <pre>\n",
    "        <code>\n",
    "    for i in range(n):\n",
    "        for j in range(k):\n",
    "            sum = 0\n",
    "            for t in range(m):\n",
    "                sum = sum + ...\n",
    "            c[i][j] = sum\n",
    "        </code>\n",
    "    </pre>\n",
    "     A video explanation can be found <a href=\"https://www.youtube.com/watch?v=OMA2Mwo0aZg\">here</a>.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def matrix_mult(a : Matrix, b : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-3:-Matrix-multiplication.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inverse Matrices\n",
    "\n",
    "A square $n \\times n$ matrix $A$ is **invertible** if it has an inverse $n \\times n$ matrix $A^{-1}$ with the following property:\n",
    "\n",
    "$$AA^{-1} = A^{-1}A = I_n$$\n",
    "\n",
    "In other words, $A^{-1}$ acts as the **multiplicative inverse** of $A$.\n",
    "\n",
    "Another, equivalent definition highlights what makes this an interesting property. For any matrices $B$ and $C$ of compatible sizes:\n",
    "\n",
    "$$A^{-1}(AB) = A(A^{-1}B) = B \\\\\n",
    "(CA)A^{-1} = (CA^{-1})A = C$$\n",
    "\n",
    "A square matrix has a property called the **determinant**, with the determinant of matrix $A$ being written as $|A|$. A matrix is invertible if and only if its determinant isn't equal to $0$.\n",
    "\n",
    "For a $2 \\times 2$ matrix $A$, the determinant is defined as $|A| = (A_{0,0} \\cdot A_{1,1}) - (A_{0,1} \\cdot A_{1,0})$.\n",
    "\n",
    "For larger matrices, the determinant is defined through determinants of sub-matrices. You can learn more from [Wikipedia](https://en.wikipedia.org/wiki/Determinant) or from [Wolfram MathWorld](http://mathworld.wolfram.com/Determinant.html)."
   ]
  },
  {
   "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}$.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    Try to come up with a general method of doing it by hand first. If you get stuck, you may find <a href=\"https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of_2_%C3%97_2_matrices\">this Wikipedia article</a> useful. For this exercise, $|A|$ is guaranteed to be non-zero. <br>\n",
    "    A video explanation can be found <a href=\"https://www.youtube.com/watch?v=01c12NaUQDw\">here</a>.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def matrix_inverse(a : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-4:-Matrix-Inversion.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transpose\n",
    "\n",
    "The **transpose** operation, denoted as $A^T$, is essentially a reflection of the matrix across the diagonal: $(A^T)_{i,j} = A_{j,i}$.\n",
    "\n",
    "Given an $n \\times m$ matrix $A$, its transpose is the $m \\times n$ matrix $A^T$, such that if:\n",
    "\n",
    "$$A =\n",
    "\\begin{bmatrix}\n",
    "    x_{0,0} & x_{0,1} & \\dotsb & x_{0,m-1} \\\\\n",
    "    x_{1,0} & x_{1,1} & \\dotsb & x_{1,m-1} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    x_{n-1,0} & x_{n-1,1} & \\dotsb & x_{n-1,m-1}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "then:\n",
    "\n",
    "$$A^T =\n",
    "\\begin{bmatrix}\n",
    "    x_{0,0} & x_{1,0} & \\dotsb & x_{n-1,0} \\\\\n",
    "    x_{0,1} & x_{1,1} & \\dotsb & x_{n-1,1} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    x_{0,m-1} & x_{1,m-1} & \\dotsb & x_{n-1,m-1}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "For example:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    1 & 2 \\\\\n",
    "    3 & 4 \\\\\n",
    "    5 & 6\n",
    "\\end{bmatrix}^T\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    1 & 3 & 5 \\\\\n",
    "    2 & 4 & 6\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "A **symmetric** matrix is a square matrix which equals its own transpose: $A = A^T$. To put it another way, it has reflection symmetry (hence the name) across the main diagonal. For example, the following matrix is symmetric:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    1 & 2 & 3 \\\\\n",
    "    2 & 4 & 5 \\\\\n",
    "    3 & 5 & 6\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "The transpose of a matrix product is equal to the product of transposed matrices, taken in reverse order:\n",
    "\n",
    "$$(AB)^T = B^TA^T$$"
   ]
  },
  {
   "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$.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    A video explanation can be found <a href=\"https://www.youtube.com/watch?v=TZrKrNVhbjI\">here</a>.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def transpose(a : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-5:-Transpose.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conjugate\n",
    "\n",
    "The next important single-matrix operation is the **matrix conjugate**, denoted as $\\overline{A}$. This, as the name might suggest, involves taking the [complex conjugate](../ComplexArithmetic/ComplexArithmetic.ipynb#Complex-Conjugate) of every element of the matrix: if\n",
    "\n",
    "$$A =\n",
    "\\begin{bmatrix}\n",
    "    x_{0,0} & x_{0,1} & \\dotsb & x_{0,m-1} \\\\\n",
    "    x_{1,0} & x_{1,1} & \\dotsb & x_{1,m-1} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    x_{n-1,0} & x_{n-1,1} & \\dotsb & x_{n-1,m-1}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Then:\n",
    "\n",
    "$$\\overline{A} =\n",
    "\\begin{bmatrix}\n",
    "    \\overline{x}_{0,0} & \\overline{x}_{0,1} & \\dotsb & \\overline{x}_{0,m-1} \\\\\n",
    "    \\overline{x}_{1,0} & \\overline{x}_{1,1} & \\dotsb & \\overline{x}_{1,m-1} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    \\overline{x}_{n-1,0} & \\overline{x}_{n-1,1} & \\dotsb & \\overline{x}_{n-1,m-1}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "The conjugate of a matrix product equals to the product of conjugates of the matrices:\n",
    "\n",
    "$$\\overline{AB} = (\\overline{A})(\\overline{B})$$"
   ]
  },
  {
   "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",
    "> As a reminder, you can get the real and imaginary components of complex number `z` using `z.real` and `z.imag`, respectively.\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    To calculate the conjugate of a matrix take the conjugate of each element, check the <a href=\"../ComplexArithmetic/ComplexArithmetic.ipynb#Exercise-4:-Complex-conjugate.\">complex arithmetic tutorial</a> to see how to calculate the conjugate of a complex number.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def conjugate(a : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-6:-Conjugate.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adjoint\n",
    "\n",
    "The final important single-matrix operation is a combination of the above two. The **conjugate transpose**, also called the **adjoint** of matrix $A$, is defined as $A^\\dagger = \\overline{(A^T)} = (\\overline{A})^T$.\n",
    "\n",
    "A matrix is known as **Hermitian** or **self-adjoint** if it equals its own adjoint: $A = A^\\dagger$. For example, the following matrix is Hermitian:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    1 & i \\\\\n",
    "    -i & 2\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "The adjoint of a matrix product can be calculated as follows:\n",
    "\n",
    "$$(AB)^\\dagger = B^\\dagger A^\\dagger$$"
   ]
  },
  {
   "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",
    "> Don't forget, you can re-use functions you've written previously."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def adjoint(a : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-7:-Adjoint.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unitary Matrices\n",
    "\n",
    "**Unitary matrices** are very important for quantum computing. A matrix is unitary when it is invertible, and its inverse is equal to its adjoint: $U^{-1} = U^\\dagger$. That is, an $n \\times n$ square matrix $U$ is unitary if and only if $UU^\\dagger = U^\\dagger U = I_n$.\n",
    "\n",
    "For example, the following matrix is unitary:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\\n",
    "    \\frac{i}{\\sqrt{2}} & \\frac{-i}{\\sqrt{2}} \\\\\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "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.\n",
    "\n",
    "> Because of inaccuracy when dealing with floating point numbers on a computer (rounding errors), you won't always get the exact result you are expecting from a long series of calculations. To get around this, Python has a function `approx` which can be used to check if two numbers are \"close enough:\" `a == approx(b)`.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    Keep in mind, you have only implemented matrix inverses for $2 \\times 2$ matrices, and this exercise may give you larger inputs. There is a way to solve this without taking the inverse.\n",
    "</details>"
   ]
  },
  {
   "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",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-8:-Unitary-Verification.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Next Steps\n",
    "\n",
    "Congratulations! At this point, you should understand enough linear algebra to be able to get started with the tutorials on [the concept of qubit](../Qubit/Qubit.ipynb) and on [single-qubit quantum gates](../SingleQubitGates/SingleQubitGates.ipynb). The next section covers more advanced matrix operations that help explain the properties of qubits and quantum gates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II. Advanced Operations\n",
    "\n",
    "## Inner Product\n",
    "\n",
    "The **inner product** is yet another important matrix operation that is only applied to vectors. Given two vectors $V$ and $W$ of the same size, their inner product $\\langle V , W \\rangle$ is defined as a product of matrices $V^\\dagger$ and $W$:\n",
    "\n",
    "$$\\langle V , W \\rangle = V^\\dagger W$$\n",
    "\n",
    "Let's break this down so it's a bit easier to understand. A $1 \\times n$ matrix (the adjoint of an $n \\times 1$ vector) multiplied by an $n \\times 1$ vector results in a $1 \\times 1$ matrix (which is equivalent to a scalar). The result of an inner product is that scalar. \n",
    "\n",
    "To put it another way, to calculate the inner product of two vectors, take the corresponding elements $V_k$ and $W_k$, multiply the complex conjugate of $V_k$ by $W_k$, and add up those products:\n",
    "\n",
    "$$\\langle V , W \\rangle = \\sum_{k=0}^{n-1}\\overline{V_k}W_k$$\n",
    "\n",
    "Here is a simple example:\n",
    "\n",
    "$$\\langle\n",
    "\\begin{bmatrix}\n",
    "    -6 \\\\\n",
    "    9i\n",
    "\\end{bmatrix}\n",
    ",\n",
    "\\begin{bmatrix}\n",
    "    3 \\\\\n",
    "    -8\n",
    "\\end{bmatrix}\n",
    "\\rangle =\n",
    "\\begin{bmatrix}\n",
    "    -6 \\\\\n",
    "    9i\n",
    "\\end{bmatrix}^\\dagger\n",
    "\\begin{bmatrix}\n",
    "    3 \\\\\n",
    "    -8\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix} -6 & -9i \\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "    3 \\\\\n",
    "    -8\n",
    "\\end{bmatrix}\n",
    "= (-6) \\cdot (3) + (-9i) \\cdot (-8) = -18 + 72i$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are familiar with the **dot product**, you will notice that it is equivalent to inner product for real-numbered vectors.\n",
    "\n",
    "> We use our definition for these tutorials because it matches the notation used in quantum computing. You might encounter other sources which define the inner product a little differently: $\\langle V , W \\rangle = W^\\dagger V = V^T\\overline{W}$, in contrast to the $V^\\dagger W$ that we use. These definitions are almost equivalent, with some differences in the scalar multiplication by a complex number.\n",
    "\n",
    "An immediate application for the inner product is computing the **vector norm**. The norm of vector $V$ is defined as $||V|| = \\sqrt{\\langle V , V \\rangle}$. This condenses the vector down to a single non-negative real value. If the vector represents coordinates in space, the norm happens to be the length of the vector. A vector is called **normalized** if its norm is equal to $1$.\n",
    "\n",
    "The inner product has the following properties:\n",
    "\n",
    "* Distributivity over addition: $\\langle V + W , X \\rangle = \\langle V , X \\rangle + \\langle W , X \\rangle$ and $\\langle V , W + X \\rangle = \\langle V , W \\rangle + \\langle V , X \\rangle$\n",
    "* Partial associativity with scalar multiplication: $x \\cdot \\langle V , W \\rangle = \\langle \\overline{x}V , W \\rangle = \\langle V , xW \\rangle$\n",
    "* Skew symmetry: $\\langle V , W \\rangle = \\overline{\\langle W , V \\rangle}$\n",
    "* Multiplying a vector by a unitary matrix **preserves the vector's inner product with itself** (and therefore the vector's norm): $\\langle UV , UV \\rangle = \\langle V , V \\rangle$\n",
    "\n",
    "> Note that just like matrix multiplication, the inner product is **not commutative**: $\\langle V , W \\rangle$ won't always equal $\\langle W , V \\rangle$."
   ]
  },
  {
   "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$.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    A video explanation can be found <a href=\"https://www.youtube.com/watch?v=FCmH4MqbFGs\">here</a>.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def inner_prod(v : Matrix, w : Matrix) -> complex:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_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$.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    You might need the square root function to solve this exercise. As a reminder, <a href=https://docs.python.org/3/library/math.html#math.sqrt>Python's square root function</a> is available in the <code>math</code> library.<br>\n",
    "    A video explanation can be found <a href=\"https://www.youtube.com/watch?v=7fn03DIW3Ak\">here</a>. Note that when this method is used with complex vectors, you should take the modulus of the complex number for the division.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def normalize(v : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-10:-Normalized-vectors.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Outer Product\n",
    "\n",
    "The **outer product** of two vectors $V$ and $W$ is defined as $VW^\\dagger$. That is, the outer product of an $n \\times 1$ vector and an $m \\times 1$ vector is an $n \\times m$ matrix. If we denote the outer product of $V$ and $W$ as $X$, then $X_{i,j} = V_i \\cdot \\overline{W_j}$. \n",
    "\n",
    "Here is a simple example:\n",
    "outer product of $\\begin{bmatrix} -3i \\\\ 9 \\end{bmatrix}$ and $\\begin{bmatrix} 9i \\\\ 2 \\\\ 7 \\end{bmatrix}$ is:\n",
    "\n",
    "$$\\begin{bmatrix} \\color{blue} {-3i} \\\\ \\color{blue} 9 \\end{bmatrix}\n",
    "\\begin{bmatrix} \\color{red} {9i} \\\\ \\color{red} 2 \\\\ \\color{red} 7 \\end{bmatrix}^\\dagger\n",
    "=\n",
    "\\begin{bmatrix} \\color{blue} {-3i} \\\\ \\color{blue} 9 \\end{bmatrix}\n",
    "\\begin{bmatrix} \\color{red} {-9i} & \\color{red} 2 & \\color{red} 7 \\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    \\color{blue} {-3i} \\cdot \\color{red} {(-9i)} & \\color{blue} {-3i} \\cdot \\color{red} 2 & \\color{blue} {-3i} \\cdot \\color{red} 7 \\\\\n",
    "    \\color{blue} 9 \\cdot \\color{red} {(-9i)} & \\color{blue} 9 \\cdot \\color{red} 2 & \\color{blue} 9 \\cdot \\color{red} 7\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    -27 & -6i & -21i \\\\\n",
    "    -81i & 18 & 63\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def outer_prod(v : Matrix, w : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_LinearAlgebra.ipynb#Exercise-11:-Outer-product.).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tensor Product\n",
    "\n",
    "The **tensor product** is a different way of multiplying matrices. Rather than multiplying rows by columns, the tensor product multiplies the second matrix by every element of the first matrix.\n",
    "\n",
    "Given $n \\times m$ matrix $A$ and $k \\times l$ matrix $B$, their tensor product $A \\otimes B$ is an $(n \\cdot k) \\times (m \\cdot l)$ matrix defined as follows:\n",
    "\n",
    "$$A \\otimes B =\n",
    "\\begin{bmatrix}\n",
    "    A_{0,0} \\cdot B & A_{0,1} \\cdot B & \\dotsb & A_{0,m-1} \\cdot B \\\\\n",
    "    A_{1,0} \\cdot B & A_{1,1} \\cdot B & \\dotsb & A_{1,m-1} \\cdot B \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    A_{n-1,0} \\cdot B & A_{n-1,1} \\cdot B & \\dotsb & A_{n-1,m-1} \\cdot B\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    A_{0,0} \\cdot \\color{red} {\\begin{bmatrix}B_{0,0} & \\dotsb & B_{0,l-1} \\\\ \\vdots & \\ddots & \\vdots \\\\ B_{k-1,0} & \\dotsb & b_{k-1,l-1} \\end{bmatrix}} & \\dotsb &\n",
    "    A_{0,m-1} \\cdot \\color{blue} {\\begin{bmatrix}B_{0,0} & \\dotsb & B_{0,l-1} \\\\ \\vdots & \\ddots & \\vdots \\\\ B_{k-1,0} & \\dotsb & B_{k-1,l-1} \\end{bmatrix}} \\\\\n",
    "    \\vdots & \\ddots & \\vdots \\\\\n",
    "    A_{n-1,0} \\cdot \\color{blue} {\\begin{bmatrix}B_{0,0} & \\dotsb & B_{0,l-1} \\\\ \\vdots & \\ddots & \\vdots \\\\ B_{k-1,0} & \\dotsb & B_{k-1,l-1} \\end{bmatrix}} & \\dotsb &\n",
    "    A_{n-1,m-1} \\cdot \\color{red} {\\begin{bmatrix}B_{0,0} & \\dotsb & B_{0,l-1} \\\\ \\vdots & \\ddots & \\vdots \\\\ B_{k-1,0} & \\dotsb & B_{k-1,l-1} \\end{bmatrix}}\n",
    "\\end{bmatrix}\n",
    "= \\\\\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    A_{0,0} \\cdot \\color{red} {B_{0,0}} & \\dotsb & A_{0,0} \\cdot \\color{red} {B_{0,l-1}} & \\dotsb & A_{0,m-1} \\cdot \\color{blue} {B_{0,0}} & \\dotsb & A_{0,m-1} \\cdot \\color{blue} {B_{0,l-1}} \\\\\n",
    "    \\vdots & \\ddots & \\vdots & \\dotsb & \\vdots & \\ddots & \\vdots \\\\\n",
    "    A_{0,0} \\cdot \\color{red} {B_{k-1,0}} & \\dotsb & A_{0,0} \\cdot \\color{red} {B_{k-1,l-1}} & \\dotsb & A_{0,m-1} \\cdot \\color{blue} {B_{k-1,0}} & \\dotsb & A_{0,m-1} \\cdot \\color{blue} {B_{k-1,l-1}} \\\\\n",
    "    \\vdots & \\vdots & \\vdots & \\ddots & \\vdots & \\vdots & \\vdots \\\\\n",
    "    A_{n-1,0} \\cdot \\color{blue} {B_{0,0}} & \\dotsb & A_{n-1,0} \\cdot \\color{blue} {B_{0,l-1}} & \\dotsb & A_{n-1,m-1} \\cdot \\color{red} {B_{0,0}} & \\dotsb & A_{n-1,m-1} \\cdot \\color{red} {B_{0,l-1}} \\\\\n",
    "    \\vdots & \\ddots & \\vdots & \\dotsb & \\vdots & \\ddots & \\vdots \\\\\n",
    "    A_{n-1,0} \\cdot \\color{blue} {B_{k-1,0}} & \\dotsb & A_{n-1,0} \\cdot \\color{blue} {B_{k-1,l-1}} & \\dotsb & A_{n-1,m-1} \\cdot \\color{red} {B_{k-1,0}} & \\dotsb & A_{n-1,m-1} \\cdot \\color{red} {B_{k-1,l-1}}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Here is a simple example:\n",
    "\n",
    "$$\\begin{bmatrix} 1 & 2 \\\\ 3 & 4 \\end{bmatrix} \\otimes \\begin{bmatrix} 5 & 6 \\\\ 7 & 8 \\end{bmatrix} =\n",
    "\\begin{bmatrix}\n",
    "    1 \\cdot \\begin{bmatrix} 5 & 6 \\\\ 7 & 8 \\end{bmatrix} & 2 \\cdot \\begin{bmatrix} 5 & 6 \\\\ 7 & 8 \\end{bmatrix} \\\\\n",
    "    3 \\cdot \\begin{bmatrix} 5 & 6 \\\\ 7 & 8 \\end{bmatrix} & 4 \\cdot \\begin{bmatrix} 5 & 6 \\\\ 7 & 8 \\end{bmatrix}\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    1 \\cdot 5 & 1 \\cdot 6 & 2 \\cdot 5 & 2 \\cdot 6 \\\\\n",
    "    1 \\cdot 7 & 1 \\cdot 8 & 2 \\cdot 7 & 2 \\cdot 8 \\\\\n",
    "    3 \\cdot 5 & 3 \\cdot 6 & 4 \\cdot 5 & 4 \\cdot 6 \\\\\n",
    "    3 \\cdot 7 & 3 \\cdot 8 & 4 \\cdot 7 & 4 \\cdot 8\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    5 & 6 & 10 & 12 \\\\\n",
    "    7 & 8 & 14 & 16 \\\\\n",
    "    15 & 18 & 20 & 24 \\\\\n",
    "    21 & 24 & 28 & 32\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Notice that the tensor product of two vectors is another vector: if $V$ is an $n \\times 1$ vector, and $W$ is an $m \\times 1$ vector, $V \\otimes W$ is an $(n \\cdot m) \\times 1$ vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tensor product has the following properties:\n",
    "\n",
    "* Distributivity over addiotion: $(A + B) \\otimes C = A \\otimes C + B \\otimes C$, $A \\otimes (B + C) = A \\otimes B + A \\otimes C$\n",
    "* Associativity with scalar multiplication: $x(A \\otimes B) = (xA) \\otimes B = A \\otimes (xB)$\n",
    "* Mixed-product property (relation with matrix multiplication): $(A \\otimes B) (C \\otimes D) = (AC) \\otimes (BD)$"
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def tensor_product(a : Matrix, b : Matrix) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the* <i><a href=\"./Workbook_LinearAlgebra.ipynb#Exercise-12*:-Tensor-Product.\">Linear Algebra Workbook</a></i>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Next Steps\n",
    "\n",
    "At this point, you know enough to complete the tutorials on [the concept of qubit](../Qubit/Qubit.ipynb), [single-qubit gates](../SingleQubitGates/SingleQubitGates.ipynb), [multi-qubit systems](../MultiQubitSystems/MultiQubitSystems.ipynb), and [multi-qubit gates](../MultiQubitGates/MultiQubitGates.ipynb). \n",
    "The last part of this tutorial is a brief introduction to eigenvalues and eigenvectors, which are used for more advanced topics in quantum computing. \n",
    "Feel free to move on to the next tutorials, and come back here once you encounter eigenvalues and eigenvectors elsewhere."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part III: Eigenvalues and Eigenvectors\n",
    "\n",
    "Consider the following example of multiplying a matrix by a vector:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    1 & -3 & 3 \\\\\n",
    "    3 & -5 & 3 \\\\\n",
    "    6 & -6 & 4\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "    1 \\\\\n",
    "    1 \\\\\n",
    "    2\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "    4 \\\\\n",
    "    4 \\\\\n",
    "    8\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Notice that the resulting vector is just the initial vector multiplied by a scalar (in this case 4). This behavior is so noteworthy that it is described using a special set of terms.\n",
    "\n",
    "Given a nonzero $n \\times n$ matrix $A$, a nonzero vector $V$, and a scalar $x$, if $AV = xV$, then $x$ is an **eigenvalue** of $A$, and $V$ is an **eigenvector** of $A$ corresponding to that eigenvalue.\n",
    "\n",
    "The properties of eigenvalues and eigenvectors are used extensively in quantum computing. You can learn more about eigenvalues, eigenvectors, and their properties at [Wolfram MathWorld](http://mathworld.wolfram.com/Eigenvector.html) or on [Wikipedia](https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 13</span>: Finding an eigenvalue.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. An $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.\n",
    "\n",
    "> Note that in this task the matrices are real-valued.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    Multiply the matrix by the vector, then divide the elements of the result by the elements of the original vector. Don't forget though, some elements of the vector may be $0$.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def find_eigenvalue(a : Matrix, v : Matrix) -> float:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_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",
    "\n",
    "**Output:** Return any non-zero eigenvector of $A$ that is associated with $x$.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    A matrix and an eigenvalue will have multiple eigenvectors (infinitely many, in fact), but you only need to find one.<br/>\n",
    "    Try treating the elements of the vector as variables in a system of two equations. Watch out for division by $0$! \n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@exercise\n",
    "def find_eigenvector(a : Matrix, x : float) -> Matrix:\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Linear Algebra Workbook](./Workbook_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
}