Review-02-Systems-of-Linear-Equations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review-02-Systems-of-Linear-Equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Answers to review questions from Chapter 2: Systems of Linear Equations <cite data-cite=\"heath2018scientific\">(Heath, 2018)</cite>.\n",
    "\n",
    "---\n",
    "Questions marked with $\\bigtriangledown$ are considered more difficult."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.1. True or false: If a matrix A is nonsingular, then the number of solutions to the linear system Ax = b depends on the particular choice of right- hand-side vector b.\n",
    "\n",
    "False. If A is nonsingular, then there exists exactly **one** unique solution for every unique right hand side.  The original statement is false in the sense that the number of solutions is always 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.3. True or false: For a symmetric matrix A, it is always the case that $||A||_1 = ||A||_{\\inf}$.\n",
    "\n",
    "* $||A||_1$ is the maximum absolute column sum.\n",
    "* $||A||_{\\inf}$ is the maximum absolute row sum.\n",
    "\n",
    "True.  For a symmetric matrix, the maximum absolute column and row sum are equal.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.5. True or false: If any matrix has a zero entry on its main diagonal, then the matrix is necessar- ily singular.\n",
    "\n",
    "False. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.7. True or false: The product of two upper triangular matrices is upper triangular.\n",
    "\n",
    "True."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.9. True or false: The inverse of a nonsingular upper triangular matrix is upper triangular.\n",
    "\n",
    "True."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.11. True or false: A system of linear equations Ax = b has a solution if, and only if, the $m \\times n$ matrix A and the augmented $m \\times (n + 1)$ matrix $[A \\quad b]$ have the same rank.\n",
    "\n",
    "False. Ax = b has solution when A is nonsingular.  If A is nonsingular then the $\\text{rank}(A) = n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.13. True or false: Provided row interchanges are allowed, the LU factorization always exists, even for a singular matrix A.\n",
    "\n",
    "True. LU factorization always exists when row interchanges are allowed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.15. True or false: If a matrix is singular then it cannot have an LU factorization.\n",
    "\n",
    "False. LU factorization exists provided that leading principal minors are non-zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.17. True or false: A symmetric positive definite matrix is always well-conditioned.\n",
    "\n",
    "True. If a matrix is symmetric positive definite, then no pivoting is required since the matrix is well-conditioned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.19. True or false: Once the LU factorization of a matrix has been computed to solve a linear system, then subsequent linear systems with the same matrix but different right-hand-side vectors can be solved without refactoring the matrix.\n",
    "\n",
    "True.  Once a matrix is factorized and you have a new right hand side $b$, then solve using the following steps.\n",
    "\n",
    "1. Solve $L y = b$ for $y$ by forward substitution.\n",
    "2. Solve $U x = y$ for $x$ by backward substitution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.21. True or false: If x is any n-vector, then $||x||_1 \\geq ||x_||_{\\inf}$.\n",
    "\n",
    "False. For any vector $x \\in \\mathbb{R}$ then $||x||_1 \\leq ||x||_2 \\leq \\dots \\leq ||x||_{\\inf}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.23. True or false: If $||A|| = 0$, then $A = 0$.\n",
    "\n",
    "True."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.25. True or false: If A is any n × n nonsingular matrix, then $\\text{cond}(A) = \\text{cond}(A^{-1})$.\n",
    "\n",
    "True.  The condition number is the product of the norm of the matrix and its' inverse, hence:\n",
    "$$\n",
    "\\text{cond}(A) = ||A|| \\cdot ||A^{-1}|| = \\text{cond}(A^{-1})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.27. True or false: The multipliers in Gaussian elimination with partial pivoting are bounded by 1 in magnitude, so the entries of the successive reduced matrices cannot grow in magnitude.\n",
    "\n",
    "True.  In partial pivoting, the element having the largest magnitude in a column are used as pivots.  The multipliers are formed from the elements below the pivot divided by the pivot, hence the value of the multipliers will always be < 1.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.29. Can the number of solutions to a linear system Ax = b ever be determined solely from the matrix A without knowing the right-hand-side vector b?\n",
    "\n",
    "No.  \n",
    "* When A is nonsingular, there is a unique solution $x$ for every unique $b$ hence the number of solutions depends on the number of unique right-hand-side vectors.  \n",
    "* When A is singular, the number of solutions could be infinite or 0 depending on whether $b \\in \\text{span}(A)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.31. (a) State one defining property of a singu- lar matrix A.\n",
    "(b) Suppose that the linear system Ax = b has two distinct solutions x and y. Use the property you gave in part a to prove that A must be sin- gular.\n",
    "\n",
    "\n",
    "(a) If $\\det(A) = 0$, then A is singular.\n",
    "\n",
    "(b) If $Ax = Ay = b$ and $x != y$, then no matrix $A^{-1}$ can exist such that $A A^{-1} = I$ since $Ix != Iy$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.33. Suppose that both sides of a system of lin- ear equations Ax = b are multiplied by a nonzero scalar $\\alpha$.\n",
    "(a) Does this change the true solution x?\n",
    "(b) Does this change the residual vector r = b−Ax for a given x?\n",
    "(c) What conclusion can be drawn about assessing the quality of a computed solution?\n",
    "\n",
    "(a) No, scaling both sides of $Ax = b$ by $\\alpha$ does not change the solution $x$.\n",
    "\n",
    "(b) Yes, scaling both sides of $Ax = b$ by $\\alpha$ increases the residual by $\\log_{10}(\\alpha)$ digits of precision.\n",
    "\n",
    "(c) The residual can be made arbitrarily large or small, depending on the scaling of the problem and is meaningless unless it is considered relative to the size of the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.35. Specify an elementary elimination matrix that zeros the last two components of the vector $[3 \\quad 2 \\quad -1 \\quad 4]^T$.\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "1/3 & 0 & 1 & 0 \\\\\n",
    "-4/3 & 0 & 0 & 1\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.37. With a singular matrix and the use of exact arithmetic, at what point will the solution process break down in solving a linear system by Gaussian elimination\n",
    "(a) With partial pivoting? (b) Without pivoting?\n",
    "\n",
    "(a) Gaussian elimination with partial pivoting of a singular matrix will break down when all elements in the pivot column are zero. \n",
    "\n",
    "(b) Gaussian elimination without partial pivoting of a singular matrix will break down when the first zero pivot element is found since divide-by-zero is undefined.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.39. Consider the following matrix A, whose LU factorization we wish to compute using Gaussian elimination:\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "4 & -8 & 1 \\\\\n",
    "6 & 5 & 7 \\\\\n",
    "0 & -10 & -3\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "> What will the initial pivot element be if (a) No pivoting is used? (b) Partial pivoting is used? (c) Complete pivoting is used?\n",
    "\n",
    "(a) Without pivoting, the first pivot element will be 4.\n",
    "\n",
    "(b) With partial pivoting, the first pivot element will be 6 (max value in column).\n",
    "\n",
    "(c) With complete pivoting, the first pivot element will be -10 (max value in submatrix below and to right of current pivot element).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.41. If A is an ill-conditioned matrix, and its LU factorization is computed by Gaussian elimi- nation with partial pivoting, would you expect the ill-conditioning to be reflected in L, in U, or both? Why?\n",
    "\n",
    "The matrix of lower triangular values, $L$, holds the coefficients used to eliminate each row in the matrix.  For LU factorization with partial pivoting the elements of this matrix are $0 \\leq l_{ij} \\leq 1$.\n",
    "\n",
    "The matrix of upper triangular values, $U$, holds the row reduced submatrix that is results from subtracting a row with a multiple of the pivot row.\n",
    "\n",
    "Since the values of $U$ have less constraints in comparison to $L$, I would expect that ill-conditioning would be reflected in $U$ but not $L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.43. (a) Can every nonsingular $n \\times n$ matrix A be written as a product, $A=LU$,where $L$ is a lower triangular matrix and $U$ is an upper trian- gular matrix?\n",
    "(b) If so, what is an algorithm for accomplishing this? If not, give a counterexample to illustrate.\n",
    "\n",
    "(a) Yes, LU factorization exits for every square matrix, singular or nonsingular, provided that row interchanges are allowed.\n",
    "\n",
    "(b) Gaussian elimination with partial pivoting can be used to factorize A into L and U."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.45. If A and B are $n \\times n$ matrices, with A nonsingular, and $c$ is an n-vector, how would you efficiently compute the product $A^{-1} B c$?\n",
    "\n",
    "Use Gauss-Jordan elimination to transform the augmented matrix $|A \\quad I|$ to $|I \\quad A^{-1}|$.  Plug $A^{-1}$ into the product $A^{-1} B c$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.47. How does the computational work in solv- ing an $n \\times n$ triangular system of linear equations compare with that for solving a general $n \\times n$ sys- tem of linear equations?\n",
    "\n",
    "A triangular system of linear equations can be solved using back or forward substitution with complexity of $O(n^2)$ multiplications and additions.\n",
    "\n",
    "A general system can be solvied using LU factorization with complexity of $O(n^3/3)$ multiplications and additions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.49. If L is a nonsingular lower triangular ma- trix, P is a permutation matrix, and b is a given vector, how would you solve each of the following linear systems?\n",
    "(a) LPx = b\n",
    "(b) PLx = b\n",
    "\n",
    "(a) Note: Treat this as LU factorization with P = U.\n",
    "\n",
    "Solve $L P x = b$ for $x$ by setting $y = P x$.\n",
    "1. Solve $L y = b$ for $y$\n",
    "2. Solve $P x = y$ for $x$.\n",
    "\n",
    "(b) Note: Permutation matrix P has property that $P^T = P^{-1}$.\n",
    "$$\n",
    "P L x = b \\\\\n",
    "P^T P L x = P^T b \\\\\n",
    "I L x = P^T b \\\\\n",
    "L x = P^T b \\\\\n",
    "$$\n",
    "Solve for $x$ using forward substitution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.51. In the plane $\\mathbb{R}^2$, is it possible to have two vectors x and y such that $||x||_1 \\gt ||y||_1$, but $||x||_{\\inf} \\lt ||y||_{\\inf}$? If so, give an example.\n",
    "\n",
    "...not sure\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.53. (a) Is the magnitude of the determinant of a matrix a good indicator of whether the matrix is nearly singular?\n",
    "(b) If so, why? If not, what is a better indicator of near singularity?\n",
    "\n",
    "(a) A matrix with a determinant **exactly** equal to 0 is singular, but a matrix with a determinant **near** 0 is not necessarily singular.  \n",
    "* For example, imagine the identity matrix multiplied by a small number.\n",
    "\n",
    "(b) A better indicator of singularity is the condition number which is computed from matrix norms as $\\text{cond}(A) = ||A|| \\cdot ||A^{-1}||$.\n",
    "* Returning to the previous example, the condition number will unambigously identify the matrix as nonsingular."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.55. Why is computing the condition number of a general matrix a nontrivial problem?\n",
    "\n",
    "The condition number, $\\text{cond}(A) = ||A|| \\cdot ||A^{-1}||$, requires the matrix inverse which is expensive and difficult to compute for ill-conditioned matrices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.57. (a) What is the condition number of the following matrix using the 1-norm? (b) Does your answer differ using the $\\infty-norm$?\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "4 & 0 & 0 \\\\\n",
    "0 & -6 & 0 \\\\\n",
    "0 & 0 & 2 \n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "(a) 1-norm is the maximum absolute column sum which is $0 + |-6| + 0 = 6$.\n",
    "\n",
    "(b) $\\infty-norm$ is the maximum absolute row sum which is $0 + |-6| + 0 = 6$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "> 2.59. Let A = diag(1/2) be an $n \\times n$ diagonal matrix with all its diagonal entries equal to 1/2. (a) What is the value of det(A)?\n",
    "(b) What is the value of cond(A)?\n",
    "(c) What conclusion can you draw from these re- sults?\n",
    "\n",
    "(a) $\\det(A) = (1/2)^n$\n",
    "\n",
    "(b) Condition number of diagonal matrix is $max|d_i| / min|d_i|$ and in this case $\\text{cond}(A) = 1$.\n",
    "\n",
    "(c) As the size of $n$ increases, the determinant will get smaller and smaller, but the condition number will remain unchanged."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}