%**************************************%
%*    Generated from PreTeXt source   *%
%*    on 2017-10-08T23:16:08+01:00    *%
%*                                    *%
%*   http://mathbook.pugetsound.edu   *%
%*                                    *%
%**************************************%
\documentclass[11pt,]{article}
%% Custom Preamble Entries, early (use latex.preamble.early)
%% Inline math delimiters, \(, \), need to be robust
%% 2016-01-31:  latexrelease.sty  supersedes  fixltx2e.sty
%% If  latexrelease.sty  exists, bugfix is in kernel
%% If not, bugfix is in  fixltx2e.sty
%% See:  https://tug.org/TUGboat/tb36-3/tb114ltnews22.pdf
%% and read "Fewer fragile commands" in distribution's  latexchanges.pdf
\IfFileExists{latexrelease.sty}{}{\usepackage{fixltx2e}}
%% Text height identically 9 inches, text width varies on point size
%% See Bringhurst 2.1.1 on measure for recommendations
%% 75 characters per line (count spaces, punctuation) is target
%% which is the upper limit of Bringhurst's recommendations
%% Load geometry package to allow page margin adjustments
\usepackage{geometry}
\geometry{letterpaper,total={374pt,9.0in}}
%% Custom Page Layout Adjustments (use latex.geometry)
\geometry{paperheight=297mm,paperwidth=210mm,margin=20mm}
%% This LaTeX file may be compiled with pdflatex, xelatex, or lualatex
%% The following provides engine-specific capabilities
%% Generally, xelatex and lualatex will do better languages other than US English
%% You can pick from the conditional if you will only ever use one engine
\usepackage{ifthen}
\usepackage{ifxetex,ifluatex}
\ifthenelse{\boolean{xetex} \or \boolean{luatex}}{%
%% begin: xelatex and lualatex-specific configuration
%% fontspec package will make Latin Modern (lmodern) the default font
\ifxetex\usepackage{xltxtra}\fi
\usepackage{fontspec}
%% realscripts is the only part of xltxtra relevant to lualatex 
\ifluatex\usepackage{realscripts}\fi
%% 
%% Extensive support for other languages
\usepackage{polyglossia}
%% Main document language is US English
\setdefaultlanguage{english}
%% Spanish
\setotherlanguage{spanish}
%% Vietnamese
\setotherlanguage{vietnamese}
%% end: xelatex and lualatex-specific configuration
}{%
%% begin: pdflatex-specific configuration
%% translate common Unicode to their LaTeX equivalents
%% Also, fontenc with T1 makes CM-Super the default font
%% (\input{ix-utf8enc.dfu} from the "inputenx" package is possible addition (broken?)
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
%% end: pdflatex-specific configuration
}
%% Symbols, align environment, bracket-matrix
\usepackage{amsmath}
\usepackage{amssymb}
%% allow page breaks within display mathematics anywhere
%% level 4 is maximally permissive
%% this is exactly the opposite of AMSmath package philosophy
%% there are per-display, and per-equation options to control this
%% split, aligned, gathered, and alignedat are not affected
\allowdisplaybreaks[4]
%% allow more columns to a matrix
%% can make this even bigger by overriding with  latex.preamble.late  processing option
\setcounter{MaxMatrixCols}{30}
%%
%% Color support, xcolor package
%% Always loaded.  Used for:
%% mdframed boxes, add/delete text, author tools
\PassOptionsToPackage{usenames,dvipsnames,svgnames,table}{xcolor}
\usepackage{xcolor}
%%
%% Semantic Macros
%% To preserve meaning in a LaTeX file
%% Only defined here if required in this document
%% Used for inline definitions of terms
\newcommand{\terminology}[1]{\textbf{#1}}
%% Subdivision Numbering, Chapters, Sections, Subsections, etc
%% Subdivision numbers may be turned off at some level ("depth")
%% A section *always* has depth 1, contrary to us counting from the document root
%% The latex default is 3.  If a larger number is present here, then
%% removing this command may make some cross-references ambiguous
%% The precursor variable $numbering-maxlevel is checked for consistency in the common XSL file
\setcounter{secnumdepth}{3}
%% Environments with amsthm package
%% Theorem-like environments in "plain" style, with or without proof
\usepackage{amsthm}
\theoremstyle{plain}
%% Numbering for Theorems, Conjectures, Examples, Figures, etc
%% Controlled by  numbering.theorems.level  processing parameter
%% Always need a theorem environment to set base numbering scheme
%% even if document has no theorems (but has other environments)
\newtheorem{theorem}{Theorem}[section]
%% Only variants actually used in document appear here
%% Style is like a theorem, and for statements without proofs
%% Numbering: all theorem-like numbered consecutively
%% i.e. Corollary 4.3 follows Theorem 4.2
\newtheorem{lemma}[theorem]{Lemma}
%% Definition-like environments, normal text
%% Numbering is in sync with theorems, etc
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
%% Example-like environments, normal text
%% Numbering is in sync with theorems, etc
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
%% Miscellaneous environments, normal text
%% Numbering for inline exercises and lists is in sync with theorems, etc
\theoremstyle{definition}
\newtheorem{exercise}[theorem]{Exercise}
%% Localize LaTeX supplied names (possibly none)
\renewcommand*{\abstractname}{Abstract}
%% Raster graphics inclusion, wrapped figures in paragraphs
%% \resizebox sometimes used for images in side-by-side layout
\usepackage{graphicx}
%%
%% More flexible list management, esp. for references and exercises
%% But also for specifying labels (i.e. custom order) on nested lists
\usepackage{enumitem}
%% Lists of references in their own section, maximum depth 1
\newlist{referencelist}{description}{4}
\setlist[referencelist]{leftmargin=!,labelwidth=!,labelsep=0ex,itemsep=1.0ex,topsep=1.0ex,partopsep=0pt,parsep=0pt}
%% hyperref driver does not need to be specified, it will be detected
\usepackage{hyperref}
%% configure hyperref's  \url  to match listings' inline verbatim
\renewcommand\UrlFont{\small\ttfamily}
%% Hyperlinking active in PDFs, all links solid and blue
\hypersetup{colorlinks=true,linkcolor=blue,citecolor=blue,filecolor=blue,urlcolor=blue}
\hypersetup{pdftitle={Advanced Linear Algebra - Algorithms}}
%% If you manually remove hyperref, leave in this next command
\providecommand\phantomsection{}
%% Graphics Preamble Entries
\usepackage{pgfplots}
%% If tikz has been loaded, replace ampersand with \amp macro
%% extpfeil package for certain extensible arrows,
%% as also provided by MathJax extension of the same name
%% NB: this package loads mtools, which loads calc, which redefines
%%     \setlength, so it can be removed if it seems to be in the 
%%     way and your math does not use:
%%     
%%     \xtwoheadrightarrow, \xtwoheadleftarrow, \xmapsto, \xlongequal, \xtofrom
%%     
%%     we have had to be extra careful with variable thickness
%%     lines in tables, and so also load this package late
\usepackage{extpfeil}
%% Custom Preamble Entries, late (use latex.preamble.late)
%% Begin: Author-provided packages
%% (From  docinfo/latex-preamble/package  elements)
%% End: Author-provided packages
%% Begin: Author-provided macros
%% (From  docinfo/macros  element)
%% Plus three from MBX for XML characters
\newcommand{\Cs}{\mathbb{Cs}}
\newcommand{\Cm}{\mathbb{C}^{m}}
\newcommand{\Cmm}{\mathbb{C}^{m\times m}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rm}{\mathbb{R}^{m}}
\newcommand{\Rmm}{\mathbb{R}^{m\times m}}
\DeclareMathOperator{\Rank}{rank}
\newcommand{\definiteintegral}[4]{\int_{#1}^{#2}\,#3\,d#4}
\newcommand{\indefiniteintegral}[2]{\int#1\,d#2} 
\graphicspath{ {images/} }
\usepackage{amsmath}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
%% End: Author-provided macros
%% Title page information for article
\title{Advanced Linear Algebra - Algorithms}
\date{}
\begin{document}
%% Target for xref to top-level element is document start
\hypertarget{MA500-1}{}
\maketitle
\thispagestyle{empty}
Niall Madden\\
School of Mathematics, Statistics and Applied Mathematics\\
National University of Ireland, Galway\\
\href{mailto:Niall.Madden@NUIGalway.ie}{\nolinkurl{Niall.Madden@NUIGalway.ie}}
\and
October 8, 2017These notes accompany the Algorithms section of Advanced Linear Algebra (MA500-1) taught at NUI Galway in Semester 1 2017/2018 by Niall Madden. For notes of the theory section, taught by Rachel Quinlan, please see \url{http://www.maths.nuigalway.ie/\~rquinlan/linearalgebra/}.%
\typeout{************************************************}
\typeout{Section 1 Introduction (RQ)}
\typeout{************************************************}
\section[{Introduction (RQ)}]{Introduction (RQ)}\label{Lecture-01}
RQ and NM introduced themselves, and introduced the module. RQ then discussed linear transformations and eigenvalues.%
\typeout{************************************************}
\typeout{Section 2 Matrix Multiplication (NM)}
\typeout{************************************************}
\section[{Matrix Multiplication (NM)}]{Matrix Multiplication (NM)}\label{Lecture-02}
These section closely follows Lecture 1 of Trefethen and Bau's Numerical Linear Algebra. The first 5 lectures are freely available from \href{https://people.maths.ox.ac.uk/trefethen/text.html}{the first author's home page}. The summary below should be read in the context of those notes. I don't reproduce their text, just repeat the examples done in class.%
\par
Some of the following exercises are taken from Ilse Ipsen's \href{http://epubs.siam.org.libgate.library.nuigalway.ie/doi/book/10.1137/1.9780898717686}{Numerical Matrix Analysis}. Full text is available online through the library portal.%
\typeout{************************************************}
\typeout{Subsection 2.1 Matrix vector multiplication}
\typeout{************************************************}
\subsection[{Matrix vector multiplication}]{Matrix vector multiplication}\label{subsection-1}
If \(A\) is an \(m \times n\) matrix, and \(x\) and \(b\) are \(m\)-vectors, with given by \(b = A x\), then%
\begin{equation*}
b_i = \sum_{j=1}^N a_{ij} x_j.
\end{equation*}
%
\begin{example}[]\label{example-1}
Let%
\begin{equation*}
A = \begin{pmatrix} a \amp b \\ c \amp d
\end{pmatrix}, 
x = \begin{pmatrix} x_1 \\ x_2
\end{pmatrix}.
\end{equation*}
This gives%
\begin{equation*}
b = 
\begin{pmatrix}
x_1 a + x_2 b \\ x_1 c + x_2 d
\end{pmatrix}
=
x_1 \begin{pmatrix}  a \\ c \end{pmatrix} + 
x_2 \begin{pmatrix}  b \\ d \end{pmatrix}.
\end{equation*}
So \(b\) is  a linear combination of the columns of \(A\) with coefficients from \(x\).%
\end{example}
\typeout{************************************************}
\typeout{Subsection 2.2 Matrix-matrix multiplication}
\typeout{************************************************}
\subsection[{Matrix-matrix multiplication}]{Matrix-matrix multiplication}\label{subsection-2}
If \(A\) is a \(m \times n\)-matrix, \(C\) is a \(n \times p\) matrix, and \(B=AC\), then \(B\) is the \(m \times p\) matrix given by%
\begin{equation*}
b_{ij} = \sum_{k=1}^n a_{ik}c_{kj}.
\end{equation*}
But in keeping with the ideas above, let us consider the formula for column \(j\) of \(B\):%
\begin{equation*}
b_j = \sum_{k=1}^n c_{kj} {a_k}.
\end{equation*}
So column \(j\) of \(B\) is a linear combination of all the columns of \(A\), with the coefficients taken from column \(j\) of \(C\).%
\par
Other examples that are worth considering, include computing the inner and outer  products of the vectors \((a, b, c)^T\) and \((d,e,f)^T\).%
\begin{example}[]\label{example-2}
%
\begin{equation*}
A=\begin{pmatrix}
0 \amp 1 \amp 1 \amp 1\\
0 \amp 0 \amp 1 \amp 1\\
0 \amp 0 \amp 0 \amp 1\\
0 \amp 0 \amp 0 \amp 0
\end{pmatrix}.
\end{equation*}
\(A^2\)\(A^3\)\(A^4\)\end{example}
Please also read Section 1.7 of \hyperlink{biblio-Ipsen-2009}{[1]} for more on four different ``views'' of matrix-matrix multiplication.%
\typeout{************************************************}
\typeout{Subsection 2.3 Exercises}
\typeout{************************************************}
\subsection[{Exercises}]{Exercises}\label{subsection-3}
\begin{exercise}\label{exercise-1}
Use the ``column version'' of matrix-matrix multiplication to show that the product of two lower-triangular matrices is lower-triangular.%
\end{exercise}
We partition the identity matrix into columns as%
\begin{equation*}
I= (e_1 | e_2 | \cdots | e_n).
\end{equation*}
That is,%
\begin{equation*}
e_1 = \begin{pmatrix}1 \\ 0 \\ \vdots \\ 0 \\ 0\end{pmatrix} 
\quad
e_2 = \begin{pmatrix}0 \\ 1 \\ \vdots \\ 0 \\ 0	\end{pmatrix}
\quad \dots \quad
e_n = \begin{pmatrix}0 \\ 0 \\ \vdots \\ 0 \\ 1	\end{pmatrix} 
\end{equation*}
%
\begin{exercise}\label{exercise-2}
\leavevmode%
\begin{enumerate}
\item\hypertarget{li-1}{}Show that \(Ae_j\) is the \(j\)th column on \(A\).%
\item\hypertarget{li-2}{}Let \(v\) be the vector \(v=(1,1,\dots,1)\). What is \(A v\)?%
\end{enumerate}
\end{exercise}
The next one is from \hyperlink{biblio-Ipsen-2009}{[1]}. To answer it you need to know that a matrix \(A\) is \leavevmode%
\begin{itemize}[label=\textbullet]
\item{}involutory if \(A^2=I\),%
\item{}nilpotent if \(A^k=0\) for some integer \(k>0\)%
\item{}a \emph{projector} (also known as \emph{idempotent}) if \(A^2=A\)%
\end{itemize}
%
\begin{exercise}\label{exercise-3}
\leavevmode%
\begin{enumerate}
\item\hypertarget{li-6}{}Which is the only matrix that is both a projector and involutory?%
\item\hypertarget{li-7}{}Which is the only matrix that is both idempotent and nilpotent?%
\item\hypertarget{li-8}{}Prove that if \(A\) is a projector, then so too is \(I-A\).%
\item\hypertarget{li-9}{}Prove that if \(A\) and \(B\) are both projectors, and \(AB=BA\), them \(AB\) is also a projector.%
\item\hypertarget{li-10}{}Prove that \(A\)  is involutory if and only if \((I-A)(I+A)=0\).%
\item\hypertarget{li-11}{}Show that if \(A\) is involutory \(B=\frac{1}{2}(I+A)\), then \(B\) is a projector.%
\end{enumerate}
\end{exercise}
\begin{exercise}\label{exercise-4}
A matrix \(L \in \Rmm\) is  \emph{lower triangular} if \(l_{ij}=0\) when  \(i \lt j\). If, in addition,  \(l_{ii}=1\), then it is \emph{unit lower triangular}. Show that the product of two unit lower triangular matrices is lower triangular.%
\par
Show that if we write the unit lower triangular matrix \(L\) as \(L=I+N\), then \(N\) is nilpotent.%
\par
Show that%
\begin{equation*}
L^{-1} = I -N +N^2 -N^3 + \dots.
\end{equation*}
Deduce that \(L^{-1}\) is itself a unit lower triangular  matrix.%
\end{exercise}
\typeout{************************************************}
\typeout{Section 3 Range, nullspace, and rank (NM)}
\typeout{************************************************}
\section[{Range, nullspace, and rank (NM)}]{Range, nullspace, and rank (NM)}\label{Lecture-03}
More from Lecture 1 of Trefethen and	Bau.%
\typeout{************************************************}
\typeout{Subsection 3.1 Exercises}
\typeout{************************************************}
\subsection[{Exercises}]{Exercises}\label{subsection-4}
\begin{exercise}\label{exercise-5}
Prove that \(A \in \Cmm\) has full rank if and only if it maps no two distinct vectors to the same vector. That is, show that if \(x\) and \(y\) are vectors, with \(x \neq y\), then%
\begin{equation*}
Ax \neq Ay \iff \Rank(A)=m.
\end{equation*}
%
\end{exercise}
\begin{exercise}\label{exercise-6}
Suppose you know the rank of the \(m\times m\) matrices   \(A\) and \(B\). What, if anything,  can you say about the rank of \(C=AB\)? Suppose \(A\) or \(B\) have full rank, what can you say about the rank of \(C\)?%
\end{exercise}
\typeout{************************************************}
\typeout{Section 4 The matrix of a linear transformation (RQ)}
\typeout{************************************************}
\section[{The matrix of a linear transformation (RQ)}]{The matrix of a linear transformation (RQ)}\label{Lecture-04}
See \url{http://www.maths.nuigalway.ie/\~rquinlan/linearalgebra/lecture4.pdf}%
\typeout{************************************************}
\typeout{Section 5 Some bases are better than others (RQ)}
\typeout{************************************************}
\section[{Some bases are better than others (RQ)}]{Some bases are better than others (RQ)}\label{Lecture-05}
See \url{http://www.maths.nuigalway.ie/\~rquinlan/linearalgebra/lecture5.pdf}%
\typeout{************************************************}
\typeout{Section 6 Orthogonal Vectors (NM)}
\typeout{************************************************}
\section[{Orthogonal Vectors (NM)}]{Orthogonal Vectors (NM)}\label{Lecture-06}
\typeout{************************************************}
\typeout{Subsection 6.1 Some bases are better than others}
\typeout{************************************************}
\subsection[{Some bases are better than others}]{Some bases are better than others}\label{Lecture-06-1}
We recalled that, towards the end of \hyperref[Lecture-04]{Lecture~\ref{Lecture-04}}, we observed that, if \(A\) is an \(n \times n\) matrix with \(n\) linearly independent rows, then there exists a matrix \(A^{-1}\) such that%
\begin{equation*}
A A^{-1} = A^{-1}A = I.
\end{equation*}
We say that \(A\) is non-singular or invertible. We then noted that multiplying by \(A^{-1}\) (or, indeed, by \(A\)) can be interpreted as a change of basis operation.%
\typeout{************************************************}
\typeout{Subsection 6.2 Transpose}
\typeout{************************************************}
\subsection[{Transpose}]{Transpose}\label{Lecture-06-transpose}
The transpose of the matrix \(A \in \mathbb{R}^{m \times n}\) is \(A^T \in \mathbb{R}\) where%
\begin{equation*}
(A)_{i,j} = (A^T)_{j,i}\text{.}
\end{equation*}
However, if \(A \in \mathbb{C}^{m \times n}\) we need to define the related concept of the Hermetian Transpose, \(A^\star\), for which%
\begin{equation*}
(A)_{i,j} = \overline{(A^T)_{j,i}}\text{.}
\end{equation*}
Here \(\bar{z}\) denotes the \emph{complex conjugate} of \(z\). It is easy to show that%
\begin{equation*}
(AB)^\star = B^\star A^\star.
\end{equation*}
%
\begin{exercise}\label{exercise-7}
Show that if \(A \in \mathbb{C}^{n \times n}\) is non-singular, then%
\begin{equation*}
(A^{-1})^\star = (A^\star)^{-1}.
\end{equation*}
%
\end{exercise}
\typeout{************************************************}
\typeout{Subsection 6.3 Vector spaces and inner product spaces}
\typeout{************************************************}
\subsection[{Vector spaces and inner product spaces}]{Vector spaces and inner product spaces}\label{Lecture-06-ip}
\begin{exercise}\label{exercise-8}
Find a definition of a vector space.%
\end{exercise}
An inner product space (of vectors over a field \(\mathbb{F}\)) is a vector space, \(V\),  equipped with the function \((\cdot, \cdot) : V \times V \to \mathbb{F},\) such that, if \(x,y,z \in V\) and \(a \in \mathbb{F}\) then%
\begin{equation*}
\begin{split}
(x,y) \amp =\overline{(x,y)}\\
(ax,y) \amp = a(x,y)\\
(x+y,z) \amp = (x,z)+(y,z)\\
(x,x) \amp \geq 0\\
(x,x) \amp = 0 \text{ iff } x=0.
\end{split}
\end{equation*}
%
\par
There are many possible inner products, but the most important, for vectors with entries in \(\mathbb{C}\) is the usual \emph{dot product}:%
\begin{equation*}
(u,v) := u^\star v = \sum_{i=0}^n \bar{u}_i v_i.
\end{equation*}
For real-valued vectors it can be understood as the ``angle'' between the vectors in \(\mathbb{R}\). That is, if \(\alpha\) is the angle between two vectors, \(u\) and \(v\), then,%
\begin{equation*}
\cos(\alpha) = \frac{(u,v)}{\sqrt{(u,u)} \sqrt{(v,v)}}.
\end{equation*}
The most important/interesting situation  when \((u,v)=0\), in which case we say that \(u\) and \(v\) are \emph{orthogonal}.%
\typeout{************************************************}
\typeout{Subsection 6.4 Exercises}
\typeout{************************************************}
\subsection[{Exercises}]{Exercises}\label{subsection-8}
\begin{exercise}\label{exercise-9}
A matrix \(S \in \Cmm\) is ``skew-hermitian'' if \(S^\star = -  S\). Show that the eigenvalues of \(S\) are pure imaginary.%
\end{exercise}
\typeout{************************************************}
\typeout{Section 7 Unitary Matrices (NM, 18 Sep)}
\typeout{************************************************}
\section[{Unitary Matrices (NM, 18 Sep)}]{Unitary Matrices (NM, 18 Sep)}\label{Lecture-07}
\begin{definition}[{}]\label{definition-1}
A matrix \(Q \in \Cmm\) is \terminology{unitary} if its  columns form an orthogonal, orthonormal set.%
\end{definition}
It follows that \(Q^{-1} =Q^\star\).%
\typeout{************************************************}
\typeout{Subsection 7.1 Exercise(s)}
\typeout{************************************************}
\subsection[{Exercise(s)}]{Exercise(s)}\label{subsection-9}
\begin{exercise}[{(Exercise  2.1 of \hyperlink{biblio-TB-1997}{[2]})}]\label{exercise-10}
Show that if a matrix is both triangular and unitary, then it is diagonal.%
\par\smallskip
\noindent\textbf{Hint.}\hypertarget{hint-1}{}\quad
There are at least two approaches to this. One is to consider what the structure of the inverse and of the Hermetian transpose of an upper  triangular matrix might look like (to simplify, consider just upper triangular matrices). The second is to assume the matrix is upper triangular, and then check what conditions its second column must satisfy in order to be orthogonal to its first.\end{exercise}
\typeout{************************************************}
\typeout{Section 8 Symmetric Matrices I (RQ, 19 Sep)}
\typeout{************************************************}
\section[{Symmetric Matrices I (RQ, 19 Sep)}]{Symmetric Matrices I (RQ, 19 Sep)}\label{Lecture-08}
See \url{http://www.maths.nuigalway.ie/\~rquinlan/linearalgebra/lecture8-9.pdf}%
\typeout{************************************************}
\typeout{Section 9 Symmetric Matrices II (RQ, 20 Sep)}
\typeout{************************************************}
\section[{Symmetric Matrices II (RQ, 20 Sep)}]{Symmetric Matrices II (RQ, 20 Sep)}\label{Lecture-09}
See \url{http://www.maths.nuigalway.ie/\~rquinlan/linearalgebra/lecture8-9.pdf}%
\typeout{************************************************}
\typeout{Section 10 Vector Norms (NM, 25 Sep)}
\typeout{************************************************}
\section[{Vector Norms (NM, 25 Sep)}]{Vector Norms (NM, 25 Sep)}\label{Lecture-10}
\begin{definition}[{Norm on \(\Cm\)}]\label{definition-2}
A function \(\| \cdot \|\) is called a \emph{\terminology{norm}} on \(\Cm\) if, for all vectors \(x\) and \(y\) in \(\Cm\) \leavevmode%
\begin{enumerate}
\item\hypertarget{li-12}{}\(\|x\| \geq 0\), and \(\|x\|=0\) if and only if \(x=0\).%
\item\hypertarget{li-13}{}\(\|\lambda x\| = |\lambda| \| x\|\) for any scalar \(\lambda \in \Cs\).%
\item\hypertarget{li-14}{}\(\|x + y\| \leq \| x\| + \| y\|\) (triangle inequality).%
\end{enumerate}
%
\end{definition}
The norm of a  vector gives us some information about the ``\emph{size}''  of the vector. But there are different ways of measuring the size: you could take the absolute value of the largest entry, you cold look at the ``distance'' for the origin, etc...%
\begin{definition}[{\(p\)-norms.}]\label{definition-3}
For any \(p \lt 1\), define%
\begin{equation*}
\|x\|_p = \big( \sum_{i=1}^m|x_i|^p\big)^{1/p}.
\end{equation*}
%
\end{definition}
Of particular importance are the norms \leavevmode%
\begin{enumerate}
\item\hypertarget{li-15}{}The 1-norm (or ``taxi-cab norm''): \(\|\vec x\|_1 = \sum_{i=1}^n |x_i|\).%
\item\hypertarget{li-16}{}The \(2\)-norm  (a.k.a. the \emph{Euclidean norm}): \(\|x\|_2 = \bigg(\sum_{i=1}^n |x_i|^2\bigg)^{1/2}.\) Note,  if \(x \in \Cm\),  then \(x^\star x =  \|x\|_2^2\).%
\item\hypertarget{li-17}{}The \(\infty\)-norm (also known as the \emph{max-norm}): \(\|\vec x\|_\infty = \max_{i=1}^n |x_i|\).%
\end{enumerate}
%
\par
It takes a little bit of effort to show that \(\| \cdot
\|_2\) satisfies the triangle inequality. First  we need the Cauchy-Schwarz inequality.%
\begin{lemma}[{Cauchy-Schwarz inequality}]\label{lemma-1}
For all \(x, y \in \Cm\),%
\begin{equation*}
| x^Ty | \leq \| x\|_2 \| y \|_2.
\end{equation*}
%
\end{lemma}
This can then be applied to show that%
\begin{equation*}
\| x + y \|_2 \leq \| x\|_2 + \|y\|_2.
\end{equation*}
It follows directly that \(\| \cdot\|_2\) is a norm.%
\typeout{************************************************}
\typeout{Subsection 10.1 Exercises}
\typeout{************************************************}
\subsection[{Exercises}]{Exercises}\label{subsection-10}
\begin{exercise}\label{exercise-11}
Define the function \(\| \cdot \|_{A,1} : \Cm \to
\R\) as \(\|x\|_{A,1} = \|Ax\|_1\) where \(\|\cdot \|_1\) is the usual 1-norm (a.k.a. ``the taxicab norm'') on \(\Cm\), and 	\(A \in \Cmm\)  is non-singular. Is it true that \(\|Ax\|_1\) is a  norm on \(\Cm\)?%
\end{exercise}
\begin{exercise}\label{exercise-12}
Show that  the following inequalities hold for all vectors \(x \in \Cm\). If possible, give a nontrivial  example for which equality holds.%
\leavevmode%
\begin{enumerate}
\item\hypertarget{li-18}{}\(\| x \|_\infty \leq \| x\|_2\)%
\item\hypertarget{li-19}{}\(\|x \|_2 \leq  \sqrt{m}\|  x\|_\infty\)%
\item\hypertarget{li-20}{}\(\|  x \|_2 \leq \| \sqrt{x\|_1 \|  x\|_\infty}\)%
\item\hypertarget{li-21}{}\(\|x\|_\infty \leq \|x\|_2 \leq  \|x\|_1\)%
\end{enumerate}
Which, if any, of these inequalities extend to the matrix norms induced by these vector norms?%
\end{exercise}
\typeout{************************************************}
\typeout{Section 11 Matrix Norms (NM, 26 Sep)}
\typeout{************************************************}
\section[{Matrix Norms (NM, 26 Sep)}]{Matrix Norms (NM, 26 Sep)}\label{Lecture-11}
\begin{definition}[{}]\label{definition-4}
A \terminology{matrix norm}...%
\end{definition}
\typeout{************************************************}
\typeout{Subsection 11.1 Exercises}
\typeout{************************************************}
\subsection[{Exercises}]{Exercises}\label{subsection-11}
\begin{exercise}\label{exercise-13}
Show that the function that maps \(A\in \Rmm\) to \(A \rightarrow |\det(A)|\) is \emph{not} a matrix norm.%
\end{exercise}
\begin{exercise}\label{exercise-14}
Show that for any of subordinate matrix norm, \(\|I\|=1\). (That is, the norm of the identity matrix is 1). Is this also true of \(\|\cdot\|_F\)?%
\end{exercise}
\begin{exercise}\label{exercise-15}
Show that for any matrix \(A \in \Rmm\), \leavevmode%
\begin{enumerate}
\item\hypertarget{li-22}{}%
\begin{equation*}
\|A\|_\infty = \max_{i=1, \dots, m} \sum_{j=1}^m |a_{i,j}|.
\end{equation*}
%
\item\hypertarget{li-23}{}%
\begin{equation*}
\|A\|_1 = \max_{j=1, \dots, m} \sum_{i=1}^m |a_{i,j}|.
\end{equation*}
%
\end{enumerate}
%
\end{exercise}
\begin{exercise}\label{exercise-16}
Show that for any subordinate matrix norm, \(\|A\| \geq |\lambda|\) for any eigenvalue  \(\lambda\) of \(A\).%
\end{exercise}
\begin{exercise}\label{exercise-17}
Consider the function \(\| \cdot \|:\Rmm \rightarrow \R\) defined by%
\begin{equation*}
\| A\|_{\widetilde\infty} = \max_{i,j} |a_{ij}|.
\end{equation*}
Show that this is a norm. Show that it is \emph{not} sub-multiplicative.%
\end{exercise}
\typeout{************************************************}
\typeout{References  References}
\typeout{************************************************}
\section*{References}\label{references-1}
\addcontentsline{toc}{section}{References}
%% If this is a top-level references
%%   you can replace with "thebibliography" environment
\begin{referencelist}
\bibitem[1]{biblio-Ipsen-2009}\hypertarget{biblio-Ipsen-2009}{}Isle C.F. Ipsen, \textit{Numerical matrix analysis: Linear systems and least squares}. Society for Industrial and Applied Mathematics, 2009.
\bibitem[2]{biblio-TB-1997}\hypertarget{biblio-TB-1997}{}L.N. Trefethen and D. Bau III, \textit{Numerical linear algebra} Society for Industrial and Applied Mathematics, 1997.
\end{referencelist}
\end{document}