MATH662: Numerical linear algebraJanuary 16, 2019

Due date: Jan 30, 2019, 11:55PM.

Bibliography: Trefethen & Bau, Lectures 1-8. Problems 1-4 = 1 pt each, Problem 5 = 4 points.

1. Exercises 2.3, 2.4, 2.5

   2.3

   $A\in {ℂ}^{m\times m}$, $A=A^{\ast }$, $Ax=\lambda x$, $A^{\ast }x=\lambda x$, $x\ne 0$.

   1. $\lambda \in ℝ$. Proof: From $Ax=\lambda x$, take adjoint $x^{\ast }{A}^{\ast }=x^{\ast }A=\bar{\lambda }{x}^{\ast }$. Multiple by $x,x^{\ast }$ (non-zero)

      ${\displaystyle \begin{array}{lll}Ax=\lambda x& \Rightarrow & x^{\ast }Ax=\lambda x^{\ast }x\\ x^{\ast }A=\bar{\lambda }{x}^{\ast }& \Rightarrow & x^{\ast }Ax=\bar{\lambda }{x}^{\ast }x\end{array}\Rightarrow 0=(\lambda -\bar{\lambda })x^{\ast }x=0\Rightarrow \lambda =\bar{\lambda }\Rightarrow \lambda \in ℝ.}$

   2. $Ax=\lambda x,Ay=\mu y,\lambda \ne \mu$, $\lambda ,\mu \in ℝ$

      ${\displaystyle \begin{array}{lll}Ax=\lambda x& \Rightarrow & y^{\ast }Ax=\lambda y^{\ast }x\\ y^{\ast }A=\mu y^{\ast }& \Rightarrow & y^{\ast }Ax=\mu y^{\ast }x\end{array}\Rightarrow 0=(\lambda -\mu )y^{\ast }x=0\Rightarrow y^{\ast }x=0\Rightarrow x\perp y.}$

   2.4

   $A\in {ℂ}^{m\times m}$, $A{A}^{\ast }=A^{\ast }A=I$. Take adjoint of eigenvalue relation $AV=\Lambda V$ to obtain $V^{\ast }{A}^{\ast }=V^{\ast }{\Lambda }^{\ast }$. Multiply the two equations to obtain $V^{\ast }{A}^{\ast }AV=V^{\ast }{\Lambda }^{\ast }\Lambda V\Rightarrow V^{\ast }{\left|\Lambda \right|}^{2}V=V^{\ast }V$, hence eigenvalues satisfy ${\left|{\lambda }_i\right|}^2=1$, i.e., lie on the unit circle.

   octave:

   A=randn(100); [Q,R]=qr(A); L=eig(Q);

   octave:

   cd('/home/student/courses/MATH662')

   octave:

   data = [real(L) imag(L)];

   octave:

   save -ascii hw1fig1.data data

   octave:

   [min(abs(L)) max(abs(L))]

   ans =

   
      1.00000   1.00000

   octave:

   GNUplot]

   cd '/home/student/courses/MATH662'; set xlabel 're(\lambda)'; set ylabel 'im(\lambda)'; set grid; set size square; plot 'hw1fig1.data' using 1:2 w p

   

   GNUplot]

   2.5

   $S\in {ℂ}^{m\times m},S^{\ast }=-S$

   1. As in 2.3

      ${\displaystyle \begin{array}{lll}Ax=\lambda x& \Rightarrow & x^{\ast }Ax=\lambda x^{\ast }x\\ -x^{\ast }A=\bar{\lambda }{x}^{\ast }& \Rightarrow & -x^{\ast }Ax=\bar{\lambda }{x}^{\ast }x\end{array}\Rightarrow 0=(\lambda +\bar{\lambda })x^{\ast }x=0\Rightarrow \lambda =-\bar{\lambda }\Rightarrow \lambda =i\alpha ,\alpha \in ℝ.}$

   2. This is a matrix generalization of $|1+i\alpha |>0$ for any $\alpha \in ℝ$. Recall that $A$ singular is equivalent to $A$ having a zero eigenvalue. Ask: can $\mu =0$ be an eigenvalue of $I-S$? If so $(I-S)x=\mu x=0\Rightarrow Sx=1\cdot x$, implying $1\in ℝ$ is an eigenvalue of $S$, contradicting finding from (a). Or, consider $x$ to be an eigenvector of $S$, $Sx=i\alpha x$, and compute

      ${\displaystyle (I-S)x=x-i\alpha x=(1-i\alpha )x,}$

      hence $1-i\alpha$ is an eigenvalue of $I-S$, and $|1-i\alpha |=\sqrt{1+{\alpha }^2}>0$. Note that the above also implies

      ${\displaystyle {(I-S)}^{-1}x=\frac{1}{1-i\alpha }x,}$

      hence ${(1-i\alpha )}^{-1}$ is an eigenvalue of ${(I-S)}^{-1}$.

   3. Per (2.4) eigenvalues of a unitary matrix lie on the unit circle. As above, let $x$ be an eigenvector of $S$, $Sx=i\alpha x$,

      ${\displaystyle Qx={(I-S)}^{-1}(I+S)x={(I-S)}^{-1}(1+i\alpha )x=(1+i\alpha ){(I-S)}^{-1}x=\frac{1+i\alpha }{1-i\alpha }x=\mu x,}$

      and $\left|\mu \right|=|1+i\alpha |/|1-i\alpha |=1$, hence $Q$ unitary.

