1
$\begingroup$

I'm currently looking over a section in my textbook on Matrix Condition Numbers and it's given the definition $cond(A) = ||A|| \cdot ||A^{-1}||$ but it's also equated this definition of a condition number to the following:

$$ ||A|| \cdot ||A^{-1}|| = \Big(\max_{x \neq 0} \frac{||Ax||}{||x||}\Big) \cdot \Big(\min_{x \neq 0} \frac{||Ax||}{||x||}\Big)^{-1} $$

without an explanation.

I believe that the proof to this relation lies in estimating $||A^{-1}||$ but I'm not quite sure how to approach this problem given the properties of this estimation, namely if $x$ is the solution to $Ax = y$, then

$$ ||x|| = ||A^{-1}y|| \leq ||A^{-1}|| \cdot ||y|| \text, $$

so that

$$ \frac{||x||}{||y||} \leq ||A^{-1}|| $$

My attempt at the solution:

$$cond(A) = ||A|| \cdot ||A^{-1}||$$ $$cond(A) = \Big( \max_{x \neq 0} \frac{||Ax||}{||x||} \Big) \cdot \Big( \max_{x \neq 0} \frac{||A^{-1}x||}{||x||} \Big)$$ by definition of the norm of a matrix. $$cond(A) = \Big( \max_{x \neq 0} \frac{||Ax||}{||x||} \Big) \cdot \Big( \frac{1}{\min_{x \neq 0} \frac{||x||}{||A^{-1}x||}} \Big)$$ $$cond(A) = \Big( \max_{x \neq 0} \frac{||Ax||}{||x||} \Big) \cdot \Big( \frac{1}{\min_{x \neq 0} \frac{||Ay||}{||y||}} \Big) $$ from the properties of matrix inverse approximation.

However, this last part is where I get stuck. Any suggestions on how to proceed or how to prove this equality using the matrix inverse estimation properties I have above?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

By definition (well, one of the definitions, but they're all easily seen to be equivalent), $\|A\|$ is the maximum of $\|Ax\|/\|x\|$ over all $x \ne 0$. So if $A^{-1}$ exists, $\|A^{-1}\|$ is the maximum of $\|A^{-1} x\|/\|x\|$ over all $x \ne 0$. Now if $y = A^{-1} x$ we have $x = A y$, and both $x$ and $y$ are nonzero iff one is nonzero. So the maximum of $\|A^{-1} x\|/\|x\|$ over $x \ne 0$ is the same as the maximum of $\|y\|/\|A y\|$ over $y \ne 0$, and the reciprocal of this is the minimum of $\|Ay\|/\|y\|$ over $y \ne 0$.

$\endgroup$
2
  • $\begingroup$ I see how you ended up with the final result, but why does the equality have $\min_{x \neq 0} \frac{||Ax||}{||x||}$ instead of $\min_{x \neq 0} \frac{||Ay||}{||y||}$ that you arrived at? $\endgroup$
    – Josh Black
    Commented Mar 17, 2015 at 1:28
  • 2
    $\begingroup$ $\min_{x \ne 0} \dfrac{\|Ax\|}{\|x\|}$ is the same as $\min_{y \ne 0} \dfrac{\|Ay\|}{\|y\|}$. Only the name of the dummy variable has been changed. $\endgroup$
    – Robert Israel
    Commented Mar 17, 2015 at 14:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .