%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
% This top part of the document is called the 'preamble'.  Modify it with caution!
%
% The real document starts below where it says 'The main document starts here'.

\documentclass[12pt]{article}

\usepackage{amssymb,amsmath,amsthm}
\usepackage[top=1in, bottom=1in, left=1.25in, right=1.25in]{geometry}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{verbatim}

% Comment the following line to use TeX's default font of Computer Modern.
\usepackage{times,txfonts}

\newtheoremstyle{homework}% name of the style to be used
  {18pt}% measure of space to leave above the theorem. E.g.: 3pt
  {12pt}% measure of space to leave below the theorem. E.g.: 3pt
  {}% name of font to use in the body of the theorem
  {}% measure of space to indent
  {\bfseries}% name of head font
  {:}% punctuation between head and body
  {2ex}% space after theorem head; " " = normal interword space
  {}% Manually specify head
\theoremstyle{homework} 

% Set up an Exercise environment and a Solution label.
\newtheorem*{exercisecore}{\@currentlabel}
\newenvironment{exercise}[1]
{\def\@currentlabel{#1}\exercisecore}
{\endexercisecore}

\newcommand{\localhead}[1]{\par\smallskip\noindent\textbf{#1}\nobreak\\}%
\newcommand\solution{\localhead{Solution:}}



% \newcommand{includematlab}[1]{\verbatiminput{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Stuff for getting the name/document date/title across the header
\makeatletter
\RequirePackage{fancyhdr}
\pagestyle{fancy}
\fancyfoot[C]{\ifnum \value{page} > 1\relax\thepage\fi}
\fancyhead[L]{\ifx\@doclabel\@empty\else\@doclabel\fi}
\fancyhead[C]{\ifx\@docdate\@empty\else\@docdate\fi}
\fancyhead[R]{\ifx\@docauthor\@empty\else\@docauthor\fi}
\headheight 15pt

\def\doclabel#1{\gdef\@doclabel{#1}}
\doclabel{Use {\tt\textbackslash doclabel\{MY LABEL\}}.}
\def\docdate#1{\gdef\@docdate{#1}}
\docdate{Use {\tt\textbackslash docdate\{MY DATE\}}.}
\def\docauthor#1{\gdef\@docauthor{#1}}
\docauthor{Use {\tt\textbackslash docauthor\{MY NAME\}}.}
\makeatother

%% General formatting parameters
\parindent 0pt
\parskip 12pt plus 1pt

% Shortcuts for blackboard bold number sets (reals, integers, etc.)
\newcommand{\Reals}{\ensuremath{\mathbb R}}
\newcommand{\Nats}{\ensuremath{\mathbb N}}
\newcommand{\Ints}{\ensuremath{\mathbb Z}}
\newcommand{\Rats}{\ensuremath{\mathbb Q}}
\newcommand{\Cplx}{\ensuremath{\mathbb C}}
%% Some equivalents that some people may prefer.
\let\RR\Reals
\let\NN\Nats
\let\II\Ints
\let\CC\Cplx

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
% The main document start here.

% The following commands set up the material that appears in the header.
\doclabel{Math 426: Homework 7}
\docauthor{Your name here!}
\docdate{October 14, 2020}

\begin{document}
\begin{exercise} {Problem 7.3 [Modified]} \strut

\begin{itemize}
	\item Do part (a).
	\item Write a Matlab function {\tt LUNoPivot} that 
	takes as input a square matrix and returns two matrices $L$ and $U$,
	lower and upper triangular matrices such that $L$ has 1's
	on the diagonal and such that $A=LU$.  Do not pivot (i.e., do not perform row interchanges).  You can use the code on page 140
	of your text as a starting point. You should test your code on the 
	$3\times 3$ matrix presented in class today; the matrix $A$ from
	page 135.  That is, verify that indeed $LU=A$.

	Note that the code on page 140 is being sneaky.  Rather than building two matrices, it builds just one. Since $L$ always has 1s on the diagonal, it only has interesting entries below the diagonal.  And since $U$ is all zeros below the diagonal, there's space there to store the entries of $L$!  This is an important space saving technique when the matrices involved are large: no need to go around working with extra matrices that are half zeros and use up twice the needed storage.  But for the purposes of this exercise and clarity,
	we'll return $L$ and $U$ seperately.
	\item Now do part (c). You'll need to use {\tt lsolve} from the
	text (page 140) and ${\tt usolve}$ from Problem 7.2.
\end{itemize}
\end{exercise}

\begin{exercise}{Supplemental 1}
Write a function to compute the inverse of a $n\times n$ matrix $A$ as follows.
\begin{enumerate}[(a)]
	\item Let $\mathbf{b}_i$ be column $i$ of $A^{-1}$.  What
	are the entries of  $A \mathbf{b}_i$?  Hint: most of them are zero!
	Use the column perspective of matrix multiplication.
	\item Call your {\tt LUNoPivot} code (or better code with pivoting!)
	to get $L$ and $U$ (and $P$ if you want!).
	\item For each $i$, compute column $\mathbf{b}_i$ of $A^{-1}$
	using the strategy of part a).  For each column, you will call your {\tt lsolve} and your {\tt usolve} funtions exactly once.
\end{enumerate}
\end{exercise}

\begin{exercise}{Supplemental 2}
Determine, with justification, the number of floating point operations 
required to compute the inverse of a matrix using the strategy of
the previous problem.  A complete answer will be of the form
\[
c n^j + O(n^k)
\]
where $c$ is an explicit number, and where $j$ and $k$ are explicit integers with $j>k$.
\end{exercise}

\begin{exercise}{Supplemental 3}
How many $6\times 6$ permutation matrices are there?  A complete answer will justify the number.
\end{exercise}

\begin{exercise}{Supplemental 4}
A permutation matrix can be represented by a vector $[p_1,\ldots,p_n]$
where $p_i$ records which column contains the 1 in row $i$.

Modify the code for {\tt lsolve} to make a new function
{\tt plsolve} so that it takes as arguments
\begin{enumerate}
\item {\tt P}, an $n$-dimensional vector representing a permuation matrix, 
\item {\tt L}, a lower triangular $n\times n$ matrix with $1$'s on the diagonal.
\item {\tt b} an $n$-dimensional vector
\end{enumerate}
It should return the solution to $L\mathbf{c} = P\mathbf{b}$.

Test your code on problem 15 of the {\tt WSPartialPivoting} worksheet.
That is, you will type in the matrics $U$, $L$ you determined on 
the worksheet along with a vector $P$ representing the permutation matrix.
Then use your brand new {\tt plsolve} along with your older {\tt usolve}
to compute the solution of $A\mathbf{x}=\mathbf{b}$.  You should verify that the $\mathbf{x}$ that you compute really works by multiplying by $A$!
\end{exercise}


\end{document}