5.6: Exercises

Exercise 5.1

Suppose the complex \(m \times n\) matrix \(A\) is perturbed to the matrix \(A + E\).

(a) Show that

\[\left|\sigma_{\max }(A+E)-\sigma_{\max }(A)\right| \leq \sigma_{\max }\tag{E}\]

Also find an \(E\) that results in the inequality being achieved with equality.

(Hint: To show the inequality, write \((A + E) = A + E\) and \(A = (A + E) - E\), take the 2-norm on both sides of each equation, and use the triangle inequality.)

It turns out that the result in (a) actually applies to all the singular values of \(A\) and \(A + E\), not just the largest one. Part (b) below is one version of the result for the smallest singular value.

(b) Suppose A has less than full column rank, i.e. has rank \(< n\), but \(A + E\) has full column rank. Show (following a procedure similar to part (a) - but looking at \(min \|(A+E)x\|_{2}\) rather than the norm of \(A + E\), etc.) that

\[\sigma_{\min }(A+E) \leq \sigma_{\max }\tag{E}\]

Again find an \(E\) that results in the inequality being achieved with equality.

[The result in (b), and some extensions of it, give rise to the following sound (and widely used) procedure for estimating the rank of some underlying matrix \(A\), given only the matrix \(A + E\) and knowledge of \(\|E\|_{2}\): Compute the SVD of \(A + E\), then declare the "numerical rank" of \(A\) to be the number of singular values of \(A + E\) that are larger than the threshold \(\|E\|_{2}\). The given information is consistent with having an \(A\) of this rank.]

(c) Verify the above results using your own examples in MATLAB. You might also find it interesting to verify numerically that for large \(m, n\), the norm of the matrix \(E = s * randn(m, n)\) - which is a matrix whose entries are independent, zero-mean, Gaussian, with standard deviation \(s\) - is close to \(s *(\sqrt{m}+\sqrt{n})\). So if \(A\) is perturbed by such a matrix, then a reasonable value to use as a threshold when determining the numerical rank of \(A\) is this number.

Exercise 5.2

Let \(A\) and \(E\) be \(m \times n\) matrices. Show that

\[\min _{\operatorname{rank} E \leq r}\|A-E\|_{2}=\sigma_{r+1}\tag{A}\]

To prove this, notice that the rank constraint on \(E\) can be interpreted as follows: If \(v_{1},. . . v_{r+1}\) are linearly independent vectors, then there exists a nonzero vector \(z\), expressed as a linear combination of such vectors, that belongs to the nullspace of \(E\). Proceed as follows:

1. Select the \(v_{i}\)'s from the SVD of A.
2. Select a candidate element \(z\) with \(\|z\|_{2} = 1\).
3. Show that \(\|(A - E)z\|_{2} \geq \sigma_{r+1}\). This implies that \(\|(A - E)\|_{2} \geq \sigma_{r+1}\).
4. Construct an \(E\) that achieves the above bound.

Exercise 5.3

Consider the real, square system of equations \(Ax = (U \Sigma V^{T})x = y\), where \(U\) and \(V\) are orthogonal matrices, with

\[\Sigma=\left(\begin{array}{cc}
1 & 0 \\
0 & 10^{-6}
\end{array}\right), \quad y=U\left(\begin{array}{c}
1 \\
10^{-6}
\end{array}\right)\nonumber\]

All norms in this problem are taken to be 2-norms.

(a) What is the norm of the exact solution \(x\)?

(b) Suppose \(y\) is perturbed to \(y + \delta y\), and that correspondingly the solution changes from \(x\) in (a) to \(x + \delta x\). Find a perturbation \(\delta y\), with \(\|\delta y\|= 10^{-6}\), such that

\[\frac{\|\delta x\|}{\|x\|} \approx \kappa(A) \frac{\|\delta y\|}{\|y\|}\nonumber\]

where \(\kappa (A)\) is the condition number of \(A\).

(c) Suppose instead of perturbing \(y\) we perturb \(A\), changing it to \(A + \delta A\), with the solution correspondingly changing from \(x\) to \(x + \delta x\) (for some \(\delta x\) that is different than in part (b) ). Find a perturbation \(\delta A\), with \(\|\delta A\|= 10^{-7}\), such that

\[\frac{\|\delta x\|}{\|x\|} \approx \kappa(A) \frac{\|\delta A\|}{\|A\|}\nonumber\]

Exercise 5.4 Positive Definite Matrices

A matrix \(A\) is positive semi-definite if \(x^{\prime}Ax \geq 0\) for all \(x \neq 0\). We say \(Y\) is the square root of a Hermitian positive semi-definite matrix if \(Y^{\prime}Y = A\). Show that \(Y\) always exists and can be constructed from the SVD of \(A\).

