At this point in the course homework has addressed:

HW0

Tools needed for scientific computation (number representation, number approximation techniques, basic coding constructs, an environment for method documentation and reproducible computational experiments).

HW2

Discretization of continuous functions leads to finite-dimensional vectors that can often be approximated by linear combination of just a few of the basis vectors required for the entire space.

HW3

Large data sets, readily acquired from observations, can guide selection of vectors within a basis to obtain data compression or efficient data representation through linear combination.

Homework 4 reinforces analytical skills within the mathematical framework of finite-dimensional vector spaces used for the above topics. Such technical proficiency is just as important as efficient coding. The midterm examination verifies proficiency in such analytical skills

Note: The exercises below contain well-known results, but should be attempted individually and independently, without recourse to references. Simply looking up a proof and transcribing it will not aid understanding nor ensure good results on the midterm examination. If you do not obtain an exercise proof within 10 minutes reread the relevant theoretical material from the lecture notes and then try again for another 15 minutes.

1Tracks 1 and 2

1. Prove the parallelogram identity

   ${\displaystyle {||𝒙+𝒚||}^2+{||𝒙-𝒚||}^2=2({||𝒙||}^2+{||𝒚||}^2),}$

   for $𝒙,𝒚\in {ℂ}^m$, with $||||$ denoting the 2-norm.

   Solution. ${||𝒙+𝒚||}^2+{||𝒙-𝒚||}^2={(𝒙+𝒚)}^T(𝒙+𝒚)+{(𝒙-𝒚)}^T(𝒙-𝒚)=({𝒙}^T+{𝒚}^T)(𝒙+𝒚)+({𝒙}^T-{𝒚}^T)(𝒙-𝒚)={𝒙}^T𝒙+{𝒚}^T𝒙+{𝒙}^T𝒚+{𝒚}^T𝒚+{𝒙}^T𝒙-{𝒚}^T𝒙-{𝒙}^T𝒚+{𝒚}^T𝒚=2({𝒙}^T𝒙+{𝒚}^T𝒚)=2({||𝒙||}^2+{||𝒚||}^2)$.

2. Consider $𝒖,𝒗\in V$, $𝒱=(V,ℝ,+,\cdot )$ a vector space with norm induced by a scalar product ${||𝒖||}^2=(𝒖,𝒖)$. Prove that $||𝒖||=||𝒗||\Rightarrow$ $(𝒖+𝒗)\perp (𝒖-𝒗)$. Is the converse true?

   Solution. $||𝒖||=||𝒗||\Rightarrow {||𝒖||}^2={||𝒗||}^2\Rightarrow {𝒖}^T𝒖={𝒗}^T𝒗\Rightarrow {𝒖}^T𝒖-{𝒗}^T𝒗=0\Rightarrow {𝒖}^T𝒖+{𝒗}^T𝒖-{𝒖}^T𝒗-{𝒗}^T𝒗=0\Rightarrow ({𝒖}^T+{𝒗}^T)(𝒖-𝒗)=0\Rightarrow {(𝒖+𝒗)}^T(𝒖-𝒗)=0\Rightarrow$ $(𝒖+𝒗)\perp (𝒖-𝒗)$. Converse is also true:

   ${\displaystyle (𝒖+𝒗)\perp (𝒖-𝒗)\Rightarrow {(𝒖+𝒗)}^T(𝒖-𝒗)=0\Rightarrow {𝒖}^T𝒖+{𝒗}^T𝒖-{𝒖}^T𝒗-{𝒗}^T𝒗=0\Rightarrow {𝒖}^T𝒖={𝒗}^T𝒗\Rightarrow ||𝒖||=||𝒗||.}$