2. Exercises 3.1-3.6

   3.1

   $W\in {ℂ}^{m\times m}$ nonsingular, ${||x||}_W=||Wx||$. Prove norm properties:

   1. ${||x||}_W⩾0$ results from $||Wx||⩾0$. Consider ${||x||}_W=0$, or $||Wx||=0\Rightarrow Wx=0$. Since $W$ nonsingular cannot have a zero eigenvalue, it results that $x=0$.

   2. ${||x+y||}_W=||Wx+Wy||⩽||Wx||+||Wy||={||x||}_W+{||y||}_W$

   3. ${||\alpha x||}_W=||\alpha Wx||=\left|\alpha \right|||Wx||=\left|\alpha \right|{||x||}_W$.

   3.2

   Write eigenvalue relation for $A\in {ℂ}^{m\times m}$, $A{x}_i={\lambda }_i{x}_i$, and $||A{x}_i||=\left|{\lambda }_i\right|||x_i||$. By definition of induced norm

   ${\displaystyle ||A||={sup}_{x\in {ℂ}^m,x\ne 0}\frac{||Ax||}{||x||}⩾{max}_i\left|{\lambda }_i\right|=\rho \left(A\right).}$

   3.3

   1. ${||x||}_{\infty }={max}_i\left|x_i\right|⩽{(x_1^2+\cdots +x_m^2)}^{1/2}={||x||}_2$. Equality attained for $x=e_i$, inequality for $x=e_1+e_2$.

   2. ${||x||}_2={(x_1^2+\cdots +x_m^2)}^{1/2}⩽{max}_i\left|x_i\right|\sqrt{m}=\sqrt{m}{||x||}_{\infty }$. Equality for $x=(1,1,\dots ,1)$, inequality for $x=e_i$.

   3. From (a) ${||Ax||}_{\infty }⩽{||Ax||}_2$, and from (b) $1/{||x||}_{\infty }⩽\sqrt{n}/{||x||}_2$, combine to obtain

      ${\displaystyle \frac{{||Ax||}_{\infty }}{{||x||}_{\infty }}⩽\sqrt{n}\frac{{||Ax||}_2}{{||x||}_2}}$

3. Exercise 5.4. State and solve the analogous problem for skew-symmetric matrices.

4. Exercises 6.1-3, 6.5

5. Consider a black and white image represented as a matrix $A\in {\{0,1\}}^{32\times 256}$. In each $32\times 32$ block set element values to represent a letter of the words: “absolute”, “computer”, “measures”.

   Read in an image

   octave>

   chdir('/home/student/courses/MATH662')

   /home/student/courses/MATH662

   octave>

   load('b.mat');

   octave>

   [U,S,V]=svd(B);

   'Expression1' undefined near line 1 column 7

   octave>

   1. Guess the rank of the matrices. Then, compute the rank of the matrices.

   2. Obtain a sequence of approximations $A_{\nu }$ for $\nu =2^p$, $p=2,3,4,5$, with $A_{\nu }$ the successive approximations from truncation of the SVD rank-1 expansions.

   3. Consider $B(x_1,x_2,x_3)=x_1{A}_1+x_2{A}_2+x_3{A}_3,$ with $x_1+x_2+x_3=1$. Repeat (b) for $x_1,x_2,x_3$ by sampling points within the tetrahedron. Comment.

   4. Consider $H\left(\xi \right)=A_1+\xi (A_2-A_1)$. Repeat (b) for $\xi \in (0,1)$. Comment.