Exercise 5.5

Let \(A\) and \(B\) have compatible dimensions. Show that if

\[$\|A x\|_{2} \leq\|B x\|_{2}$
for all $x$\nonumber\]

then there exists a matrix \(Y\) with \(\|Y\|_{2} \leq 1\) such that

\[A=YB\nonumber\]

Assume \(B\) has full rank to simplicity.

Exercise 5.6

(a) Suppose

\[\left\|\left(\begin{array}{cc}
X \\
A
\end{array}\right)\right\| \leq \gamma\nonumber\]

Show that there exists a matrix \(Y\) with \(\|Y\|_{2} \leq 1\) such that

\[X=Y\left(\gamma^{2} I-A^{\prime} A\right)^{\frac{1}{2}}\nonumber\]

(b) Suppose

\[\left\|\left(\begin{array}{cc}
X & A\\\end{array}\right)\right\| \leq \gamma\nonumber\]

Show that there exists a matrix \(Z\) with \(\|Z\| \leq 1\) such that \(X = (\gamma^{2}I - AA^{*})^{\frac{1}{2}}Z\)

Exercise 5.7 Matrix Dilation

The problems above can help us prove the following important result:

\[\gamma_{0}:=\min _{X}\left\|\left(\begin{array}{cc}
X & B \\
C & A
\end{array}\right)\right\|=\max \left\{\|\left(\begin{array}{cc}
C & \left.A)\|,\|\left(\begin{array}{c}
B \\
A
\end{array}\right) \|\right\}
\end{array}\right.\right.\nonumber\]

This is known as the matrix dilation theorem. Notice that the left hand side is always greater than or equal to the right hand side irrespective of the choice of \(X\). Below, we outline the steps necessary to prove that this lower bound is tight. Matrix dilations play an important role in systems theory particularly in model reduction problems.

1. Let \(\gamma_{1}\) be defined as

\[\gamma_{1}=\max \left\{\left\|\left(\begin{array}{ll}
C & A
\end{array}\right)\right\|,\left\|\left(\begin{array}{l}
B \\
A
\end{array}\right)\right\|\right\}\nonumber\]

Show that:

\[\gamma_{0} \geq \gamma_{1}\nonumber\]

2. Use the previous exercise to show that there exists two matrices \(Y\) and \(Z\) with norms less than or equal to one such that

\[B=Y\left(\gamma_{1}^{2} I-A^{*} A\right)^{\frac{1}{2}}, \quad C=\left(\gamma_{1}^{2} I-A A^{*}\right)^{\frac{1}{2}} Z\nonumber\]

3. Define a candidate solution to be \(\tilde{X}=-Y A^{*} Z\). Show by direct substitution that

\[\begin{aligned}
\left.\| \begin{array}{cc}
\tilde{X} & B \\
C & A
\end{array}\right) \| &=\left\|\left(\begin{array}{cc}
-Y A^{*} Z & Y\left(\gamma_{1}^{2} I-A^{*} A\right)^{\frac{1}{2}} \\
C=\left(\gamma_{1}^{2} I-A A^{*}\right)^{\frac{1}{2}} Z & A
\end{array}\right)\right\| \\
&=\left\|\left(\begin{array}{cc}
Y & 0 \\
0 & I
\end{array}\right)\left(\begin{array}{cc}
-A^{*} & \left(\gamma_{1}^{2} I-A^{*} A\right)^{\frac{1}{2}} \\
C=\left(\gamma_{1}^{2} I-A A^{*}\right)^{\frac{1}{2}} & A
\end{array}\right)\left(\begin{array}{cc}
Z & 0 \\
0 & I
\end{array}\right)\right\|
\end{aligned}\nonumber\]

4. Show that

\[\left\|\left(\begin{array}{cc}
\tilde{X} & B \\
C & A
\end{array}\right)\right\| \leq \gamma_{1}\nonumber\]

This implies that \(\gamma_{0} \leq \gamma_{1}\) which proves the assertion.

Exercise 5.8

Prove or disprove (through a counter example) the following singular values inequalities.

1. \(\sigma_{\min }(A+B) \leq \sigma_{\min }(A)+\sigma_{\min }(B)\) for any \(A\) and \(B\).
2. \(\sigma_{\min }(A+E) \leq \sigma_{\max }(E)\) whenever \(A\) does not have column rank, and \(E\) is any matrix.
3. \(\sigma_{\max }(A) <1\), then \[\sigma_{m a x}(I-A)^{-1} \leq \frac{1}{1-\sigma_{\max }(A)}\nonumber\]
4. \(\sigma_{i }(I + A) \leq \sigma_{i}(A)+1\).