3. Consider $𝑨\in {ℝ}^{m\times m}$, $C\left(𝑨\right)={ℝ}^m$. Prove that

   ${\displaystyle {({𝒙}^T{𝑨}^T𝑨𝒙)}^{1/2}}$

   is a norm. (Track 2: generalize above to ${ℂ}^m$)

   Solution. Verify norm properties:

   1. $||𝒙||=0\Rightarrow 𝒙=𝟎$. ${||𝒙||}^2={𝒙}^T{𝑨}^T𝑨𝒙={𝒚}^T𝒚=0\Rightarrow 𝒚=𝟎$. Consider now $𝑨𝒙=𝟎$. Since $𝑨$ is of full rank, $𝒙=𝟎$ is the only solution. Note that if $\mathrm{rank}\left(𝑨\right)<m$, the above is not a norm.

   2. $||c𝒙||=\left|c\right|||𝒙||$. Compute: $||c𝒙||=$${(c{𝒙}^T{𝑨}^T𝑨c𝒙)}^{1/2}=\left|c\right|{({𝒙}^T{𝑨}^T𝑨𝒙)}^{1/2}=\left|c\right|||𝒙||$.

   3. $||𝒙+𝒚||⩽||𝒙||+||𝒚||$. When $𝑨=𝑰$ the standard Euclidean 2-norm ${||||}_2$ is obtained. For $𝑨\ne 𝑰$ of full rank for any $𝒖,𝒗$ there exist $𝒙,𝒚$ such that $𝒖=𝑨𝒙$, $𝒗=𝑨𝒚$ and

      ${\displaystyle ||𝒙||={({𝒙}^T{𝑨}^T𝑨𝒙)}^{1/2}={({𝒖}^T𝒖)}^{1/2}={||𝒖||}_2.}$

      Similarily $||𝒚||={||𝒗||}_2$, $||𝒙+𝒚||={||𝒖+𝒗||}_2$, hence it is sufficient to establish the triangle inequality for the 2-norm ${||𝒖+𝒗||}_2⩽{||𝒖||}_2+{||𝒗||}_2$. Taking squares

      ${\displaystyle {||𝒖+𝒗||}_2^2={(𝒖+𝒗)}^T(𝒖+𝒗)={𝒖}^T𝒖+{𝒗}^T𝒗+2{𝒖}^T𝒗={||𝒖||}_2^2+{||𝒗||}_2^2+2{𝒖}^T𝒗⩽{||𝒖||}_2^2+{||𝒗||}_2^2+2{||𝒖||}_2{||𝒗||}_2\Rightarrow {𝒖}^T𝒗⩽{||𝒖||}_2{||𝒗||}_2,}$

      so it remains to establish the last inequality (known as the Schwarz inequality). The Schwarz inequality can be established by asking: when is equality obtained in the triangle inequality? This occurs if $𝒖,𝒗$ are colinear, and suggest building the vector $𝒘={||𝒗||}_2𝒖-{||𝒖||}_2𝒗$ that becomes zero when $𝒖,𝒗$ are colinear. Calculate

      ${\displaystyle 0⩽{𝒘}^T𝒘={({||𝒗||}_2𝒖-{||𝒖||}_2𝒗)}^T({||𝒗||}_2𝒖-{||𝒖||}_2𝒗)=2{||𝒖||}_2^2{||𝒗||}_2^2-2{||𝒖||}_2{||𝒗||}_2{𝒖}^T𝒗,}$

      from which ${𝒖}^T𝒗⩽{||𝒖||}_2{||𝒗||}_2$, as desired.

4. Construct the matrix $𝑨$ that represents the mapping $𝒇:{ℝ}^3\to {ℝ}^3$, $𝒇$ reflects a vector across the $x_1{x}_2$ plane. Construct the matrix $𝑩$ that represents the mapping $𝒈:{ℝ}^3\to {ℝ}^3$, $𝒈$ reflects a vector across the $x_2{x}_3$ plane. Determine the mapping represented by $𝑪=𝑩𝑨$.

   Solution. Reflecting the point $𝒙={\left[\begin{array}{lll}{x}_1& x_2& x_3\end{array}\right]}^T$ across the $x_1{x}_2$ plane gives $𝑨𝒙={\left[\begin{array}{lll}{x}_1& x_2& -x_3\end{array}\right]}^T$, hence

   ${\displaystyle 𝑨=\left[\begin{array}{ll}{𝑰}_2& 𝟎\\ 𝟎& -1\end{array}\right]=\left[\begin{array}{lll}1& 0& 0\\ 0& 1& 0\\ 0& 0& -1\end{array}\right].}$

   Note the block structure of $𝑨$. Since the first two components of $𝑨𝒙$ are unchanged from those of $𝒙$, an identity matrix on these two components ${𝑰}_2$ appears. Similarily

   ${\displaystyle 𝑩=\left[\begin{array}{lll}-1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right],𝑪=𝑩𝑨=\left[\begin{array}{lll}-1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{lll}1& 0& 0\\ 0& 1& 0\\ 0& 0& -1\end{array}\right]=\left[\begin{array}{lll}-1& 0& 0\\ 0& 1& 0\\ 0& 0& -1\end{array}\right],}$

   where $𝑪$ is the reflection across the $x_2$ axis.

