{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-1 fw=all -->\n",
    "\n",
    "# Linear Algebra\n",
    "\n",
    "By now, we can load datasets into tensors\n",
    "and manipulate these tensors\n",
    "with basic mathematical operations.\n",
    "To start building sophisticated models,\n",
    "we will also need a few tools from linear algebra.\n",
    "This section offers a gentle introduction\n",
    "to the most essential concepts,\n",
    "starting from scalar arithmetic\n",
    "and ramping up to matrix multiplication.\n",
    "The notation introduced here is collected,\n",
    "together with the rest of the book's notation,\n",
    "in that section."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra"
   },
   "source": [
    "import torch"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-2 fw=all -->\n",
    "\n",
    "## The Objects\n",
    "\n",
    "Linear algebra deals in a small cast of objects: scalars, vectors,\n",
    "matrices, and higher-order tensors. We introduce each in turn, together\n",
    "with its notation and its realization in code.\n",
    "\n",
    "### Scalars\n",
    "\n",
    "Most everyday mathematics\n",
    "consists of manipulating\n",
    "numbers one at a time.\n",
    "Formally, we call these values *scalars*.\n",
    "For example, the temperature in Palo Alto\n",
    "is a balmy $72$ degrees Fahrenheit.\n",
    "If you wanted to convert the temperature to Celsius\n",
    "you would evaluate the expression\n",
    "$c = \\frac{5}{9}(f - 32)$, setting $f$ to $72$.\n",
    "In this equation, the values\n",
    "$5$, $9$, and $32$ are constant scalars.\n",
    "The variables $c$ and $f$\n",
    "in general represent unknown scalars.\n",
    "\n",
    "We denote scalars\n",
    "by ordinary lower-cased letters\n",
    "(e.g., $x$, $y$, and $z$)\n",
    "and the space of all (continuous)\n",
    "*real-valued* scalars by $\\mathbb{R}$.\n",
    "For expedience, we will skip past\n",
    "rigorous definitions of *spaces*:\n",
    "just remember that the expression $x \\in \\mathbb{R}$\n",
    "is a formal way to say that $x$ is a real-valued scalar.\n",
    "The symbol $\\in$ (pronounced \"in\")\n",
    "denotes membership in a set.\n",
    "For example, $x, y \\in \\{0, 1\\}$\n",
    "indicates that $x$ and $y$ are variables\n",
    "that can only take values $0$ or $1$.\n",
    "\n",
    "Scalars are implemented as tensors\n",
    "that contain only one element.\n",
    "Below, we assign two scalars\n",
    "and perform the familiar addition, multiplication,\n",
    "division, and exponentiation operations."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-scalars"
   },
   "source": [
    "x = torch.tensor(3.0)\n",
    "y = torch.tensor(2.0)\n",
    "\n",
    "x + y, x * y, x / y, x**y"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor(5.), tensor(6.), tensor(1.5000), tensor(9.))"
     },
     "metadata": {},
     "execution_count": 2
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-3 fw=all -->\n",
    "\n",
    "### Vectors\n",
    "\n",
    "For current purposes, you can think of a vector as a fixed-length array of scalars.\n",
    "As with their code counterparts,\n",
    "we call these scalars the *elements* of the vector\n",
    "(synonyms include *entries* and *components*).\n",
    "When vectors represent examples from real-world datasets,\n",
    "their values hold some real-world significance.\n",
    "For example, if we were training a model to predict\n",
    "the risk of a loan defaulting,\n",
    "we might associate each applicant with a vector\n",
    "whose components correspond to quantities\n",
    "like their income, length of employment,\n",
    "or number of previous defaults.\n",
    "If we were studying the risk of heart attack,\n",
    "each vector might represent a patient\n",
    "and its components might correspond to\n",
    "their most recent vital signs, cholesterol levels,\n",
    "minutes of exercise per day, etc.\n",
    "We denote vectors by bold lowercase letters,\n",
    "(e.g., $\\mathbf{x}$, $\\mathbf{y}$, and $\\mathbf{z}$).\n",
    "\n",
    "Vectors are implemented as $1^{\\textrm{st}}$-order tensors.\n",
    "In general, such tensors can have arbitrary lengths,\n",
    "subject to memory limitations.\n",
    "\n",
    "Caution: in Python, as in most programming languages,\n",
    "vector indices start at $0$, also known as *zero-based indexing*,\n",
    "whereas in linear algebra subscripts begin at $1$ (one-based indexing)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-vectors-1"
   },
   "source": [
    "x = torch.arange(3)\n",
    "x"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([0, 1, 2])"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-4 fw=all -->\n",
    "\n",
    "We can refer to an element of a vector by using a subscript.\n",
    "For example, $x_2$ denotes the second element of $\\mathbf{x}$.\n",
    "Since $x_2$ is a scalar, we do not bold it.\n",
    "By default, we visualize vectors\n",
    "by stacking their elements vertically:\n",
    "\n",
    "$$\\mathbf{x} =\\begin{bmatrix}x_{1}  \\\\ \\vdots  \\\\x_{n}\\end{bmatrix}.$$\n",
    "\n",
    "Here $x_1, \\ldots, x_n$ are elements of the vector.\n",
    "Later on, we will distinguish between such *column vectors*\n",
    "and *row vectors* whose elements are stacked horizontally.\n",
    "Recall that we access a tensor's elements via indexing."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-vectors-2"
   },
   "source": [
    "x[2]"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(2)"
     },
     "metadata": {},
     "execution_count": 4
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-5 fw=all -->\n",
    "\n",
    "To indicate that a vector contains $n$ elements,\n",
    "we write $\\mathbf{x} \\in \\mathbb{R}^n$.\n",
    "Formally, we call $n$ the *dimensionality* of the vector.\n",
    "In code, this corresponds to the tensor's length,\n",
    "accessible via Python's built-in `len` function."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-vectors-3"
   },
   "source": [
    "len(x)"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "3"
     },
     "metadata": {},
     "execution_count": 5
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-6 fw=all -->\n",
    "\n",
    "We can also access the length via the `shape` attribute.\n",
    "The shape is a tuple that indicates a tensor's length along each axis.\n",
    "Tensors with just one axis have shapes with just one element."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-vectors-4"
   },
   "source": [
    "x.shape"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "torch.Size([3])"
     },
     "metadata": {},
     "execution_count": 6
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-7 fw=all -->\n",
    "\n",
    "Oftentimes, the word \"dimension\" gets overloaded\n",
    "to mean both the number of axes\n",
    "and the length along a particular axis.\n",
    "To avoid this confusion,\n",
    "we use *order* to refer to the number of axes\n",
    "and *dimensionality* exclusively to refer\n",
    "to the number of components.\n",
    "(NumPy and the deep learning frameworks instead call the number of axes\n",
    "the array's *rank* or `ndim`; take care not to confuse this with the\n",
    "*rank* of a matrix in linear algebra, which is the number of linearly\n",
    "independent rows or columns; see that section.)\n",
    "\n",
    "\n",
    "### Matrices\n",
    "\n",
    "Just as scalars are $0^{\\textrm{th}}$-order tensors\n",
    "and vectors are $1^{\\textrm{st}}$-order tensors,\n",
    "matrices are $2^{\\textrm{nd}}$-order tensors.\n",
    "We denote matrices by bold capital letters\n",
    "(e.g., $\\mathbf{X}$, $\\mathbf{Y}$, and $\\mathbf{Z}$),\n",
    "and represent them in code by tensors with two axes.\n",
    "The expression $\\mathbf{A} \\in \\mathbb{R}^{m \\times n}$\n",
    "indicates that a matrix $\\mathbf{A}$\n",
    "contains $m \\times n$ real-valued scalars,\n",
    "arranged as $m$ rows and $n$ columns.\n",
    "When $m = n$, we say that a matrix is *square*.\n",
    "Visually, we can illustrate any matrix as a table.\n",
    "To refer to an individual element,\n",
    "we subscript both the row and column indices, e.g.,\n",
    "$a_{ij}$ is the value that belongs to $\\mathbf{A}$'s\n",
    "$i^{\\textrm{th}}$ row and $j^{\\textrm{th}}$ column:\n",
    "\n",
    "$$\\mathbf{A}=\\begin{bmatrix} a_{11} & a_{12} & \\cdots & a_{1n} \\\\ a_{21} & a_{22} & \\cdots & a_{2n} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ a_{m1} & a_{m2} & \\cdots & a_{mn} \\\\ \\end{bmatrix}.$$\n",
    "\n",
    "\n",
    "In code, we represent a matrix $\\mathbf{A} \\in \\mathbb{R}^{m \\times n}$\n",
    "by a $2^{\\textrm{nd}}$-order tensor with shape ($m$, $n$).\n",
    "We can convert any appropriately sized $m \\times n$ tensor\n",
    "into an $m \\times n$ matrix\n",
    "by passing the desired shape to `reshape`:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-matrices-1"
   },
   "source": [
    "A = torch.arange(6).reshape(3, 2)\n",
    "A"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[0, 1],\n        [2, 3],\n        [4, 5]])"
     },
     "metadata": {},
     "execution_count": 7
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-8 fw=all -->\n",
    "\n",
    "Sometimes we want to flip the axes.\n",
    "When we exchange a matrix's rows and columns,\n",
    "the result is called its *transpose*.\n",
    "Formally, we signify a matrix $\\mathbf{A}$'s transpose\n",
    "by $\\mathbf{A}^\\top$ and if $\\mathbf{B} = \\mathbf{A}^\\top$,\n",
    "then $b_{ij} = a_{ji}$ for all $i$ and $j$.\n",
    "Thus, the transpose of an $m \\times n$ matrix\n",
    "is an $n \\times m$ matrix:\n",
    "\n",
    "$$\n",
    "\\mathbf{A}^\\top =\n",
    "\\begin{bmatrix}\n",
    "    a_{11} & a_{21} & \\dots  & a_{m1} \\\\\n",
    "    a_{12} & a_{22} & \\dots  & a_{m2} \\\\\n",
    "    \\vdots & \\vdots & \\ddots  & \\vdots \\\\\n",
    "    a_{1n} & a_{2n} & \\dots  & a_{mn}\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "In code, we can access any matrix's transpose as follows:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-matrices-2"
   },
   "source": [
    "A.T"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[0, 2, 4],\n        [1, 3, 5]])"
     },
     "metadata": {},
     "execution_count": 8
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-9 fw=all -->\n",
    "\n",
    "Symmetric matrices are the subset of square matrices\n",
    "that are equal to their own transposes:\n",
    "$\\mathbf{A} = \\mathbf{A}^\\top$.\n",
    "The following matrix is symmetric:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-matrices-3"
   },
   "source": [
    "A = torch.tensor([[1, 2, 3], [2, 0, 4], [3, 4, 5]])\n",
    "(A == A.T).all()"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(True)"
     },
     "metadata": {},
     "execution_count": 9
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-10 fw=all -->\n",
    "\n",
    "Matrices are useful for representing datasets.\n",
    "Typically, rows correspond to individual records\n",
    "and columns correspond to distinct attributes.\n",
    "\n",
    "\n",
    "### Tensors\n",
    "\n",
    "While you can go far in machine learning\n",
    "with only scalars, vectors, and matrices,\n",
    "eventually you may need to work with\n",
    "higher-order tensors.\n",
    "Tensors give us a generic way of describing\n",
    "extensions to $n^{\\textrm{th}}$-order arrays.\n",
    "We call software objects of the *tensor class* \"tensors\"\n",
    "precisely because they too can have arbitrary numbers of axes.\n",
    "While it may be confusing to use the word\n",
    "*tensor* for both the mathematical object\n",
    "and its realization in code,\n",
    "our meaning should usually be clear from context.\n",
    "We denote general tensors by capital letters\n",
    "with a special font face\n",
    "(e.g., $\\mathsf{X}$, $\\mathsf{Y}$, and $\\mathsf{Z}$)\n",
    "and their indexing mechanism\n",
    "(e.g., $x_{ijk}$ and $[\\mathsf{X}]_{1, 2i-1, 3}$)\n",
    "follows naturally from that of matrices.\n",
    "\n",
    "Tensors will become more important\n",
    "when we start working with images.\n",
    "Each image arrives as a $3^{\\textrm{rd}}$-order tensor\n",
    "with axes corresponding to the height, width, and *channel*.\n",
    "At each spatial location, the intensities\n",
    "of each color (red, green, and blue)\n",
    "are stacked along the channel.\n",
    "Furthermore, a collection of images is represented\n",
    "in code by a $4^{\\textrm{th}}$-order tensor,\n",
    "where distinct images are indexed\n",
    "along the first axis.\n",
    "Higher-order tensors are constructed, as were vectors and matrices,\n",
    "by growing the number of shape components."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-tensors"
   },
   "source": [
    "torch.arange(24).reshape(2, 3, 4)"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[ 0,  1,  2,  3],\n         [ 4,  5,  6,  7],\n         [ 8,  9, 10, 11]],\n\n        [[12, 13, 14, 15],\n         [16, 17, 18, 19],\n         [20, 21, 22, 23]]])"
     },
     "metadata": {},
     "execution_count": 10
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-11 fw=all -->\n",
    "\n",
    "## Arithmetic and Reductions\n",
    "\n",
    "With the objects in hand, we turn to what we can do with them:\n",
    "elementwise arithmetic, and *reductions* that summarize a tensor\n",
    "along one or more of its axes.\n",
    "\n",
    "### Basic Properties of Tensor Arithmetic\n",
    "\n",
    "Scalars, vectors, matrices,\n",
    "and higher-order tensors\n",
    "all have some handy properties.\n",
    "For example, elementwise operations\n",
    "produce outputs that have the\n",
    "same shape as their operands."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-basic-properties-of-tensor-arithmetic-1"
   },
   "source": [
    "A = torch.arange(6, dtype=torch.float32).reshape(2, 3)\n",
    "B = A.clone()  # Assign a copy of A to B by allocating new memory\n",
    "A, A + B"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([[0., 1., 2.],\n         [3., 4., 5.]]),\n tensor([[ 0.,  2.,  4.],\n         [ 6.,  8., 10.]]))"
     },
     "metadata": {},
     "execution_count": 11
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-12 fw=all -->\n",
    "\n",
    "The elementwise product of two matrices\n",
    "is called their *Hadamard product* (denoted $\\odot$).\n",
    "We can spell out the entries\n",
    "of the Hadamard product of two matrices\n",
    "$\\mathbf{A}, \\mathbf{B} \\in \\mathbb{R}^{m \\times n}$:\n",
    "\n",
    "\n",
    "$$\n",
    "\\mathbf{A} \\odot \\mathbf{B} =\n",
    "\\begin{bmatrix}\n",
    "    a_{11}  b_{11} & a_{12}  b_{12} & \\dots  & a_{1n}  b_{1n} \\\\\n",
    "    a_{21}  b_{21} & a_{22}  b_{22} & \\dots  & a_{2n}  b_{2n} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    a_{m1}  b_{m1} & a_{m2}  b_{m2} & \\dots  & a_{mn}  b_{mn}\n",
    "\\end{bmatrix}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-basic-properties-of-tensor-arithmetic-2"
   },
   "source": [
    "A * B"
   ],
   "execution_count": 12,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[ 0.,  1.,  4.],\n        [ 9., 16., 25.]])"
     },
     "metadata": {},
     "execution_count": 12
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-13 fw=all -->\n",
    "\n",
    "Adding or multiplying a scalar and a tensor produces a result\n",
    "with the same shape as the original tensor.\n",
    "Here, each element of the tensor is added to (or multiplied by) the scalar."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-basic-properties-of-tensor-arithmetic-3"
   },
   "source": [
    "a = 2\n",
    "X = torch.arange(24).reshape(2, 3, 4)\n",
    "a + X, (a * X).shape"
   ],
   "execution_count": 13,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([[[ 2,  3,  4,  5],\n          [ 6,  7,  8,  9],\n          [10, 11, 12, 13]],\n \n         [[14, 15, 16, 17],\n          [18, 19, 20, 21],\n          [22, 23, 24, 25]]]),\n torch.Size([2, 3, 4]))"
     },
     "metadata": {},
     "execution_count": 13
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-14 fw=all -->\n",
    "\n",
    "### Reduction\n",
    "\n",
    "Often, we wish to calculate the sum of a tensor's elements.\n",
    "To express the sum of the elements in a vector $\\mathbf{x}$ of length $n$,\n",
    "we write $\\sum_{i=1}^n x_i$. There is a simple function for it:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-reduction-1"
   },
   "source": [
    "x = torch.arange(3, dtype=torch.float32)\n",
    "x, x.sum()"
   ],
   "execution_count": 14,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([0., 1., 2.]), tensor(3.))"
     },
     "metadata": {},
     "execution_count": 14
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-15 fw=all -->\n",
    "\n",
    "To express sums over the elements of tensors of arbitrary shape,\n",
    "we simply sum over all its axes.\n",
    "For example, the sum of the elements\n",
    "of an $m \\times n$ matrix $\\mathbf{A}$\n",
    "could be written $\\sum_{i=1}^{m} \\sum_{j=1}^{n} a_{ij}$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-reduction-2"
   },
   "source": [
    "A.shape, A.sum()"
   ],
   "execution_count": 15,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(torch.Size([2, 3]), tensor(15.))"
     },
     "metadata": {},
     "execution_count": 15
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-16 fw=all -->\n",
    "\n",
    "By default, invoking the sum function\n",
    "*reduces* a tensor along all of its axes,\n",
    "eventually producing a scalar.\n",
    "Our libraries also allow us to specify the axes\n",
    "along which the tensor should be reduced.\n",
    "To sum over all elements along the rows (axis 0),\n",
    "we specify `axis=0` in `sum`.\n",
    "Since the input matrix reduces along axis 0\n",
    "to generate the output vector,\n",
    "this axis is missing from the shape of the output."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-reduction-3"
   },
   "source": [
    "A.shape, A.sum(axis=0).shape"
   ],
   "execution_count": 16,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(torch.Size([2, 3]), torch.Size([3]))"
     },
     "metadata": {},
     "execution_count": 16
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-17 fw=all -->\n",
    "\n",
    "Specifying `axis=1` will reduce the column dimension (axis 1) by summing up elements of all the columns."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-reduction-4"
   },
   "source": [
    "A.shape, A.sum(axis=1).shape"
   ],
   "execution_count": 17,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(torch.Size([2, 3]), torch.Size([2]))"
     },
     "metadata": {},
     "execution_count": 17
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-18 fw=all -->\n",
    "\n",
    "Reducing a matrix along both rows and columns via summation\n",
    "is equivalent to summing up all the elements of the matrix."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-reduction-5"
   },
   "source": [
    "A.sum(axis=[0, 1]) == A.sum()  # Same as A.sum()"
   ],
   "execution_count": 18,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(True)"
     },
     "metadata": {},
     "execution_count": 18
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-19 fw=all -->\n",
    "\n",
    "A related quantity is the *mean*, also called the *average*.\n",
    "We calculate the mean by dividing the sum\n",
    "by the total number of elements.\n",
    "Because computing the mean is so common,\n",
    "it gets a dedicated library function\n",
    "that works analogously to `sum`."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-reduction-6"
   },
   "source": [
    "A.mean(), A.sum() / A.numel()"
   ],
   "execution_count": 19,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor(2.5000), tensor(2.5000))"
     },
     "metadata": {},
     "execution_count": 19
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-20 fw=all -->\n",
    "\n",
    "Likewise, the function for calculating the mean\n",
    "can also reduce a tensor along specific axes."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-reduction-7"
   },
   "source": [
    "A.mean(axis=0), A.sum(axis=0) / A.shape[0]"
   ],
   "execution_count": 20,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([1.5000, 2.5000, 3.5000]), tensor([1.5000, 2.5000, 3.5000]))"
     },
     "metadata": {},
     "execution_count": 20
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-21 fw=all -->\n",
    "\n",
    "### Non-Reduction Sum\n",
    "\n",
    "Sometimes it can be useful to keep the number of axes unchanged\n",
    "when invoking the function for calculating the sum or mean.\n",
    "This matters when we want to use the broadcast mechanism\n",
    "(that section)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-non-reduction-sum-1"
   },
   "source": [
    "sum_A = A.sum(axis=1, keepdims=True)\n",
    "sum_A, sum_A.shape"
   ],
   "execution_count": 21,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([[ 3.],\n         [12.]]),\n torch.Size([2, 1]))"
     },
     "metadata": {},
     "execution_count": 21
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-22 fw=all -->\n",
    "\n",
    "For instance, since `sum_A` keeps its two axes after summing each row,\n",
    "we can divide `A` by `sum_A` with broadcasting\n",
    "to create a matrix where each row sums up to $1$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-non-reduction-sum-2"
   },
   "source": [
    "A / sum_A"
   ],
   "execution_count": 22,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[0.0000, 0.3333, 0.6667],\n        [0.2500, 0.3333, 0.4167]])"
     },
     "metadata": {},
     "execution_count": 22
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-23 fw=all -->\n",
    "\n",
    "If we want to calculate the cumulative sum of elements of `A` along some axis,\n",
    "say `axis=0` (row by row), we can call the `cumsum` function.\n",
    "By design, this function does not reduce the input tensor along any axis."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-non-reduction-sum-3"
   },
   "source": [
    "A.cumsum(axis=0)"
   ],
   "execution_count": 23,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[0., 1., 2.],\n        [3., 5., 7.]])"
     },
     "metadata": {},
     "execution_count": 23
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-24 fw=all -->\n",
    "\n",
    "## Products\n",
    "\n",
    "So far, we have only performed elementwise operations, sums, and averages.\n",
    "Products mix elements across positions:\n",
    "the dot product, the matrix--vector product,\n",
    "and matrix--matrix multiplication.\n",
    "\n",
    "### Dot Products\n",
    "\n",
    "One of the most fundamental operations is the dot product.\n",
    "Given two vectors $\\mathbf{x}, \\mathbf{y} \\in \\mathbb{R}^d$,\n",
    "their *dot product* $\\mathbf{x}^\\top \\mathbf{y}$ (also known as *inner product*, $\\langle \\mathbf{x}, \\mathbf{y}  \\rangle$)\n",
    "is a sum over the products of the elements at the same position:\n",
    "$\\mathbf{x}^\\top \\mathbf{y} = \\sum_{i=1}^{d} x_i y_i$.\n",
    "As the figure shows, this one number admits two readings:\n",
    "algebraically it is elementwise-multiply-then-sum,\n",
    "and geometrically it measures how much the two vectors point\n",
    "in the same direction.\n",
    "\n",
    "![The dot product: algebraically, multiply matching entries and sum; geometrically, $\\mathbf{a} \\cdot \\mathbf{b} = \\|\\mathbf{a}\\| \\|\\mathbf{b}\\| \\cos\\theta$ measures alignment.](../img/linear-algebra-dot.svg)"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-dot-products-1"
   },
   "source": [
    "y = torch.ones(3, dtype = torch.float32)\n",
    "x, y, torch.dot(x, y)"
   ],
   "execution_count": 24,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([0., 1., 2.]), tensor([1., 1., 1.]), tensor(3.))"
     },
     "metadata": {},
     "execution_count": 24
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-25 fw=all -->\n",
    "\n",
    "Equivalently, we can calculate the dot product of two vectors\n",
    "by performing an elementwise multiplication followed by a sum:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-dot-products-2"
   },
   "source": [
    "torch.sum(x * y)"
   ],
   "execution_count": 25,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(3.)"
     },
     "metadata": {},
     "execution_count": 25
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-26 fw=all -->\n",
    "\n",
    "Dot products are useful in a wide range of contexts.\n",
    "For example, given some set of values,\n",
    "denoted by a vector $\\mathbf{x}  \\in \\mathbb{R}^n$,\n",
    "and a set of weights, denoted by $\\mathbf{w} \\in \\mathbb{R}^n$,\n",
    "the weighted sum of the values in $\\mathbf{x}$\n",
    "according to the weights $\\mathbf{w}$\n",
    "could be expressed as the dot product $\\mathbf{x}^\\top \\mathbf{w}$.\n",
    "When the weights are nonnegative\n",
    "and sum to $1$, i.e., $\\sum_{i=1}^{n} w_i = 1$,\n",
    "the dot product expresses a *weighted average*.\n",
    "\n",
    "To make the geometric reading precise:\n",
    "for any two nonzero vectors, the angle $\\theta$ between them satisfies\n",
    "\n",
    "$$\n",
    "\\cos\\theta = \\frac{\\mathbf{x}^\\top \\mathbf{y}}{\\|\\mathbf{x}\\| \\|\\mathbf{y}\\|},\n",
    "$$\n",
    "\n",
    "where $\\|\\mathbf{x}\\|$ denotes the *length* (norm) of $\\mathbf{x}$,\n",
    "formally introduced later in this section.\n",
    "In particular, after normalizing two vectors to have unit length,\n",
    "their dot product *is* the cosine of the angle between them:\n",
    "it equals $1$ when they point the same way, $0$ when they are\n",
    "perpendicular, and $-1$ when they point in opposite directions\n",
    "(the figure).\n",
    "Why is this ratio always in $[-1, 1]$?\n",
    "That is the *Cauchy--Schwarz inequality*\n",
    "$|\\mathbf{x}^\\top \\mathbf{y}| \\leq \\|\\mathbf{x}\\| \\|\\mathbf{y}\\|$,\n",
    "proved in that section.\n",
    "We can verify both facts numerically on one random pair\n",
    "(any draw will do):\n",
    "\n",
    "![Two unit vectors at angle $\\theta$: their dot product equals $\\cos\\theta$, ranging from $1$ (aligned) through $0$ (perpendicular) to $-1$ (opposed).](../img/mdl-prelim-cosine.svg)"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-dot-products-3"
   },
   "source": [
    "u, v = torch.randn(8), torch.randn(8)\n",
    "cos_theta = torch.dot(u, v) / (torch.norm(u) * torch.norm(v))\n",
    "torch.acos(cos_theta), torch.abs(torch.dot(u, v)) <= torch.norm(u) * torch.norm(v)"
   ],
   "execution_count": 26,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor(1.5027), tensor(True))"
     },
     "metadata": {},
     "execution_count": 26
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-27 fw=all -->\n",
    "\n",
    "### Matrix--Vector Products\n",
    "\n",
    "Now that we know how to calculate dot products,\n",
    "we can begin to understand the *product*\n",
    "between an $m \\times n$ matrix $\\mathbf{A}$\n",
    "and an $n$-dimensional vector $\\mathbf{x}$.\n",
    "To start off, we visualize our matrix\n",
    "in terms of its row vectors\n",
    "\n",
    "$$\\mathbf{A}=\n",
    "\\begin{bmatrix}\n",
    "\\mathbf{a}^\\top_{1} \\\\\n",
    "\\mathbf{a}^\\top_{2} \\\\\n",
    "\\vdots \\\\\n",
    "\\mathbf{a}^\\top_m \\\\\n",
    "\\end{bmatrix},$$\n",
    "\n",
    "where each $\\mathbf{a}^\\top_{i} \\in \\mathbb{R}^n$\n",
    "is a row vector representing the $i^\\textrm{th}$ row\n",
    "of the matrix $\\mathbf{A}$.\n",
    "\n",
    "The matrix--vector product $\\mathbf{A}\\mathbf{x}$\n",
    "is simply a column vector of length $m$,\n",
    "whose $i^\\textrm{th}$ element is the dot product\n",
    "$\\mathbf{a}^\\top_i \\mathbf{x}$:\n",
    "\n",
    "$$\n",
    "\\mathbf{A}\\mathbf{x}\n",
    "= \\begin{bmatrix}\n",
    "\\mathbf{a}^\\top_{1} \\\\\n",
    "\\mathbf{a}^\\top_{2} \\\\\n",
    "\\vdots \\\\\n",
    "\\mathbf{a}^\\top_m \\\\\n",
    "\\end{bmatrix}\\mathbf{x}\n",
    "= \\begin{bmatrix}\n",
    " \\mathbf{a}^\\top_{1} \\mathbf{x}  \\\\\n",
    " \\mathbf{a}^\\top_{2} \\mathbf{x} \\\\\n",
    "\\vdots\\\\\n",
    " \\mathbf{a}^\\top_{m} \\mathbf{x}\\\\\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "the figure traces the computation on a small example:\n",
    "each output entry is the dot product of one row of $\\mathbf{A}$\n",
    "with $\\mathbf{x}$.\n",
    "\n",
    "![The matrix--vector product $\\mathbf{A}\\mathbf{x}$: one dot product per row of $\\mathbf{A}$, so a $2\\times3$ matrix maps a length-3 vector to a length-2 vector.](../img/linear-algebra-matvec.svg)\n",
    "\n",
    "We can think of multiplication with a matrix\n",
    "$\\mathbf{A}\\in \\mathbb{R}^{m \\times n}$\n",
    "as a linear transformation that maps vectors\n",
    "from $\\mathbb{R}^{n}$ to $\\mathbb{R}^{m}$\n",
    "(a view developed in that section).\n",
    "For example, we can represent rotations\n",
    "as multiplications by certain square matrices:\n",
    "multiplying by\n",
    "$\\begin{bmatrix} \\cos\\theta & -\\sin\\theta \\\\ \\sin\\theta & \\cos\\theta \\end{bmatrix}$\n",
    "rotates any vector in the plane by the angle $\\theta$.\n",
    "For $\\theta = 90°$ the matrix is simple,\n",
    "and we can watch it turn one axis unit vector into the other:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-matrix-vector-products-2"
   },
   "source": [
    "R = torch.tensor([[0.0, -1.0], [1.0, 0.0]])  # Rotation by 90 degrees\n",
    "R @ torch.tensor([1.0, 0.0]), R @ torch.tensor([0.0, 1.0])"
   ],
   "execution_count": 27,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([0., 1.]), tensor([-1.,  0.]))"
     },
     "metadata": {},
     "execution_count": 27
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-28 fw=all -->\n",
    "\n",
    "Matrix--vector products also describe\n",
    "the key calculation involved in computing\n",
    "the outputs of each layer in a neural network\n",
    "given the outputs from the previous layer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-29 fw=pytorch -->\n",
    "\n",
    "To express a matrix--vector product in code,\n",
    "we use the `mv` function.\n",
    "Note that the column dimension of `A`\n",
    "(its length along axis 1)\n",
    "must be the same as the dimension of `x` (its length).\n",
    "Python has a convenience operator `@`\n",
    "that can execute both matrix--vector\n",
    "and matrix--matrix products\n",
    "(depending on its arguments).\n",
    "Thus we can write `A@x`."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-matrix-vector-products"
   },
   "source": [
    "A.shape, x.shape, torch.mv(A, x), A@x"
   ],
   "execution_count": 28,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(torch.Size([2, 3]), torch.Size([3]), tensor([ 5., 14.]), tensor([ 5., 14.]))"
     },
     "metadata": {},
     "execution_count": 28
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-30 fw=all -->\n",
    "\n",
    "### Matrix--Matrix Multiplication\n",
    "\n",
    "Once you have gotten the hang of dot products and matrix--vector products,\n",
    "then *matrix--matrix multiplication* should be straightforward.\n",
    "\n",
    "Say that we have two matrices\n",
    "$\\mathbf{A} \\in \\mathbb{R}^{n \\times k}$\n",
    "and $\\mathbf{B} \\in \\mathbb{R}^{k \\times m}$:\n",
    "\n",
    "$$\\mathbf{A}=\\begin{bmatrix}\n",
    " a_{11} & a_{12} & \\cdots & a_{1k} \\\\\n",
    " a_{21} & a_{22} & \\cdots & a_{2k} \\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    " a_{n1} & a_{n2} & \\cdots & a_{nk} \\\\\n",
    "\\end{bmatrix},\\quad\n",
    "\\mathbf{B}=\\begin{bmatrix}\n",
    " b_{11} & b_{12} & \\cdots & b_{1m} \\\\\n",
    " b_{21} & b_{22} & \\cdots & b_{2m} \\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    " b_{k1} & b_{k2} & \\cdots & b_{km} \\\\\n",
    "\\end{bmatrix}.$$\n",
    "\n",
    "\n",
    "Let $\\mathbf{a}^\\top_{i} \\in \\mathbb{R}^k$ denote\n",
    "the row vector representing the $i^\\textrm{th}$ row\n",
    "of the matrix $\\mathbf{A}$\n",
    "and let $\\mathbf{b}_{j} \\in \\mathbb{R}^k$ denote\n",
    "the column vector from the $j^\\textrm{th}$ column\n",
    "of the matrix $\\mathbf{B}$:\n",
    "\n",
    "$$\\mathbf{A}=\n",
    "\\begin{bmatrix}\n",
    "\\mathbf{a}^\\top_{1} \\\\\n",
    "\\mathbf{a}^\\top_{2} \\\\\n",
    "\\vdots \\\\\n",
    "\\mathbf{a}^\\top_n \\\\\n",
    "\\end{bmatrix},\n",
    "\\quad \\mathbf{B}=\\begin{bmatrix}\n",
    " \\mathbf{b}_{1} & \\mathbf{b}_{2} & \\cdots & \\mathbf{b}_{m} \\\\\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "\n",
    "To form the matrix product $\\mathbf{C} \\in \\mathbb{R}^{n \\times m}$,\n",
    "we simply compute each element $c_{ij}$\n",
    "as the dot product between\n",
    "the $i^{\\textrm{th}}$ row of $\\mathbf{A}$\n",
    "and the $j^{\\textrm{th}}$ column of $\\mathbf{B}$,\n",
    "i.e., $\\mathbf{a}^\\top_i \\mathbf{b}_j$:\n",
    "\n",
    "$$\\mathbf{C} = \\mathbf{AB} = \\begin{bmatrix}\n",
    "\\mathbf{a}^\\top_{1} \\\\\n",
    "\\mathbf{a}^\\top_{2} \\\\\n",
    "\\vdots \\\\\n",
    "\\mathbf{a}^\\top_n \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    " \\mathbf{b}_{1} & \\mathbf{b}_{2} & \\cdots & \\mathbf{b}_{m} \\\\\n",
    "\\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "\\mathbf{a}^\\top_{1} \\mathbf{b}_1 & \\mathbf{a}^\\top_{1}\\mathbf{b}_2& \\cdots & \\mathbf{a}^\\top_{1} \\mathbf{b}_m \\\\\n",
    " \\mathbf{a}^\\top_{2}\\mathbf{b}_1 & \\mathbf{a}^\\top_{2} \\mathbf{b}_2 & \\cdots & \\mathbf{a}^\\top_{2} \\mathbf{b}_m \\\\\n",
    " \\vdots & \\vdots & \\ddots &\\vdots\\\\\n",
    "\\mathbf{a}^\\top_{n} \\mathbf{b}_1 & \\mathbf{a}^\\top_{n}\\mathbf{b}_2& \\cdots& \\mathbf{a}^\\top_{n} \\mathbf{b}_m\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "We can think of the matrix--matrix multiplication $\\mathbf{AB}$\n",
    "as performing $m$ matrix--vector products\n",
    "or $m \\times n$ dot products\n",
    "and stitching the results together\n",
    "to form an $n \\times m$ matrix.\n",
    "the figure locates one such dot product:\n",
    "entry $c_{ij}$ sits at the intersection\n",
    "of row $i$ of $\\mathbf{A}$ and column $j$ of $\\mathbf{B}$.\n",
    "\n",
    "![Matrix--matrix multiplication: each entry $c_{ij}$ of $\\mathbf{C} = \\mathbf{AB}$ is the dot product of row $i$ of $\\mathbf{A}$ with column $j$ of $\\mathbf{B}$.](../img/linear-algebra-matmul.svg)\n",
    "\n",
    "In the following snippet,\n",
    "we perform matrix multiplication on `A` and `B`.\n",
    "Here, `A` is a matrix with two rows and three columns,\n",
    "and `B` is a matrix with three rows and four columns.\n",
    "After multiplication, we obtain a matrix with two rows and four columns."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-matrix-matrix-multiplication"
   },
   "source": [
    "B = torch.ones(3, 4)\n",
    "torch.mm(A, B), A@B"
   ],
   "execution_count": 29,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(tensor([[ 3.,  3.,  3.,  3.],\n         [12., 12., 12., 12.]]),\n tensor([[ 3.,  3.,  3.,  3.],\n         [12., 12., 12., 12.]]))"
     },
     "metadata": {},
     "execution_count": 29
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-31 fw=all -->\n",
    "\n",
    "The term *matrix--matrix multiplication* is\n",
    "often simplified to *matrix multiplication*,\n",
    "and should not be confused with the Hadamard product.\n",
    "\n",
    "\n",
    "## Norms\n",
    "\n",
    "Some of the most useful operators in linear algebra are *norms*.\n",
    "Informally, the norm of a vector tells us how *big* it is.\n",
    "For instance, the $\\ell_2$ norm measures\n",
    "the (Euclidean) length of a vector.\n",
    "Here, we are employing a notion of *size* that concerns the magnitude of a vector's components\n",
    "(not its dimensionality).\n",
    "\n",
    "A norm is a function $\\| \\cdot \\|$ that maps a vector\n",
    "to a scalar and satisfies the following three properties:\n",
    "\n",
    "1. Given any vector $\\mathbf{x}$, if we scale (all elements of) the vector\n",
    "   by a scalar $\\alpha \\in \\mathbb{R}$, its norm scales accordingly:\n",
    "   $$\\|\\alpha \\mathbf{x}\\| = |\\alpha| \\|\\mathbf{x}\\|.$$\n",
    "2. For any vectors $\\mathbf{x}$ and $\\mathbf{y}$:\n",
    "   norms satisfy the triangle inequality:\n",
    "   $$\\|\\mathbf{x} + \\mathbf{y}\\| \\leq \\|\\mathbf{x}\\| + \\|\\mathbf{y}\\|.$$\n",
    "3. The norm of a vector is nonnegative and it only vanishes if the vector is zero:\n",
    "   $$\\|\\mathbf{x}\\| > 0 \\textrm{ for all } \\mathbf{x} \\neq 0.$$\n",
    "\n",
    "Many functions are valid norms and different norms\n",
    "encode different notions of size.\n",
    "The Euclidean norm that we all learned in elementary school geometry\n",
    "when calculating the hypotenuse of a right triangle\n",
    "is the square root of the sum of squares of a vector's elements.\n",
    "Formally, this is called the $\\ell_2$ *norm* and expressed as\n",
    "\n",
    "$$\\|\\mathbf{x}\\|_2 = \\sqrt{\\sum_{i=1}^n x_i^2}.$$\n",
    "\n",
    "The method `norm` calculates the $\\ell_2$ norm."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-norms-1"
   },
   "source": [
    "u = torch.tensor([3.0, -4.0])\n",
    "torch.norm(u)"
   ],
   "execution_count": 30,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(5.)"
     },
     "metadata": {},
     "execution_count": 30
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-32 fw=all -->\n",
    "\n",
    "The $\\ell_1$ norm is also common\n",
    "and the associated measure is called the Manhattan distance.\n",
    "By definition, the $\\ell_1$ norm sums\n",
    "the absolute values of a vector's elements:\n",
    "\n",
    "$$\\|\\mathbf{x}\\|_1 = \\sum_{i=1}^n \\left|x_i \\right|.$$\n",
    "\n",
    "the figure contrasts the two on a single vector:\n",
    "the $\\ell_2$ norm is the straight-line distance to the origin,\n",
    "while the $\\ell_1$ norm is the distance walked along the grid.\n",
    "\n",
    "![Two notions of length for the same vector: the $\\ell_2$ norm measures straight-line (Euclidean) distance, while the $\\ell_1$ norm measures distance along the grid (Manhattan).](../img/linear-algebra-norms.svg)\n",
    "\n",
    "Compared to the $\\ell_2$ norm, it is less sensitive to outliers.\n",
    "To compute the $\\ell_1$ norm,\n",
    "we compose the absolute value\n",
    "with the sum operation."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-norms-2"
   },
   "source": [
    "torch.abs(u).sum()"
   ],
   "execution_count": 31,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(7.)"
     },
     "metadata": {},
     "execution_count": 31
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-33 fw=all -->\n",
    "\n",
    "Both the $\\ell_2$ and $\\ell_1$ norms are special cases\n",
    "of the more general $\\ell_p$ *norms*, defined for $p \\geq 1$ by\n",
    "\n",
    "$$\\|\\mathbf{x}\\|_p = \\left(\\sum_{i=1}^n \\left|x_i \\right|^p \\right)^{1/p}.$$\n",
    "\n",
    "(For $p < 1$ the formula above violates the triangle inequality,\n",
    "so it is not a norm.)\n",
    "Each of the three axioms can be verified in code.\n",
    "Here we check homogeneity and the triangle inequality\n",
    "for the $\\ell_2$ norm on random vectors:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-norms-4"
   },
   "source": [
    "u, v, alpha = torch.randn(6), torch.randn(6), -2.5\n",
    "print(torch.norm(alpha * u), abs(alpha) * torch.norm(u))\n",
    "print(torch.norm(u + v) <= torch.norm(u) + torch.norm(v))"
   ],
   "execution_count": 32,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "tensor(2.5362) tensor(2.5362)\ntensor(True)\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-34 fw=all -->\n",
    "\n",
    "For the $\\ell_2$ norm, the triangle inequality is\n",
    "the Cauchy--Schwarz inequality in disguise:\n",
    "expanding $\\|\\mathbf{u} + \\mathbf{v}\\|_2^2\n",
    "= \\|\\mathbf{u}\\|_2^2 + 2\\mathbf{u}^\\top\\mathbf{v} + \\|\\mathbf{v}\\|_2^2$\n",
    "and bounding $\\mathbf{u}^\\top\\mathbf{v}$\n",
    "by $\\|\\mathbf{u}\\|_2 \\|\\mathbf{v}\\|_2$\n",
    "yields exactly the triangle inequality\n",
    "(see that section).\n",
    "\n",
    "In the case of matrices, matters are more complicated.\n",
    "After all, matrices can be viewed both as collections of individual entries\n",
    "*and* as objects that operate on vectors and transform them into other vectors.\n",
    "For instance, we can ask by how much longer\n",
    "the matrix--vector product $\\mathbf{X} \\mathbf{v}$\n",
    "could be relative to $\\mathbf{v}$.\n",
    "This line of thought leads to what is called the *spectral* norm,\n",
    "whose full development (it equals the largest *singular value*\n",
    "of the matrix) appears in that section.\n",
    "For now, we introduce the *Frobenius norm*,\n",
    "which is much easier to compute and defined as\n",
    "the square root of the sum of the squares\n",
    "of a matrix's elements:\n",
    "\n",
    "$$\\|\\mathbf{X}\\|_\\textrm{F} = \\sqrt{\\sum_{i=1}^m \\sum_{j=1}^n x_{ij}^2}.$$\n",
    "\n",
    "The Frobenius norm behaves as if it were\n",
    "an $\\ell_2$ norm of a matrix-shaped vector.\n",
    "Invoking the following function will calculate\n",
    "the Frobenius norm of a matrix."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-norms-3"
   },
   "source": [
    "torch.norm(torch.ones((4, 9)))"
   ],
   "execution_count": 33,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(6.)"
     },
     "metadata": {},
     "execution_count": 33
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-35 fw=all -->\n",
    "\n",
    "In deep learning, we are often trying to solve optimization problems:\n",
    "*maximize* the probability assigned to observed data;\n",
    "*maximize* the revenue associated with a recommender model;\n",
    "*minimize* the distance between predictions\n",
    "and the ground truth observations;\n",
    "*minimize* the distance between representations\n",
    "of photos of the same person\n",
    "while *maximizing* the distance between representations\n",
    "of photos of different people.\n",
    "These distances, which constitute\n",
    "the objectives of deep learning algorithms,\n",
    "are often expressed as norms.\n",
    "\n",
    "### Eigenvalues: A First Look\n",
    "\n",
    "Norms ask how much a matrix can stretch a vector.\n",
    "A complementary question is whether there are directions\n",
    "that a square matrix does not turn at all.\n",
    "A nonzero vector $\\mathbf{v}$ is an *eigenvector*\n",
    "of a square matrix $\\mathbf{A}$, with associated *eigenvalue* $\\lambda$, if\n",
    "\n",
    "$$\\mathbf{A}\\mathbf{v} = \\lambda \\mathbf{v}.$$\n",
    "\n",
    "Along such a direction, multiplying by $\\mathbf{A}$\n",
    "reduces to multiplying by the scalar $\\lambda$:\n",
    "the vector is stretched (if $|\\lambda| > 1$),\n",
    "shrunk (if $|\\lambda| < 1$), or flipped (if $\\lambda < 0$),\n",
    "but never rotated.\n",
    "The library computes eigenvalues directly.\n",
    "Here we apply this to the symmetric matrix we met\n",
    "when discussing transposes;\n",
    "symmetric matrices are especially pleasant\n",
    "because all of their eigenvalues are real\n",
    "(shown in that section):"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-eigenvalues-1"
   },
   "source": [
    "S = torch.tensor([[1.0, 2, 3], [2, 0, 4], [3, 4, 5]])\n",
    "torch.linalg.eigvalsh(S)  # Eigenvalues of a symmetric matrix are real"
   ],
   "execution_count": 34,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([-2.2628, -0.5985,  8.8612])"
     },
     "metadata": {},
     "execution_count": 34
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-36 fw=all -->\n",
    "\n",
    "Eigenvalues answer the stretching question exactly\n",
    "for symmetric matrices: the spectral norm of a symmetric matrix\n",
    "equals the largest absolute eigenvalue $\\max_i |\\lambda_i|$\n",
    "(we state this without proof; see that section).\n",
    "They also govern what happens under *repeated* multiplication.\n",
    "Applying $\\mathbf{A}$ to an eigenvector $k$ times multiplies it\n",
    "by $\\lambda^k$, which explodes when $|\\lambda| > 1$\n",
    "and vanishes when $|\\lambda| < 1$.\n",
    "For a symmetric matrix such as $\\mathbf{S}$,\n",
    "a generic vector is a mixture of eigenvector components,\n",
    "so it is soon dominated by the component\n",
    "with the largest absolute eigenvalue.\n",
    "We can watch this happen: the factor by which the norm grows\n",
    "per multiplication approaches $\\max_i |\\lambda_i|$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "linear-algebra-eigenvalues-2"
   },
   "source": [
    "v = torch.randn(3)\n",
    "for _ in range(10):\n",
    "    prev, v = v, S @ v\n",
    "torch.norm(v) / torch.norm(prev)"
   ],
   "execution_count": 35,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor(8.8612)"
     },
     "metadata": {},
     "execution_count": 35
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-37 fw=all -->\n",
    "\n",
    "Deep networks multiply by many matrices in succession,\n",
    "so whether signals (and gradients) explode or vanish\n",
    "is governed by exactly this effect,\n",
    "as we will see when we analyze numerical stability\n",
    "in that section.\n",
    "The full story (eigendecompositions, their computation,\n",
    "and their uses) is developed in that section.\n",
    "\n",
    "\n",
    "## Discussion\n",
    "\n",
    "In this section, we have reviewed all the linear algebra\n",
    "that you will need to understand\n",
    "a significant chunk of modern deep learning.\n",
    "There is a lot more to it: matrix decompositions, for example,\n",
    "reveal low-dimensional structure in real-world datasets\n",
    "and power entire subfields of machine learning.\n",
    "But the best time to learn more mathematics\n",
    "is once you have gotten your hands dirty\n",
    "applying machine learning to real data,\n",
    "so we wrap up here.\n",
    "\n",
    "If you are eager to learn more linear algebra,\n",
    "start with that section,\n",
    "which develops eigendecompositions, the singular value decomposition,\n",
    "and their use in machine learning in full.\n",
    "For further reading, there are many excellent books and online resources;\n",
    "consider the crash courses by\n",
    "@Strang.1993, @Kolter.2008, and @Petersen.Pedersen.ea.2008 .\n",
    "\n",
    "To recap:\n",
    "\n",
    "* Scalars, vectors, matrices, and tensors are\n",
    "  the basic mathematical objects used in linear algebra\n",
    "  and have zero, one, two, and an arbitrary number of axes, respectively.\n",
    "* Tensors can be sliced or reduced along specified axes\n",
    "  via indexing, or operations such as `sum` and `mean`, respectively.\n",
    "* Elementwise products are called Hadamard products.\n",
    "  By contrast, dot products, matrix--vector products, and matrix--matrix products\n",
    "  are not elementwise operations and in general return objects\n",
    "  having shapes that are different from the operands.\n",
    "* Compared with a Hadamard product of two $n \\times n$ matrices, which costs\n",
    "  $O(n^2)$ arithmetic operations, the standard algorithm for their matrix\n",
    "  product costs $O(n^3)$. For rectangular shapes $(m,n)(n,k)$, its cost is\n",
    "  $O(mnk)$.\n",
    "* Norms capture various notions of the magnitude of a vector (or matrix),\n",
    "  and are commonly applied to the difference of two vectors\n",
    "  to measure their distance apart.\n",
    "* Common vector norms include the $\\ell_1$ and $\\ell_2$ norms.\n",
    "  For matrices, we introduced the *Frobenius* norm\n",
    "  and previewed the *spectral* norm,\n",
    "  which is developed in that section.\n",
    "* A square matrix scales its eigenvectors without rotating them:\n",
    "  $\\mathbf{A}\\mathbf{v} = \\lambda \\mathbf{v}$.\n",
    "  The largest absolute eigenvalue governs how repeated\n",
    "  multiplication amplifies or damps a vector.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Prove that the transpose of the transpose of a matrix is the matrix itself: $(\\mathbf{A}^\\top)^\\top = \\mathbf{A}$.\n",
    "1. Given two matrices $\\mathbf{A}$ and $\\mathbf{B}$, show that sum and transposition commute: $\\mathbf{A}^\\top + \\mathbf{B}^\\top = (\\mathbf{A} + \\mathbf{B})^\\top$.\n",
    "1. Given any square matrix $\\mathbf{A}$, is $\\mathbf{A} + \\mathbf{A}^\\top$ always symmetric? Can you prove the result by using only the results of the previous two exercises?\n",
    "1. We defined the tensor `X` of shape (2, 3, 4) in this section. What is the output of `len(X)`? Write your answer without implementing any code, then check your answer using code.\n",
    "1. For a tensor `X` of arbitrary shape, does `len(X)` always correspond to the length of a certain axis of `X`? What is that axis?\n",
    "1. Run `A / A.sum(axis=1)` and see what happens. Can you analyze the results?\n",
    "1. When traveling between two points in downtown Manhattan, what is the distance that you need to cover in terms of the coordinates, i.e., in terms of avenues and streets? Can you travel diagonally?\n",
    "1. Consider a tensor of shape (2, 3, 4). What are the shapes of the summation outputs along axes 0, 1, and 2?\n",
    "1. Feed a tensor with three or more axes to the `linalg.norm` function and observe its output. What does this function compute for tensors of arbitrary shape?\n",
    "1. Consider three large matrices, say $\\mathbf{A} \\in \\mathbb{R}^{2^{10} \\times 2^{16}}$, $\\mathbf{B} \\in \\mathbb{R}^{2^{16} \\times 2^{5}}$ and $\\mathbf{C} \\in \\mathbb{R}^{2^{5} \\times 2^{14}}$, initialized with Gaussian random variables. You want to compute the product $\\mathbf{A} \\mathbf{B} \\mathbf{C}$. Is there any difference in memory footprint and speed, depending on whether you compute $(\\mathbf{A} \\mathbf{B}) \\mathbf{C}$ or $\\mathbf{A} (\\mathbf{B} \\mathbf{C})$? Why?\n",
    "1. Consider three large matrices, say $\\mathbf{A} \\in \\mathbb{R}^{2^{10} \\times 2^{16}}$, $\\mathbf{B} \\in \\mathbb{R}^{2^{16} \\times 2^{5}}$ and $\\mathbf{C} \\in \\mathbb{R}^{2^{5} \\times 2^{16}}$. Is there any difference in speed depending on whether you compute $\\mathbf{A} \\mathbf{B}$ or $\\mathbf{A} \\mathbf{C}^\\top$? Why? What changes if you initialize $\\mathbf{C} = \\mathbf{B}^\\top$ without cloning memory? Why?\n",
    "1. Consider three matrices, say $\\mathbf{A}, \\mathbf{B}, \\mathbf{C} \\in \\mathbb{R}^{100 \\times 200}$. Construct a tensor with three axes by stacking $[\\mathbf{A}, \\mathbf{B}, \\mathbf{C}]$. What is the dimensionality? Slice out the second coordinate of the third axis to recover $\\mathbf{B}$. Check that your answer is correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=linear-algebra-md-38 fw=pytorch -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/31)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
