Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
+1: Very nicely done. –  copper.hat Feb 23 '13 at 4:19
    
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. –  rioneye Feb 23 '13 at 4:33
1  
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 ... –  user7530 Feb 23 '13 at 4:43
    
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. –  user7530 Feb 23 '13 at 4:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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