5. Prove that the inverse of a rank-1 perturbation of $𝑰$ is itself a rank-1 perturbation of $𝑰$, namely

   ${\displaystyle {(𝑰+𝒖{𝒗}^{\ast })}^{-1}=𝑰+\theta 𝒖{𝒗}^{\ast }.}$

   Determine the scalar $\theta$.

   Solution. Assume $𝒖,𝒗\ne 𝟎$. By definition of an inverse

   ${\displaystyle 𝑰=(𝑰+𝒖{𝒗}^{\ast }){(𝑰+𝒖{𝒗}^{\ast })}^{-1}=(𝑰+𝒖{𝒗}^{\ast })(𝑰+\theta 𝒖{𝒗}^{\ast })=𝑰+(\theta +1)𝒖{𝒗}^{\ast }+\theta 𝒖{𝒗}^{\ast }𝒖{𝒗}^{\ast }\Rightarrow }$

   ${\displaystyle (\theta +1)𝒖{𝒗}^{\ast }+\theta 𝒖{𝒗}^{\ast }𝒖{𝒗}^{\ast }=𝟎.}$

   Note that in $𝒖{𝒗}^{\ast }𝒖{𝒗}^{\ast }$ the product ${𝒗}^{\ast }𝒖$ is a scalar, hence $𝒖{𝒗}^{\ast }𝒖{𝒗}^{\ast }=\left({𝒗}^{\ast }𝒖\right)𝒖{𝒗}^{\ast }$, and the above matrix equality becomes

   ${\displaystyle [\theta +1+\theta {𝒗}^{\ast }𝒖]𝒖{𝒗}^{\ast }=𝟎.}$

   For the above to be true for any $𝒖,𝒗$ choose $\theta$ such that

   ${\displaystyle \theta +1+\theta {𝒗}^{\ast }𝒖=0\Rightarrow \theta =-\frac{1}{1+{𝒗}^{\ast }𝒖},}$

   if ${𝒗}^{\ast }𝒖\ne -1$. When would ${𝒗}^{\ast }𝒖=-1$? An example is $-{𝒆}_k^T{𝒆}_k$ in which case

   ${\displaystyle 𝑰-{𝒆}_k^T{𝒆}_k}$

   has a $k^{\mathrm{th}}$ column of zeros and is therefore singular.

6. Determine the rank of $𝑩={𝑨}^{-1}𝒖{𝒗}^{\ast }$.

   Solution. The inverse ${𝑨}^{-1}$ exists only if $𝑨$ is square, $𝑨\in {ℂ}^{m\times m}$ and of full rank, hence $\mathrm{rank}\left({𝑨}^{-1}\right)=m$. What is ${𝑨}^{-1}𝒖{𝒗}^{\ast }$? Recall that a matrix-vector product $𝑪𝒘$ is a linear combination of the columns of $𝑪$, and the matrix-matrix product $𝑪𝑫$ is simply a collection of matrix vector products

   ${\displaystyle 𝑪𝑫=𝑪\left[\begin{array}{llll}{𝒅}_1& {𝒅}_2& \dots & {𝒅}_n\end{array}\right]=\left[\begin{array}{llll}𝑪{𝒅}_1& 𝑪{𝒅}_2& \dots & 𝑪{𝒅}_n\end{array}\right].}$

   Now $𝑫=𝒖{𝒗}^{\ast }$ is of rank one, $\mathrm{rank}(𝒖{𝒗}^{\ast })=1$ with colinear columns

   ${\displaystyle 𝑫=\left[\begin{array}{llll}{\bar{v}}_1𝒖& {\bar{v}}_2𝒖& \dots & {\bar{v}}_n𝒖\end{array}\right].}$

   Multiplying with $𝑪$ gives

   ${\displaystyle 𝑪𝑫=\left[\begin{array}{llll}{\bar{v}}_1𝑪𝒖& {\bar{v}}_2𝑪𝒖& \dots & {\bar{v}}_n𝑪𝒖\end{array}\right],}$

   again with colinear columns such that $\mathrm{rank}(𝑪𝑫)=1$. Deduce that $\mathrm{rank}\left(𝑩\right)=\mathrm{rank}({𝑨}^{-1}𝒖{𝒗}^{\ast })=1$.

