{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 18.06 pset 2\n",
    "\n",
    "Due Wed. 9/19 at 10:55am by electronic submission."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1 (10 points)\n",
    "\n",
    "For the matrix\n",
    "\n",
    "$$\n",
    "A = \\begin{pmatrix}\n",
    "1 & 2 & 1 & -1 & 1 \\\\\n",
    "1 & 0 & 1 & -1 & 0 \\\\\n",
    "1 & 2 & 1 & 0 & 0 \\\\\n",
    "1 & 1 & 0 &  0 & 0 \\\\\n",
    "-1 & 0 & 0 &  0 & 0 \\end{pmatrix}\n",
    "$$\n",
    "\n",
    "and the vector $b = \\begin{pmatrix} 0\\\\0\\\\0\\\\0\\\\1 \\end{pmatrix}$:\n",
    "\n",
    "**(a)** Show *hand calculations* to compute $x = A^{-1} b$.  (Hint: remember what I said in class about computing inverses of matrices.)\n",
    "\n",
    "**(b)** Compute $A^{-1}$ in Julia with `inv(A)` and compare it to your solution $x$.  Explain why your $x$ appears in $A^{-1}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [ 1 2 1 -1 1\n",
    "      1 0 1 -1 0\n",
    "      1 2 1  0 0\n",
    "      1 1 0  0 0\n",
    "     -1 0 0  0 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inv(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2 (15 points)\n",
    "\n",
    "Consider the matrix $$A = \\begin{pmatrix} 1 & 4 & 1 \\\\ 1 & 2 & -1 \\\\ 3 & 14 & 6 \\end{pmatrix}$$ from lecture 4.\n",
    "\n",
    "In this problem, we will consider transforming this matrix by a sequence of invertible linear **column operations** — multiplying *columns* by scalars and adding/subtracting them.\n",
    "\n",
    "**(a)** Come up with column operations that change the first row from $\\begin{pmatrix} 1 & 4 & 1\\end{pmatrix}$ to $\\begin{pmatrix} 1 & 0 & 0\\end{pmatrix}$, i.e. that put zeros to the *right* of the first pivot.   Express these operations in terms of multipling $A$ on the left or right by some matrix $E$.   Give $E$ and $E^{-1}$.\n",
    "\n",
    "(Note that your operations must be invertible, like Gaussian-elimination steps — no fair just multipling the second and third columns by zero, since this would lead to a non-invertible $E$.)\n",
    "\n",
    "**(b)** If we do a *sequence* of column operations that transform $A$ into $I$, and then do the *same* column operations to the $3\\times 3$ identity matrix $I$, what is the resulting matrix?\n",
    "\n",
    "**(c)** Carry out the process from (b): perform column operations on $A$ that transform it into $I$, and perform the *same* column operations on $I$.   Do them both at once by \"augmenting\" $A$ in a certain way (maybe not the usual way).   Check your result against the lecture-4 notes or with Julia to see that you got the expected result from (b)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [1  4  1\n",
    "     1  2 -1\n",
    "     3 14  6]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3 (10 points)\n",
    "\n",
    "From Strang, section 2.6: Compute $L$ and $U$ for the following symmetric matrix $A$:\n",
    "\n",
    "$$\n",
    "A = \\begin{pmatrix} a & a & a & a \\\\ a & b & b & b \\\\ a & b & c & c \\\\ a & b & c & d \\end{pmatrix}\n",
    "$$\n",
    "\n",
    "and find four conditions on the numbers $a,b,c,d$ to get $A=LU$ with four pivots."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 4 (10 points)\n",
    "\n",
    "From Strang, section 2.6.  Consider $$L = \\begin{pmatrix} 1 & 0 & 0 \\\\ a & 1 & 0 \\\\ b & c & 1 \\end{pmatrix}$$ for some numbers $a,b,c$.\n",
    "\n",
    "**(a)** When you perform the usual Gaussian elimination steps to $L$, what matrix will you obtain?\n",
    "\n",
    "**(b)** If you apply the *same* row operations to $I$, what matrix will you get?\n",
    "\n",
    "**(c)** If you apply the *same* row operations to $LB$ for some $3\\times n$ matrix $B$, what will you get?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 5 (10 points)\n",
    "\n",
    "Consider the following matrices:\n",
    "\n",
    "$$\n",
    "U = \\begin{pmatrix} 1 & 1 & -1 \\\\ 0 & 1 & 2 \\\\ 0 & 0 & 1 \\end{pmatrix}, \\;\n",
    "L = \\begin{pmatrix} 1 & 0 & 0 \\\\ -1 & 1 & 0 \\\\ -2 & 1 & 1 \\end{pmatrix}, \\;\n",
    "B = \\begin{pmatrix} 1 & 2 & 3 \\\\ 3 & 2 & 1 \\\\ 1 & 0 & 1 \\end{pmatrix}\n",
    "$$\n",
    "\n",
    "Let $A = U B^{-1} L$.\n",
    "\n",
    "**(a)** Compute the *second column* of $A^{-1}$.  (If you think about it, you can do it *without inverting any matrices*.)\n",
    "\n",
    "**(b)** Check your answer by explicitly computing $A^{-1}$ in Julia."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# fill these in:\n",
    "U = ...\n",
    "L = ...\n",
    "B = ...\n",
    "\n",
    "A = U * (B \\ L)  # computes UB⁻¹L\n",
    "inv(A) # computes A⁻¹"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 6 (10 points)\n",
    "\n",
    "Suppose you have a 5×5 matrix of the form \n",
    "\n",
    "$$A = \\begin{pmatrix}\n",
    "\\star & \\star & 0 & 0 & 0 \\\\\n",
    "\\star & \\star & \\star & 0 & 0 \\\\\n",
    "0 & \\star & \\star & \\star & 0 \\\\\n",
    "0 & 0 & \\star & \\star & \\star \\\\\n",
    "0 & 0 & 0 & \\star & \\star\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "where \"$\\star$\" denotes nonzero entries (**not necessarily all the same numbers**).   This is called a [tridiagonal matrix](https://en.wikipedia.org/wiki/Tridiagonal_matrix).\n",
    "\n",
    "The following code constructs a random tridiagonal matrix in Julia, using a special `Tridiagonal` type that allows Julia to take advantage of this structure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = Tridiagonal(randn(4), randn(5), randn(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The *inverse* of a tridiagonal matrix has no special pattern of nonzero entries in general:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inv(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But the *LU factorization* of a tridiagonal matrix is very special.\n",
    "\n",
    "**(a)** Assuming no row swaps are required and the matrix is nonsingular, what pattern of nonzero entries do you generically expect to see in the $L$ and $U$ factors of a matrix $A$ of this form, and why?\n",
    "\n",
    "Check your answer against your random 5×5 $A$ in Julia."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L, U = lu(A, Val{false})\n",
    "display(L)\n",
    "display(U)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b)** If $A$ is an $m \\times m$ tridiagonal matrix (i.e. same pattern of zeros, but extended to an arbitrary size), how does the count of scalar arithmetic operations (±,×,÷) to compute the L, U factors (i.e. to perform elimination) scale with $m$?  You need not give an exact count, just say whether it is roughtly proportional to $m$, $m^2$, $m^3$, etcetera for large $m$.)\n",
    "\n",
    "You need not count operations on numbers that are *guaranteed* to be zero for *any* tridiagonal matrix.  The computer can store *just* the nonzero entries of the matrix and only operate on those."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.2",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}