Show that for non-singular $A \in R^{m\times m}$ there exists non-zero vectors $\textbf{b}$ and $\delta \textbf{b}$ in $R^m$ such that the following equations hold: $A \textbf{x} = \textbf{b}$, $A (\textbf{x} \delta \textbf{x}) = \textbf{b} + \delta \textbf{b}$, and $\frac{\Vert \delta \textbf{x} \Vert_p}{\Vert \textbf{x} \Vert_p} = \kappa_p(A) \frac{\Vert \delta \textbf{b} \Vert_p}{\Vert \textbf{b} \Vert_p}$, where $p = 1, 2, \infty$ and $\kappa_p = \Vert A \Vert_p \Vert A^{-1} \Vert_p$

We are encouraged to use the following information:

$$\Vert B \Vert_p = \max \limits_{0 \neq \textbf{z} \in R^m}\frac{\Vert B\textbf{z} \Vert_p}{\Vert \textbf{z} \Vert_p}$$

and that there always exists a particular nonzero $\textbf{z} \in R^m$ such that

$$\Vert B \Vert_p = \frac{\Vert B\textbf{z} \Vert_p}{\Vert \textbf{z} \Vert_p}$$

We also know that $B = A$ and $B = A^{-1}$.

My Thoughts

So first I wanted to establish what I am trying to prove. From what I understand I am supposed to use
$$\Vert B \Vert_p = \frac{\Vert B\textbf{z} \Vert_p}{\Vert \textbf{z} \Vert_p}$$ and somehow manipulate it to have the form $Ax = b$. If I can do that then I should have no problem with $A (x+dx) = b + db$. The closest I have gotten is $$ \Vert \textbf{z} \Vert_p = \frac{\Vert B\textbf{z} \Vert_p}{\Vert B\Vert_p} = \frac{\Vert A^{-1}\textbf{z} \Vert_p}{\Vert A^{-1}\Vert_p} $$ Is it ok for me to just say then that $A^{-1} \textbf{z} = \textbf{x}$ for some $\textbf{x} \in R^m$ and that $\textbf{z} = \textbf{b}$? For the second part I would do the same as the above but have $\textbf{z = z + dz}$ and instead say that $A^{-1} \textbf{(z + dz)} = \textbf{x + dx}$. This simplifies to $A^{-1} \textbf{dz} = \textbf{dx}$

For the third part,

$$ \Vert \delta \textbf{z} \Vert_p = \frac{\Vert B \delta\textbf{z} \Vert_p}{\Vert B\Vert_p} =\frac{\Vert A^{-1} \delta\textbf{z} \Vert_p}{\Vert A^{-1} \Vert_p} $$ If I divide both sides by the x p-norm I get $$ \frac{\Vert \delta \textbf{z} \Vert_p \Vert A^{-1} \Vert_p }{\Vert \textbf{x} \Vert_p} =\frac{\Vert A^{-1} \delta\textbf{z} \Vert_p}{\Vert \textbf{x} \Vert_p} $$ I know that $$ \Vert \textbf{b} \Vert_p = \Vert A \textbf{x} \Vert_p \leq \Vert A \Vert_p \Vert\textbf{x} \Vert_p \Rightarrow \frac{\Vert \textbf{b} \Vert_p} { \Vert A \Vert_p} \leq \Vert\textbf{x} \Vert_p $$

This can be rewritten as (I substituted z = b) $$ \frac{\Vert \delta \textbf{z} \Vert_p \Vert A^{-1} \Vert_p }{\frac{\Vert \textbf{b} \Vert_p} { \Vert A \Vert_p} } \leq \frac{\Vert A^{-1} \delta\textbf{z} \Vert_p}{\Vert \textbf{x} \Vert_p} \Rightarrow \frac{\Vert \delta \textbf{z} \Vert_p }{\Vert \textbf{b} \Vert_p } \kappa_p(A) \leq \frac{\Vert A^{-1} \delta\textbf{z} \Vert_p}{\Vert \textbf{x} \Vert_p} $$ We showed elsewhere that $$ \frac{\Vert \delta \textbf{z} \Vert_p }{\Vert \textbf{b} \Vert_p } \kappa_p(A) \geq \frac{\Vert A^{-1} \delta\textbf{z} \Vert_p}{\Vert \textbf{x} \Vert_p} $$ so this should prove the equality.

Any feedback on this proof would be very valuable. I just want to make sure I have all the pieces. Also, I'm not even sure if I did it right.

