Posted: 08/30/21

Due: 09/08/21, 11:55PM

1Track 1

1. Implement the classical and modified Gram-Schmidt algorithms to compute $𝑸𝑹=\mathrm{qr}\left(𝑨\right)$. Test orthogonality of $𝑸$ for $𝑨=\mathrm{randn}(m,m)$, $m=20k$, $k=1,2,\dots ,5$.

   $•$Solution.

2. Generate point clouds that conform to two columns of your choice from Fig. 1. Compute the associated correlation matrix $𝑪$ and superimpose on the plots the columns of $𝑸$ from the orthogonal decomposition $𝑪=𝑸𝑹$ obtained through the modified Gram-Schmidt algorithm

   Figure 1. Point clouds with associated Pearson correlation coefficients. See Wikipedia: Correlation

   $•$Solution.

3. Construct families of curves equidistant from the $x_1=0$ and $x_2=0$ axes in the plane using the $𝑨-$norm

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

   with $𝑨\in {ℝ}^{2\times 2}$ of full rank of your choice that is not diagonal.

   $\circ$Solution.

   This problem is an invitation to study implications of choice of functionals that define magnitude (norms) and orientation (scalar product, i.e, $(𝒙,𝒚)={𝒙}^T{𝑨}^T𝑨𝒚$), see L05: Fig. 2-3.

   First start with $𝑨=𝑰$ to gain insight, in which case the Euclidean norm

   ${\displaystyle {||𝒙||}^2=x_1^2+x_2^2,}$

   and standard inner product

   ${\displaystyle (𝒙,𝒚)=x_1{y}_1+x_2{y}_2,}$

   are obtained. The curves equidistant from the $x_2=0$ axis are given by $x_2=C$. How are these obtained? Consider a point on the $x_1$-axis (i.e., with $x_2=0$) that has position vector

   ${\displaystyle 𝒓\left(s\right)=\left[\begin{array}{l}s\\ 0\end{array}\right].}$

   Points at distance $C$ from $𝒓\left(s\right)$ are on the circle

   ${\displaystyle {(x_1-s)}^2+x_2^2=C^2.}$

   Variation of $s\in ℝ$ gives a family or circles.

   ∴	function circle(xC,yC,r) θ=2*π*(0:36)/36.0; x=r*cos.(θ).+xC; y=r*sin.(θ).+yC; plot(x,y,"-b"); axis("equal"); end;

   ∴	figure(1); clf(); circle.(-5:5,0,1); grid("on"); xlabel("x"); ylabel("y"); title("Equidistant curves are envelopes"); plot([-6; 6],[1; 1],"-r"); plot([-6; 6],[-1; -1],"-r");

   ∴

   Figure 2. Curves equidistant from the $x_1$-axis in the Euclidean norm are straight lines, and envelopes of circles centerd on the $x_1$-axis.

   Having gained insight from a familiar example, consider what changes when $𝑨\ne 𝑰$. The squared distance from $𝒓\left(s\right)$ on the $x_1$-axis and some point $𝒙\in {ℝ}^2$ is

   ${\displaystyle d^2(s,t)={𝒚}^T{𝑨}^T𝑨𝒚,}$

   with

   ${\displaystyle 𝒚\left(s\right)=𝒓\left(s\right)-𝒙.}$

   Evaluate using

   ${\displaystyle 𝑨=𝑼𝚺{𝑽}^T,𝚺=\left[\begin{array}{ll}{\sigma }_1& 0\\ 0& {\sigma }_2\end{array}\right],{\sigma }_1⩾{\sigma }_2>0}$

   the SVD of $𝑨$ of full rank,

   ${\displaystyle d^2(s,t)={𝒚}^T𝑽{𝚺}^T𝚺{𝑽}^T𝒚={𝒛}^T𝑫𝒛,}$

   with

   ${\displaystyle 𝒛={𝑽}^T𝒚={𝑽}^T(𝒓\left(s\right)-𝒙),𝑫={𝚺}^T𝚺=\left[\begin{array}{ll}{\sigma }_1^2& 0\\ 0& {\sigma }_2^2\end{array}\right].}$

   Note that a distance of zero implies $𝒛=𝟎\Rightarrow 𝒙=𝒓\left(s\right)$, i.e., the image of the $x_1$-axis is the $z_1$-axis. In the $z_1{z}_2$ plane points at distance $C$ from the $z_1$ axis are ellipses of semiaxes $1/\left(C{\sigma }_{{}_1}\right)$, $1/\left(C{\sigma }_{{}_2}\right)$.

   ${\displaystyle {(z_1{\sigma }_1)}^2+{(z_2{\sigma }_2)}^2=C^2.}$

   The images of theses ellipse in the $x_1{x}_2$-plane are given by

   ${\displaystyle 𝒙=𝒓-𝑽𝒛,}$

   and be graphically represented for various values of $C$. The envelopes of these ellipse images are the sought equidistant curves.

   Track 1 extra credit (T1EC1, 3 points). Derive an analytical parametric form for the equidistant curves, and plot them. Recall that for some point $𝒙\left(t\right)$ on curve $\Gamma$ the $𝑨$-norm distance to the $x_1$-axis is defined by

   ${\displaystyle {min}_{u\in ℝ}d(u,t),}$

   and is attained at

   ${\displaystyle s={\mathrm{argmin}}_{u\in ℝ}d(u,t)={\mathrm{argmin}}_{u\in ℝ}{d}^2(u,t).}$