7. Write the inverse ${(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })}^{-1}$ as a rank-1 perturbation of $𝑰$.

   Solution. Since ${𝑨}^{-1}𝒖{𝒗}^{\ast }=𝒘{𝒗}^{\ast }$ is of rank one with $𝒘={𝑨}^{-1}𝒖$, use

   ${\displaystyle {(𝑰+𝒘{𝒗}^{\ast })}^{-1}=𝑰-\frac{𝒘{𝒗}^{\ast }}{1+{𝒗}^{\ast }𝒘},}$

   to obtain

   ${\displaystyle {(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })}^{-1}=𝑰-\frac{{𝑨}^{-1}𝒖{𝒗}^{\ast }}{1+{𝒗}^{\ast }{𝑨}^{-1}𝒖}.}$

8. Consider $𝑪=𝑨+𝒖{𝒗}^{\ast }=𝑨(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })$. Write ${𝑪}^{-1}$ as a rank-1 perturbation of ${𝑨}^{-1}$.

   Solution. Apply above results

   ${\displaystyle {𝑪}^{-1}={\left[𝑨(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })\right]}^{-1}={(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })}^{-1}{𝑨}^{-1}=(𝑰-\frac{{𝑨}^{-1}𝒖{𝒗}^{\ast }}{1+{𝒗}^{\ast }{𝑨}^{-1}𝒖}){𝑨}^{-1}={𝑨}^{-1}-\frac{{𝑨}^{-1}𝒖{𝒗}^{\ast }{𝑨}^{-1}}{1+{𝒗}^{\ast }{𝑨}^{-1}𝒖}}$

2Track 2

1. For $𝒙\in {ℝ}^m$, prove ${||𝒙||}_{\infty }⩽{||𝒙||}_2$.

   Solution. By definition

   ${\displaystyle {||𝒙||}_{\infty }={max}_i\left|x_i\right|=\left|x_k\right|,}$

   with $k$ the index of the (not necessarily unique) maximal element. Then

   ${\displaystyle {||𝒙||}_2={(x_k^2+\sum _{j=1,j\ne k}^m{x}_j^2)}^{1/2}={(x_k^2+a)}^{1/2}⩾x_k,}$

   since $a⩾0$.

2. For $𝒙\in {ℝ}^m$, prove ${||𝒙||}_2⩽\sqrt{m}{||𝒙||}_{\infty }$.

   Solution. With above notations, $\left|x_j\right|⩽\left|x_k\right|$, hence

   ${\displaystyle {||𝒙||}_2={\left(\sum _{j=1}^m{x}_j^2\right)}^{1/2}⩽{(m{x}_k^2)}^{1/2}=\sqrt{m}{||𝒙||}_{\infty }.}$