Note: Proofs are my greatest weakness.


Something goes wrong in your step following "This can be rewritten as": the inequality is wrong and should be $$\frac{\Vert \delta \textbf{z} \Vert_p \Vert A^{-1} \Vert_p }{\frac{\Vert \textbf{b} \Vert_p} { \Vert A \Vert_p} } \geq \frac{\Vert A^{-1} \delta\textbf{z} \Vert_p}{\Vert \textbf{x} \Vert_p}.$$

In any case, there is no need to use inequalities to solve this problem. The key is to slowly transform what you know into a form where you can infer the right $\bf{x}$ and $\delta \bf{x}$.

First, you know that $\mathbf{b} = A \bf{x}$ and $\delta \mathbf{b} = A \delta \bf x$, and you also have a formula for $k_p$. Plugging it in, you are trying to find a $\bf x$ and $\delta \bf x$ with $$\frac{\|\delta \mathbf{x}\|_p}{\|\mathbf{x}\|_p} = \|A\|_p\|A^{-1}\|_p \frac{\|A\delta \mathbf{x}\|_p}{\|A\mathbf{x}\|_p}.$$ You can now plug in your second property of matrix norms: there exists a $\mathbf z$ with $$\|A\|_p = \frac{\|A\mathbf{z}\|_p}{\|\mathbf{z}\|_p},$$ and likewise for $A^{-1}$ and a vector $\mathbf{w}$.

Thus you are trying to find a $\bf x$ and $\delta \bf x$ with $$\frac{\|\delta \mathbf{x}\|_p}{\|\mathbf{x}\|_p} = \frac{\|A\mathbf{z}\|_p}{\|\mathbf{z}\|_p}\frac{\|A^{-1}\mathbf{w}\|_p}{\|\mathbf{w}\|_p} \frac{\|A\delta \mathbf{x}\|_p}{\|A\mathbf{x}\|_p},$$ or, separating the knowns and unknowns, $$\frac{\|\delta \mathbf{x}\|_p}{\|\mathbf{x}\|_p} \frac{\|A\mathbf{x}\|_p}{\|A\delta \mathbf{x}\|_p}= \frac{\|A\mathbf{z}\|_p}{\|\mathbf{z}\|_p}\frac{\|A^{-1}\mathbf{w}\|_p}{\|\mathbf{w}\|_p} .$$ Comparing the LHS and RHS, you should get a strong urge to set $\mathbf{x} = \mathbf{z}$. We still don't know what we need for $\delta\mathbf{x}$, but after plugging in $\mathbf{x}=\mathbf{z}$ and simplifying, $$\frac{\|\delta \mathbf{x}\|_p}{\|A\delta \mathbf{x}\|_p}= \frac{\|A^{-1}\mathbf{w}\|_p}{\|\mathbf{w}\|_p},$$ and we see that $\delta \mathbf{x} = A^{-1}\mathbf{w}$ will work like a charm.

| cite | improve this answer | |
  • $\begingroup$ So as I said at the bottom of my post, I struggle with proofs. We are really just trying to verify that the equation holds and are not trying to derive it. Is that correct? Also thanks for pointing out the error in my last proof. $\endgroup$ – rioneye Feb 23 '13 at 4:33
  • 1
    $\begingroup$ Well, you are trying to verify it, but one good way to write an existence proof (which is the form of your question: prove that there exists an $\mathbf{x}, \delta\mathbf{x}$...) is to construct the objects in question. In my post I try to describe my thought process that leads me to finding the values that work. In a formal proof you could just start off with, "by property (2) of matrix norms, there exists a $\mathbf{z}$ with $\|A\|_p = \|A\mathbf{z}\|_p/\|\mathbf{z}\|_p$, and likewise there exists a $\mathbf{w}$ with... Set $\mathbf{x} = \mathbf{z}$, $\mathbf{b} = A\mathbf{x}$, ... then ... $\endgroup$ – user7530 Feb 23 '13 at 4:43
  • $\begingroup$ and therefore $\frac{\Vert \delta \textbf{x} \Vert_p}{\Vert \textbf{x} \Vert_p} = \kappa_p(A) \frac{\Vert \delta \textbf{b} \Vert_p}{\Vert \textbf{b} \Vert_p}$, as desired." Which would be a completely correct proof, but hopefully for learning it's more helpful to have the scaffolding left in. $\endgroup$ – user7530 Feb 23 '13 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.