Numerical Analysis - January 2026

Please do each of the following problems, providing concise answers with justification. The total number of points is 100.

Problem 1

(15 points) Let $P\in {ℂ}^{m\times m}$ be a nonzero projector. Show that $\parallel P{\parallel }_2\ge 1$.

Problem 2

(15 points) Let $A$ be an $n\times n$ matrix with $\parallel A\parallel <1$, where $\parallel \cdot \parallel$ is an induced matrix norm.

1. Show that the matrix $I+A$ is nonsingular.

2. Show that

$$\parallel {(I+A)}^{-1}\parallel \le \frac{1}{1-\parallel A\parallel }.$$

Problem 3

(15 points) Let $A\in {ℂ}^{m\times n}$, $m\ge n$, with linearly independent columns:

$$A=[a_1,\cdots ,a_n].$$

What are the eigenvalues and eigenvectors of the projection matrix

$$P=I-A{\left(A^{*}A\right)}^{-1}{A}^{*}?$$

Problem 4

(10 points) Suppose $A$ is an invertible $202\times 202$ matrix with $\parallel A{\parallel }_2=100$ and $\parallel A{\parallel }_F=101$. Give the sharpest possible lower bound on the 2-norm condition number $\kappa \left(A\right)$.

Problem 5

(15 points) Prove Gershgorin’s Disk Theorem:

Let $A\in {ℂ}^{m\times m}$ with entries $\{a_{ij}\}$. Let $r_i={\sum }_{j\ne i}\left|a_{ij}\right|$. Let $D_i$ be the closed disk in the complex plane centered at $a_{ii}$ with radius $r_i$.

Prove that if $\lambda$ is an eigenvalue of $A$, then

$$\lambda \in \bigcup _i{D}_i.$$

In other words, prove that every eigenvalue lies within at least one of the disks $D_i$.

Problem 6

(15 points) Let

$$B=\left(\begin{array}{ccc}\hfill 3\hfill & \hfill -6\hfill & \hfill 41/5\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 4\hfill & \hfill -8\hfill & \hfill 63/5\hfill \end{array}\right).$$

1. Find the QR decomposition of $B$ using the Gram-Schmidt orthogonalization process.

2. Write down the unitary Householder reflector matrix that you should multiply against $B$ in order to zero out all but the first entry of its first column.

Problem 7

(15 points) Let $x_j\in {ℝ}^m$ be the j-th column of $X\in {ℝ}^{m\times n}$ be given. Let $y\in {ℝ}^m$ and $\lambda >0$ also be given. Given a vector $w\in {ℝ}^n$, define the following function

$$J\left(w\right)=\parallel Xw-y{\parallel }_2^2+\lambda \parallel w{\parallel }_1,$$

where $\parallel \cdot {\parallel }_2$ and $\parallel \cdot {\parallel }_1$ denote the 2- and 1-norm in ${ℝ}^n$, respectively. Letting the i-th component $w_i$ of $w$ vary and the other components of $w$ be fixed, consider the following one-variable minimization problem reduced from $J\left(w\right)$:

$$\begin{array}{cc}\hfill \underset{w_i}{min}f\left(w_i\right)& \equiv \underset{w_i}{min}{\parallel \sum _{j=1}^n{w}_j{x}_j-y\parallel }_2^2+\lambda \left|w_i\right|+\lambda \sum _{j\ne i}\left|w_j\right|\hfill \\ \hfill & =\underset{w_i}{min}\parallel w_i{x}_i+r{\parallel }_2^2+\lambda \left|w_i\right|+C\hfill \\ \hfill & =\underset{w_i}{min}\sum _{j=1}^m{(w_i{x}_{ji}+r_j)}^2+\lambda \left|w_i\right|+C.\hfill \end{array}$$

where $r\equiv {\sum }_{j\ne i}{w}_j{x}_j-y$ is in ${ℝ}^m$ with $r={\left(r_k\right)}_{m\times 1}$, and $C=\lambda {\sum }_{j\ne i}\left|w_j\right|$. Show that the optimal solution $w_i^{*}$ is given by

$$w_i^{*}=\{\begin{array}{cc}0\hfill & \mathrm{\text{if}}\left|a\right|\le \lambda ,\hfill \\ \frac{-\lambda +a}{b}\hfill & \mathrm{\text{if}}\frac{-\lambda +a}{b}>0,\hfill \\ \frac{\lambda +a}{b}\hfill & \mathrm{\text{if}}\frac{\lambda +a}{b}<0,\hfill \end{array}$$

where $a=-{\sum }_{j=1}^{m}2x_{ji}{r}_j$ and $b={\sum }_{j=1}^{m}2x_{ji}^2$.