{ "cells": [ { "cell_type": "markdown", "id": "98505d72", "metadata": {}, "source": [ "# Week 3: Inner-Product Spaces" ] }, { "cell_type": "markdown", "id": "a1617046", "metadata": {}, "source": [ "## Key Terms" ] }, { "cell_type": "markdown", "id": "9ca37629", "metadata": {}, "source": [ "* Vector spaces with inner product and norm\n", "* $\\mathbb{R}^n$ and $\\mathbb{C}^n$ \n", "* Projections on the line\n", "* Orthonormal bases\n", "* The Gram-Schmidt procedure\n", "* Orthogonal and unitary matrices" ] }, { "cell_type": "markdown", "id": "bf62b463", "metadata": {}, "source": [ "## Preparation and Syllabus" ] }, { "cell_type": "markdown", "id": "8cf1bdca", "metadata": {}, "source": [ "* Long Day: Sections 2.3, 2.4, and 2.5 \n", "* Short Day: Section 2.6\n", "* Python demo for [Week 3](../demos/demo03_inner_product_spaces.ipynb)" ] }, { "cell_type": "markdown", "id": "09e381ea", "metadata": {}, "source": [ "___" ] }, { "cell_type": "markdown", "id": "33cbfbf1", "metadata": {}, "source": [ "## Exercises -- Long Days" ] }, { "cell_type": "code", "execution_count": null, "id": "3d2896d8", "metadata": { "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "from sympy import*\n", "from dtumathtools import*" ] }, { "cell_type": "markdown", "id": "4fb6b4d2", "metadata": {}, "source": [ "### 1: Orthonormal Basis (Coordinates). By Hand." ] }, { "cell_type": "markdown", "id": "e0e444b8", "metadata": {}, "source": [ "#### Question a" ] }, { "cell_type": "markdown", "id": "80042ae7", "metadata": {}, "source": [ "Do the vectors \n", "\n", "\\begin{equation*}\n", " \\pmb{u}_1=\\left( \\frac{1}{3},\\frac{2}{3},\\frac{2}{3}\\right), \\quad\n", "\\pmb{u}_2=\\left( \\frac{2}{3}, \\frac{1}{3}, -\\frac{2}{3}\\right),\\quad\n", "\\pmb{u}_3=\\left( \\frac{2}{3}, -\\frac{2}{3}, \\frac{1}{3}\\right)\n", "\\end{equation*}\n", "\n", "constitute an orthonormal basis in $\\mathbb{R}^3$?" ] }, { "cell_type": "markdown", "id": "9d65d171", "metadata": {}, "source": [ "#### Question b" ] }, { "cell_type": "markdown", "id": "c8aa76d7", "metadata": {}, "source": [ "Consider the vector $\\pmb{x} = [1,2,3]^T$. Compute the inner products $\\langle \\pmb{x}, \\pmb{u}_k \\rangle$ for $k=1,2,3$." ] }, { "cell_type": "markdown", "id": "ed191a6e", "metadata": {}, "source": [ "#### Question c" ] }, { "cell_type": "markdown", "id": "4cf86690", "metadata": {}, "source": [ "Let us denote the basis by $\\beta = \\pmb{u}_1, \\pmb{u}_2, \\pmb{u}_3$. State the coordinate vector ${}_{\\beta} \\pmb{x}$ for $\\pmb{x}$ with respect to $\\beta$. Compute the norm of both $\\pmb{x}$ and the coordinate vector ${}_{\\beta} \\pmb{x}$." ] }, { "cell_type": "markdown", "id": "b790c6da", "metadata": {}, "source": [ "#### Question d" ] }, { "cell_type": "markdown", "id": "b3d035b1", "metadata": {}, "source": [ "Create the $3\\times 3$ matrix $U = [\\pmb{u}_1 \\vert \\pmb{u}_2 \\vert \\pmb{u}_3]$ with $\\pmb{u}_1, \\pmb{u}_2, \\pmb{u}_3$ as the three columns. Compute $U^T \\pmb{x}$ and compare the result with the previous exercise." ] }, { "cell_type": "markdown", "id": "f897adaa", "metadata": {}, "source": [ "### 2: Orthonormal Basis (Construction). By Hand." ] }, { "cell_type": "markdown", "id": "15a464c5", "metadata": {}, "source": [ "Create an orthonormal basis in $\\mathbb{R}^3$, in which \n", "\n", "\\begin{equation*}\n", " \\left(\\frac {\\sqrt 2}2,\\frac {\\sqrt 2}2,0\\right)\n", "\\end{equation*}\n", "\n", "is the first basis vector." ] }, { "cell_type": "markdown", "id": "173f7f10", "metadata": {}, "source": [ "### 3: Orthonormalizing. By Hand." ] }, { "cell_type": "markdown", "id": "aadde838", "metadata": {}, "source": [ "Determine the solution set to the homogeneous equation\n", "\n", "\\begin{equation*}\n", " x_1+x_2+x_3=0\n", "\\end{equation*}\n", "\n", "and justify for it being a subspace in $\\mathbb{R}^3$. Find an orthonormal basis for this *solution space*." ] }, { "cell_type": "markdown", "id": "7a147304", "metadata": {}, "source": [ "### 4: Orthogonal Projections" ] }, { "cell_type": "markdown", "id": "9197d611", "metadata": {}, "source": [ "Let $\\boldsymbol{y}=(2,1,2) \\in \\mathbb{R}^3$ be given. Then the projection of $\\boldsymbol{x} \\in \\mathbb{R}^3$ onto the line $Y = \\mathrm{span}\\{\\boldsymbol{y}\\}$ is given by:\n", "\n", "\\begin{equation*}\n", "\\operatorname{Proj}_Y(\\boldsymbol{x}) = \\frac{\\left<\\boldsymbol{x},\\boldsymbol{y} \\right>}{\\left<\\boldsymbol{y},\\boldsymbol{y} \\right>}\\boldsymbol{y}\n", "= \\left<\\boldsymbol{x},\\boldsymbol{u}\\right>\\boldsymbol{u},\n", "\\end{equation*}\n", "\n", "where $\\boldsymbol{u} = \\frac{\\boldsymbol{y}}{||\\boldsymbol{y}||}$." ] }, { "cell_type": "markdown", "id": "e3b67625", "metadata": {}, "source": [ "#### Question a" ] }, { "cell_type": "markdown", "id": "265d7ad1", "metadata": {}, "source": [ "Let $\\boldsymbol{x} = (1,2,3) \\in \\mathbb{R}^3$. Compute $\\operatorname{Proj}_Y(\\boldsymbol{x})$, $\\operatorname{Proj}_Y(\\boldsymbol{y})$ and $\\operatorname{Proj}_Y(\\boldsymbol{u})$." ] }, { "cell_type": "markdown", "id": "787ddf11", "metadata": {}, "source": [ "#### Question b" ] }, { "cell_type": "markdown", "id": "ef9ef5b2", "metadata": {}, "source": [ "We, as usual, consider all vectors as column vectors. Now set up the $3 \\times 3$ matrix $P = \\boldsymbol{u} \\boldsymbol{u}^T$ and compute both $P\\boldsymbol{x}$ and $P\\boldsymbol{y}$." ] }, { "cell_type": "markdown", "id": "e6e96c77", "metadata": {}, "source": [ "### 5: An Orthonormal Basis for a Subspace of $\\mathbb{C}^4$" ] }, { "cell_type": "markdown", "id": "dbdf9fe9", "metadata": {}, "source": [ "#### Question a\n", "\n", "Find an orthonormal basis $\\pmb{u}_1, \\pmb{u}_2$ for the subspace $Y = \\mathrm{span}\\{\\pmb{v}_1, \\pmb{v}_2\\}$ spanned by the vectors:" ] }, { "cell_type": "code", "execution_count": null, "id": "b8e3bb5a", "metadata": { "tags": [ "remove-output" ] }, "outputs": [], "source": [ "v1 = Matrix([I, 1, 1, 0])\n", "v2 = Matrix([0, I, I, sqrt(2)])" ] }, { "cell_type": "markdown", "id": "763e46cf", "metadata": {}, "source": [ "#### Question b\n", "\n", "Let \n", "\n", "\\begin{equation*}\n", "\\pmb{x} = \\left[\\begin{matrix}3 i\\\\3 - 2 i\\\\3 - 2 i\\\\-2\\sqrt{2}\\end{matrix}\\right].\n", "\\end{equation*}\n", "\n", "Compute $\\langle \\pmb{x}, \\pmb{u}_1 \\rangle$, $\\langle \\pmb{x}, \\pmb{u}_2 \\rangle$ as well as\n", "\n", "\\begin{equation*}\n", "\\langle \\pmb{x}, \\pmb{u}_1 \\rangle \\pmb{u}_1 + \\langle \\pmb{x}, \\pmb{u}_2 \\rangle \\pmb{u}_2 .\n", "\\end{equation*}\n", "\n", "What does this linear combination give? Does $\\pmb{x}$ belong to the subspace $Y$?" ] }, { "cell_type": "markdown", "id": "1a699e61", "metadata": {}, "source": [ "### 6: A Python Algorithm" ] }, { "cell_type": "markdown", "id": "e60f5396", "metadata": {}, "source": [ "#### Question a" ] }, { "cell_type": "markdown", "id": "2649b3b2", "metadata": {}, "source": [ "Consider the following code and explain what it does. **Before** you run the code in a Jupyter Notebook you must explain what will be the output." ] }, { "cell_type": "code", "execution_count": null, "id": "d90de8df", "metadata": { "tags": [ "remove-output" ] }, "outputs": [], "source": [ "from sympy import *\n", "from dtumathtools import *\n", "init_printing()\n", "\n", "x1, x2, x3 = symbols('x1:4', real=True)\n", "eqns = [Eq(1*x1 + 2*x2 + 3*x3, 1), Eq(4*x1 + 5*x2 + 6*x3, 0), Eq(5*x1 + 7*x2 + 8*x3, -1)]\n", "eqns" ] }, { "cell_type": "code", "execution_count": null, "id": "4f908413", "metadata": { "tags": [ "remove-output" ] }, "outputs": [], "source": [ "A, b = linear_eq_to_matrix(eqns,x1,x2,x3)\n", "T = A.row_join(b) # augmented matrix\n", "\n", "A, b, T" ] }, { "cell_type": "markdown", "id": "bfa2b334", "metadata": {}, "source": [ "#### Question b" ] }, { "cell_type": "markdown", "id": "88cd7d80", "metadata": {}, "source": [ "We continue the Jupyter Notebook with the following code (do not run it yet). Go through the code by hand (calculate the for-loop iterations manually). Which $T$ matrix will be the output? Copy/paste the code into a chatbot such as https://copilot.microsoft.com/ (log in with your DTU account) and ask the chatbot to explain the code line by line. Now check the result by running the code in a Python Notebook. Remember that `T.shape[0]` gives the number of rows in matrix $T$." ] }, { "cell_type": "code", "execution_count": null, "id": "2baba5bb", "metadata": { "tags": [ "remove-output" ] }, "outputs": [], "source": [ "for col in range(T.shape[0]):\n", " for row in range(col + 1, T.shape[0]):\n", " T[row, :] = T[row, :] - T[row, col] / T[col, col] * T[col, :]\n", " T[col, :] = T[col, :] / T[col, col]\n", "\n", "T" ] }, { "cell_type": "markdown", "id": "b2bc74d3", "metadata": {}, "source": [ "#### Question c" ] }, { "cell_type": "markdown", "id": "4cd480c3", "metadata": {}, "source": [ "Write Python code that ensures zeroes above the diagonal in matrix $T$ such that $T$ ends out being in reduced-row echelon form. \n", "\n", "**Note:** \n", "You should not take into account any potential divisions by zero (for general $T$ matrices). We will assume that the calculations will work well." ] }, { "cell_type": "markdown", "id": "56542ab8", "metadata": {}, "source": [ "#### Question d" ] }, { "cell_type": "markdown", "id": "9be4f7ae", "metadata": {}, "source": [ "What algorithm is it that we have implemented? Test the same algorithm on:" ] }, { "cell_type": "code", "execution_count": null, "id": "7659b442", "metadata": {}, "outputs": [], "source": [ "x1, x2, x3, x4 = symbols('x1:5', real=True)\n", "eqns = [Eq(1*x1 + 2*x2 + 3*x3, 1), Eq(4*x1 + 5*x2 + 6*x3, 0), Eq(4*x1 + 5*x2 + 6*x3, 0), Eq(5*x1 + 7*x2 + 8*x3, -1)]\n", "A, b = linear_eq_to_matrix(eqns,x1,x2,x3,x4)\n", "T = A.row_join(b) # augmented matrix" ] }, { "cell_type": "markdown", "id": "4ac75331", "metadata": {}, "source": [ "### 7: Orthogonal Polynomials" ] }, { "cell_type": "markdown", "id": "c77fcc19", "metadata": {}, "source": [ "This is an exercise from the textbook. You can find help there. \n", "\n", "Consider the list $\\alpha=1,x,x^{2},x^{3}$ of polynomials in $P_{3}([-1,1])$ constructed with the $L^{2}$-inner product." ] }, { "cell_type": "markdown", "id": "59ca6915", "metadata": {}, "source": [ "#### Question a" ] }, { "cell_type": "markdown", "id": "d03140c1", "metadata": {}, "source": [ "Argument for why $\\alpha$ is a list of linearly independent vectors." ] }, { "cell_type": "markdown", "id": "a30d1044", "metadata": {}, "source": [ "#### Question b" ] }, { "cell_type": "markdown", "id": "b9f924af", "metadata": {}, "source": [ "Utilize the Gram-Schmidt procedure on $\\alpha$ and show that the procedure gives a *normalized* version of the Legendre polynomials." ] }, { "cell_type": "markdown", "id": "34b39235", "metadata": {}, "source": [ "___" ] }, { "cell_type": "markdown", "id": "f3803e0b", "metadata": {}, "source": [ "## Exercises -- Short Day" ] }, { "cell_type": "markdown", "id": "f29e6c61", "metadata": {}, "source": [ "### 1: Matrix Multiplications. By Hand." ] }, { "cell_type": "markdown", "id": "6ebb6455", "metadata": {}, "source": [ "Define\n", "\n", "\\begin{equation*}\n", " A = \\left[\\begin{matrix}1 & 2 & 3 & 4\\\\5 & 6 & 7 & 8\\\\4 & 4 & 4 & 4\\end{matrix}\\right], \\quad\n", " \\pmb{x} = \\left[\\begin{matrix} x_1\\\\ x_2\\\\ x_3\\\\ x_4\\end{matrix}\\right] = \\left[\\begin{matrix}1\\\\2\\\\-1\\\\1\\end{matrix}\\right].\n", "\\end{equation*}\n", "\n", "\n", "Let $\\pmb{a}_1, \\pmb{a}_2,\\pmb{a}_3,\\pmb{a}_4$ denote the columns of $A$. Let $\\pmb{b}_1, \\pmb{b}_2,\\pmb{b}_3$ denote the **rows** of $A$. We will now calculate $A\\pmb{x}$ in two different ways." ] }, { "cell_type": "markdown", "id": "4a871ca3", "metadata": {}, "source": [ "#### Question a" ] }, { "cell_type": "markdown", "id": "1d3afb50", "metadata": {}, "source": [ "*Method 1: As a linear combination of the columns*. Compute the linear combination\n", "\n", "\\begin{equation*}\n", " x_1 \\pmb{a}_1 + x_2 \\pmb{a}_2 + x_3 \\pmb{a}_3 + x_4 \\pmb{a}_4.\n", "\\end{equation*}" ] }, { "cell_type": "markdown", "id": "35382f15", "metadata": {}, "source": [ "#### Question b" ] }, { "cell_type": "markdown", "id": "d1289f3a", "metadata": {}, "source": [ "*Method 2: As a \"dot product\" of the rows of $A$ by $\\pmb{x}$*. Compute \n", "\n", "\\begin{equation*}\n", "\\left[\\begin{matrix} \\pmb{b}_1 \\pmb{x} \\\\ \\pmb{b}_2 \\pmb{x} \\\\ \\pmb{b}_3 \\pmb{x} \\end{matrix}\\right].\n", "\\end{equation*}\n", "\n", "**Note:**\n", "Since $\\pmb{b}_k$ is a row vector, $(\\pmb{b}_k)^T$ is a column vector. The product $\\pmb{b}_k \\pmb{x}$ hence corresponds to the dot product of $\\pmb{x}$ and $(\\pmb{b}_k)^T$." ] }, { "cell_type": "markdown", "id": "6d5822b6", "metadata": {}, "source": [ "#### Question c" ] }, { "cell_type": "markdown", "id": "80123d79", "metadata": {}, "source": [ "Compute $A\\pmb{x}$ using SymPy and compare with your calculations in the previous exercises.\n", "\n", "\n", "### 2: A Subspace in $\\mathbb{C}^4$ and its Orthogonal Complement" ] }, { "cell_type": "markdown", "id": "f18120a7", "metadata": {}, "source": [ "In $\\mathbb{C}^4\\,$ the following vectors are given\n", "\\begin{equation*}\n", " \\pmb{v}_1=(1,1,1,1),\\,\\pmb{v}_2=(3 i ,i,i,3 i),\\,\\pmb{v}_3=(2,0,-2,4)\\,\\,\\,\\,\\mathrm{and}\\,\\,\\,\\,\\pmb{v}_4=(4-3i,2-i,-i,6-3i).\n", "\\end{equation*}\n", "\n", "A subspace $Y$ in $\\mathbb{C}^4$ is determined by $Y=\\mathrm{span}\\lbrace\\pmb{v}_1,\\pmb{v}_2,\\pmb{v}_3,\\pmb{v}_4\\rbrace$." ] }, { "cell_type": "markdown", "id": "40b5ad3e", "metadata": {}, "source": [ "#### Question a" ] }, { "cell_type": "code", "execution_count": null, "id": "cf9449ac", "metadata": {}, "outputs": [], "source": [ "v1 = Matrix([1,1,1,1])\n", "v2 = Matrix([3*I,I,I,3*I])\n", "v3 = Matrix([2,0,-2,4])\n", "v4 = Matrix([4-3*I,2-I,-I,6-3*I])" ] }, { "cell_type": "markdown", "id": "c4fb4acf", "metadata": {}, "source": [ "Run the command `GramSchmidt([v1,v2,v3,v4], orthonormal=True)` in Python. What does Python tell you?" ] }, { "cell_type": "code", "execution_count": null, "id": "45e94a75", "metadata": {}, "outputs": [], "source": [ "# GramSchmidt([v1, v2, v3, v4], orthonormal = True) " ] }, { "cell_type": "markdown", "id": "9c92039a", "metadata": {}, "source": [ "#### Question b" ] }, { "cell_type": "markdown", "id": "f58df11c", "metadata": {}, "source": [ "Now show that $(\\pmb{v}_1,\\pmb{v}_2,\\pmb{v}_3)\\,$ is a basis for $Y$, and determine the coordinate vector of $\\pmb{v}_4\\,$ with respect to this basis." ] }, { "cell_type": "markdown", "id": "f142bae1", "metadata": {}, "source": [ "#### Question c" ] }, { "cell_type": "markdown", "id": "05efd89b", "metadata": {}, "source": [ "State an orthonormal basis for $Y$.\n", "\n", "\n", "\n", "\n", "\n", "#### Question d\n", "\n", "Find the coordinate vector of $\\pmb{v}_4 \\in Y$ with respect to the orthonormal basis for $Y$.\n", "\n", "\n", "\n", "#### Question e\n", "\n", "Determine the orthogonal complement $Y^\\perp$ in $\\mathbb{C}^4$ to $Y$. \n", "\n", "\n", "\n", "\n", "\n", "\n", "#### Question f\n", "\n", "Choose a vector $\\pmb{y}$ in $Y^\\perp$ and choose a vector $\\pmb{x}$ in $Y$. Compute $\\Vert \\pmb{x} \\Vert$, $\\Vert \\pmb{y} \\Vert$ and $\\Vert \\pmb{x} + \\pmb{y} \\Vert$. Check that $\\Vert \\pmb{x} \\Vert^2 +\\Vert \\pmb{y} \\Vert^2 = \\Vert \\pmb{x} + \\pmb{y} \\Vert^2$.\n", "\n", "\n", "### 3: Orthogonal Projection on a Plane" ] }, { "cell_type": "markdown", "id": "80288c00", "metadata": {}, "source": [ "Let a matrix $U = [\\pmb{u}_1, \\pmb{u}_2]$ be given by:\n", "\n", "\\begin{equation*}\n", " U = \\left[\\begin{matrix}\\frac{\\sqrt{3}}{3} & \\frac{\\sqrt{2}}{2}\\\\ \\frac{\\sqrt{3}}{3} & 0\\\\- \\frac{\\sqrt{3}}{3} & \\frac{\\sqrt{2}}{2}\\end{matrix}\\right].\n", "\\end{equation*}" ] }, { "cell_type": "markdown", "id": "50e53aba", "metadata": {}, "source": [ "#### Question a" ] }, { "cell_type": "markdown", "id": "7a525233", "metadata": {}, "source": [ "Show that $\\pmb{u}_1, \\pmb{u}_2$ is an orthonormal basis for $Y = \\mathrm{span}\\{\\pmb{u}_1, \\pmb{u}_2\\}$." ] }, { "cell_type": "markdown", "id": "ca6ee185", "metadata": {}, "source": [ "#### Question b" ] }, { "cell_type": "markdown", "id": "3c776916", "metadata": {}, "source": [ "Let $P = U U^* \\in \\mathbb{R}^{3 \\times 3}$. This will give us a projection matrix that describes the orthogonal projection $\\pmb{x} \\mapsto P \\pmb{x}$, $\\mathbb{R}^3 \\to \\mathbb{R}^3$ onto the plane $Y = \\mathrm{span}\\{\\pmb{u}_1, \\pmb{u}_2\\}$. Verify that $P^2 = P$, $P \\pmb{u}_1 = \\pmb{u}_1$, and $P \\pmb{u}_2 = \\pmb{u}_2$." ] }, { "cell_type": "markdown", "id": "6977f131", "metadata": {}, "source": [ "#### Question c" ] }, { "cell_type": "markdown", "id": "216129c1", "metadata": {}, "source": [ "Choose a vector $\\pmb{x} \\in \\mathbb{R}^3$ that does not belong to $Y$, and find the projection $\\mathrm{proj}_Y(\\pmb{x})$ of $\\pmb{x}$ down onto the plane $Y$. Illustrate $\\pmb{x}$, $Y$, and $\\mathrm{proj}_Y(\\pmb{x})$ in a plot." ] }, { "cell_type": "markdown", "id": "4dd6af40", "metadata": {}, "source": [ "#### Question d" ] }, { "cell_type": "markdown", "id": "4689b5dd", "metadata": {}, "source": [ "Show that $\\pmb{x} - \\mathrm{proj}_Y(\\pmb{x})$ belongs to $Y^\\perp$.\n", "\n", "\n", "\n", "\n", "\n", "\n", "### 4: Unitary Matrices" ] }, { "cell_type": "markdown", "id": "bbd85381", "metadata": {}, "source": [ "Let a matrix $F$ be given by:" ] }, { "cell_type": "code", "execution_count": null, "id": "60f7be65", "metadata": {}, "outputs": [], "source": [ "n = 4\n", "F = 1/sqrt(n) * Matrix(n, n, lambda k,j: exp(2*pi*I*k*j/n))\n", "F" ] }, { "cell_type": "markdown", "id": "13f023ad", "metadata": {}, "source": [ "Determine whether the following propositions are true or false:\n", "\n", "1. $F$ is unitary\n", "1. $F$ is invertible\n", "1. $F$ is orthogonal\n", "1. $F$ is symmetric\n", "1. $F$ is Hermitian\n", "1. The columns of $F$ constitute an orthonormal basis for $\\mathbb{C}^4$\n", "1. The columns of $F$ constitute an orthonormal basis for $\\mathbb{R}^4$\n", "1. $-F = F^{-1}$" ] } ], "metadata": { "jupytext": { "formats": "ipynb,md:myst" }, "kernelspec": { "display_name": "python3", "language": "python", "name": "python3" } }, "nbformat": 4, "nbformat_minor": 5 }