{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-1 fw=all -->\n",
    "\n",
    "# Geometry and Linear Algebraic Operations\n",
    "\n",
    "In that section, we encountered the basics of linear algebra\n",
    "and saw how it could be used to express common operations for transforming our data.\n",
    "Linear algebra is one of the pillars\n",
    "underlying much of the work that we do in deep learning\n",
    "and in machine learning more broadly.\n",
    "While that section contained enough machinery\n",
    "to communicate the mechanics of modern deep learning models,\n",
    "there is a lot more to the subject.\n",
    "In this section, we will go deeper,\n",
    "building geometric intuition for vectors, angles, projections,\n",
    "hyperplanes, and the way matrices reshape space.\n",
    "These pictures are the foundation for the two matrix decompositions\n",
    "that run through all of deep learning, which we develop in the\n",
    "sections that follow: *eigendecomposition*\n",
    "(that section), the tool for analyzing\n",
    "stability, PCA, and Hessians; and the *singular value decomposition*\n",
    "(that section), the tool behind low-rank\n",
    "approximation, conditioning, and LoRA.\n",
    "\n",
    "## Vectors and Their Geometry\n",
    "\n",
    "### Points and Directions\n",
    "\n",
    "A vector admits two common geometric readings, as a point or as a direction\n",
    "in space. We use the following imports throughout the section."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-imports"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import jax as d2l\n",
    "import jax\n",
    "from jax import numpy as jnp\n",
    "import numpy as np\n",
    "import tensorflow as tf"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-2 fw=all -->\n",
    "\n",
    "Read as a *point*, a vector's components give its location relative to a\n",
    "fixed reference called the *origin*: $\\mathbf{v} = [3,2]^\\top$ is the point\n",
    "$3$ units to the right of the origin and $2$ units up. This reading turns a\n",
    "dataset into a cloud of points, and a task such as telling pictures of cats\n",
    "from pictures of dogs into geometry: find a way to separate two clusters of\n",
    "points in space.\n",
    "\n",
    "Read as a *direction*, the same vector says \"take $3$ steps to the right and\n",
    "$2$ steps up.\" An arrow with that displacement can start anywhere, so all the\n",
    "parallel arrows in the figure are the same vector. (On\n",
    "notation: a single vector is by default a *column*, while in a matrix holding\n",
    "a tabular dataset each data example is conventionally a *row*, as described in\n",
    "that section.)\n",
    "\n",
    "![A vector can be read two ways: as a *point* whose first component is the $x$-coordinate and second is the $y$-coordinate (left), or as a *direction*, an arrow that can start anywhere, so every arrow shown is the same vector $(3,2)^\\top$ (right).](../img/mdl-la-vectors.svg)\n",
    "\n",
    "The direction view makes vector addition visual: follow one arrow, then the\n",
    "other, tip to tail, as in the figure.\n",
    "\n",
    "![We can visualize vector addition by first following one vector, and then another, placing them tip to tail.](../img/mdl-la-vector-add.svg)\n",
    "\n",
    "Vector subtraction has a similar interpretation: from the identity\n",
    "$\\mathbf{u} = \\mathbf{v} + (\\mathbf{u}-\\mathbf{v})$, the vector\n",
    "$\\mathbf{u}-\\mathbf{v}$ is the direction that takes us from the point\n",
    "$\\mathbf{v}$ to the point $\\mathbf{u}$.\n",
    "\n",
    "\n",
    "### Dot Products and Angles\n",
    "As we saw in that section,\n",
    "if we take two column vectors $\\mathbf{u}$ and $\\mathbf{v}$,\n",
    "we can form their dot product by computing:\n",
    "\n",
    "$$\\mathbf{u}^\\top\\mathbf{v} = \\sum_i u_i\\cdot v_i.$$\n",
    "\n",
    "Because the equation is symmetric, we will mirror the notation\n",
    "of classical multiplication and write\n",
    "\n",
    "$$\n",
    "\\mathbf{u}\\cdot\\mathbf{v} = \\mathbf{u}^\\top\\mathbf{v} = \\mathbf{v}^\\top\\mathbf{u},\n",
    "$$\n",
    "\n",
    "to highlight the fact that exchanging the order of the vectors will yield the same answer.\n",
    "\n",
    "The dot product the equation also admits a geometric interpretation: it is closely related to the angle between two vectors.  Consider the angle shown in the figure.\n",
    "\n",
    "![Between any two vectors in the plane there is a well defined angle $\\theta$.  We will see this angle is intimately tied to the dot product.](../img/mdl-la-angle.svg)\n",
    "\n",
    "To start, let's consider two specific vectors:\n",
    "\n",
    "$$\n",
    "\\mathbf{v} = (r,0) \\; \\textrm{and} \\; \\mathbf{w} = (s\\cos(\\theta), s \\sin(\\theta)).\n",
    "$$\n",
    "\n",
    "The vector $\\mathbf{v}$ is length $r$ and runs parallel to the $x$-axis,\n",
    "and the vector $\\mathbf{w}$ is of length $s$ and at angle $\\theta$ with the $x$-axis.\n",
    "If we compute the dot product of these two vectors, we see that\n",
    "\n",
    "$$\n",
    "\\mathbf{v}\\cdot\\mathbf{w} = rs\\cos(\\theta) = \\|\\mathbf{v}\\|\\|\\mathbf{w}\\|\\cos(\\theta).\n",
    "$$\n",
    "\n",
    "In short, for these two specific vectors the dot product, combined with the\n",
    "norms, tells us the angle between them. The same identity holds for **any**\n",
    "pair of vectors, in any number of dimensions. Two short arguments *justify*\n",
    "the formula and pin down exactly when it makes sense.\n",
    "\n",
    "The first argument is purely planar. Any two vectors $\\mathbf{v}$ and\n",
    "$\\mathbf{w}$, however many coordinates they have, both lie in the\n",
    "two-dimensional plane they span, and the angle $\\theta$ between them lives in\n",
    "that plane. So we lose nothing by reasoning in two dimensions. Expanding\n",
    "$\\|\\mathbf{v} - \\mathbf{w}\\|^2$ with the dot product gives\n",
    "\n",
    "$$\n",
    "\\|\\mathbf{v} - \\mathbf{w}\\|^2\n",
    " = (\\mathbf{v}-\\mathbf{w})\\cdot(\\mathbf{v}-\\mathbf{w})\n",
    " = \\|\\mathbf{v}\\|^2 - 2\\,\\mathbf{v}\\cdot\\mathbf{w} + \\|\\mathbf{w}\\|^2,\n",
    "$$\n",
    "\n",
    "while the planar law of cosines applied to the triangle with sides\n",
    "$\\mathbf{v}$, $\\mathbf{w}$, and $\\mathbf{v}-\\mathbf{w}$ gives\n",
    "\n",
    "$$\n",
    "\\|\\mathbf{v} - \\mathbf{w}\\|^2\n",
    " = \\|\\mathbf{v}\\|^2 + \\|\\mathbf{w}\\|^2 - 2\\,\\|\\mathbf{v}\\|\\|\\mathbf{w}\\|\\cos\\theta.\n",
    "$$\n",
    "\n",
    "Equating the two and cancelling $\\|\\mathbf{v}\\|^2 + \\|\\mathbf{w}\\|^2$ leaves the\n",
    "**geometric formula for the dot product**,\n",
    "\n",
    "$$\n",
    "\\mathbf{v}\\cdot\\mathbf{w} = \\|\\mathbf{v}\\|\\|\\mathbf{w}\\|\\cos\\theta,\n",
    "$$\n",
    "\n",
    "which we may solve for the angle:\n",
    "\n",
    "$$\\theta = \\arccos\\left(\\frac{\\mathbf{v}\\cdot\\mathbf{w}}{\\|\\mathbf{v}\\|\\|\\mathbf{w}\\|}\\right).$$\n",
    "\n",
    "Nothing in the computation referenced the ambient dimension, so\n",
    "the equation holds in three or three million dimensions\n",
    "without change.\n",
    "\n",
    "There is, however, a subtlety we must not skip. The function $\\arccos$ is only\n",
    "defined on the interval $[-1, 1]$, so the equation is\n",
    "meaningful *only if* the fraction inside it never escapes that interval. That\n",
    "this is guaranteed, in every dimension, is the content of the following\n",
    "inequality.\n",
    "\n",
    "**Proposition (Cauchy–Schwarz).** *For any vectors $\\mathbf{v}, \\mathbf{w}$,*\n",
    "\n",
    "$$\n",
    "|\\mathbf{v}\\cdot\\mathbf{w}| \\le \\|\\mathbf{v}\\|\\,\\|\\mathbf{w}\\|,\n",
    "$$\n",
    "\n",
    "*with equality if and only if $\\mathbf{v}$ and $\\mathbf{w}$ are collinear\n",
    "(one is a scalar multiple of the other).*\n",
    "\n",
    "**Proof.** If $\\mathbf{w} = \\mathbf{0}$ both sides are zero and there is\n",
    "nothing to prove, so assume $\\mathbf{w} \\neq \\mathbf{0}$. The trick is to look\n",
    "at the squared length of $\\mathbf{v} - t\\mathbf{w}$ as a function of the real\n",
    "number $t$. A squared length is never negative, so\n",
    "\n",
    "$$\n",
    "q(t) = \\|\\mathbf{v} - t\\mathbf{w}\\|^2\n",
    "     = \\|\\mathbf{w}\\|^2\\, t^2 - 2(\\mathbf{v}\\cdot\\mathbf{w})\\, t + \\|\\mathbf{v}\\|^2\n",
    "     \\;\\ge\\; 0\n",
    "     \\quad\\textrm{for every } t.\n",
    "$$\n",
    "\n",
    "This is a quadratic in $t$ with positive leading coefficient $\\|\\mathbf{w}\\|^2$.\n",
    "A quadratic that stays non-negative cannot have two distinct real roots, so its\n",
    "discriminant must be $\\le 0$:\n",
    "\n",
    "$$\n",
    "\\bigl(2\\,\\mathbf{v}\\cdot\\mathbf{w}\\bigr)^2 - 4\\,\\|\\mathbf{w}\\|^2\\,\\|\\mathbf{v}\\|^2 \\le 0,\n",
    "\\qquad\\textrm{i.e.}\\qquad\n",
    "(\\mathbf{v}\\cdot\\mathbf{w})^2 \\le \\|\\mathbf{v}\\|^2\\,\\|\\mathbf{w}\\|^2.\n",
    "$$\n",
    "\n",
    "Taking square roots gives the equation. Equality forces the\n",
    "discriminant to vanish, which means $q$ has a (repeated) real root $t^\\star$\n",
    "with $q(t^\\star) = \\|\\mathbf{v} - t^\\star\\mathbf{w}\\|^2 = 0$, that is\n",
    "$\\mathbf{v} = t^\\star \\mathbf{w}$. $\\blacksquare$\n",
    "\n",
    "The whole argument used nothing but the fact that *a squared length is\n",
    "non-negative*. Dividing the equation by\n",
    "$\\|\\mathbf{v}\\|\\|\\mathbf{w}\\|$ for nonzero $\\mathbf{v}, \\mathbf{w}$ yields the\n",
    "**well-definedness of the angle**:\n",
    "\n",
    "$$\n",
    "-1 \\;\\le\\; \\frac{\\mathbf{v}\\cdot\\mathbf{w}}{\\|\\mathbf{v}\\|\\,\\|\\mathbf{w}\\|} \\;\\le\\; 1,\n",
    "$$\n",
    "\n",
    "so the $\\arccos$ in the equation is always defined and\n",
    "$\\theta$ is a genuine angle in $[0, \\pi]$, no matter the dimension. The\n",
    "equality cases are exactly the familiar ones: $\\cos\\theta = +1$ ($\\theta = 0$)\n",
    "when the vectors point the same way, and $\\cos\\theta = -1$ ($\\theta = \\pi$)\n",
    "when they point in opposite directions, precisely the collinear cases of the\n",
    "proposition.\n",
    "\n",
    "Cauchy–Schwarz also has a one-picture summary, shown in\n",
    "the figure. It is a way to *remember* the inequality\n",
    "rather than a second proof, since the picture reads off the angle $\\theta$\n",
    "(and with it the equation) that Cauchy–Schwarz itself makes\n",
    "legitimate.\n",
    "On the left, the projection of $\\mathbf{v}$\n",
    "onto $\\mathbf{w}$ has signed length $\\|\\mathbf{v}\\|\\cos\\theta$, and the residual\n",
    "$\\mathbf{r} = \\mathbf{v} - \\operatorname{proj}_{\\mathbf{w}}\\mathbf{v}$ meets\n",
    "$\\mathbf{w}$ at a right angle (we prove both facts in the next section). Because\n",
    "the right triangle's hypotenuse $\\mathbf{v}$ can be no shorter than its leg,\n",
    "$\\|\\mathbf{v}\\|\\,|\\cos\\theta| \\le \\|\\mathbf{v}\\|$, which is exactly\n",
    "$|\\mathbf{v}\\cdot\\mathbf{w}| \\le \\|\\mathbf{v}\\|\\|\\mathbf{w}\\|$. On the right is\n",
    "the equality case: when $\\mathbf{v}$ is collinear with $\\mathbf{w}$ the residual\n",
    "vanishes and the inequality becomes an equality.\n",
    "\n",
    "![Left: the orthogonal projection of $\\mathbf{v}$ onto $\\mathbf{w}$ has signed length $\\|\\mathbf{v}\\|\\cos\\theta$, and the residual $\\mathbf{r}$ meets $\\mathbf{w}$ at a right angle, so $\\mathbf{v}$ is the hypotenuse of a right triangle. Right: the Cauchy–Schwarz equality case, where $\\mathbf{v}$ is collinear with $\\mathbf{w}$ and the residual vanishes.](../img/mdl-la-projection.svg)\n",
    "\n",
    "Cauchy–Schwarz immediately gives the **triangle inequality**, which says\n",
    "that a detour through a third point is never shorter than going straight.\n",
    "\n",
    "**Corollary (triangle inequality).** *For any $\\mathbf{v}, \\mathbf{w}$,*\n",
    "$\\|\\mathbf{v} + \\mathbf{w}\\| \\le \\|\\mathbf{v}\\| + \\|\\mathbf{w}\\|$.\n",
    "\n",
    "**Proof.** Expand and apply the equation:\n",
    "\n",
    "$$\n",
    "\\|\\mathbf{v} + \\mathbf{w}\\|^2\n",
    " = \\|\\mathbf{v}\\|^2 + 2\\,\\mathbf{v}\\cdot\\mathbf{w} + \\|\\mathbf{w}\\|^2\n",
    " \\le \\|\\mathbf{v}\\|^2 + 2\\,\\|\\mathbf{v}\\|\\|\\mathbf{w}\\| + \\|\\mathbf{w}\\|^2\n",
    " = \\bigl(\\|\\mathbf{v}\\| + \\|\\mathbf{w}\\|\\bigr)^2.\n",
    "$$\n",
    "\n",
    "Taking square roots gives the claim. $\\blacksquare$\n",
    "\n",
    "As a simple example, let's see how to compute the angle between a pair of vectors:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-dot-products-and-angles"
   },
   "source": [
    "import numpy as onp\n",
    "def angle(v, w):\n",
    "    return onp.arccos(v.dot(w) / (onp.linalg.norm(v) * onp.linalg.norm(w)))\n",
    "\n",
    "angle(onp.array([0, 1, 2]), onp.array([2, 3, 4]))"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "np.float64(0.4189900840328574)"
     },
     "metadata": {},
     "execution_count": 2
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-3 fw=all -->\n",
    "\n",
    "Two vectors whose angle is $\\pi/2$ (equivalently $90^{\\circ}$) are called\n",
    "*orthogonal*. From the equation, the angle is $\\pi/2$ exactly when\n",
    "$\\cos\\theta = 0$, and since $\\|\\mathbf{v}\\|\\|\\mathbf{w}\\| \\neq 0$ for nonzero\n",
    "vectors, this happens if and only if the dot product itself vanishes. We\n",
    "therefore *define* two vectors to be **orthogonal when**\n",
    "$\\mathbf{v}\\cdot\\mathbf{w} = 0$. (We take this as the definition because it\n",
    "extends gracefully to the zero vector, which is orthogonal to everything even\n",
    "though no angle is defined for it.) We will use this condition throughout the\n",
    "chapter.\n",
    "\n",
    "### Projection and Orthogonality\n",
    "\n",
    "Cauchy–Schwarz answers \"how aligned are two vectors?\"; the closely related\n",
    "operation of *projection* answers \"how much of $\\mathbf{v}$ points along\n",
    "$\\mathbf{w}$?\" Geometrically, we look for the point on the line\n",
    "$\\{t\\mathbf{w} : t \\in \\mathbb{R}\\}$ that is closest to $\\mathbf{v}$.\n",
    "\n",
    "**Proposition (orthogonal projection).** *Let $\\mathbf{w} \\neq \\mathbf{0}$. The\n",
    "closest multiple of $\\mathbf{w}$ to $\\mathbf{v}$ is*\n",
    "\n",
    "$$\n",
    "\\operatorname{proj}_{\\mathbf{w}}\\mathbf{v}\n",
    " = \\frac{\\mathbf{v}\\cdot\\mathbf{w}}{\\mathbf{w}\\cdot\\mathbf{w}}\\,\\mathbf{w},\n",
    "$$\n",
    "\n",
    "*and the residual $\\mathbf{r} = \\mathbf{v} - \\operatorname{proj}_{\\mathbf{w}}\\mathbf{v}$\n",
    "is orthogonal to $\\mathbf{w}$.*\n",
    "\n",
    "**Proof.** We minimize the squared distance\n",
    "$f(t) = \\|\\mathbf{v} - t\\mathbf{w}\\|^2\n",
    " = \\|\\mathbf{w}\\|^2 t^2 - 2(\\mathbf{v}\\cdot\\mathbf{w})\\,t + \\|\\mathbf{v}\\|^2$.\n",
    "This is a convex parabola in $t$; setting $f'(t) = 2\\|\\mathbf{w}\\|^2 t -\n",
    "2(\\mathbf{v}\\cdot\\mathbf{w}) = 0$ gives the unique minimizer\n",
    "$t^\\star = \\dfrac{\\mathbf{v}\\cdot\\mathbf{w}}{\\mathbf{w}\\cdot\\mathbf{w}}$, which\n",
    "is the equation. For orthogonality of the residual, compute\n",
    "\n",
    "$$\n",
    "\\mathbf{r}\\cdot\\mathbf{w}\n",
    " = \\mathbf{v}\\cdot\\mathbf{w}\n",
    "   - \\frac{\\mathbf{v}\\cdot\\mathbf{w}}{\\mathbf{w}\\cdot\\mathbf{w}}\\,(\\mathbf{w}\\cdot\\mathbf{w})\n",
    " = 0. \\qquad \\blacksquare\n",
    "$$\n",
    "\n",
    "Because $\\mathbf{r}$ is orthogonal to $\\operatorname{proj}_{\\mathbf{w}}\\mathbf{v}$\n",
    "(which is a multiple of $\\mathbf{w}$), the decomposition\n",
    "$\\mathbf{v} = \\operatorname{proj}_{\\mathbf{w}}\\mathbf{v} + \\mathbf{r}$ splits\n",
    "$\\mathbf{v}$ into two perpendicular pieces, and **Pythagoras** applies:\n",
    "\n",
    "$$\n",
    "\\|\\mathbf{v}\\|^2 = \\|\\operatorname{proj}_{\\mathbf{w}}\\mathbf{v}\\|^2 + \\|\\mathbf{r}\\|^2 .\n",
    "$$\n",
    "\n",
    "Two remarks tie this back to the rest of the section. First, the *signed\n",
    "length* of the projection is\n",
    "\n",
    "$$\n",
    "\\frac{\\mathbf{v}\\cdot\\mathbf{w}}{\\|\\mathbf{w}\\|} = \\|\\mathbf{v}\\|\\cos\\theta ,\n",
    "$$\n",
    "\n",
    "which is exactly the quantity the hyperplane discussion below will use, so the\n",
    "hyperplane material is now fully self-contained. Second, we just solved a\n",
    "*least-squares* problem in one dimension: we found the best approximation of\n",
    "$\\mathbf{v}$ from the subspace spanned by $\\mathbf{w}$. We state the general\n",
    "version below, as soon as the vocabulary of subspaces and bases is in hand.\n",
    "\n",
    "### Span, Bases, and Subspaces\n",
    "\n",
    "The projection result spoke of \"the one-dimensional subspace spanned by\n",
    "$\\mathbf{w}$,\" and the planar argument for the dot-product formula reasoned\n",
    "inside the plane that two vectors span. These words (*span*, *subspace*,\n",
    "*basis*) are the organizing vocabulary of linear algebra, and the\n",
    "decompositions later in this chapter lean on them constantly, so let us pin\n",
    "them down. \n",
    "\n",
    "Given vectors $\\mathbf{v}_1, \\ldots, \\mathbf{v}_k$, their **span** is the set\n",
    "of everything reachable by scaling and adding them:\n",
    "\n",
    "$$\n",
    "\\operatorname{span}(\\mathbf{v}_1, \\ldots, \\mathbf{v}_k)\n",
    " = \\bigl\\{ a_1\\mathbf{v}_1 + \\cdots + a_k\\mathbf{v}_k\n",
    "   : a_1, \\ldots, a_k \\in \\mathbb{R} \\bigr\\}.\n",
    "$$\n",
    "\n",
    "A weighted sum $a_1\\mathbf{v}_1 + \\cdots + a_k\\mathbf{v}_k$ is called a\n",
    "*linear combination*, so the span is the set of all linear combinations. In\n",
    "$\\mathbb{R}^2$ the possibilities are easy to picture\n",
    "(the figure): the span of a single nonzero vector is the line\n",
    "through the origin in its direction, while the span of two vectors that do not\n",
    "lie on a common line is the entire plane. A span is closed under further\n",
    "addition and scaling, and any set of vectors with that closure property is\n",
    "called a **subspace**. The complete list of subspaces of $\\mathbb{R}^2$ is\n",
    "short: the origin alone, the lines through the origin, and $\\mathbb{R}^2$\n",
    "itself; in $\\mathbb{R}^3$, the planes through the origin join the list. Note\n",
    "that every subspace contains the origin (scale any of its elements by zero),\n",
    "so a line that misses the origin is not a subspace.\n",
    "\n",
    "![Left: the span of a single nonzero vector $\\mathbf{v}$, the set of all of its scalar multiples, is the line through the origin in its direction, a one-dimensional subspace. Right: two vectors not on a common line span the whole plane; the dashed parallelogram construction resolves $\\mathbf{x}$ as $2\\mathbf{u} + \\mathbf{w}$, coordinates that are unique because $\\mathbf{u}$ and $\\mathbf{w}$ are linearly independent.](../img/mdl-la-span.svg)\n",
    "\n",
    "A spanning set can be wasteful. If one of the vectors already lies in the span\n",
    "of the others, deleting it shrinks the list without shrinking the span. A\n",
    "collection with no such redundancy (equivalently, one where the only linear\n",
    "combination producing $a_1\\mathbf{v}_1 + \\cdots + a_k\\mathbf{v}_k = \\mathbf{0}$\n",
    "is the trivial one with every $a_i = 0$) is called **linearly independent**.\n",
    "(We return to the redundant case, *linear dependence*, when we study matrices\n",
    "and rank below.) A **basis** of a subspace is a linearly independent set that\n",
    "spans it: enough vectors to reach everything, none to spare. The coordinate\n",
    "vectors $\\mathbf{e}_1 = [1, 0]^\\top$ and $\\mathbf{e}_2 = [0, 1]^\\top$ form the\n",
    "*standard basis* of $\\mathbb{R}^2$, but the slanted pair in\n",
    "the figure is an equally valid basis. A fundamental theorem,\n",
    "which we will use without proof, says that every basis of a given subspace has\n",
    "the same number of elements, and that any linearly independent set can be\n",
    "extended to a basis; these are the two facts we take on faith in this chapter.\n",
    "The common count of basis elements is the subspace's\n",
    "**dimension**. That gives, at last, a precise meaning to the $d$ in\n",
    "\"$d$-dimensional space\": $\\mathbb{R}^d$ has dimension $d$ because\n",
    "$\\mathbf{e}_1, \\ldots, \\mathbf{e}_d$ is a basis for it.\n",
    "\n",
    "What independence buys is *coordinates*.\n",
    "\n",
    "**Proposition (coordinates are unique).** *Let $\\mathbf{v}_1, \\ldots,\n",
    "\\mathbf{v}_k$ be a basis of a subspace $S$. Then every $\\mathbf{x} \\in S$ can\n",
    "be written as $\\mathbf{x} = a_1\\mathbf{v}_1 + \\cdots + a_k\\mathbf{v}_k$ for\n",
    "exactly one choice of coefficients $a_1, \\ldots, a_k$.*\n",
    "\n",
    "**Proof.** At least one representation exists because the basis spans $S$. If\n",
    "there were two, say\n",
    "$\\mathbf{x} = \\sum_i a_i \\mathbf{v}_i = \\sum_i b_i \\mathbf{v}_i$, then\n",
    "subtracting gives $\\sum_i (a_i - b_i)\\,\\mathbf{v}_i = \\mathbf{0}$, and linear\n",
    "independence forces $a_i = b_i$ for every $i$. $\\blacksquare$\n",
    "\n",
    "A basis therefore turns an abstract subspace into a concrete copy of\n",
    "$\\mathbb{R}^k$: once the basis is agreed upon, the coefficient list\n",
    "$(a_1, \\ldots, a_k)$ *is* the point. Much of applied linear algebra is the art\n",
    "of choosing a basis in which a problem's coordinates become simple; the\n",
    "eigenvector and singular-vector bases of the next two sections are chosen for\n",
    "exactly this reason.\n",
    "\n",
    "Finally, two subspaces attach to every matrix $\\mathbf{A}$, and they organize\n",
    "everything matrices do in the remainder of this chapter. The **column space**\n",
    "of $\\mathbf{A}$ is the span of its columns; since the product\n",
    "$\\mathbf{A}\\mathbf{v}$ is exactly the linear combination of the columns of\n",
    "$\\mathbf{A}$ weighted by the entries of $\\mathbf{v}$ (a fact we put to work\n",
    "when we take up matrices as maps below), the column space is the set of all\n",
    "possible *outputs* of $\\mathbf{A}$. The **null space** of $\\mathbf{A}$ is the\n",
    "set of inputs sent to zero, $\\{\\mathbf{x} : \\mathbf{A}\\mathbf{x} =\n",
    "\\mathbf{0}\\}$; it is a subspace because if $\\mathbf{A}\\mathbf{x} =\n",
    "\\mathbf{A}\\mathbf{y} = \\mathbf{0}$ then $\\mathbf{A}(a\\mathbf{x} + b\\mathbf{y})\n",
    "= a\\,\\mathbf{A}\\mathbf{x} + b\\,\\mathbf{A}\\mathbf{y} = \\mathbf{0}$. In words:\n",
    "the column space records what a matrix can produce, and the null space records\n",
    "what it destroys. We will measure the first when we define the *rank* below,\n",
    "and meet both again among the SVD's *four fundamental subspaces* in\n",
    "that section.\n",
    "\n",
    "### Projection onto a Subspace\n",
    "\n",
    "The projection proposition dropped $\\mathbf{v}$ onto a line. With subspaces\n",
    "and bases in hand, we can state the general version promised there: the same\n",
    "formula, one matrix heavier, drops a vector onto an arbitrary subspace. Call a\n",
    "basis $\\mathbf{q}_1, \\ldots, \\mathbf{q}_k$ of a subspace $S \\subseteq\n",
    "\\mathbb{R}^n$ **orthonormal** when each vector has unit length and distinct\n",
    "vectors are orthogonal; compactly, $\\mathbf{Q}^\\top\\mathbf{Q} = \\mathbf{I}_k$,\n",
    "where $\\mathbf{Q}$ is the $n \\times k$ matrix with the $\\mathbf{q}_i$ as\n",
    "columns.\n",
    "\n",
    "**Proposition (projection onto a subspace).** *Let $\\mathbf{Q}$ have\n",
    "orthonormal columns spanning $S$, and set $\\mathbf{P} =\n",
    "\\mathbf{Q}\\mathbf{Q}^\\top$. Then for every $\\mathbf{x} \\in \\mathbb{R}^n$:*\n",
    "(i) *$\\mathbf{P}\\mathbf{x} \\in S$, and the residual $\\mathbf{x} -\n",
    "\\mathbf{P}\\mathbf{x}$ is orthogonal to every vector of $S$;*\n",
    "(ii) *$\\mathbf{P}\\mathbf{x}$ is the unique closest point of $S$ to\n",
    "$\\mathbf{x}$;*\n",
    "(iii) *$\\mathbf{P}^2 = \\mathbf{P}$ and $\\mathbf{P}^\\top = \\mathbf{P}$.*\n",
    "\n",
    "**Proof.** For (i), $\\mathbf{P}\\mathbf{x} = \\mathbf{Q}(\\mathbf{Q}^\\top\\mathbf{x})$\n",
    "is a linear combination of the columns of $\\mathbf{Q}$, hence lies in $S$; and\n",
    "$$\\mathbf{Q}^\\top(\\mathbf{x} - \\mathbf{P}\\mathbf{x}) = \\mathbf{Q}^\\top\\mathbf{x}\n",
    "- (\\mathbf{Q}^\\top\\mathbf{Q})\\mathbf{Q}^\\top\\mathbf{x} = \\mathbf{0},$$ \n",
    "so the\n",
    "residual is orthogonal to each $\\mathbf{q}_i$ and therefore to everything they\n",
    "span. For (ii), take any $\\mathbf{s} \\in S$ and split $\\mathbf{x} - \\mathbf{s}\n",
    "= (\\mathbf{x} - \\mathbf{P}\\mathbf{x}) + (\\mathbf{P}\\mathbf{x} - \\mathbf{s})$:\n",
    "the second piece lies in $S$, the first is orthogonal to it, so Pythagoras\n",
    "the equation gives \n",
    "$$\\|\\mathbf{x} - \\mathbf{s}\\|^2 = \\|\\mathbf{x}\n",
    "- \\mathbf{P}\\mathbf{x}\\|^2 + \\|\\mathbf{P}\\mathbf{x} - \\mathbf{s}\\|^2 \\ge\n",
    "\\|\\mathbf{x} - \\mathbf{P}\\mathbf{x}\\|^2,$$ \n",
    "with equality exactly when\n",
    "$\\mathbf{s} = \\mathbf{P}\\mathbf{x}$. For (iii), $\\mathbf{P}^2 =\n",
    "\\mathbf{Q}(\\mathbf{Q}^\\top\\mathbf{Q})\\mathbf{Q}^\\top = \\mathbf{Q}\\mathbf{Q}^\\top\n",
    "= \\mathbf{P}$, and symmetry is immediate from the form\n",
    "$\\mathbf{Q}\\mathbf{Q}^\\top$. $\\blacksquare$\n",
    "\n",
    "Property (iii) restates the geometry algebraically: projecting a second time\n",
    "changes nothing, because after the first projection you are already in $S$.\n",
    "For $k = 1$ with the single unit column\n",
    "$\\mathbf{q} = \\mathbf{w}/\\|\\mathbf{w}\\|$, the matrix\n",
    "$\\mathbf{P} = \\mathbf{q}\\mathbf{q}^\\top$ reproduces the one-dimensional formula\n",
    "the equation exactly.\n",
    "\n",
    "This proposition is the geometry of **least squares**, the fitting problem\n",
    "behind linear regression. Given a data matrix $\\mathbf{A}$ whose columns are\n",
    "features and a target vector $\\mathbf{b}$, least squares asks for\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{x}} \\|\\mathbf{A}\\mathbf{x} - \\mathbf{b}\\|^2 .\n",
    "$$\n",
    "\n",
    "As $\\mathbf{x}$ ranges over all coefficient vectors, $\\mathbf{A}\\mathbf{x}$\n",
    "ranges over the column space of $\\mathbf{A}$, so minimizing\n",
    "the equation means finding the closest point to $\\mathbf{b}$\n",
    "in that column space, and by property (i) the optimal residual is orthogonal\n",
    "to every column of $\\mathbf{A}$. The singular value decomposition solves\n",
    "the equation in full generality in\n",
    "that section.\n",
    "\n",
    "Where does an orthonormal basis come from? The library's `qr` routine (the\n",
    "*QR factorization*, a matrix form of the Gram–Schmidt process we describe when\n",
    "we meet orthogonal matrices below) turns any full-rank matrix into one with\n",
    "orthonormal columns and the same column space. Let us verify the proposition\n",
    "numerically on a random 3-dimensional subspace of $\\mathbb{R}^5$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-geometry-linear-algebraic-ops-projection-onto-a-subspace"
   },
   "source": [
    "import numpy as onp\n",
    "# A random 5x3 matrix whose columns span a 3-dim subspace of R^5\n",
    "onp.random.seed(0)\n",
    "A = onp.random.randn(5, 3)\n",
    "Q, _ = onp.linalg.qr(A)  # orthonormal basis of the column space\n",
    "P = Q.dot(Q.T)          # projection matrix onto that subspace\n",
    "x = onp.random.randn(5)\n",
    "r = x - P.dot(x)        # residual\n",
    "(onp.linalg.norm(P.dot(P) - P),  # P^2 = P (idempotent)\n",
    " onp.linalg.norm(Q.T.dot(r)))    # residual is orthogonal to the subspace"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(np.float64(4.153077993666847e-16), np.float64(4.211628519682908e-16))"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-4 fw=all -->\n",
    "\n",
    "Both numbers are zero up to floating-point roundoff: $\\mathbf{P}$ really is\n",
    "idempotent, and the residual really is orthogonal to the whole subspace, just\n",
    "as the proposition demands.\n",
    "\n",
    "## Similarity in High Dimensions\n",
    "\n",
    "Why is the *angle*, rather than the raw distance, so often the right notion\n",
    "of similarity? The answer is invariance to scale.\n",
    "Consider an image and a copy of it dimmed to $10\\%$ brightness. Pixel by pixel\n",
    "the two are far apart, so their Euclidean distance is large; yet the content is\n",
    "identical, and a cat/dog classifier should treat them the same. The angle does:\n",
    "for any vector $\\mathbf{v}$, the angle between $\\mathbf{v}$ and $0.1\\,\\mathbf{v}$\n",
    "is zero, because scaling changes a vector's length but not its direction. This\n",
    "is why, when the angle is used to compare two vectors, practitioners work with\n",
    "its cosine and call it **cosine similarity**,\n",
    "\n",
    "$$\n",
    "\\cos(\\theta) = \\frac{\\mathbf{v}\\cdot\\mathbf{w}}{\\|\\mathbf{v}\\|\\,\\|\\mathbf{w}\\|}\n",
    " \\;\\in\\; [-1, 1],\n",
    "$$\n",
    "\n",
    "equal to $+1$ when the vectors point the same way, $-1$ when opposite, and $0$\n",
    "when orthogonal. Cosine similarity is the metric behind nearest-neighbor\n",
    "retrieval over **embeddings**, the scaled dot products inside **attention**\n",
    "(that section), and the alignment objective of\n",
    "**contrastive learning** [@Oord.Li.Vinyals.2018]: in each case we have\n",
    "represented objects as vectors and we measure relatedness by direction,\n",
    "deliberately discarding magnitude.\n",
    "\n",
    "If we drop two *unrelated* vectors into a high-dimensional space, what cosine\n",
    "should we expect between them? **In high dimensions, random vectors are almost\n",
    "always nearly orthogonal**, and the higher the dimension, the more sharply\n",
    "this holds.\n",
    "\n",
    "**Proposition (near-orthogonality).** *Fix a unit vector $\\mathbf{u} \\in\n",
    "\\mathbb{R}^d$ and let $\\mathbf{v}$ be drawn uniformly from the unit sphere in\n",
    "$\\mathbb{R}^d$. Then $\\cos\\theta = \\mathbf{u}\\cdot\\mathbf{v}$ satisfies*\n",
    "\n",
    "$$\n",
    "\\mathbb{E}[\\cos\\theta] = 0,\n",
    "\\qquad\n",
    "\\operatorname{Var}(\\cos\\theta) = \\frac{1}{d}.\n",
    "$$\n",
    "\n",
    "**Proof.** The uniform distribution on the sphere is invariant under rotations,\n",
    "so we may rotate coordinates until $\\mathbf{u} = \\mathbf{e}_1$; then\n",
    "$\\cos\\theta = \\mathbf{u}\\cdot\\mathbf{v} = v_1$. By the symmetry $\\mathbf{v}\n",
    "\\mapsto -\\mathbf{v}$ we have $\\mathbb{E}[v_1] = 0$. For the variance, every\n",
    "coordinate plays the same role by symmetry, so $\\mathbb{E}[v_i^2]$ is the same\n",
    "for all $i$; summing and using $\\sum_i v_i^2 = \\|\\mathbf{v}\\|^2 = 1$ gives\n",
    "$d\\,\\mathbb{E}[v_1^2] = \\mathbb{E}\\!\\left[\\sum_i v_i^2\\right] = 1$, hence\n",
    "$\\operatorname{Var}(\\cos\\theta) = \\mathbb{E}[v_1^2] = 1/d$. Chebyshev's\n",
    "inequality, $\\Pr(|X - \\mathbb{E}X| \\ge \\varepsilon) \\le\n",
    "\\operatorname{Var}(X)/\\varepsilon^2$ (we prove it in that section),\n",
    "then bounds the chance of a large cosine,\n",
    "\n",
    "$$\n",
    "\\Pr\\bigl(|\\cos\\theta| \\ge \\varepsilon\\bigr) \\le \\frac{1}{d\\,\\varepsilon^2},\n",
    "$$\n",
    "\n",
    "which tends to $0$ as $d \\to \\infty$ for any fixed $\\varepsilon > 0$.\n",
    "$\\blacksquare$\n",
    "\n",
    "So the typical cosine between random directions has standard deviation\n",
    "$1/\\sqrt{d}$, concentrating ever more tightly at $0$. This is a first taste of\n",
    "*concentration of measure*, the phenomenon that makes high-dimensional geometry\n",
    "behave very differently from our $2$- and $3$-dimensional intuition; we\n",
    "quantify it with exponential tail bounds in\n",
    "that section. It is also\n",
    "why cosine similarity is a useful signal: since unrelated items are nearly\n",
    "orthogonal by default, a cosine that is appreciably above $0$ is unlikely to\n",
    "be an accident and instead reflects real shared structure. This is the\n",
    "working assumption behind embedding-based retrieval and the attention\n",
    "mechanism.\n",
    "\n",
    "We can watch the concentration happen by sampling random unit vectors and\n",
    "histogramming their pairwise cosines as the dimension grows, shown in\n",
    "the figure. Very low dimensions are genuinely\n",
    "different: in the plane ($d = 2$) the histogram piles up at $\\pm 1$ (the\n",
    "density is arcsine-shaped), so two random directions are *more* likely to be\n",
    "nearly aligned or nearly opposed than nearly orthogonal. Raising the dimension\n",
    "reverses the picture: by $d = 10$ the histogram is a bell centered at $0$ with\n",
    "standard deviation $1/\\sqrt{10} \\approx 0.32$, and by $d = 1000$ it has\n",
    "collapsed into a spike of width $\\approx 0.03$.\n",
    "\n",
    "![Histograms of the cosine between independent random unit vectors at dimensions $d = 2$, $10$, and $1000$. In $d = 2$ the mass piles up near $\\pm 1$ in an arcsine-shaped density: random directions in the plane are typically far from orthogonal. In moderate dimension the histogram flattens into a bell around $0$, and by $d = 1000$ it is a narrow spike of width $\\approx 1/\\sqrt{d}$, exactly as the proposition predicts.](../img/mdl-la-cosine-highd.svg)\n",
    "\n",
    "This concentration is the operating environment of **dot-product attention**\n",
    "(that section). An\n",
    "attention layer compares one query $\\mathbf{q}$ against thousands of keys\n",
    "$\\mathbf{k}_1, \\mathbf{k}_2, \\ldots$ by dot product, and near-orthogonality is\n",
    "what makes the comparison informative at scale: the scores of the many\n",
    "unrelated keys concentrate near zero, so the few keys that genuinely share\n",
    "structure with the query stand out against a quiet background. A short\n",
    "variance computation also explains the otherwise mysterious $\\sqrt{d}$ in the\n",
    "attention scores $\\mathbf{Q}\\mathbf{K}^\\top/\\sqrt{d}$\n",
    "[@Vaswani.Shazeer.Parmar.ea.2017]. Let the query and key have\n",
    "independent, mean-zero, unit-variance entries. Each summand of\n",
    "$\\mathbf{q}\\cdot\\mathbf{k} = \\sum_i q_i k_i$ then has mean zero and variance\n",
    "$\\mathbb{E}[q_i^2 k_i^2] = \\mathbb{E}[q_i^2]\\,\\mathbb{E}[k_i^2] = 1$, and\n",
    "distinct summands are uncorrelated, since independence gives\n",
    "$\\mathbb{E}[(q_i k_i)(q_j k_j)] = 0$ for $i \\neq j$. The variances of the $d$\n",
    "summands therefore add:\n",
    "\n",
    "$$\n",
    "\\operatorname{Var}(\\mathbf{q}\\cdot\\mathbf{k})\n",
    " = \\sum_{i=1}^d \\operatorname{Var}(q_i k_i) = d.\n",
    "$$\n",
    "\n",
    "The raw scores have standard deviation $\\sqrt{d}$, growing with the dimension,\n",
    "and dividing by $\\sqrt{d}$ is exactly dividing by that standard deviation: it\n",
    "standardizes the scores to size $O(1)$ so that the softmax downstream stays in\n",
    "its responsive range instead of saturating on whichever score happens to be\n",
    "largest (we study that softmax's derivative in\n",
    "that section). The sphere proposition gives the\n",
    "same answer as geometric intuition: each vector has length about $\\sqrt{d}$\n",
    "while the cosine between unrelated directions has typical size $1/\\sqrt{d}$,\n",
    "so the product lands at size $\\sqrt{d}$.\n",
    "\n",
    "## Hyperplanes and Decision Boundaries\n",
    "\n",
    "In addition to working with vectors, another key object\n",
    "that you must understand\n",
    "is the *hyperplane*, a generalization to higher dimensions\n",
    "of a line (two dimensions) or of a plane (three dimensions).\n",
    "In a $d$-dimensional vector space, a hyperplane has $d-1$ dimensions\n",
    "and divides the space into two half-spaces.\n",
    "\n",
    "Let's start with an example.\n",
    "Suppose that we have a column vector $\\mathbf{w}=[2,1]^\\top$ and a scalar\n",
    "*bias* $b$. We want to know, \"what are the points $\\mathbf{v}$ with\n",
    "$\\mathbf{w}\\cdot\\mathbf{v} = b$?\" For concreteness we first take $b = 1$.\n",
    "By recalling the connection between dot products and angles above the equation,\n",
    "we can see that this is equivalent to\n",
    "$$\n",
    "\\|\\mathbf{v}\\|\\|\\mathbf{w}\\|\\cos(\\theta) = 1 \\; \\iff \\; \\|\\mathbf{v}\\|\\cos(\\theta) = \\frac{1}{\\|\\mathbf{w}\\|} = \\frac{1}{\\sqrt{5}}.\n",
    "$$\n",
    "\n",
    "If we consider the geometric meaning of this expression,\n",
    "we see that this is equivalent to saying\n",
    "that the signed length of the projection of $\\mathbf{v}$\n",
    "onto the direction of $\\mathbf{w}$ is exactly $1/\\|\\mathbf{w}\\|$; recall the\n",
    "signed projection length $\\|\\mathbf{v}\\|\\cos(\\theta)$ from\n",
    "the figure.\n",
    "The set of all points where this is true is a line\n",
    "at right angles to the vector $\\mathbf{w}$.\n",
    "If we wanted, we could find the equation for this line\n",
    "and see that it is $2x + y = 1$ or equivalently $y = 1 - 2x$.\n",
    "\n",
    "More generally, the equation $\\mathbf{w}\\cdot\\mathbf{v} = b$ for any scalar\n",
    "$b$ describes a line (in higher dimensions, a hyperplane) at right angles to\n",
    "$\\mathbf{w}$. The vector $\\mathbf{w}$ is called the *normal* to the hyperplane,\n",
    "and the bias $b$ controls *where along that normal* the hyperplane sits.\n",
    "By the same projection argument, every point on it has the same signed\n",
    "projection $\\mathbf{w}\\cdot\\mathbf{v}/\\|\\mathbf{w}\\| = b/\\|\\mathbf{w}\\|$ onto the\n",
    "direction of $\\mathbf{w}$, so the hyperplane passes at (signed) distance\n",
    "$b/\\|\\mathbf{w}\\|$ from the origin. Changing $b$ slides the hyperplane along\n",
    "$\\mathbf{w}$ without rotating it; the case $b=0$ is the hyperplane through the\n",
    "origin. More usefully, for *any* point $\\mathbf{x}$ the quantity\n",
    "$$\n",
    "\\frac{\\mathbf{w}\\cdot\\mathbf{x} - b}{\\|\\mathbf{w}\\|}\n",
    "$$\n",
    "is the *signed distance* from $\\mathbf{x}$ to the hyperplane: positive on the\n",
    "side $\\mathbf{w}$ points toward, negative on the other, and zero exactly on it.\n",
    "This signed distance is precisely the *margin* used by linear classifiers. The\n",
    "derivation is just the projection result of the previous section applied to the\n",
    "displacement of $\\mathbf{x}$ from any point on the hyperplane, which is why the\n",
    "projection material had to come first. the figure\n",
    "collects all of these facts in a single picture.\n",
    "\n",
    "![The hyperplane $\\mathbf{w}\\cdot\\mathbf{x} = b$ with normal $\\mathbf{w}$. Sliding the offset $b$ translates the hyperplane along $\\mathbf{w}$ without rotating it; the shaded region is the half-space $\\mathbf{w}\\cdot\\mathbf{x} > b$; and the signed distance from any point to the hyperplane is $(\\mathbf{w}\\cdot\\mathbf{x} - b)/\\|\\mathbf{w}\\|$, the quantity a linear classifier reads off as its margin.](../img/mdl-la-hyperplane.svg)\n",
    "\n",
    "If we now look at what happens when we ask about the set of points with\n",
    "$\\mathbf{w}\\cdot\\mathbf{v} > b$ or $\\mathbf{w}\\cdot\\mathbf{v} < b$,\n",
    "we can see that these are cases where the projections\n",
    "are longer or shorter than $b/\\|\\mathbf{w}\\|$, respectively\n",
    "(equivalently, the signed distance above is positive or negative).\n",
    "Thus, those two inequalities define either side of the line, cutting our space\n",
    "into two halves: all the points on one side have dot product below a threshold,\n",
    "and the other side above.\n",
    "\n",
    "Higher dimensions work the same way.\n",
    "If we now take $\\mathbf{w} = [1,2,3]^\\top$\n",
    "and ask about the points in three dimensions with $\\mathbf{w}\\cdot\\mathbf{v} = b$,\n",
    "we obtain a plane at right angles to the given vector $\\mathbf{w}$,\n",
    "offset from the origin by the signed distance $b/\\|\\mathbf{w}\\|$.\n",
    "The two inequalities again define the two sides of the plane.\n",
    "\n",
    "While our ability to visualize runs out at this point,\n",
    "nothing stops us from doing this in tens, hundreds, or billions of dimensions (or even infinite dimensional spaces in the case of kernel methods).\n",
    "This occurs often when thinking about machine learned models.\n",
    "For instance, we can understand linear classification models\n",
    "like those from that section,\n",
    "as methods to find hyperplanes that separate the different target classes.\n",
    "In this context, such hyperplanes are often referred to as *decision planes*:\n",
    "the learned weight vector is the normal $\\mathbf{w}$ and the learned bias is\n",
    "exactly the offset $b$, with the predicted class read off from the sign of\n",
    "$\\mathbf{w}\\cdot\\mathbf{x} - b$.\n",
    "The majority of deep learned classification models end\n",
    "with a linear layer fed into a softmax,\n",
    "so one can interpret the role of the deep neural network\n",
    "to be to find a non-linear embedding such that the target classes\n",
    "can be separated by hyperplanes.\n",
    "\n",
    "To give a hand-built example, notice that we can produce a reasonable model\n",
    "to classify tiny images of t-shirts and trousers from the Fashion-MNIST dataset\n",
    "(seen in that section)\n",
    "by just taking the vector between their means to define the decision plane\n",
    "and eyeball a crude threshold.  First we will load the data and compute the averages."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-hyperplanes-1"
   },
   "source": [
    "# Load in the dataset\n",
    "((train_images, train_labels), (\n",
    "    test_images, test_labels)) = tf.keras.datasets.fashion_mnist.load_data()\n",
    "\n",
    "X_train_0 = jnp.array(train_images[train_labels == 0], dtype=jnp.float32) * 256\n",
    "X_train_1 = jnp.array(train_images[train_labels == 1], dtype=jnp.float32) * 256\n",
    "X_test = jnp.array(\n",
    "    test_images[(test_labels == 0) | (test_labels == 1)], dtype=jnp.float32) * 256\n",
    "y_test = jnp.array(\n",
    "    test_labels[(test_labels == 0) | (test_labels == 1)], dtype=jnp.float32)\n",
    "\n",
    "# Compute averages\n",
    "ave_0 = jnp.mean(X_train_0, axis=0)\n",
    "ave_1 = jnp.mean(X_train_1, axis=0)"
   ],
   "execution_count": 4,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-5 fw=all -->\n",
    "\n",
    "The two class means are blurry but recognizable images; let's plot them side\n",
    "by side."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-hyperplanes-2"
   },
   "source": [
    "# Plot the two class means side by side\n",
    "d2l.set_figsize((6, 3))\n",
    "_, axes = d2l.plt.subplots(1, 2)\n",
    "axes[0].imshow(np.array(ave_0.reshape(28, 28)), cmap='Greys')\n",
    "axes[0].set_title('mean t-shirt')\n",
    "axes[1].imshow(np.array(ave_1.reshape(28, 28)), cmap='Greys')\n",
    "axes[1].set_title('mean trousers')\n",
    "d2l.plt.show()"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"368.925pt\" height=\"198.378068pt\" viewBox=\"0 0 368.925 198.378068\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:54:17.295927</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M -0 198.378068 \nL 368.925 198.378068 \nL 368.925 0 \nL -0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 26.925 174.499943 \nL 179.106818 174.499943 \nL 179.106818 22.318125 \nL 26.925 22.318125 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#p31c3cd97cb)\">\n    <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAANQAAADUCAYAAADk3g0YAAAI/0lEQVR4nO3dy2qUSxTF8YompnOTQMcLIQpqQFEQB4IThw58JB/FB/BRnCgORAQFCWoIERU1msROOrfzBLW2fHsV3eH8f9NNdXe6XeeD2mdXTZycnJyUEYjeVtWHw6Fcu7m5KeuvX7+u1r5+/SrXbm9vV2s7Ozty7WAwqNYODg7k2uj7mpycrNampqbk2tnZ2WptcXFRru33+9XaysqKXHv79m1ZV++t/t7IxMRE57WRM81eGfgfIlCAEYECjAgUYESgACMCBRgRKMCo+2b+P1C9k6ivcnh4WK39+vVLrn327JmsP336tFpTfaZSStnb26vWjo6O5Fol6o1k613Xqh5VVL9z545c++TJE1l/8OBBtRb9vWfPnq3Won97me+SJxRgRKAAIwIFGBEowIhAAUYECjBKbZuPaPIj3NaMxhV6vV61Fo0FqPeOvo/j4+Nq7cwZ/d+2zLZ5Zm3m+4i23NXWdiT6m9RvwfgGcEoQKMCIQAFGBAowIlCAEYECjAgUYNR0fEPJ9LCyPRs1ZqHGRiKqz5QV/U3Rd6K06gdFR6NlfseWIxiZHhZPKMCIQAFGBAowIlCAEYECjAgUYDSyU48you3WqJ7ZGh9XrcYVWo7oZEZDxhVPKMCIQAFGBAowIlCAEYECjAgUYESgAKOwD9WqD5F53WjcQB0T1lLLvknLY8Qy1O8YHed27tw5Wc+Mb2T+fXH7BjAmCBRgRKAAIwIFGBEowIhAAUZNb9/IbF2qtdF4xszMjKxntmMzWt2QUYr+TjI3VWRE2+LT09NN3neUeEIBRgQKMCJQgBGBAowIFGBEoAAjAgUYjewYsUwPK+qrzM/Py7o6vmo4HMq1qt/TciQlM1KQ6XFFPT9140jLPhTjG8D/AIECjAgUYESgACMCBRgRKMCIQAFGp/IW+GwfKnPreea29VG8bimj62FFc2nRMWNKyz5mBk8owIhAAUYECjAiUIARgQKMCBRgNLJt85aibXM1NjAYDOTaVlvQ0bb5qI4Ciz6Xet/MGE302uOKJxRgRKAAIwIFGBEowIhAAUYECjAiUIDRqTxGLNLy+KrUEVOJK2eydSUz6pAZ38iM0bS6KimLJxRgRKAAIwIFGBEowIhAAUYECjBqegt8q9eO3jfajlXb5tFrj+r2jYyWox/qc0fb5pFWW+OZ7yNayxMKMCJQgBGBAowIFGBEoAAjAgUYESjA6FSOb0Rro15BNN7RVeYosOyNEJnvS8ncCpL9nkc1/pPBEwowIlCAEYECjAgUYESgACMCBRidym3z4+PjzmtLaXdyUTSCkTn1KKLWZ76PzNrobzo6OpJ19TtnTmPi1CPglCBQgBGBAowIFGBEoAAjAgUYESjAqOkxYple0uHhYbW2v78v1w6HQ1mP+h+K6iVFow6ZHlbLXpKifofIwcFB07qSGTvJ4AkFGBEowIhAAUYECjAiUIARgQKMCBRg1LQPpXpNUS9pMBhUazs7O3Ltt2/fZF31VjJzSeFVJ4keViQzO9SK+g1LKeXHjx+yrj733Nxc57XRd525WognFGBEoAAjAgUYESjAiEABRgQKMGq6bf73799qLdra/v79e7X2+fNnuXZtbU3W1ZZ9Zks1c7RV9qb2UY0rqO8j+o1fvHgh61evXq3WlpeX5dqLFy9Wa0tLS3Lt5GT3WPCEAowIFGBEoAAjAgUYESjAiEABRgQKMAo33FX/IzqOS/WSXr16JdeqXtP6+nrn9y2llL29vWot08/JHCOW6WFFoiPbMseqqc/15csXuTYa71D/BlSPqpRS7t69W63Nzs7KtZnb63lCAUYECjAiUIARgQKMCBRgRKAAo9T4RrQdu7W1Va1FIxYbGxvV2qdPn+Tazc1NWVe3OkT/677a+o7WZk7iydyoHq1VIxjRb6zWRu2L6NQj9d7R5+r3+9Xa6uqqXJu5rYQnFGBEoAAjAgUYESjAiEABRgQKMCJQgFGqD5U5cksdMVaKvmFjd3dXro1ugVefK/pf91U9c2tD1MNK9UYajqSoflA0FhLd8r69vV2tzc/Py7Xq+4p+p8yoDE8owIhAAUYECjAiUIARgQKMCBRgFG6bqy3EaPvx/Pnz1Vq0HatOJoosLCzIutqujf6mzO0bmW31lq+deV21bT41NZV6bfU7qYvHSyllZmamWuv1enIt2+bAmCBQgBGBAowIFGBEoAAjAgUYESjAqOn4hupDqVoke3uCGguIRg4yfRfV34j6KtljxpTMDSvqc0W/w/T0dOfXjr7rCxcudP5c9KGAMUGgACMCBRgRKMCIQAFGBAowIlCAUWoeKuqNqKOerly5Ite+efOmWouOn4quOlHHjEXHm2WuWFGifk90jFhmTku9d/Q3qePPonmnqB+kXntxcVGuvXTpUqfXLYU+FDA2CBRgRKAAIwIFGBEowIhAAUap8Y1oe1H97/k3b96Ua1++fFmtRaMO+/v7st7qyK1o61t9rsztGqXovynaJs5s96t/A9mjz+bm5qq1GzduyLVLS0ud3zeDJxRgRKAAIwIFGBEowIhAAUYECjAiUIBRqg8Vvrjof1y/fl2uVX0qdUP8v8iMHKh+UdTPicZOlMwIRrQ2M66gvq9oPENdOVNKKZcvX67W7t27J9eqo+ZaHsnGEwowIlCAEYECjAgUYESgACMCBRg1Hd9Q25PRqTWPHz+u1tSpRaWU8v79e1lX4x/RCMafP3+qtWhsZHd3t9NnKiXe6lXfSfRdqy3m6IaMhYWFai26YWV5eVnWHz16VK3dunVLro1u52iFJxRgRKAAIwIFGBEowIhAAUYECjAiUIDRxEn2/Coh89KqL/P792+59t27d7L+/Pnzau3t27dy7draWrX24cMHuVb1sFQ/p5R4rOTnz5/VWjRWcu3atWptdXVVrlX1+/fvy7UPHz6U9ZWVlWqt1+vJtZnjzTJ4QgFGBAowIlCAEYECjAgUYESgAKOm2+YZmY+VuQVja2tLrl1fX6/WNjY25Np+v9+pVko8vqFGQz5+/CjXqtOJojEJNYKhxkJKiUcsRrX1ncETCjAiUIARgQKMCBRgRKAAIwIFGBEowOg/U/O7K0EIO/EAAAAASUVORK5CYII=\" id=\"imagebb08fcb5ef\" transform=\"scale(1 -1) translate(0 -152.64)\" x=\"26.925\" y=\"-21.859943\" width=\"152.64\" height=\"152.64\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"mb8a13c890b\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mb8a13c890b\" x=\"29.642532\" y=\"174.499943\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(26.461282 189.098381) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#mb8a13c890b\" x=\"83.993182\" y=\"174.499943\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 10 -->\n      <g transform=\"translate(77.630682 189.098381) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#mb8a13c890b\" x=\"138.343831\" y=\"174.499943\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 20 -->\n      <g transform=\"translate(131.981331 189.098381) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_4\">\n      <defs>\n       <path id=\"meb939ebe75\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"26.925\" y=\"25.035657\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 0 -->\n      <g transform=\"translate(13.5625 28.834876) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"26.925\" y=\"52.210982\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 5 -->\n      <g transform=\"translate(13.5625 56.010201) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-35\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"26.925\" y=\"79.386307\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 10 -->\n      <g transform=\"translate(7.2 83.185526) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"26.925\" y=\"106.561631\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 15 -->\n      <g transform=\"translate(7.2 110.36085) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"26.925\" y=\"133.736956\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 20 -->\n      <g transform=\"translate(7.2 137.536175) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"26.925\" y=\"160.912281\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 25 -->\n      <g transform=\"translate(7.2 164.7115) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 26.925 174.499943 \nL 26.925 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 179.106818 174.499943 \nL 179.106818 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 26.925 174.499943 \nL 179.106818 174.499943 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 26.925 22.318125 \nL 179.106818 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_10\">\n    <!-- mean t-shirt -->\n    <g transform=\"translate(66.162784 16.318125) scale(0.12 -0.12)\">\n     <defs>\n      <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-2d\" d=\"M 313 2009 \nL 1997 2009 \nL 1997 1497 \nL 313 1497 \nL 313 2009 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-6d\"/>\n     <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(97.412109 0)\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(158.935547 0)\"/>\n     <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(220.214844 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(283.59375 0)\"/>\n     <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(315.380859 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2d\" transform=\"translate(354.589844 0)\"/>\n     <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(390.673828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(442.773438 0)\"/>\n     <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(506.152344 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(533.935547 0)\"/>\n     <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(575.048828 0)\"/>\n    </g>\n   </g>\n  </g>\n  <g id=\"axes_2\">\n   <g id=\"patch_7\">\n    <path d=\"M 209.543182 174.499943 \nL 361.725 174.499943 \nL 361.725 22.318125 \nL 209.543182 22.318125 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#pd815f7c07c)\">\n    <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAANQAAADUCAYAAADk3g0YAAAHhklEQVR4nO3dO25USxQF0OLjvwEBshAiMwGjYApEzINBESBGQEJAQMIIHAMOCPgZ27htaHgxlu6ph++2unGvlR6V+7bN1pXOoaou/f79+3ebQ2Me69evX2V9Op0O1iaTSbl2Z2dnsPbixYty7a1btwZrjx8/LtdubW2V9Xfv3g3Wnj17Vq79+fPnYO3Ro0fl2gcPHgzWVlZWyrWXL18u65cuXSrr57V2jPobAX9FoCBIoCBIoCBIoCBIoCBIoCDo6qw+uDdnquq9tdWcqbXWTk5OBmsfP34s1758+XKw9vz583Lt9evXB2vb29vl2ocPH5b1169fD9aePn1arr1y5cpgbXNzs1x7586dwVo1d2uttaWlpbJezal6c6bq38h5zqi8oSBIoCBIoCBIoCBIoCBIoCBoZm3zWRrTNq1a8r2fu7GxMVjrtaer1nZrra2urg7W1tbWyrVjPndMa/si8oaCIIGCIIGCIIGCIIGCIIGCIIGCoIWcQ1X/tb+39WNvb2+wdnR0VK6t6mOP1Do+Ph6sHRwclGurWdPh4WG5dk5PoZsZbygIEigIEigIEigIEigIEigIWsi2eaW6iaK11vb39wdrP378OPPPHts2rz6791yVqh3fWv+mk8pF3N7hDQVBAgVBAgVBAgVBAgVBAgVBAgVB5zqH+hf/a39v7lJtZ+ht/ah+H2PnUNWNIr05VLV9YzKZlGv/xb/xefKGgiCBgiCBgiCBgiCBgiCBgqCF3L5RtXqr9nNr/VOAKlVbvdc276la4712frUFo/f70Db/kzcUBAkUBAkUBAkUBAkUBAkUBAkUBJ3rHKracjCv84ve3OX79++Dtd4Wi6p+nnOo3lFf1XP1jlWb17/jrHhDQZBAQZBAQZBAQZBAQZBAQZBAQZD9UKf05lDVXObq1frXWR3XVdX+j968qFJ99rzOmXrPNaurcryhIEigIEigIEigIEigIEigIGgh2+bVdobeTRVVO7bX+u611cc4Ojo689rl5eXB2kW8qf08eUNBkEBBkEBBkEBBkEBBkEBBkEBBkDnUKWNuTO8dBba0tDRYG3tc18HBwZmfa2Vl5cxrzan+5A0FQQIFQQIFQQIFQQIFQQIFQQvZNq9a1GPa173tGVWLubf9oneDxpcvX8p6pWqba4v/HW8oCBIoCBIoCBIoCBIoCBIoCBIoCDKHOuX4+LhcW82DeseITSaTwVp1u3xrrU2n07K+t7dX1ivVrKn3ubO6nWNe52PeUBAkUBAkUBAkUBAkUBAkUBC0kG3zSu/S6upUpF7bvGqNHx4elmt77evPnz8P1not5upko94YofdclXm9eHoMbygIEigIEigIEigIEigIEigIEigIMoc6pTd3qeq9Y8S+fft2plpr/fnYmDlUtSWl2nLSWj2Xm9XWjlnyhoIggYIggYIggYIggYIggYIggYKghZxDVfOR3nFe1bUzy8vL5dpqptO7jqY3H/v69WtZr4yZQ/Wea1ZmtZfKGwqCBAqCBAqCBAqCBAqCBAqCtM1P6R3nVW1XWF9fL9dWt358+PChXLu/v1/Wq+0f1S3vrdVt815bvBoj2L4BjCJQECRQECRQECRQECRQECRQELSQc6jKmDlU7zqb6tqY3d3dcu2nT5/KevXcq6ur5dpqXlR9397nmkMBowgUBAkUBAkUBAkUBAkUBC1k27xq5x4cHJx5bU91KtLbt2/LtTs7O2W92hpStet7em3z6rQmbXNgFIGCIIGCIIGCIIGCIIGCIIGCoIWcQ1WqY7F6ptNpWa9uia9ucW+ttTdv3pT16raJ3raSSm+WtLe3d+affRF5Q0GQQEGQQEGQQEGQQEGQQEHQQrbNq+0M1TaInl7bvGpf905bevXqVVlfWlo60+f29L6T2zf+5A0FQQIFQQIFQQIFQQIFQQIFQQIFQXM7h6q2I4ydb4z52dWN6b0ZVjXT6R3XVd3y3lpra2trg7Xq+7ZWf6feHOrk5KSsLxpvKAgSKAgSKAgSKAgSKAgSKAgSKAia2RyqNxup5kG9tT3V/qCVlZVybTUv6s1kqnlP78qZar9Ta/Vzj5lD9WZr1c8e+3f6F3lDQZBAQZBAQZBAQZBAQZBAQdDcbt8Yo9eurW7BuHbtWrm2aiOPOYKs98xj2ubneYzYxsbGYK33nS5iW90bCoIECoIECoIECoIECoIECoIECoLMoU7Z2toq11azpt72jTHHny0vL5f13pyqUj139btqrbXbt28P1sbOmf7FrSHeUBAkUBAkUBAkUBAkUBAkUBB0IdvmPVUreHt7u1y7vr4+WOu1xattFGPa3q3VbeTeiUrVc928ebNce+/evTN/7kW0eN8YzpFAQZBAQZBAQZBAQZBAQZBAQdDczqHG/Pf83tpqPlLNVXprd3d36wcr9I7r6m2jqJ6rt/Vjc3NzsNb7fdy4cWOw5hgxYBSBgiCBgiCBgiCBgiCBgqC5bZuPMebUo/v375drnzx5Mlh7//59uba6qaLXFl9bWyvrk8mkrFeqbSe97Sx3794drPVu/biIbXVvKAgSKAgSKAgSKAgSKAgSKAgSKAj6DyYMPu1GcpwLAAAAAElFTkSuQmCC\" id=\"image48139cb2ce\" transform=\"scale(1 -1) translate(0 -152.64)\" x=\"209.543182\" y=\"-21.859943\" width=\"152.64\" height=\"152.64\"/>\n   </g>\n   <g id=\"matplotlib.axis_3\">\n    <g id=\"xtick_4\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#mb8a13c890b\" x=\"212.260714\" y=\"174.499943\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- 0 -->\n      <g transform=\"translate(209.079464 189.098381) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#mb8a13c890b\" x=\"266.611364\" y=\"174.499943\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_12\">\n      <!-- 10 -->\n      <g transform=\"translate(260.248864 189.098381) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#mb8a13c890b\" x=\"320.962013\" y=\"174.499943\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_13\">\n      <!-- 20 -->\n      <g transform=\"translate(314.599513 189.098381) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_4\">\n    <g id=\"ytick_7\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"209.543182\" y=\"25.035657\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_14\">\n      <!-- 0 -->\n      <g transform=\"translate(196.180682 28.834876) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"209.543182\" y=\"52.210982\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_15\">\n      <!-- 5 -->\n      <g transform=\"translate(196.180682 56.010201) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-35\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"209.543182\" y=\"79.386307\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_16\">\n      <!-- 10 -->\n      <g transform=\"translate(189.818182 83.185526) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_10\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"209.543182\" y=\"106.561631\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_17\">\n      <!-- 15 -->\n      <g transform=\"translate(189.818182 110.36085) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_11\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"209.543182\" y=\"133.736956\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_18\">\n      <!-- 20 -->\n      <g transform=\"translate(189.818182 137.536175) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_12\">\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#meb939ebe75\" x=\"209.543182\" y=\"160.912281\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_19\">\n      <!-- 25 -->\n      <g transform=\"translate(189.818182 164.7115) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 209.543182 174.499943 \nL 209.543182 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_9\">\n    <path d=\"M 361.725 174.499943 \nL 361.725 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_10\">\n    <path d=\"M 209.543182 174.499943 \nL 361.725 174.499943 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_11\">\n    <path d=\"M 209.543182 22.318125 \nL 361.725 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_20\">\n    <!-- mean trousers -->\n    <g transform=\"translate(242.144403 16.318125) scale(0.12 -0.12)\">\n     <defs>\n      <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-6d\"/>\n     <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(97.412109 0)\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(158.935547 0)\"/>\n     <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(220.214844 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(283.59375 0)\"/>\n     <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(315.380859 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(354.589844 0)\"/>\n     <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(393.453125 0)\"/>\n     <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(454.634766 0)\"/>\n     <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(518.013672 0)\"/>\n     <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(570.113281 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(631.636719 0)\"/>\n     <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(672.75 0)\"/>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p31c3cd97cb\">\n   <rect x=\"26.925\" y=\"22.318125\" width=\"152.181818\" height=\"152.181818\"/>\n  </clipPath>\n  <clipPath id=\"pd815f7c07c\">\n   <rect x=\"209.543182\" y=\"22.318125\" width=\"152.181818\" height=\"152.181818\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-6 fw=all -->\n",
    "\n",
    "In a fully machine learned solution, we would learn the threshold from the\n",
    "dataset. Here we set it geometrically instead: the normal is the difference of\n",
    "the two class means $\\mathbf{w} = \\overline{\\mathbf{x}}_1 - \\overline{\\mathbf{x}}_0$,\n",
    "and the natural decision boundary is the hyperplane that *bisects* the two\n",
    "means: $\\mathbf{w}\\cdot\\mathbf{x} = b$ with\n",
    "$b = \\mathbf{w}\\cdot\\tfrac12(\\overline{\\mathbf{x}}_0 + \\overline{\\mathbf{x}}_1)$,\n",
    "the midpoint of the two means' projections onto $\\mathbf{w}$. We classify a test\n",
    "image as class $1$ when it lands on the class-$1$ side, i.e.\n",
    "$\\mathbf{w}\\cdot\\mathbf{x} > b$. Note that deriving $b$ from the data this way is\n",
    "*scale-equivariant*: it gives the same boundary whatever convention each\n",
    "framework uses for pixel intensities, which a hand-picked numeric threshold\n",
    "would not."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-hyperplanes-4"
   },
   "source": [
    "import numpy as onp\n",
    "def as_numpy(x):\n",
    "    if hasattr(x, 'asnumpy'):                   # MXNet\n",
    "        return x.asnumpy()\n",
    "    if hasattr(x, 'detach'):                    # PyTorch\n",
    "        return x.detach().cpu().numpy()\n",
    "    if hasattr(x, 'numpy'):                     # TensorFlow\n",
    "        return x.numpy()\n",
    "    return onp.asarray(x)                       # JAX / NumPy\n",
    "\n",
    "X_test_np, y_test_np = as_numpy(X_test), as_numpy(y_test)\n",
    "ave_0_np, ave_1_np = as_numpy(ave_0), as_numpy(ave_1)\n",
    "# Normal = difference of class means; threshold = midpoint of their projections\n",
    "w = (ave_1_np - ave_0_np).ravel()\n",
    "b = onp.dot(w, (ave_0_np + ave_1_np).ravel()) / 2\n",
    "predictions = X_test_np.reshape(len(X_test_np), -1).dot(w) > b\n",
    "\n",
    "# Accuracy\n",
    "onp.mean(predictions.astype(y_test_np.dtype) == y_test_np, dtype=onp.float64)"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "np.float64(0.9155)"
     },
     "metadata": {},
     "execution_count": 6
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-7 fw=all -->\n",
    "\n",
    "This rule classifies about $92\\%$ of the\n",
    "$2{,}000$ test images correctly, and *nothing was trained*. We computed two\n",
    "class means, took their difference as the normal $\\mathbf{w}$, and asked of\n",
    "each test image only which side of one hyperplane its $784$-dimensional pixel\n",
    "vector lies on. To see the geometry of why such a crude rule works, project\n",
    "every test image onto the normal: reduce each image to the single\n",
    "number $\\mathbf{w}\\cdot\\mathbf{x}$, its (scaled) signed position along the\n",
    "direction from \"mean t-shirt\" to \"mean trousers\", and histogram the two\n",
    "classes separately."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-projection-histogram"
   },
   "source": [
    "import numpy as onp\n",
    "# Histogram of the test images' projections onto the normal direction w\n",
    "proj = X_test_np.reshape(len(X_test_np), -1).dot(w)\n",
    "d2l.set_figsize()\n",
    "d2l.plt.hist(proj[y_test_np == 0], bins=50, alpha=0.6, label='t-shirts')\n",
    "d2l.plt.hist(proj[y_test_np == 1], bins=50, alpha=0.6, label='trousers')\n",
    "d2l.plt.axvline(float(b), color='black', linestyle='--', label='threshold')\n",
    "d2l.plt.xlabel(r'$\\mathbf{w}\\cdot\\mathbf{x}$')\n",
    "d2l.plt.legend()\n",
    "d2l.plt.show()"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"235.7875pt\" height=\"184.637943pt\" viewBox=\"0 0 235.7875 184.637943\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:54:17.546773</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 184.637943 \nL 235.7875 184.637943 \nL 235.7875 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 33.2875 147.081693 \nL 228.5875 147.081693 \nL 228.5875 8.481693 \nL 33.2875 8.481693 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 42.164773 147.081693 \nL 44.985705 147.081693 \nL 44.985705 145.720868 \nL 42.164773 145.720868 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 44.985705 147.081693 \nL 47.806637 147.081693 \nL 47.806637 147.081693 \nL 44.985705 147.081693 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 47.806637 147.081693 \nL 50.627583 147.081693 \nL 50.627583 147.081693 \nL 47.806637 147.081693 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 50.627583 147.081693 \nL 53.448515 147.081693 \nL 53.448515 144.360043 \nL 50.627583 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_7\">\n    <path d=\"M 53.448515 147.081693 \nL 56.269447 147.081693 \nL 56.269447 144.360043 \nL 53.448515 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 56.269447 147.081693 \nL 59.090379 147.081693 \nL 59.090379 145.720868 \nL 56.269447 145.720868 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_9\">\n    <path d=\"M 59.090379 147.081693 \nL 61.911311 147.081693 \nL 61.911311 145.720868 \nL 59.090379 145.720868 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_10\">\n    <path d=\"M 61.911311 147.081693 \nL 64.732257 147.081693 \nL 64.732257 141.638394 \nL 61.911311 141.638394 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_11\">\n    <path d=\"M 64.732257 147.081693 \nL 67.553189 147.081693 \nL 67.553189 134.83427 \nL 64.732257 134.83427 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_12\">\n    <path d=\"M 67.553189 147.081693 \nL 70.374121 147.081693 \nL 70.374121 137.55592 \nL 67.553189 137.55592 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_13\">\n    <path d=\"M 70.374121 147.081693 \nL 73.195053 147.081693 \nL 73.195053 129.390971 \nL 70.374121 129.390971 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_14\">\n    <path d=\"M 73.195053 147.081693 \nL 76.015992 147.081693 \nL 76.015992 126.669322 \nL 73.195053 126.669322 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_15\">\n    <path d=\"M 76.015992 147.081693 \nL 78.836931 147.081693 \nL 78.836931 123.947672 \nL 76.015992 123.947672 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_16\">\n    <path d=\"M 78.836931 147.081693 \nL 81.657863 147.081693 \nL 81.657863 117.143549 \nL 78.836931 117.143549 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_17\">\n    <path d=\"M 81.657863 147.081693 \nL 84.478795 147.081693 \nL 84.478795 107.617775 \nL 81.657863 107.617775 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_18\">\n    <path d=\"M 84.478795 147.081693 \nL 87.299727 147.081693 \nL 87.299727 107.617775 \nL 84.478795 107.617775 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_19\">\n    <path d=\"M 87.299727 147.081693 \nL 90.120666 147.081693 \nL 90.120666 92.648703 \nL 87.299727 92.648703 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_20\">\n    <path d=\"M 90.120666 147.081693 \nL 92.941605 147.081693 \nL 92.941605 100.813652 \nL 90.120666 100.813652 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_21\">\n    <path d=\"M 92.941605 147.081693 \nL 95.762537 147.081693 \nL 95.762537 118.504373 \nL 92.941605 118.504373 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_22\">\n    <path d=\"M 95.762537 147.081693 \nL 98.583469 147.081693 \nL 98.583469 104.896126 \nL 95.762537 104.896126 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_23\">\n    <path d=\"M 98.583469 147.081693 \nL 101.404401 147.081693 \nL 101.404401 96.731178 \nL 98.583469 96.731178 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_24\">\n    <path d=\"M 101.404401 147.081693 \nL 104.22534 147.081693 \nL 104.22534 94.009528 \nL 101.404401 94.009528 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_25\">\n    <path d=\"M 104.22534 147.081693 \nL 107.046272 147.081693 \nL 107.046272 89.927054 \nL 104.22534 89.927054 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_26\">\n    <path d=\"M 107.046272 147.081693 \nL 109.867211 147.081693 \nL 109.867211 108.9786 \nL 107.046272 108.9786 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_27\">\n    <path d=\"M 109.867211 147.081693 \nL 112.688143 147.081693 \nL 112.688143 91.287879 \nL 109.867211 91.287879 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_28\">\n    <path d=\"M 112.688143 147.081693 \nL 115.509082 147.081693 \nL 115.509082 91.287879 \nL 112.688143 91.287879 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_29\">\n    <path d=\"M 115.509082 147.081693 \nL 118.330014 147.081693 \nL 118.330014 106.256951 \nL 115.509082 106.256951 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_30\">\n    <path d=\"M 118.330014 147.081693 \nL 121.150946 147.081693 \nL 121.150946 98.092002 \nL 118.330014 98.092002 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_31\">\n    <path d=\"M 121.150946 147.081693 \nL 123.971885 147.081693 \nL 123.971885 99.452827 \nL 121.150946 99.452827 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_32\">\n    <path d=\"M 123.971885 147.081693 \nL 126.792817 147.081693 \nL 126.792817 114.421899 \nL 123.971885 114.421899 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_33\">\n    <path d=\"M 126.792817 147.081693 \nL 129.613756 147.081693 \nL 129.613756 121.226023 \nL 126.792817 121.226023 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_34\">\n    <path d=\"M 129.613756 147.081693 \nL 132.434688 147.081693 \nL 132.434688 117.143549 \nL 129.613756 117.143549 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_35\">\n    <path d=\"M 132.434688 147.081693 \nL 135.25562 147.081693 \nL 135.25562 106.256951 \nL 132.434688 106.256951 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_36\">\n    <path d=\"M 135.25562 147.081693 \nL 138.076559 147.081693 \nL 138.076559 115.782724 \nL 135.25562 115.782724 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_37\">\n    <path d=\"M 138.076559 147.081693 \nL 140.897491 147.081693 \nL 140.897491 111.70025 \nL 138.076559 111.70025 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_38\">\n    <path d=\"M 140.897491 147.081693 \nL 143.71843 147.081693 \nL 143.71843 113.061074 \nL 140.897491 113.061074 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_39\">\n    <path d=\"M 143.71843 147.081693 \nL 146.539362 147.081693 \nL 146.539362 111.70025 \nL 143.71843 111.70025 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_40\">\n    <path d=\"M 146.539362 147.081693 \nL 149.360294 147.081693 \nL 149.360294 100.813652 \nL 146.539362 100.813652 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_41\">\n    <path d=\"M 149.360294 147.081693 \nL 152.181233 147.081693 \nL 152.181233 114.421899 \nL 149.360294 114.421899 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_42\">\n    <path d=\"M 152.181233 147.081693 \nL 155.002165 147.081693 \nL 155.002165 114.421899 \nL 152.181233 114.421899 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_43\">\n    <path d=\"M 155.002165 147.081693 \nL 157.823104 147.081693 \nL 157.823104 122.586848 \nL 155.002165 122.586848 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_44\">\n    <path d=\"M 157.823104 147.081693 \nL 160.644036 147.081693 \nL 160.644036 122.586848 \nL 157.823104 122.586848 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_45\">\n    <path d=\"M 160.644036 147.081693 \nL 163.464975 147.081693 \nL 163.464975 125.308497 \nL 160.644036 125.308497 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_46\">\n    <path d=\"M 163.464975 147.081693 \nL 166.285907 147.081693 \nL 166.285907 121.226023 \nL 163.464975 121.226023 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_47\">\n    <path d=\"M 166.285907 147.081693 \nL 169.106839 147.081693 \nL 169.106839 136.195095 \nL 166.285907 136.195095 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_48\">\n    <path d=\"M 169.106839 147.081693 \nL 171.927771 147.081693 \nL 171.927771 126.669322 \nL 169.106839 126.669322 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_49\">\n    <path d=\"M 171.927771 147.081693 \nL 174.748717 147.081693 \nL 174.748717 137.55592 \nL 171.927771 137.55592 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_50\">\n    <path d=\"M 174.748717 147.081693 \nL 177.569649 147.081693 \nL 177.569649 132.112621 \nL 174.748717 132.112621 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_51\">\n    <path d=\"M 177.569649 147.081693 \nL 180.390581 147.081693 \nL 180.390581 144.360043 \nL 177.569649 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_52\">\n    <path d=\"M 180.390581 147.081693 \nL 183.211517 147.081693 \nL 183.211517 144.360043 \nL 180.390581 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_53\">\n    <path d=\"M 104.286856 147.081693 \nL 106.595326 147.081693 \nL 106.595326 144.360043 \nL 104.286856 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_54\">\n    <path d=\"M 106.595326 147.081693 \nL 108.903789 147.081693 \nL 108.903789 147.081693 \nL 106.595326 147.081693 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_55\">\n    <path d=\"M 108.903789 147.081693 \nL 111.212258 147.081693 \nL 111.212258 145.720868 \nL 108.903789 145.720868 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_56\">\n    <path d=\"M 111.212258 147.081693 \nL 113.520728 147.081693 \nL 113.520728 147.081693 \nL 111.212258 147.081693 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_57\">\n    <path d=\"M 113.520728 147.081693 \nL 115.829191 147.081693 \nL 115.829191 145.720868 \nL 113.520728 145.720868 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_58\">\n    <path d=\"M 115.829191 147.081693 \nL 118.137661 147.081693 \nL 118.137661 142.999219 \nL 115.829191 142.999219 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_59\">\n    <path d=\"M 118.137661 147.081693 \nL 120.446131 147.081693 \nL 120.446131 147.081693 \nL 118.137661 147.081693 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_60\">\n    <path d=\"M 120.446131 147.081693 \nL 122.754593 147.081693 \nL 122.754593 142.999219 \nL 120.446131 142.999219 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_61\">\n    <path d=\"M 122.754593 147.081693 \nL 125.063063 147.081693 \nL 125.063063 145.720868 \nL 122.754593 145.720868 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_62\">\n    <path d=\"M 125.063063 147.081693 \nL 127.371533 147.081693 \nL 127.371533 138.916745 \nL 125.063063 138.916745 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_63\">\n    <path d=\"M 127.371533 147.081693 \nL 129.679996 147.081693 \nL 129.679996 144.360043 \nL 127.371533 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_64\">\n    <path d=\"M 129.679996 147.081693 \nL 131.988466 147.081693 \nL 131.988466 142.999219 \nL 129.679996 142.999219 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_65\">\n    <path d=\"M 131.988466 147.081693 \nL 134.296932 147.081693 \nL 134.296932 142.999219 \nL 131.988466 142.999219 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_66\">\n    <path d=\"M 134.296932 147.081693 \nL 136.605398 147.081693 \nL 136.605398 141.638394 \nL 134.296932 141.638394 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_67\">\n    <path d=\"M 136.605398 147.081693 \nL 138.913868 147.081693 \nL 138.913868 144.360043 \nL 136.605398 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_68\">\n    <path d=\"M 138.913868 147.081693 \nL 141.222334 147.081693 \nL 141.222334 141.638394 \nL 138.913868 141.638394 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_69\">\n    <path d=\"M 141.222334 147.081693 \nL 143.530801 147.081693 \nL 143.530801 140.277569 \nL 141.222334 140.277569 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_70\">\n    <path d=\"M 143.530801 147.081693 \nL 145.839271 147.081693 \nL 145.839271 144.360043 \nL 143.530801 144.360043 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_71\">\n    <path d=\"M 145.839271 147.081693 \nL 148.147737 147.081693 \nL 148.147737 133.473446 \nL 145.839271 133.473446 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_72\">\n    <path d=\"M 148.147737 147.081693 \nL 150.456203 147.081693 \nL 150.456203 138.916745 \nL 148.147737 138.916745 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_73\">\n    <path d=\"M 150.456203 147.081693 \nL 152.764673 147.081693 \nL 152.764673 142.999219 \nL 150.456203 142.999219 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_74\">\n    <path d=\"M 152.764673 147.081693 \nL 155.073139 147.081693 \nL 155.073139 141.638394 \nL 152.764673 141.638394 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_75\">\n    <path d=\"M 155.073139 147.081693 \nL 157.381606 147.081693 \nL 157.381606 142.999219 \nL 155.073139 142.999219 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_76\">\n    <path d=\"M 157.381606 147.081693 \nL 159.690075 147.081693 \nL 159.690075 137.55592 \nL 157.381606 137.55592 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_77\">\n    <path d=\"M 159.690075 147.081693 \nL 161.998542 147.081693 \nL 161.998542 132.112621 \nL 159.690075 132.112621 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_78\">\n    <path d=\"M 161.998542 147.081693 \nL 164.307008 147.081693 \nL 164.307008 140.277569 \nL 161.998542 140.277569 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_79\">\n    <path d=\"M 164.307008 147.081693 \nL 166.615478 147.081693 \nL 166.615478 134.83427 \nL 164.307008 134.83427 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_80\">\n    <path d=\"M 166.615478 147.081693 \nL 168.92394 147.081693 \nL 168.92394 136.195095 \nL 166.615478 136.195095 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_81\">\n    <path d=\"M 168.92394 147.081693 \nL 171.23241 147.081693 \nL 171.23241 140.277569 \nL 168.92394 140.277569 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_82\">\n    <path d=\"M 171.23241 147.081693 \nL 173.54088 147.081693 \nL 173.54088 130.751796 \nL 171.23241 130.751796 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_83\">\n    <path d=\"M 173.54088 147.081693 \nL 175.849343 147.081693 \nL 175.849343 138.916745 \nL 173.54088 138.916745 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_84\">\n    <path d=\"M 175.849343 147.081693 \nL 178.157813 147.081693 \nL 178.157813 128.030147 \nL 175.849343 128.030147 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_85\">\n    <path d=\"M 178.157813 147.081693 \nL 180.466283 147.081693 \nL 180.466283 128.030147 \nL 178.157813 128.030147 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_86\">\n    <path d=\"M 180.466283 147.081693 \nL 182.774745 147.081693 \nL 182.774745 132.112621 \nL 180.466283 132.112621 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_87\">\n    <path d=\"M 182.774745 147.081693 \nL 185.083215 147.081693 \nL 185.083215 118.504373 \nL 182.774745 118.504373 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_88\">\n    <path d=\"M 185.083215 147.081693 \nL 187.391685 147.081693 \nL 187.391685 117.143549 \nL 185.083215 117.143549 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_89\">\n    <path d=\"M 187.391685 147.081693 \nL 189.700148 147.081693 \nL 189.700148 103.535301 \nL 187.391685 103.535301 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_90\">\n    <path d=\"M 189.700148 147.081693 \nL 192.008618 147.081693 \nL 192.008618 107.617775 \nL 189.700148 107.617775 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_91\">\n    <path d=\"M 192.008618 147.081693 \nL 194.317087 147.081693 \nL 194.317087 99.452827 \nL 192.008618 99.452827 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_92\">\n    <path d=\"M 194.317087 147.081693 \nL 196.62555 147.081693 \nL 196.62555 84.483755 \nL 194.317087 84.483755 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_93\">\n    <path d=\"M 196.62555 147.081693 \nL 198.93402 147.081693 \nL 198.93402 68.153858 \nL 196.62555 68.153858 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_94\">\n    <path d=\"M 198.93402 147.081693 \nL 201.24249 147.081693 \nL 201.24249 30.050765 \nL 198.93402 30.050765 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_95\">\n    <path d=\"M 201.24249 147.081693 \nL 203.550953 147.081693 \nL 203.550953 21.885817 \nL 201.24249 21.885817 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_96\">\n    <path d=\"M 203.550953 147.081693 \nL 205.859422 147.081693 \nL 205.859422 25.968291 \nL 203.550953 25.968291 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_97\">\n    <path d=\"M 205.859422 147.081693 \nL 208.167892 147.081693 \nL 208.167892 28.68994 \nL 205.859422 28.68994 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_98\">\n    <path d=\"M 208.167892 147.081693 \nL 210.476355 147.081693 \nL 210.476355 15.081693 \nL 208.167892 15.081693 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_99\">\n    <path d=\"M 210.476355 147.081693 \nL 212.784825 147.081693 \nL 212.784825 58.628085 \nL 210.476355 58.628085 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_100\">\n    <path d=\"M 212.784825 147.081693 \nL 215.093295 147.081693 \nL 215.093295 95.370353 \nL 212.784825 95.370353 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_101\">\n    <path d=\"M 215.093295 147.081693 \nL 217.401757 147.081693 \nL 217.401757 115.782724 \nL 215.093295 115.782724 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"patch_102\">\n    <path d=\"M 217.401757 147.081693 \nL 219.710227 147.081693 \nL 219.710227 133.473446 \nL 217.401757 133.473446 \nz\n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"mfff25d80e2\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mfff25d80e2\" x=\"56.669154\" y=\"147.081693\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- −3 -->\n      <g transform=\"translate(49.29806 161.68013) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-2212\" d=\"M 678 2272 \nL 4684 2272 \nL 4684 1741 \nL 678 1741 \nL 678 2272 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(83.789062 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#mfff25d80e2\" x=\"100.287393\" y=\"147.081693\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- −2 -->\n      <g transform=\"translate(92.916299 161.68013) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(83.789062 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#mfff25d80e2\" x=\"143.905633\" y=\"147.081693\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- −1 -->\n      <g transform=\"translate(136.534539 161.68013) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(83.789062 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#mfff25d80e2\" x=\"187.523872\" y=\"147.081693\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 0 -->\n      <g transform=\"translate(184.342622 161.68013) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_5\">\n     <!-- $\\mathbf{w}\\cdot\\mathbf{x}$ -->\n     <g transform=\"translate(119.5375 175.358255) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-Bold-77\" d=\"M 225 3500 \nL 1313 3500 \nL 1900 1088 \nL 2491 3500 \nL 3425 3500 \nL 4013 1113 \nL 4603 3500 \nL 5691 3500 \nL 4769 0 \nL 3547 0 \nL 2956 2406 \nL 2369 0 \nL 1147 0 \nL 225 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-22c5\" d=\"M 684 2619 \nL 1344 2619 \nL 1344 1825 \nL 684 1825 \nL 684 2619 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-Bold-78\" d=\"M 1422 1791 \nL 159 3500 \nL 1344 3500 \nL 2059 2463 \nL 2784 3500 \nL 3969 3500 \nL 2706 1797 \nL 4031 0 \nL 2847 0 \nL 2059 1106 \nL 1281 0 \nL 97 0 \nL 1422 1791 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-Bold-77\" transform=\"translate(0 0.3125)\"/>\n      <use xlink:href=\"#DejaVuSans-22c5\" transform=\"translate(111.865234 0.3125)\"/>\n      <use xlink:href=\"#DejaVuSans-Bold-78\" transform=\"translate(163.134766 0.3125)\"/>\n     </g>\n    </g>\n    <g id=\"text_6\">\n     <!-- 1e11 -->\n     <g transform=\"translate(203.346875 174.358255) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-31\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(63.623047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(125.146484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(188.769531 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_5\">\n      <defs>\n       <path id=\"mfbe096351d\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mfbe096351d\" x=\"33.2875\" y=\"147.081693\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 0 -->\n      <g transform=\"translate(19.925 150.880912) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#mfbe096351d\" x=\"33.2875\" y=\"119.865198\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 20 -->\n      <g transform=\"translate(13.5625 123.664417) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#mfbe096351d\" x=\"33.2875\" y=\"92.648703\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 40 -->\n      <g transform=\"translate(13.5625 96.447922) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#mfbe096351d\" x=\"33.2875\" y=\"65.432208\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 60 -->\n      <g transform=\"translate(13.5625 69.231427) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#mfbe096351d\" x=\"33.2875\" y=\"38.215714\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- 80 -->\n      <g transform=\"translate(13.5625 42.014932) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-38\" d=\"M 2034 2216 \nQ 1584 2216 1326 1975 \nQ 1069 1734 1069 1313 \nQ 1069 891 1326 650 \nQ 1584 409 2034 409 \nQ 2484 409 2743 651 \nQ 3003 894 3003 1313 \nQ 3003 1734 2745 1975 \nQ 2488 2216 2034 2216 \nz\nM 1403 2484 \nQ 997 2584 770 2862 \nQ 544 3141 544 3541 \nQ 544 4100 942 4425 \nQ 1341 4750 2034 4750 \nQ 2731 4750 3128 4425 \nQ 3525 4100 3525 3541 \nQ 3525 3141 3298 2862 \nQ 3072 2584 2669 2484 \nQ 3125 2378 3379 2068 \nQ 3634 1759 3634 1313 \nQ 3634 634 3220 271 \nQ 2806 -91 2034 -91 \nQ 1263 -91 848 271 \nQ 434 634 434 1313 \nQ 434 1759 690 2068 \nQ 947 2378 1403 2484 \nz\nM 1172 3481 \nQ 1172 3119 1398 2916 \nQ 1625 2713 2034 2713 \nQ 2441 2713 2670 2916 \nQ 2900 3119 2900 3481 \nQ 2900 3844 2670 4047 \nQ 2441 4250 2034 4250 \nQ 1625 4250 1398 4047 \nQ 1172 3844 1172 3481 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-38\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#mfbe096351d\" x=\"33.2875\" y=\"10.999219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_12\">\n      <!-- 100 -->\n      <g transform=\"translate(7.2 14.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_11\">\n    <path d=\"M 157.198543 147.081693 \nL 157.198543 8.481693 \n\" clip-path=\"url(#p15cb48d415)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #000000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_103\">\n    <path d=\"M 33.2875 147.081693 \nL 33.2875 8.481693 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_104\">\n    <path d=\"M 228.5875 147.081693 \nL 228.5875 8.481693 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_105\">\n    <path d=\"M 33.2875 147.081693 \nL 228.5875 147.081693 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_106\">\n    <path d=\"M 33.2875 8.481693 \nL 228.5875 8.481693 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_107\">\n     <path d=\"M 40.2875 60.516068 \nL 119.376563 60.516068 \nQ 121.376563 60.516068 121.376563 58.516068 \nL 121.376563 15.481693 \nQ 121.376563 13.481693 119.376563 13.481693 \nL 40.2875 13.481693 \nQ 38.2875 13.481693 38.2875 15.481693 \nL 38.2875 58.516068 \nQ 38.2875 60.516068 40.2875 60.516068 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"patch_108\">\n     <path d=\"M 42.2875 25.08013 \nL 62.2875 25.08013 \nL 62.2875 18.08013 \nL 42.2875 18.08013 \nz\n\" style=\"fill: #1f77b4; opacity: 0.6\"/>\n    </g>\n    <g id=\"text_13\">\n     <!-- t-shirts -->\n     <g transform=\"translate(70.2875 25.08013) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2d\" d=\"M 313 2009 \nL 1997 2009 \nL 1997 1497 \nL 313 1497 \nL 313 2009 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-2d\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(75.292969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(127.392578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(190.771484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(218.554688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(259.667969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(298.876953 0)\"/>\n     </g>\n    </g>\n    <g id=\"patch_109\">\n     <path d=\"M 42.2875 39.758255 \nL 62.2875 39.758255 \nL 62.2875 32.758255 \nL 42.2875 32.758255 \nz\n\" style=\"fill: #ff7f0e; opacity: 0.6\"/>\n    </g>\n    <g id=\"text_14\">\n     <!-- trousers -->\n     <g transform=\"translate(70.2875 39.758255) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(78.072266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(139.253906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(202.632812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(254.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(316.255859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(357.369141 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_12\">\n     <path d=\"M 42.2875 50.93638 \nL 52.2875 50.93638 \nL 62.2875 50.93638 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #000000; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_15\">\n     <!-- threshold -->\n     <g transform=\"translate(70.2875 54.43638) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(102.587891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(141.451172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(202.974609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(255.074219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(318.453125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(379.634766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(407.417969 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p15cb48d415\">\n   <rect x=\"33.2875\" y=\"8.481693\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-8 fw=all -->\n",
    "\n",
    "This plot summarizes the key points of hyperplane classifiers. Along the single direction\n",
    "$\\mathbf{w}$, the two classes form two well-separated humps, and the dashed\n",
    "threshold (the value of $\\mathbf{w}\\cdot\\mathbf{x}$ at the midpoint of the\n",
    "two means) cuts between them; the tails that spill across it are exactly the\n",
    "$\\approx 8\\%$ of images the rule misclassifies. A *learned* linear classifier, such as the softmax\n",
    "regression of that section, improves on this only by moving and\n",
    "tilting the same kind of boundary to cut the overlap more cleverly. A deep\n",
    "network goes one step further: it learns a new representation under which the\n",
    "two humps separate so widely that a hyperplane between them becomes trivial to\n",
    "place.\n",
    "\n",
    "## Matrices as Linear Maps\n",
    "\n",
    "### Linear Transformations\n",
    "\n",
    "Through that section and the above discussions,\n",
    "we have a solid understanding of the geometry of vectors, lengths, and angles.\n",
    "The remaining object is a geometric understanding of the linear\n",
    "transformations that matrices represent, and two dimensions are the place to\n",
    "build it.\n",
    "\n",
    "Suppose that we have some matrix:\n",
    "\n",
    "$$\n",
    "\\mathbf{A} = \\begin{bmatrix}\n",
    "a & b \\\\ c & d\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "If we want to apply this to an arbitrary vector\n",
    "$\\mathbf{v} = [x, y]^\\top$,\n",
    "we multiply and see that\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbf{A}\\mathbf{v} & = \\begin{bmatrix}a & b \\\\ c & d\\end{bmatrix}\\begin{bmatrix}x \\\\ y\\end{bmatrix} \n",
    "& = \\begin{bmatrix}ax+by\\\\ cx+dy\\end{bmatrix} \\\\\n",
    "& = x\\begin{bmatrix}a \\\\ c\\end{bmatrix} + y\\begin{bmatrix}b \\\\d\\end{bmatrix} \n",
    "& = x\\left\\{\\mathbf{A}\\begin{bmatrix}1\\\\0\\end{bmatrix}\\right\\} + y\\left\\{\\mathbf{A}\\begin{bmatrix}0\\\\1\\end{bmatrix}\\right\\}.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "This may seem like an odd computation,\n",
    "where something clear became somewhat impenetrable.\n",
    "However, it tells us that we can write the way\n",
    "that a matrix transforms *any* vector\n",
    "in terms of how it transforms *two specific vectors*:\n",
    "$[1,0]^\\top$ and $[0,1]^\\top$.\n",
    "We have reduced an infinite problem\n",
    "(what happens to any pair of real numbers)\n",
    "to a finite one (what happens to these specific vectors).\n",
    "The vectors $[1,0]^\\top$ and $[0,1]^\\top$ are exactly the standard basis\n",
    "$\\mathbf{e}_1, \\mathbf{e}_2$ from our discussion of spans and bases: because\n",
    "every vector is a (unique) weighted sum of basis vectors, knowing where a\n",
    "matrix sends a basis determines where it sends everything.\n",
    "\n",
    "Let's draw what happens when we use the specific matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{A} = \\begin{bmatrix}\n",
    "1 & 2 \\\\\n",
    "-1 & 3\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "If we look at the specific vector $\\mathbf{v} = [2, -1]^\\top$,\n",
    "we see this is $2\\cdot[1,0]^\\top - [0,1]^\\top$,\n",
    "and thus we know that the matrix $\\mathbf{A}$ will send this to\n",
    "$2\\,\\mathbf{A}[1,0]^\\top - \\mathbf{A}[0,1]^\\top = 2[1, -1]^\\top - [2,3]^\\top = [0, -5]^\\top$.\n",
    "If we follow this logic through carefully,\n",
    "say by considering the grid of all integer pairs of points,\n",
    "we see that what happens is that the matrix multiplication\n",
    "can skew, rotate, and scale the grid,\n",
    "but the grid structure must remain as you see in the figure.\n",
    "\n",
    "![The matrix $\\mathbf{A} = \\bigl(\\begin{smallmatrix}1 & 2 \\\\ -1 & 3\\end{smallmatrix}\\bigr)$ acting on the plane. The basis vectors are sent to $\\mathbf{A}\\mathbf{e}_1 = (1, -1)^\\top$ and $\\mathbf{A}\\mathbf{e}_2 = (2, 3)^\\top$, and the entire grid is transported along with them: lines stay lines, the origin stays put, and equally spaced cells stay equally spaced. The shaded unit square maps to the shaded parallelogram, whose area will be the subject of the determinant below.](../img/mdl-la-linear-map.svg)\n",
    "\n",
    "The point to internalize about linear transformations represented by matrices:\n",
    "matrices are incapable of distorting some parts of space differently than others.\n",
    "All they can do is take the original coordinates on our space\n",
    "and skew, rotate, and scale them.\n",
    "\n",
    "Some distortions can be severe.  For instance the matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{B} = \\begin{bmatrix}\n",
    "2 & -1 \\\\ 4 & -2\n",
    "\\end{bmatrix},\n",
    "$$\n",
    "\n",
    "compresses the entire two-dimensional plane down to a single line.\n",
    "Identifying and working with such transformations are the topic of a later section,\n",
    "but geometrically we can see that this is fundamentally different\n",
    "from the types of transformations we saw above.\n",
    "For instance, the result from matrix $\\mathbf{A}$ can be \"bent back\" to the original grid.  The results from matrix $\\mathbf{B}$ cannot\n",
    "because we will never know where the vector $[1,2]^\\top$ came from: was\n",
    "it $[1,1]^\\top$ or $[0, -1]^\\top$?\n",
    "\n",
    "While this picture was for a $2\\times2$ matrix,\n",
    "nothing prevents us from taking the lessons learned into higher dimensions.\n",
    "If we take similar basis vectors like $[1,0, \\ldots,0]$\n",
    "and see where our matrix sends them,\n",
    "we can start to get a feeling for how the matrix multiplication\n",
    "distorts the entire space in whatever dimension space we are dealing with.\n",
    "\n",
    "Nothing requires the matrix to be square, either. An $m \\times n$ matrix takes\n",
    "vectors with $n$ entries to vectors with $m$ entries: it is a linear map\n",
    "*between* spaces, from $\\mathbb{R}^n$ to $\\mathbb{R}^m$, and it is still\n",
    "determined by where it sends the $n$ basis vectors (whose images are its\n",
    "columns). A $2 \\times 3$ matrix has an image of dimension at most two; it\n",
    "fills the output plane only when its rank is two. A $3 \\times 2$ matrix has a\n",
    "plane through the origin as its image when its rank is two, and a line or the\n",
    "origin at lower rank. Every fully connected layer of a\n",
    "neural network is exactly such a map between spaces of different dimensions,\n",
    "composed with a nonlinearity.\n",
    "\n",
    "### Orthogonal Matrices\n",
    "\n",
    "A matrix may skew, rotate, and scale, but a special and important family does\n",
    "*only* the rigid part: it rotates or reflects without any stretching. A square\n",
    "matrix $\\mathbf{Q}$ is called **orthogonal** when its columns are orthonormal,\n",
    "which we can write compactly as $\\mathbf{Q}^\\top\\mathbf{Q} = \\mathbf{I}$. The\n",
    "defining property of such maps is that they **preserve lengths and angles**,\n",
    "because they preserve every dot product:\n",
    "\n",
    "$$\n",
    "(\\mathbf{Q}\\mathbf{x})\\cdot(\\mathbf{Q}\\mathbf{y})\n",
    " = (\\mathbf{Q}\\mathbf{x})^\\top(\\mathbf{Q}\\mathbf{y})\n",
    " = \\mathbf{x}^\\top\\mathbf{Q}^\\top\\mathbf{Q}\\,\\mathbf{y}\n",
    " = \\mathbf{x}^\\top\\mathbf{y}\n",
    " = \\mathbf{x}\\cdot\\mathbf{y}.\n",
    "$$\n",
    "\n",
    "Taking $\\mathbf{y} = \\mathbf{x}$ shows $\\|\\mathbf{Q}\\mathbf{x}\\| =\n",
    "\\|\\mathbf{x}\\|$, so an orthogonal map is a rigid motion of space. Since\n",
    "$\\mathbf{Q}^\\top\\mathbf{Q} = \\mathbf{I}$ means $\\mathbf{Q}^{-1} =\n",
    "\\mathbf{Q}^\\top$, such maps are trivially invertible, and as we will prove\n",
    "when we meet the determinant at the end of this section, their volume scaling\n",
    "is $\\det\\mathbf{Q} = \\pm 1$ (the sign distinguishing rotations from\n",
    "reflections). Orthogonal matrices are the \"distortion-free\" linear maps, and\n",
    "they will turn out to be the building blocks\n",
    "of the two decompositions in the sections that follow: the spectral theorem\n",
    "writes a symmetric matrix as $\\mathbf{Q}\\boldsymbol\\Lambda\\mathbf{Q}^\\top$\n",
    "(that section), and the singular value decomposition\n",
    "writes *any* matrix as orthogonal–diagonal–orthogonal\n",
    "(that section).\n",
    "\n",
    "Where do orthonormal columns come from in the first place? Any linearly\n",
    "independent collection can be converted into an orthonormal basis of its span\n",
    "by the *Gram–Schmidt process*: walk through the vectors in order, subtract\n",
    "from each one its projection the equation onto each direction\n",
    "already produced, and normalize what remains. In matrix form this algorithm is\n",
    "the *QR factorization*, the `qr` call that produced the orthonormal basis\n",
    "in our subspace-projection demo earlier in this section. We will not need its\n",
    "inner workings in this chapter; it is enough to know that orthonormal bases\n",
    "are cheap to compute, which is one reason the decompositions built from\n",
    "them are so practical.\n",
    "\n",
    "### Linear Dependence, Rank, and Invertibility\n",
    "\n",
    "Consider again the matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{B} = \\begin{bmatrix}\n",
    "2 & -1 \\\\ 4 & -2\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "This compresses the entire plane down to live on the single line $y = 2x$.\n",
    "The question now arises: is there some way we can detect this\n",
    "just looking at the matrix itself?\n",
    "The answer is that indeed we can.\n",
    "Let's take $\\mathbf{b}_1 = [2,4]^\\top$ and $\\mathbf{b}_2 = [-1, -2]^\\top$\n",
    "be the two columns of $\\mathbf{B}$.\n",
    "Remember that we can write everything transformed by the matrix $\\mathbf{B}$\n",
    "as a linear combination of the columns of the matrix,\n",
    "like $a_1\\mathbf{b}_1 + a_2\\mathbf{b}_2$;\n",
    "in the language of spans, the outputs of $\\mathbf{B}$ fill out exactly its\n",
    "column space.\n",
    "The fact that $\\mathbf{b}_1 = -2\\cdot\\mathbf{b}_2$\n",
    "means that we can write any linear combination of those two columns\n",
    "entirely in terms of say $\\mathbf{b}_2$ since\n",
    "\n",
    "$$\n",
    "a_1\\mathbf{b}_1 + a_2\\mathbf{b}_2 = -2a_1\\mathbf{b}_2 + a_2\\mathbf{b}_2 = (a_2-2a_1)\\mathbf{b}_2.\n",
    "$$\n",
    "\n",
    "This means that one of the columns is, in a sense, redundant\n",
    "because it does not define a unique direction in space.\n",
    "This should not surprise us too much\n",
    "since we already saw that this matrix\n",
    "collapses the entire plane down into a single line.\n",
    "Moreover, we see that the linear dependence\n",
    "$\\mathbf{b}_1 = -2\\cdot\\mathbf{b}_2$ captures this.\n",
    "To make this more symmetrical between the two vectors, we will write this as\n",
    "\n",
    "$$\n",
    "\\mathbf{b}_1  + 2\\cdot\\mathbf{b}_2 = 0.\n",
    "$$\n",
    "\n",
    "The coefficients $(1, 2)$ of this relation say\n",
    "precisely that $\\mathbf{B}[1, 2]^\\top = 1\\cdot\\mathbf{b}_1 + 2\\cdot\\mathbf{b}_2\n",
    "= \\mathbf{0}$, so the dependence hands us a nonzero vector in the *null space*\n",
    "of $\\mathbf{B}$. the figure shows the two subspaces of\n",
    "$\\mathbf{B}$ at work together: the whole plane is crushed onto the column\n",
    "space, while the null-space direction is exactly the set of inputs that land\n",
    "on the origin. (For this particular $\\mathbf{B}$ the two subspaces happen to\n",
    "coincide as sets, both being the line $y = 2x$: a coincidence, equivalent\n",
    "to $\\mathbf{B}^2 = \\mathbf{0}$, that makes the picture no less instructive,\n",
    "since what the matrix *produces* and what it *destroys* are different roles\n",
    "even when they occupy the same line.)\n",
    "\n",
    "![The matrix $\\mathbf{B} = \\left(\\begin{smallmatrix}2 & -1 \\\\ 4 & -2\\end{smallmatrix}\\right)$ collapsing the plane. Left: the input plane, with three marked points and the null-space direction $(1,2)^\\top$ dashed; every input on that line is sent to the origin. Right: the image. The entire grid lands on the column space, the line $y = 2x$ spanned by the columns $\\mathbf{b}_1$ and $\\mathbf{b}_2$; the marked points land at their images, and the null-space line has collapsed to $\\mathbf{0}$. Once distinct inputs collide like this, no inverse can tell them apart.](../img/mdl-la-null-collapse.svg)\n",
    "\n",
    "In general, we will say that a collection of vectors\n",
    "$\\mathbf{v}_1, \\ldots, \\mathbf{v}_k$ are *linearly dependent*\n",
    "if there exist coefficients $a_1, \\ldots, a_k$ *not all equal to zero* so that\n",
    "\n",
    "$$\n",
    "\\sum_{i=1}^k a_i\\mathbf{v}_i = 0.\n",
    "$$\n",
    "\n",
    "In this case, we can solve for one of the vectors\n",
    "in terms of some combination of the others,\n",
    "and effectively render it redundant.\n",
    "Thus, a linear dependence in the columns of a matrix\n",
    "is a witness to the fact that our matrix\n",
    "is compressing the space down to some lower dimension.\n",
    "If there is no linear dependence we say the vectors are *linearly\n",
    "independent*, the same notion we met when defining bases, now read as a\n",
    "property of a matrix's columns. If the columns of a matrix are linearly\n",
    "independent, no compression occurs and the operation can be undone.\n",
    "\n",
    "#### Rank\n",
    "\n",
    "If we have a general $m\\times n$ matrix,\n",
    "it is reasonable to ask the dimension of the space the matrix maps *onto*,\n",
    "the dimension of its image.\n",
    "A concept known as the *rank* will be our answer.\n",
    "In the previous section, we noted that a linear dependence\n",
    "bears witness to compression of space into a lower dimension\n",
    "and so we will be able to use this to define the notion of rank.\n",
    "In particular, the rank of a matrix $\\mathbf{A}$\n",
    "is the largest number of linearly independent columns\n",
    "amongst all subsets of columns. For example, our matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{B} = \\begin{bmatrix}\n",
    "2 & -1 \\\\ 4 & -2\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "from above has $\\textrm{rank}(\\mathbf{B})=1$, since the two columns\n",
    "$[2, 4]^\\top$ and $[-1, -2]^\\top$ are linearly dependent,\n",
    "while each column on its own is linearly independent.\n",
    "For a more challenging example, we can consider\n",
    "\n",
    "$$\n",
    "\\mathbf{C} = \\begin{bmatrix}\n",
    "1& 3 & 0 & -1 & 0 \\\\\n",
    "-1 & 0 & 1 & 1 & -1 \\\\\n",
    "0 & 3 & 1 & 0 & -1 \\\\\n",
    "2 & 3 & -1 & -2 & 1\n",
    "\\end{bmatrix},\n",
    "$$\n",
    "\n",
    "and show that $\\mathbf{C}$ has rank two since, for instance,\n",
    "the first two columns are linearly independent,\n",
    "however any of the $\\binom{5}{3} = 10$ collections of three columns are\n",
    "linearly dependent. (Exercise: verify this, either by hand or with\n",
    "`matrix_rank`.)\n",
    "\n",
    "Equivalently, the rank is the *dimension of the column space* we defined\n",
    "alongside spans and bases, and a foundational theorem of linear algebra says\n",
    "this equals the dimension of the *row space*, the span of the rows. A matrix\n",
    "\"compresses space\" into a lower dimension exactly when its rank is smaller\n",
    "than its number of columns, equivalently, when its null space contains some\n",
    "nonzero vector.\n",
    "\n",
    "This procedure, as described, is very inefficient.\n",
    "It requires looking at every subset of the columns of our given matrix,\n",
    "and thus is potentially exponential in the number of columns.\n",
    "Later we will see a more computationally efficient way\n",
    "to compute the rank of a matrix, but for now,\n",
    "this is sufficient to see that the concept\n",
    "is well defined and understand the meaning.\n",
    "\n",
    "The trade-off between compression and survival is exact.\n",
    "\n",
    "**Proposition (rank--nullity).** *For an $m \\times n$ matrix $\\mathbf{A}$,*\n",
    "\n",
    "$$\n",
    "\\operatorname{rank}\\mathbf{A} + \\dim\\ker\\mathbf{A} = n,\n",
    "$$\n",
    "\n",
    "*where $\\ker\\mathbf{A}$ denotes the null space.*\n",
    "\n",
    "**Proof.** Choose a basis $\\mathbf{w}_1, \\ldots, \\mathbf{w}_k$ of the null\n",
    "space and extend it to a basis $\\mathbf{w}_1, \\ldots, \\mathbf{w}_k,\n",
    "\\mathbf{v}_1, \\ldots, \\mathbf{v}_{n-k}$ of $\\mathbb{R}^n$. The images\n",
    "$\\mathbf{A}\\mathbf{v}_1, \\ldots, \\mathbf{A}\\mathbf{v}_{n-k}$ span the column\n",
    "space (the $\\mathbf{w}_i$ contribute nothing), and they are independent: if\n",
    "$\\sum_i c_i \\mathbf{A}\\mathbf{v}_i = \\mathbf{0}$ then $\\sum_i c_i \\mathbf{v}_i$\n",
    "lies in the null space, hence is a combination of the $\\mathbf{w}_j$,\n",
    "impossible within a basis unless every $c_i = 0$. So the column space has\n",
    "dimension exactly $n - k$. $\\blacksquare$\n",
    "\n",
    "Read it as conservation of directions: of the $n$ directions coming in,\n",
    "$\\dim\\ker\\mathbf{A}$ are destroyed and $\\operatorname{rank}\\mathbf{A}$\n",
    "survive. $\\mathbf{B}$ has $1 + 1 = 2$, one column-space direction\n",
    "surviving and one null-space\n",
    "direction crushed, exactly as the figure shows. The\n",
    "singular value decomposition will make this split visible, with orthonormal\n",
    "bases attached to both halves, in that section.\n",
    "\n",
    "#### Invertibility\n",
    "\n",
    "We have seen above that multiplication by a matrix with linearly dependent columns\n",
    "cannot be undone, i.e., there is no inverse operation that can always recover the input.  However, multiplication by a *full-rank* matrix\n",
    "(an $n \\times n$ matrix $\\mathbf{A}$ with rank $n$)\n",
    "can always be undone.  Consider the matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{I} = \\begin{bmatrix}\n",
    "1 & 0 & \\cdots & 0 \\\\\n",
    "0 & 1 & \\cdots & 0 \\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "0 & 0 & \\cdots & 1\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "which is the matrix with ones along the diagonal, and zeros elsewhere.\n",
    "We call this the *identity* matrix.\n",
    "It is the matrix which leaves our data unchanged when applied.\n",
    "To find a matrix which undoes what our matrix $\\mathbf{A}$ has done,\n",
    "we want to find a matrix $\\mathbf{A}^{-1}$ such that\n",
    "\n",
    "$$\n",
    "\\mathbf{A}^{-1}\\mathbf{A} = \\mathbf{A}\\mathbf{A}^{-1} =  \\mathbf{I}.\n",
    "$$\n",
    "\n",
    "If we look at this as a system, we have $n \\times n$ unknowns\n",
    "(the entries of $\\mathbf{A}^{-1}$) and $n \\times n$ equations\n",
    "(the equality that needs to hold between every entry of the product $\\mathbf{A}^{-1}\\mathbf{A}$ and every entry of $\\mathbf{I}$)\n",
    "so we should generically expect a solution to exist.\n",
    "\"Generically\" is made precise by the *determinant*, introduced below: a\n",
    "solution exists exactly when the determinant is nonzero.\n",
    "We call such a matrix $\\mathbf{A}^{-1}$ the *inverse* matrix.\n",
    "As an example, if $\\mathbf{A}$ is the general $2 \\times 2$ matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{A} = \\begin{bmatrix}\n",
    "a & b \\\\\n",
    "c & d\n",
    "\\end{bmatrix},\n",
    "$$\n",
    "\n",
    "then we can see that the inverse is\n",
    "\n",
    "$$\n",
    " \\frac{1}{ad-bc}  \\begin{bmatrix}\n",
    "d & -b \\\\\n",
    "-c & a\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "We can test to see this by seeing that multiplying\n",
    "by the inverse given by the formula above works in practice."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-invertibility"
   },
   "source": [
    "import numpy as onp\n",
    "M = onp.array([[1, 2], [1, 4]])\n",
    "M_inv = onp.array([[2, -1], [-0.5, 0.5]])\n",
    "M_inv.dot(M)"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "array([[1., 0.],\n       [0., 1.]])"
     },
     "metadata": {},
     "execution_count": 8
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-9 fw=all -->\n",
    "\n",
    "#### Numerical Issues\n",
    "While the matrix inverse is useful in theory, in practice we rarely want to\n",
    "*compute* it. To solve the linear system $\\mathbf{A}\\mathbf{x} = \\mathbf{b}$,\n",
    "call `linalg.solve(A, b)`, which factorizes $\\mathbf{A}$ without ever forming\n",
    "its inverse, rather than the tempting but inferior `inv(A) @ b`: just as\n",
    "division by a small number is numerically unstable, so is inversion of a\n",
    "matrix that is close to having low rank. Sparsity raises the stakes further.\n",
    "A matrix with a million rows and columns but only $5$ million non-zero entries\n",
    "is cheap to store, yet its inverse is typically dense, with on the order of\n",
    "$10^{12}$ non-zero entries. The quantity that makes \"close to low rank\"\n",
    "precise, and that measures exactly how much a solve can amplify error, is the\n",
    "condition number of that section.\n",
    "\n",
    "### The Determinant\n",
    "The geometric view of linear algebra gives an intuitive way\n",
    "to interpret a fundamental quantity known as the *determinant*.\n",
    "Return to the grid picture of the figure and watch the\n",
    "shaded unit square, the square with edges $\\mathbf{e}_1 = (1,0)^\\top$ and\n",
    "$\\mathbf{e}_2 = (0,1)^\\top$, hence with area one. The matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{A} = \\begin{bmatrix}\n",
    "1 & 2 \\\\\n",
    "-1 & 3\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "carries it to the shaded parallelogram with edges\n",
    "$\\mathbf{A}\\mathbf{e}_1 = [1, -1]^\\top$ and $\\mathbf{A}\\mathbf{e}_2 = [2, 3]^\\top$.\n",
    "There is no reason this parallelogram should have the same area\n",
    "that we started with, and indeed an exercise in coordinate geometry\n",
    "shows that its area is exactly $5$: this particular matrix\n",
    "quintuples areas.\n",
    "\n",
    "In general, a matrix\n",
    "\n",
    "$$\n",
    "\\mathbf{A} = \\begin{bmatrix}\n",
    "a & b \\\\\n",
    "c & d\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "sends the unit square to the parallelogram with edges $(a, c)^\\top$ and\n",
    "$(b, d)^\\top$, and we can compute that parallelogram's area directly. Suppose\n",
    "for the moment that all four entries are positive and that $(a, c)^\\top$ makes\n",
    "the smaller angle with the $x$-axis. The parallelogram has vertices $(0,0)$,\n",
    "$(a, c)$, $(b, d)$, and $(a+b, c+d)$; enclose it in its bounding rectangle\n",
    "$[0, a+b] \\times [0, c+d]$. The part of the rectangle outside the\n",
    "parallelogram consists of two $b \\times c$ rectangles in the corners, two\n",
    "right triangles with legs $a$ and $c$, and two right triangles with legs $b$\n",
    "and $d$. Subtracting all six pieces from the rectangle's area leaves\n",
    "\n",
    "$$\n",
    "(a+b)(c+d) - 2bc - 2\\cdot\\tfrac{1}{2}\\,ac - 2\\cdot\\tfrac{1}{2}\\,bd = ad - bc.\n",
    "$$\n",
    "\n",
    "Working through the other sign configurations changes only the sign of the\n",
    "result, never its magnitude: the parallelogram's area is always $|ad - bc|$.\n",
    "The signed quantity $ad-bc$\n",
    "is referred to as the *determinant*, written $\\det\\mathbf{A}$.\n",
    "\n",
    "Let's quickly confirm the worked example in code: for the matrix\n",
    "$\\mathbf{A}$ above the determinant should come out to\n",
    "$1 \\cdot 3 - 2 \\cdot (-1) = 5$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-determinant"
   },
   "source": [
    "import numpy as onp\n",
    "onp.linalg.det(onp.array([[1, 2], [-1, 3]]))"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "np.float64(4.999999999999999)"
     },
     "metadata": {},
     "execution_count": 9
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-10 fw=all -->\n",
    "\n",
    "Note that the expression $ad - bc$ can be zero or even negative, and\n",
    "the figure shows the three possible regimes side by\n",
    "side, each for a different matrix: a positive determinant, where the unit\n",
    "square maps to a parallelogram of area $\\det\\mathbf{A}$; a negative\n",
    "determinant, where the parallelogram has area $|\\det\\mathbf{A}|$ but the map\n",
    "has *flipped the orientation* of the plane (the images of $\\mathbf{e}_1$ and\n",
    "$\\mathbf{e}_2$ have traded sides); and a zero determinant, where the square is\n",
    "crushed to a segment. The negative case is a matter of convention taken\n",
    "generally in mathematics: if the matrix flips the figure, we say the area is\n",
    "negated.\n",
    "\n",
    "![The determinant as a signed area, shown for three different matrices. The unit square spanned by the basis vectors (dashed) maps to the parallelogram spanned by the columns of each matrix, and the signed area of that parallelogram is the determinant: (a) positive; (b) negative, because the matrix flips orientation; (c) zero, because the matrix collapses the square to a segment.](../img/mdl-la-determinant.svg)\n",
    "\n",
    "Let's see now that when the determinant is zero, we learn more.\n",
    "Consider our compressing matrix from before,\n",
    "\n",
    "$$\n",
    "\\mathbf{B} = \\begin{bmatrix}\n",
    "2 & -1 \\\\ 4 & -2\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "If we compute the determinant of this matrix,\n",
    "we get $2\\cdot(-2) - (-1)\\cdot 4 = 0$.\n",
    "Given our understanding above, this makes sense.\n",
    "$\\mathbf{B}$ compresses the unit square\n",
    "down to a segment of the line $y = 2x$, which has zero area:\n",
    "the situation of panel (c) in the figure, and exactly\n",
    "the collapse pictured in the figure.\n",
    "And indeed, being compressed into a lower dimensional space\n",
    "is the only way to have zero area after the transformation.\n",
    "Thus we see the following result is true:\n",
    "a matrix $A$ is invertible if and only if\n",
    "the determinant is not equal to zero. We prove this equivalence below, once\n",
    "the determinant exists in every dimension.\n",
    "\n",
    "#### The Determinant in General\n",
    "\n",
    "The two-dimensional picture says what the determinant of an $n \\times n$\n",
    "matrix should be: the signed volume of the parallelepiped spanned by its\n",
    "columns. Rather than wrestle with $n$-dimensional geometry directly, we\n",
    "distill the three properties of signed volume that determine it completely,\n",
    "stated for the columns $\\mathbf{a}_1, \\ldots, \\mathbf{a}_n$ of an\n",
    "$n \\times n$ matrix:\n",
    "\n",
    "1. **Multilinear**: $\\det$ is linear in each column separately, with the other\n",
    "   columns held fixed. (Scaling one edge of a parallelepiped scales its\n",
    "   volume; splitting one edge as a sum splits the volume accordingly.)\n",
    "2. **Alternating**: $\\det$ is zero whenever two columns are equal. (The\n",
    "   parallelepiped then flattens into a lower-dimensional slab of zero volume.)\n",
    "3. **Normalized**: $\\det \\mathbf{I} = 1$. (The unit cube has volume one.)\n",
    "\n",
    "The granted fact for this subsection, which we use without proof, is that\n",
    "there is exactly *one* function of the columns with these three properties;\n",
    "it is the determinant (see [@Horn.Johnson.2012] for the construction and\n",
    "the uniqueness argument). Uniqueness comes in a sharper form that we will use\n",
    "below: *every* function $f$ of the columns satisfying (1) and (2) is a\n",
    "multiple of the determinant, $f = f(\\mathbf{I}) \\cdot \\det$. To see why, set\n",
    "$g = f - f(\\mathbf{I})\\cdot\\det$; then $g$ satisfies (1) and (2) with\n",
    "$g(\\mathbf{I}) = 0$, so $g + \\det$ satisfies all three properties, hence\n",
    "equals $\\det$ by uniqueness, forcing $g = 0$.\n",
    "\n",
    "The three properties are a machine for producing identities. First,\n",
    "**swapping two columns flips the sign of the determinant**. Place the vector\n",
    "$\\mathbf{u}+\\mathbf{v}$ in two different column slots and expand by\n",
    "multilinearity:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "0 &= \\det(\\ldots, \\mathbf{u}+\\mathbf{v}, \\ldots, \\mathbf{u}+\\mathbf{v}, \\ldots) \\\\\n",
    "  &= \\det(\\ldots, \\mathbf{u}, \\ldots, \\mathbf{u}, \\ldots)\n",
    "   + \\det(\\ldots, \\mathbf{u}, \\ldots, \\mathbf{v}, \\ldots)\n",
    "   + \\det(\\ldots, \\mathbf{v}, \\ldots, \\mathbf{u}, \\ldots)\n",
    "   + \\det(\\ldots, \\mathbf{v}, \\ldots, \\mathbf{v}, \\ldots).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "The left-hand side, the first term, and the last term all vanish by the\n",
    "alternating property, leaving\n",
    "\n",
    "$$\n",
    "\\det(\\ldots, \\mathbf{u}, \\ldots, \\mathbf{v}, \\ldots)\n",
    " = -\\det(\\ldots, \\mathbf{v}, \\ldots, \\mathbf{u}, \\ldots).\n",
    "$$\n",
    "\n",
    "This is where the *sign* of the signed area comes from: exchanging two edges\n",
    "reverses the orientation of the parallelepiped, and an odd permutation of the\n",
    "columns negates the determinant.\n",
    "\n",
    "Second, the three properties pin down a formula. Expand each column in the\n",
    "standard basis, $\\mathbf{a}_j = \\sum_i a_{ij}\\,\\mathbf{e}_i$, and apply\n",
    "multilinearity column by column: $\\det\\mathbf{A}$ becomes a sum of terms of\n",
    "the form $a_{i_1 1} a_{i_2 2} \\cdots a_{i_n n}\n",
    "\\det(\\mathbf{e}_{i_1}, \\ldots, \\mathbf{e}_{i_n})$. Whenever two of the chosen\n",
    "row indices coincide, the term dies by the alternating property; when all are\n",
    "distinct, the columns $\\mathbf{e}_{i_1}, \\ldots, \\mathbf{e}_{i_n}$ are a\n",
    "reshuffling of the identity matrix's, so repeated column swaps reduce the\n",
    "determinant factor to $\\pm 1$. For a $2 \\times 2$ matrix with columns\n",
    "$\\mathbf{a}_1 = a\\,\\mathbf{e}_1 + c\\,\\mathbf{e}_2$ and\n",
    "$\\mathbf{a}_2 = b\\,\\mathbf{e}_1 + d\\,\\mathbf{e}_2$, the expansion has four\n",
    "terms; the two with a repeated basis vector vanish and\n",
    "\n",
    "$$\n",
    "\\det(\\mathbf{a}_1, \\mathbf{a}_2)\n",
    " = ad\\,\\det(\\mathbf{e}_1, \\mathbf{e}_2)\n",
    " + cb\\,\\det(\\mathbf{e}_2, \\mathbf{e}_1)\n",
    " = ad - bc,\n",
    "$$\n",
    "\n",
    "recovering the parallelogram area we computed by hand. In general the\n",
    "determinant is a signed sum, over all ways of picking one entry from each row\n",
    "and each column, of the products of the chosen entries; this is the\n",
    "permutation formula, and (1)+(2)+(3) leave no other possibility.\n",
    "\n",
    "For hand computation the sum is organized as *cofactor expansion*: expanding\n",
    "the first column in the standard basis splits $\\det\\mathbf{A}$ into $n$\n",
    "smaller determinants, with alternating signs, of the submatrices obtained by\n",
    "deleting the first column and one row. Let us work a $3 \\times 3$ example,\n",
    "\n",
    "$$\n",
    "\\mathbf{A} = \\begin{bmatrix}\n",
    "2 & 1 & 0 \\\\\n",
    "1 & 3 & 1 \\\\\n",
    "0 & 1 & 2\n",
    "\\end{bmatrix},\n",
    "$$\n",
    "\n",
    "expanding along the first column:\n",
    "\n",
    "$$\n",
    "\\det \\mathbf{A}\n",
    " = 2 \\det \\begin{bmatrix} 3 & 1 \\\\ 1 & 2 \\end{bmatrix}\n",
    " - 1 \\det \\begin{bmatrix} 1 & 0 \\\\ 1 & 2 \\end{bmatrix}\n",
    " + 0 \\det \\begin{bmatrix} 1 & 0 \\\\ 3 & 1 \\end{bmatrix}\n",
    " = 2 \\cdot 5 - 1 \\cdot 2 + 0 = 8.\n",
    "$$\n",
    "\n",
    "Geometrically, $\\mathbf{A}$ maps the unit cube to a parallelepiped of volume\n",
    "$8$, and it scales the volume of every solid by that same factor. Let us\n",
    "check the equation in code, along with two consequences of the\n",
    "properties above: swapping two columns flips the sign, and the determinant of\n",
    "a triangular matrix is the product of its diagonal entries."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "mdl-geometry-linear-algebraic-ops-det-3x3"
   },
   "source": [
    "import numpy as onp\n",
    "A = onp.array([[2, 1, 0], [1, 3, 1], [0, 1, 2]])\n",
    "A_swap = onp.array([[1, 2, 0], [3, 1, 1], [1, 0, 2]])  # first two columns swapped\n",
    "T = onp.array([[2, 5, 1], [0, 3, 4], [0, 0, 1]])       # upper triangular\n",
    "(onp.linalg.det(A),       # 8, matching the cofactor expansion\n",
    " onp.linalg.det(A_swap),  # -8: a column swap flips the sign\n",
    " onp.linalg.det(T))       # 6 = 2 * 3 * 1, the diagonal product"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(np.float64(8.000000000000002),\n np.float64(-8.000000000000002),\n np.float64(6.0))"
     },
     "metadata": {},
     "execution_count": 10
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-11 fw=all -->\n",
    "\n",
    "The triangular rule deserves its one-paragraph proof, since the next section\n",
    "relies on it. Suppose $\\mathbf{T}$ is upper triangular, so $t_{ij} = 0$\n",
    "whenever $i > j$. Each term of the permutation formula picks one entry from\n",
    "every column, all in distinct rows. To be nonzero, the entry picked from\n",
    "column $1$ must come from row $1$ (every lower entry vanishes); the entry from\n",
    "column $2$ must then come from row $2$ (row $1$ is taken and rows $3, \\ldots,\n",
    "n$ hold zeros); continuing across the columns, only the diagonal choice\n",
    "survives. That single term carries the sign of no swaps at all, so\n",
    "\n",
    "$$\n",
    "\\det \\mathbf{T} = t_{11} t_{22} \\cdots t_{nn},\n",
    "$$\n",
    "\n",
    "the product of the diagonal entries. The same argument, run from column $n$\n",
    "backwards, handles lower triangular matrices.\n",
    "\n",
    "One more identity rounds out the toolkit: $\\det \\mathbf{A}^\\top =\n",
    "\\det \\mathbf{A}$. For $2 \\times 2$ matrices this is visible at a glance, since\n",
    "transposing swaps $b$ and $c$ and leaves $ad - bc$ unchanged. In general,\n",
    "transposing merely reindexes the permutation formula: each product of $n$\n",
    "entries, one from every row and every column, appears in both expansions with\n",
    "the same sign (see [@Horn.Johnson.2012] for the bookkeeping). One\n",
    "consequence: everything the determinant says about columns holds verbatim for\n",
    "rows.\n",
    "\n",
    "#### The Unifying Theorem\n",
    "\n",
    "The equivalence between a zero determinant, linearly dependent columns, and\n",
    "failure of invertibility connects three notions we have met separately. We\n",
    "state it once, with a proof we can carry out by hand in two dimensions.\n",
    "\n",
    "**Proposition (the unifying theorem).** *For a square matrix $\\mathbf{A}$, the\n",
    "following are equivalent:*\n",
    "(i) *$\\det\\mathbf{A} = 0$;*\n",
    "(ii) *the columns of $\\mathbf{A}$ are linearly dependent;*\n",
    "(iii) *$\\mathbf{A}$ is not invertible.*\n",
    "\n",
    "**Proof (for the $2 \\times 2$ case).** We give the argument for the\n",
    "$2 \\times 2$ matrix\n",
    "$\\mathbf{A} = \\bigl[\\begin{smallmatrix} a & b \\\\ c & d \\end{smallmatrix}\\bigr]$,\n",
    "where every step is a picture. Write the two\n",
    "columns as $\\mathbf{a}_1 = [a, c]^\\top$ and $\\mathbf{a}_2 = [b, d]^\\top$. As we\n",
    "saw above, $\\det\\mathbf{A} = ad - bc$ is the *signed area* of the parallelogram\n",
    "spanned by $\\mathbf{a}_1$ and $\\mathbf{a}_2$.\n",
    "\n",
    "*(i) $\\Leftrightarrow$ (ii).* A parallelogram has zero area exactly when its two\n",
    "spanning edges are collinear, i.e., when one column is a scalar multiple of the\n",
    "other (including the degenerate case where a column is $\\mathbf{0}$). That is\n",
    "precisely linear dependence of the columns. So $ad - bc = 0$ if and only if\n",
    "$\\mathbf{a}_1$ and $\\mathbf{a}_2$ are linearly dependent.\n",
    "\n",
    "*(ii) $\\Leftrightarrow$ (iii).* If the columns are dependent, every output\n",
    "$\\mathbf{A}\\mathbf{x} = x_1\\mathbf{a}_1 + x_2\\mathbf{a}_2$ lies on the single\n",
    "line spanned by the surviving column, so the whole plane is crushed onto that\n",
    "line. Distinct inputs collide there (the map is not one-to-one), so no inverse\n",
    "can recover them, and $\\mathbf{A}$ is not invertible. Conversely, if the columns\n",
    "are independent they span the plane, every target is hit exactly once, and the\n",
    "map can be undone; concretely, $ad - bc \\neq 0$ is exactly the nonvanishing\n",
    "denominator that made the explicit inverse\n",
    "$\\frac{1}{ad-bc}\\bigl[\\begin{smallmatrix} d & -b \\\\ -c & a \\end{smallmatrix}\\bigr]$\n",
    "well-defined earlier in this section. $\\blacksquare$\n",
    "\n",
    "In $n$ dimensions the same equivalences hold, and the axiomatic\n",
    "characterization of that section supplies the two\n",
    "ingredients that generalize: $\\det\\mathbf{A}$ is the signed factor by which\n",
    "$\\mathbf{A}$ scales $n$-dimensional volume, and that volume vanishes exactly\n",
    "when the columns are linearly dependent; see [@Horn.Johnson.2012] for the\n",
    "full argument. The equivalence also proves claims made earlier without proof:\n",
    "linear dependence (the columns of $\\mathbf{B}$ are redundant), the missing\n",
    "$ad - bc \\neq 0$ hypothesis under the $2 \\times 2$ inverse, and the present\n",
    "section's \"$\\det = 0$ means collapse\" all turn out to be three faces of the\n",
    "same fact.\n",
    "\n",
    "#### Multiplicativity\n",
    "\n",
    "Imagine that we have any figure drawn on the plane.\n",
    "Thinking like computer scientists, we can decompose\n",
    "that figure into a collection of little squares\n",
    "so that the area of the figure is in essence\n",
    "just the number of squares in the decomposition.\n",
    "If we now transform that figure by a matrix,\n",
    "we send each of these squares to parallelograms,\n",
    "each one of which has area given by the determinant.\n",
    "We see that for any figure, the determinant gives the (signed) number\n",
    "that a matrix scales the area of any figure.\n",
    "\n",
    "This \"scale every figure's area by the same factor\" reading has an immediate\n",
    "consequence for *composing* two transformations. First, a fact that deserves\n",
    "its own sentence: **matrix multiplication is composition of linear\n",
    "maps**. Applying $\\mathbf{B}$ and then $\\mathbf{A}$ to an input $\\mathbf{v}$\n",
    "produces $\\mathbf{A}(\\mathbf{B}\\mathbf{v})$, and writing out components,\n",
    "\n",
    "$$\n",
    "\\bigl(\\mathbf{A}(\\mathbf{B}\\mathbf{v})\\bigr)_i\n",
    " = \\sum_j a_{ij} (\\mathbf{B}\\mathbf{v})_j\n",
    " = \\sum_j \\sum_k a_{ij} b_{jk} v_k\n",
    " = \\bigl((\\mathbf{A}\\mathbf{B})\\mathbf{v}\\bigr)_i,\n",
    "$$\n",
    "\n",
    "so running the two maps in turn is the same as applying the single matrix\n",
    "$\\mathbf{A}\\mathbf{B}$. This is the real reason matrix multiplication is\n",
    "defined by the row-times-column rule, and it explains why the product is\n",
    "associative but not commutative: composing functions in the other order\n",
    "generally gives a different function. With composition in hand, we can prove\n",
    "that the determinant is multiplicative.\n",
    "\n",
    "**Proposition (multiplicativity of the determinant).** *For square matrices\n",
    "$\\mathbf{A}$ and $\\mathbf{B}$ of the same size,*\n",
    "\n",
    "$$\n",
    "\\det(\\mathbf{A}\\mathbf{B}) = \\det(\\mathbf{A})\\,\\det(\\mathbf{B}).\n",
    "$$\n",
    "\n",
    "**Geometric intuition.** Apply $\\mathbf{A}\\mathbf{B}$ to an arbitrary figure\n",
    "of area $V$ by running the two maps in turn. First $\\mathbf{B}$ acts and\n",
    "scales the area to $\\det(\\mathbf{B})\\,V$; then $\\mathbf{A}$ acts and scales\n",
    "that by a further factor of $\\det(\\mathbf{A})$. But the composite map\n",
    "$\\mathbf{A}\\mathbf{B}$ is itself a single linear transformation, which scales\n",
    "area by its own determinant, so the two factors must multiply to\n",
    "$\\det(\\mathbf{A}\\mathbf{B})$. This argument leans on the tiling picture above\n",
    "(a linear map scales *every* figure's volume by one common factor), which we\n",
    "made plausible but did not prove; the axioms of\n",
    "that section turn it into a proof.\n",
    "\n",
    "**Proof.** Fix $\\mathbf{A}$ and consider, as a function of $\\mathbf{B}$, the\n",
    "quantity $D(\\mathbf{B}) = \\det(\\mathbf{A}\\mathbf{B})$. The $j$-th column of\n",
    "$\\mathbf{A}\\mathbf{B}$ is $\\mathbf{A}\\mathbf{b}_j$, where $\\mathbf{b}_j$ is\n",
    "the $j$-th column of $\\mathbf{B}$. Because $\\mathbf{A}(\\cdot)$ is linear and\n",
    "$\\det$ is multilinear, $D$ is multilinear in the columns of $\\mathbf{B}$; and\n",
    "if two columns of $\\mathbf{B}$ are equal, then so are the corresponding\n",
    "columns of $\\mathbf{A}\\mathbf{B}$, making $D(\\mathbf{B}) = 0$, so $D$ is\n",
    "alternating. By the scaling form of uniqueness from\n",
    "that section,\n",
    "\n",
    "$$\n",
    "\\det(\\mathbf{A}\\mathbf{B}) = D(\\mathbf{B}) = D(\\mathbf{I})\\,\\det(\\mathbf{B})\n",
    " = \\det(\\mathbf{A})\\,\\det(\\mathbf{B}). \\qquad \\blacksquare\n",
    "$$\n",
    "\n",
    "A corollary is one line long but easy to miss.\n",
    "\n",
    "**Corollary.** *For square matrices $\\mathbf{A}$ and $\\mathbf{B}$ of the same\n",
    "size,*\n",
    "\n",
    "$$\n",
    "\\det(\\mathbf{A}\\mathbf{B}) = \\det(\\mathbf{A})\\,\\det(\\mathbf{B})\n",
    " = \\det(\\mathbf{B})\\,\\det(\\mathbf{A}) = \\det(\\mathbf{B}\\mathbf{A}).\n",
    "$$\n",
    "\n",
    "Even though $\\mathbf{A}\\mathbf{B} \\neq \\mathbf{B}\\mathbf{A}$ in general, their\n",
    "determinants always agree, because the two determinants are scalars and\n",
    "scalars commute. This is a genuinely useful fact: applied to the pair\n",
    "$\\mathbf{W}\\mathbf{A}$ and $\\mathbf{W}^{-1}$, it gives *similarity\n",
    "invariance*, $\\det(\\mathbf{W}\\mathbf{A}\\mathbf{W}^{-1}) =\n",
    "\\det(\\mathbf{W}^{-1}\\mathbf{W}\\mathbf{A}) = \\det(\\mathbf{A})$: matrices that\n",
    "represent the same linear map in different bases have the same determinant,\n",
    "a fact that section puts to work.\n",
    "\n",
    "Further consequences follow without any additional work. First, taking\n",
    "$\\mathbf{B} = \\mathbf{A}^{-1}$ in the equation and using\n",
    "$\\det(\\mathbf{I}) = 1$ (the identity moves no volume) gives\n",
    "\n",
    "$$\n",
    "\\det(\\mathbf{A}^{-1}) = \\frac{1}{\\det(\\mathbf{A})},\n",
    "$$\n",
    "\n",
    "which also re-confirms the unifying theorem: an inverse can exist only when\n",
    "$\\det(\\mathbf{A}) \\neq 0$, since otherwise the right-hand side is undefined.\n",
    "Second, we can prove the claim made in the orthogonal-matrices\n",
    "subsection. Combining multiplicativity with $\\det\\mathbf{Q}^\\top =\n",
    "\\det\\mathbf{Q}$ from that section and applying\n",
    "both to $\\mathbf{Q}^\\top\\mathbf{Q} = \\mathbf{I}$ gives\n",
    "\n",
    "$$\n",
    "\\det(\\mathbf{Q})^2 = \\det(\\mathbf{Q}^\\top)\\det(\\mathbf{Q})\n",
    " = \\det(\\mathbf{Q}^\\top\\mathbf{Q}) = \\det(\\mathbf{I}) = 1,\n",
    "$$\n",
    "\n",
    "so $\\det\\mathbf{Q} = \\pm 1$: a rigid motion leaves every area and volume\n",
    "unchanged in magnitude, and the sign records whether it is a pure rotation\n",
    "($+1$) or involves a reflection ($-1$).\n",
    "Third, and looking ahead, similarity invariance is exactly what lets the\n",
    "determinant pass through a diagonalization: once we can write a matrix in\n",
    "terms of its eigenvalues in that section, the same\n",
    "identities will show that the determinant is the *product of the\n",
    "eigenvalues*, $\\det(\\mathbf{A}) = \\prod_i \\lambda_i$, the volume scaling\n",
    "being the product of the per-axis stretch factors.\n",
    "\n",
    "## Tensors and Einstein Summation\n",
    "\n",
    "We close with a compact notation for all of these products at once. Every\n",
    "product in this section (dot products, matrix–vector products,\n",
    "matrix products, and the *trace* $\\textrm{tr}(\\mathbf{A}) = \\sum_i a_{ii}$,\n",
    "the sum of the diagonal entries) follows one pattern: multiply entries, then\n",
    "sum over the index that appears twice,\n",
    "\n",
    "$$\n",
    "\\mathbf{v} \\cdot \\mathbf{w} = \\sum_i v_i w_i,\n",
    "\\qquad\n",
    "(\\mathbf{A}\\mathbf{v})_i = \\sum_j a_{ij} v_j,\n",
    "\\qquad\n",
    "(\\mathbf{A}\\mathbf{B})_{ik} = \\sum_j a_{ij} b_{jk},\n",
    "\\qquad\n",
    "\\textrm{tr}(\\mathbf{A}) = \\sum_i a_{ii}.\n",
    "$$\n",
    "\n",
    "*Einstein notation* makes the pattern the entire definition: write the indexed\n",
    "factors, drop the summation sign, and sum over every index that appears more\n",
    "than once. Thus $\\mathbf{v}\\cdot\\mathbf{w} = v_i w_i$ and\n",
    "$(\\mathbf{A}\\mathbf{B})_{ik} = a_{ij}b_{jk}$. The same rule extends unchanged\n",
    "to tensors with any number of axes, where a general *tensor contraction* such\n",
    "as $y_{il} = x_{ijkl}\\,a_{jk}$ (summing over $j$ and $k$) has no tidy matrix\n",
    "notation at all. The rule is exposed directly as\n",
    "`einsum`: spell out the index pattern as a string, and the library performs\n",
    "the contraction."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "geometry-linear-algebraic-ops-expressing-in-code-2"
   },
   "source": [
    "import numpy as onp\n",
    "A = onp.array([[1.0, 2.0], [-1.0, 3.0]])\n",
    "v = onp.array([2.0, -1.0])\n",
    "(onp.einsum('i,i->', v, v),      # dot product: v.v\n",
    " onp.einsum('ij,j->i', A, v),    # matrix-vector product: Av\n",
    " onp.einsum('ij,jk->ik', A, A),  # matrix product: AA\n",
    " onp.einsum('ii->', A))          # trace: tr(A)"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(np.float64(5.0),\n array([ 0., -5.]),\n array([[-1.,  8.],\n        [-4.,  7.]]),\n np.float64(4.0))"
     },
     "metadata": {},
     "execution_count": 11
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-12 fw=all -->\n",
    "\n",
    "The matrix here is $\\mathbf{A}$ from\n",
    "the figure and the vector is $\\mathbf{v} = [2, -1]^\\top$,\n",
    "so the second entry of the output reproduces the worked example\n",
    "$\\mathbf{A}\\mathbf{v} = [0, -5]^\\top$. Index strings like\n",
    "`'ij,jk->ik'` recur throughout deep learning: batched matrix products\n",
    "(`'bij,bjk->bik'`), attention scores, and many custom layers are one `einsum`\n",
    "call away, and we will reach for the notation whenever a computation is easier\n",
    "to state in indices than in matrices, as soon as\n",
    "that section, where a one-line `einsum` will rebuild a matrix\n",
    "from its singular value decomposition.\n",
    "\n",
    "Index notation also yields one-line proofs. In indices, the trace of a\n",
    "product is\n",
    "\n",
    "$$\n",
    "\\textrm{tr}(\\mathbf{A}\\mathbf{B}) = a_{ij} b_{ji} = b_{ji} a_{ij}\n",
    " = \\textrm{tr}(\\mathbf{B}\\mathbf{A}),\n",
    "$$\n",
    "\n",
    "and the middle step costs nothing: matrix entries are numbers, so they\n",
    "commute, and only the bookkeeping of the indices matters. Note that\n",
    "the equation holds even when $\\mathbf{A}\\mathbf{B} \\neq\n",
    "\\mathbf{B}\\mathbf{A}$, just as with determinants. A corollary is that the\n",
    "trace is invariant under a change of basis,\n",
    "\n",
    "$$\n",
    "\\textrm{tr}(\\mathbf{W}\\mathbf{A}\\mathbf{W}^{-1})\n",
    " = \\textrm{tr}(\\mathbf{A}\\mathbf{W}^{-1}\\mathbf{W})\n",
    " = \\textrm{tr}(\\mathbf{A}),\n",
    "$$\n",
    "\n",
    "the identity behind the trace–eigenvalue formula\n",
    "$\\textrm{tr}(\\mathbf{A}) = \\sum_i \\lambda_i$ in\n",
    "that section.\n",
    "\n",
    "## Summary\n",
    "* Vectors can be interpreted geometrically as either points or directions in space.\n",
    "* Dot products define the notion of angle to arbitrarily high-dimensional spaces.\n",
    "* Spans, subspaces, and bases organize collections of vectors: a basis assigns every vector of a subspace unique coordinates, and the dimension counts the basis vectors. The column space and null space of a matrix record what it can produce and what it destroys.\n",
    "* Projection produces the closest point of a line (or, via the projection matrix $\\mathbf{P} = \\mathbf{Q}\\mathbf{Q}^\\top$, of any subspace) and is characterized by an orthogonal residual. This is the geometry of the least-squares problem the equation.\n",
    "* Hyperplanes are high-dimensional generalizations of lines and planes.  They can be used to define decision planes that are often used as the last step in a classification task.\n",
    "* Matrix multiplication can be geometrically interpreted as uniform distortions of the underlying coordinates: a matrix skews, rotates, and scales, and it treats every part of space the same way. Multiplying two matrices composes the corresponding maps.\n",
    "* Orthogonal matrices are the rigid motions: they preserve lengths, angles, and (up to a sign recording reflections) volumes.\n",
    "* Linear dependence is a way to tell when a collection of vectors are in a lower dimensional space than we would expect (say you have $3$ vectors living in a $2$-dimensional space). The rank of a matrix is the size of the largest subset of its columns that are linearly independent, and rank--nullity is exact: rank plus the dimension of the null space equals the number of columns.\n",
    "* When a matrix's inverse is defined, matrix inversion allows us to find another matrix that undoes the action of the first. Matrix inversion is useful in theory, but requires care in practice owing to numerical instability.\n",
    "* The determinant is the signed volume scaling of a matrix. It is characterized by three properties (multilinear, alternating, $\\det\\mathbf{I} = 1$), it flips sign under a column swap, and it satisfies $\\det(\\mathbf{A}\\mathbf{B}) = \\det(\\mathbf{A})\\det(\\mathbf{B}) = \\det(\\mathbf{B}\\mathbf{A})$. A nonzero determinant is equivalent to invertibility; a zero determinant means the matrix is singular.\n",
    "* Tensor contractions and Einstein summation express many of the computations of machine learning in one index pattern, and in index form identities such as $\\textrm{tr}(\\mathbf{A}\\mathbf{B}) = \\textrm{tr}(\\mathbf{B}\\mathbf{A})$ become one-line computations.\n",
    "\n",
    "## Exercises\n",
    "1. What is the angle between\n",
    "$$\n",
    "\\vec v_1 = \\begin{bmatrix}\n",
    "1 \\\\ 0 \\\\ -1 \\\\ 2\n",
    "\\end{bmatrix}, \\qquad \\vec v_2 = \\begin{bmatrix}\n",
    "3 \\\\ 1 \\\\ 0 \\\\ 1\n",
    "\\end{bmatrix}?\n",
    "$$\n",
    "2. True or false: $\\begin{bmatrix}1 & 2\\\\0&1\\end{bmatrix}$ and $\\begin{bmatrix}1 & -2\\\\0&1\\end{bmatrix}$ are inverses of one another?\n",
    "3. Suppose that we draw a shape in the plane with area $100\\textrm{m}^2$.  What is the area after transforming the figure by the matrix\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "2 & 3\\\\\n",
    "1 & 2\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "4. Which of the following sets of vectors are linearly independent?\n",
    " * $\\left\\{\\begin{pmatrix}1\\\\0\\\\-1\\end{pmatrix}, \\begin{pmatrix}2\\\\1\\\\-1\\end{pmatrix}, \\begin{pmatrix}3\\\\1\\\\1\\end{pmatrix}\\right\\}$\n",
    " * $\\left\\{\\begin{pmatrix}3\\\\1\\\\1\\end{pmatrix}, \\begin{pmatrix}1\\\\1\\\\1\\end{pmatrix}, \\begin{pmatrix}0\\\\0\\\\0\\end{pmatrix}\\right\\}$\n",
    " * $\\left\\{\\begin{pmatrix}1\\\\1\\\\0\\end{pmatrix}, \\begin{pmatrix}0\\\\1\\\\-1\\end{pmatrix}, \\begin{pmatrix}1\\\\0\\\\1\\end{pmatrix}\\right\\}$\n",
    "5. Suppose that you have a matrix written as $A = \\begin{bmatrix}c\\\\d\\end{bmatrix}\\cdot\\begin{bmatrix}a & b\\end{bmatrix}$ for some choice of values $a, b, c$, and $d$.  True or false: the determinant of such a matrix is always $0$?\n",
    "6. The vectors $e_1 = \\begin{bmatrix}1\\\\0\\end{bmatrix}$ and $e_2 = \\begin{bmatrix}0\\\\1\\end{bmatrix}$ are orthogonal.  What is the condition on a matrix $A$ so that $Ae_1$ and $Ae_2$ are orthogonal?\n",
    "7. How can you write $\\textrm{tr}(\\mathbf{A}^4)$ in Einstein notation for an arbitrary matrix $A$?\n",
    "8. Consider the hyperplane $\\mathbf{w}\\cdot\\mathbf{x} = b$ with $\\mathbf{w} = [3,4]^\\top$ and $b = 10$.  What is the signed distance from the point $\\mathbf{x} = [1,1]^\\top$ to this hyperplane, and on which side of it does $\\mathbf{x}$ lie?\n",
    "9. The proof of Cauchy–Schwarz shows that equality holds exactly when one vector is a scalar multiple of the other. Use this to characterize when the triangle inequality $\\|\\mathbf{v} + \\mathbf{w}\\| \\le \\|\\mathbf{v}\\| + \\|\\mathbf{w}\\|$ holds with equality, and check your characterization on $\\mathbf{v} = [1,2]^\\top$ paired first with $\\mathbf{w} = [2,4]^\\top$ and then with $\\mathbf{w} = [-1,-2]^\\top$.\n",
    "10. Compute the projection $\\operatorname{proj}_{\\mathbf{w}}\\mathbf{v}$ of $\\mathbf{v} = [1,2,3]^\\top$ onto $\\mathbf{w} = [1,1,1]^\\top$. Verify that the residual is orthogonal to $\\mathbf{w}$ and confirm the Pythagorean identity the equation numerically.\n",
    "11. In code: sample $1{,}000$ pairs of random unit vectors in $d = 10{,}000$ dimensions (draw Gaussian vectors and normalize them) and compute the cosine of the angle for each pair. Compare the empirical standard deviation to the predicted $1/\\sqrt{d} = 0.01$, and report the largest $|\\cos\\theta|$ you observe.\n",
    "12. Show that an orthogonal matrix $\\mathbf{Q}$ preserves angles: for nonzero $\\mathbf{x}$ and $\\mathbf{y}$, the angle between $\\mathbf{Q}\\mathbf{x}$ and $\\mathbf{Q}\\mathbf{y}$ equals the angle between $\\mathbf{x}$ and $\\mathbf{y}$. Conclude that rotating every embedding vector in a dataset by the same orthogonal matrix leaves all cosine similarities unchanged.\n",
    "13. Verify that the $4 \\times 5$ matrix $\\mathbf{C}$ from the rank subsection has rank two: check that the first two columns are linearly independent, and confirm, by hand or with `matrix_rank`, that every collection of three of its columns is linearly dependent.\n",
    "14. Use multilinearity to prove that $\\det(c\\mathbf{A}) = c^n \\det(\\mathbf{A})$ for an $n \\times n$ matrix $\\mathbf{A}$ and a scalar $c$. Check the identity in code for the $3 \\times 3$ matrix of the equation with $c = 2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-geometry-linear-algebraic-ops-md-13 fw=jax -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/1085)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-jax",
   "display_name": "d2l (JAX)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