2Track 2

1. Prove the Hölder inequality: for $p,q>1$, $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}.}$

   $•$Solution. Proofs of the Hölder inequality can use approaches from elementary algebra, analysis, or measure theory. However, the interest here is interpreting the Hölder inequality in the context of linear algebra. Study the following solution carefully to see how an operator was identified, represented by a matrix, and then the tools introduced to measure the magnitude of vectors and matrices (i.e., norms) were used to establish the Hölder inequality. Compare with your submitted solution, and establish links between the fields of mathematics used in your proof to the linear algebra proof presented here.

   Introduce vectors $𝒙,𝒚\in {ℝ}^m$, and matrices $𝑿,𝒀\in {ℝ}^{m\times m}$ defined as

   ${\displaystyle 𝑿=\mathrm{diag}\left(𝒙\right)=\left[\begin{array}{llll}{x}_1& 0& \dots & 0\\ 0& x_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & x_n\end{array}\right],𝒀=\mathrm{diag}\left(𝒚\right)=\left[\begin{array}{llll}{y}_1& 0& \dots & 0\\ 0& y_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & y_n\end{array}\right].}$

   Notice that $𝒛=𝑿𝒚=𝒀𝒙\in {ℝ}^m$, is a vector with components $z_i=x_i{y}_i$. The Hölder inequality can now be stated in matrix-vector form as

   ${\displaystyle {||𝑿𝒚||}_1⩽{||𝒙||}_p{||𝒚||}_q.}$

   The inequality is true for either $𝒙=𝟎$, or $𝒚=𝟎$. For the remaining case of ${||𝒙||}_p\ne 0$, ${||𝒚||}_q\ne 0$, rescale vectors such that ${||𝒙||}_p={||𝒚||}_q=1$, and restate Hölder inequality,

   ${\displaystyle {||𝑿𝒚||}_1⩽1.}$

   Use the matrix norm property ${||𝑿𝒚||}_1⩽{||𝑿||}_1{||𝒚||}_1$. The one-norm of a matrix is the largest of the one-norms of its columns (e.g., Trefethen & Bau, p.21), and since the columns of $𝑿$ contain a single non-zero entry

   ${\displaystyle {||𝑿||}_1={max}_i\left|x_i\right|⩽1,}$

   since, otherwise, if $\left|x_i\right|>1$ then ${||𝒙||}_p>1$, contradiction. This leads to

   ${\displaystyle {||𝑿𝒚||}_1⩽{||𝒚||}_1.}$

   Recall the graphical representation of unit-circles in various vector norms, ${||𝒖||}_p=1,𝒖\in {ℝ}^2$. This is readily constructed by drawing an arc in the first quadrant, that is subsequently rotated by $\frac{\pi }{2},\pi ,\frac{3\pi }{2}$ .

   ∴	function arc(p,m) u1 = LinRange(0,1,m); u2 = (1 .- u1.^p).^(1.0/p) return [u1 u2]' end;

   ∴	function R(θ) [cos(θ) -sin(θ); sin(θ) cos(θ)] end;

   ∴	clf(); m=90; c=["k" "b" "g" "r"]; axis("equal"); title("Unit circle in various p-norms");

   ∴	for p=1:4 X=[R(0); R(π/2); R(π); R(3*π/2)]*arc(p,m); for i=1:2:7 plot(X[i,:],X[i+1,:],c[p]) end end

   ∴	prefix = homedir()*"/courses/MATH661/images/";

   ∴	savefig(prefix*"H02T2P1.eps");

   ∴

   Figure 3. Visual data suggesting that for $𝒖\in {ℝ}^2$, ${||𝒖||}_1⩾{||𝒖||}_2⩾{||𝒖||}_3⩾\dots ⩾{||𝒖||}_{\infty }$

2. Prove the Minkowski inequality: for $p⩾1$,

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

   $•$Solution.

3. Prove the parallelogram identity

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

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

   $•$Solution.

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

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

   is a norm.

   $•$Solution.

5. Compute the components of the saw-tooth function $f\left(t\right)=f(t+2\pi )$, $f\left(t\right)=t$ for $-\pi <t<\pi$, on the Fourier basis set

   ${\displaystyle \{\frac{1}{\sqrt{2\pi }},\frac{\cos t}{\sqrt{\pi }},\frac{\sin t}{\sqrt{\pi }},\dots ,\frac{\cos kt}{\sqrt{\pi }},\frac{\sin kt}{\sqrt{\pi }},\dots ,\frac{\cos nt}{\sqrt{\pi }},\frac{\sin nt}{\sqrt{\pi }}\},}$

   for $n=4^p$, $p=2,3,4,5$. Superimpose a plot of the approximants with the saw-tooth function. Solve any linear system or least squares problems that arise by $𝑸𝑹$ decomposition. Comment on the plot.

   $•$Solution.

6. Construct visual representations of the Hadamard matrices ${𝑯}_m$, $m=4k+4$, $k\in \{0,1,2,\dots ,7\}$. Construct visual representations of $C\left({𝑯}_m\right)$, $N\left({𝑯}_m^{{}^T}\right)$, $C\left({𝑯}_m^T\right)$, $N\left({𝑯}_m\right)$ through the $𝑸𝑹$-decomposition of ${𝑯}_m$.

   $•$Solution.