3. For $𝑨\in {ℝ}^{m\times n}$, prove ${||𝑨||}_{\infty }⩽\sqrt{n}{||𝑨||}_2$.

   Solution. By definition

   ${\displaystyle {||𝑨||}_{\infty }={sup}_{{||𝒙||}_{\infty }=1}{||𝑨𝒙||}_{\infty }.}$

   For $𝒚=𝑨𝒙\in {ℝ}^m$ apply above results (1. and 2.) and $||𝑨𝑩||⩽||𝑨||||𝑩||$ to obtain

   ${\displaystyle {||𝑨𝒙||}_{\infty }={||𝒚||}_{\infty }⩽{||𝒚||}_2={||𝑨𝒙||}_2⩽{||𝑨||}_2{||{𝒙}_{}||}_2⩽\sqrt{n}{||𝑨||}_2{||𝒙||}_{\infty },}$

   and establish the bound

   ${\displaystyle \frac{{||𝑨𝒙||}_{\infty }}{{||𝒙||}_{\infty }}⩽\sqrt{n}{||𝑨||}_2}$

   for any $𝒙$, with the upper bound of the left hand side being ${||𝑨||}_{\infty }$, hence

   ${\displaystyle {||𝑨||}_{\infty }⩽\sqrt{n}{||𝑨||}_2.}$

4. For $𝑨\in {ℝ}^{m\times n}$, prove ${||𝑨||}_2⩽\sqrt{m}{||𝑨||}_{\infty }$.

   Solution. For $𝒚=𝑨𝒙\in {ℝ}^m$ apply above results (1. and 2.)

   ${\displaystyle \frac{{||𝑨𝒙||}_2}{{||𝒙||}_2}⩽\frac{\sqrt{m}{||𝑨𝒙||}_{\infty }}{{||𝒙||}_2}⩽\frac{\sqrt{m}{||𝑨𝒙||}_{\infty }}{{||𝒙||}_{\infty }}⩽\sqrt{m}{||𝑨||}_{\infty },}$

   for all $𝒙$ including the one for which ${||𝑨||}_2$ is attained, hence ${||𝑨||}_2⩽\sqrt{m}{||𝑨||}_{\infty }$.

5. Prove the Minkowski inequality: for $p⩾1$, $𝒙,𝒚\in {ℝ}^m$, ${||𝒙+𝒚||}_p⩽{||𝒙||}_p+{||𝒚||}_p$.

   Solution. The Minkowski inequality results from the Hölder inequality, for $1/p+1/q$=1,

   ${\displaystyle \sum _{i=1}^m|x_i{y}_i|⩽{\left(\sum _{i=1}^m{\left|x_i\right|}^p\right)}^{1/p}{\left(\sum _{i=1}^m{\left|y_i\right|}^q\right)}^{1/q}}$

   for $q=p/p-1$.

6. Construct the matrix $𝑫$ that represents the mapping $𝒇:{ℝ}^3\to {ℝ}^3$, $𝒇$ rotates a vector around the $x_3$ axis by angle $\theta$. Construct the matrix $𝑬$ that represents the mapping $𝒇:{ℝ}^3\to {ℝ}^3$, $𝒇$ rotates a vector around the $x_2$ axis by angle $\phi$.

   Solution.

   ${\displaystyle 𝑫=\left[\begin{array}{l}\cos \theta \\ \sin \theta \\ 0\end{array}\begin{array}{l}-\sin \theta \\ \cos \theta \\ 0\end{array}\begin{array}{l}0\\ 0\\ 1\end{array}\right],𝑬=\left[\begin{array}{lll}\cos \phi & 0& -\sin \phi \\ 0& 1& 0\\ \sin \phi & 0& \cos \phi \end{array}\right]}$

7. What do $𝑫𝑬$ and $𝑬𝑫$ represent?

   Solution. Composite rotation in different order, $𝑫𝑬$ first around $x_2$ then around $x_3$, $𝑬𝑫$ first around $x_3$ then around $x_2.$

8. Is $𝑫𝑬=𝑬𝑫$ true? Explain.

   Solution. No, this is an example of non-commutative matrix multiplication. Counter-example $\theta =\phi =\pi /2$, and

   ${\displaystyle 𝑫𝑬{𝒆}_2=\left[\begin{array}{l}-1\\ 0\\ 0\end{array}\right]\ne \left[\begin{array}{l}0\\ 0\\ -1\end{array}\right]=𝑬𝑫{𝒆}_2.}$