Math Problems Vault

Problem 3.8.1

(a)(b)

Recall the Sherman–Morrison formula: if $\mathbf{A}_{n \times n}$ is nonsingular and $\overrightarrow {c}$ , $\overrightarrow {d}$ are $n \times 1$ columns such that $1+\overrightarrow {d}^{T}\mathbf{A}^{-1}\overrightarrow {c} \neq 0$ , then the sum $\mathbf{A}+\overrightarrow {c}\overrightarrow {d}^{T}$ is nonsingular, and

(\mathbf{A}+\overrightarrow {c}\overrightarrow {d}^{T})^{-1} = \mathbf{A}^{-1} - \frac{\mathbf{A}^{-1}\overrightarrow {c}\overrightarrow {d}^{T}\mathbf{A}^{-1}}{1+\overrightarrow {d}^{T}\mathbf{A}^{-1}\overrightarrow {c}}.

Suppose you are given that

\mathbf{A} = \begin{bmatrix} 2 & 0 & -1 \\ -1 & 1 & 1 \\ -1 & 0 & 1 \end{bmatrix} \qquad \text{and} \qquad \mathbf{A}^{-1} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & 0 & 2 \end{bmatrix}.

?

(a)

Use the Sherman--Morrison formula to determine the inverse of the matrix $\mathbf{B}$ that is obtained by changing the $(3,2)$ -entry in $\mathbf{A}$ from $0$ to $2$ .

(b)

Let $\mathbf{C}$ be the matrix that agrees with $\mathbf{A}$ except that $c_{32}=2$ and $c_{33}=2$ . Use the Sherman--Morrison formula to find $\mathbf{C}^{-1}$ .

Problem 3.8.2

Suppose $\mathbf{A}$ and $\mathbf{B}$ are nonsingular matrices in which $\mathbf{B}$ is obtained from $\mathbf{A}$ by replacing $\mathbf{A}_{*j}$ with another column $\overrightarrow {b}$ . Use the Sherman--Morrison formula to derive the fact that

\mathbf{B}^{-1} = \mathbf{A}^{-1} - \frac{(\mathbf{A}^{-1}\overrightarrow {b}-\overrightarrow {e}_{j})[\mathbf{A}^{-1}]_{j*}}{[\mathbf{A}^{-1}]_{j*}\overrightarrow {b}}.

?

Problem 3.8.3

Suppose the coefficient matrix of a nonsingular system $\mathbf{A}\overrightarrow {x} = \overrightarrow {b}$ is updated to produce another nonsingular system $(\mathbf{A}+\overrightarrow {c}\overrightarrow {d}^{T})\overrightarrow {z} = \overrightarrow {b}$ , where $\overrightarrow {b}, \overrightarrow {c}, \overrightarrow {d} \in \mathbb {R}^{n \times 1}$ , and let $\overrightarrow {y}$ be the solution of $\mathbf{A}\overrightarrow {y} = \overrightarrow {c}$ . Show that

\overrightarrow {z} = \overrightarrow {x} - \frac{\overrightarrow {y}\overrightarrow {d}^{T}\overrightarrow {x}}{1+\overrightarrow {d}^{T}\overrightarrow {y}}.

?

Problem 3.8.4

(a)(b)

?

(a)

Use the Sherman--Morrison formula to prove that if $\mathbf{A}$ is nonsingular, then $\mathbf{A}+\alpha \overrightarrow {e}_{i}\overrightarrow {e}_{j}^{T}$ is nonsingular for a sufficiently small $\alpha$ .

(b)

Use part (a) to prove that $\mathbf{I}+\mathbf{E}$ is nonsingular when all $\epsilon_{ij}$ 's are sufficiently small in magnitude. This is an alternative to using the Neumann series argument.

Problem 3.8.5

For given matrices $\mathbf{A}$ and $\mathbf{B}$ , where $\mathbf{A}$ is nonsingular, explain why $\mathbf{A}+\epsilon \mathbf{B}$ is also nonsingular when the real number $\epsilon$ is constrained to a sufficiently small interval about the origin. In other words, prove that small perturbations of nonsingular matrices are also nonsingular.

?

Problem 3.8.6

Derive the Sherman--Morrison--Woodbury formula: if $\mathbf{A}_{n \times n}$ is nonsingular and $\mathbf{C}$ , $\mathbf{D}$ are $n \times k$ such that $(\mathbf{I}+\mathbf{D}^{T}\mathbf{A}^{-1}\mathbf{C})^{-1}$ exists, then

(\mathbf{A}+\mathbf{C}\mathbf{D}^{T})^{-1} = \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{C}(\mathbf{I}+\mathbf{D}^{T}\mathbf{A}^{-1}\mathbf{C})^{-1}\mathbf{D}^{T}\mathbf{A}^{-1}.

?

Remark.

?

Recall exercise 3.7.11 (the Schur-complement block-inverse formulas), and consider the product $\begin{pmatrix} \mathbf{I} & \mathbf{C} \\ \mathbf{0} & \mathbf{I} \end{pmatrix}\begin{pmatrix} \mathbf{A} & \mathbf{C} \\ \mathbf{D}^{T} & -\mathbf{I} \end{pmatrix}\begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{D}^{T} & \mathbf{I} \end{pmatrix}$ .

Problem 3.8.7

Recall the norm $\left\| \mathbf{A}\right\| = \max_{i}\sum_{j}\left|a_{ij}\right|$ (the maximum absolute row sum), and the associated condition number $\kappa (\mathbf{A}) = \left\| \mathbf{A}\right\| \left\| \mathbf{A}^{-1}\right\|$ of a nonsingular matrix $\mathbf{A}$ , which gauges how ill-conditioned $\mathbf{A}$ is (larger $\kappa$ means more ill-conditioned).

Using the norm above, rank the following matrices according to their degree of ill-conditioning:

\mathbf{A} = \begin{bmatrix} 100 & 0 & -100 \\ 0 & 100 & -100 \\ -100 & -100 & 300 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 1 & 8 & -1 \\ -9 & -71 & 11 \\ 1 & 17 & 18 \end{bmatrix}, \qquad \mathbf{C} = \begin{bmatrix} 1 & 22 & -42 \\ 0 & 1 & -45 \\ -45 & -948 & 1 \end{bmatrix}.

?

Problem 3.8.8

(a)(b)

Suppose that the entries in $\mathbf{A}(t)$ , $\overrightarrow {x}(t)$ , and $\overrightarrow {b}(t)$ are differentiable functions of a real variable $t$ such that $\mathbf{A}(t)\overrightarrow {x}(t) = \overrightarrow {b}(t)$ .

?

(a)

Assuming that $\mathbf{A}(t)^{-1}$ exists, explain why

\frac{d\mathbf{A}(t)^{-1}}{dt} = -\mathbf{A}(t)^{-1}\mathbf{A}'(t)\mathbf{A}(t)^{-1}.

(b)

Derive the equation

\overrightarrow {x}'(t) = \mathbf{A}(t)^{-1}\overrightarrow {b}'(t) - \mathbf{A}(t)^{-1}\mathbf{A}'(t)\overrightarrow {x}(t).

This shows that $\mathbf{A}^{-1}$ magnifies both the change in $\mathbf{A}$ and the change in $\overrightarrow {b}$ , and thus it confirms the observation derived from (3.8.8) saying that the sensitivity of a nonsingular system to small perturbations is directly related to the magnitude of the entries in $\mathbf{A}^{-1}$ .