{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
   "name": "sol.ipynb",
   "provenance": [],
   "collapsed_sections": []
},
"kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
},
"language_info": {
   "name": "python"
}
},
"cells": [
{
   "cell_type": "markdown",
   "metadata": {
   "id": "kHIAc6QyKX-p"
   },
   "source": [
   "# Q1"
   ]
},
{
   "cell_type": "markdown",
   "metadata": {
   "id": "RbHrRbNsKceK"
   },
   "source": [
   "Procedure can be described as follows:\n",
   "\n",
   "for $i=n$ downto 1:\n",
   "\n",
   "> $b'_i = b_i$\n",
   "\n",
   "> for $j=n$ downto $i+1$:\n",
   "\n",
   ">> $b'_i = b'_i - A_{i,j}x_j$ using LU factorization (or similar method)\n",
   "\n",
   "> Solve the system $A_{i,i}x_i = b'_i$\n",
   "\n",
   "Form the solution vector $x = [x_1;\\ x_2;\\ \\cdots\\ x_n]$, where $;$ denotes column concatenation.\n",
   "\n",
   "The total complexity of solving each linear system $A_{i,i}x_i = b'_i$ is $O(n^3)$ while vector $b'_i$ is formed by at most $O(n)$ vector-matrix multiplications requiring time $O(n^2)$, which implies total $O(n^3)$ time per iteration over $i$. Hence, the total time is $O(n^4)$.\n",
   "\n"
   ]

1. Let X be an invertible n by n matrix. (a) Prove that the column...