2
$\begingroup$

The 2-norm condition number can be easily extended to rectangular matrices. I'm wondering if the inequality for the product of matrices still holds in that case, i.e.,

$\operatorname{cond}(AB) \leq \operatorname{cond}(A)\operatorname{cond}(B)$

$\endgroup$
  • 1
    $\begingroup$ Yes, this is still true for rectangular matrices both in the spectral norm and in other norms. It's a good exercise so I won't ruin the challenge for you. A hint would be start by considering the definition of $\mathrm{cond}(A)$ that you're using. $\endgroup$ – Brian Borchers Mar 25 '16 at 0:04
2
$\begingroup$

I guess I figured out the answer to my question.

Suppose the SVD of $A = U \Sigma V^\ast$ (where $V^\ast$ is the conjugate transpose of the matrix $V$). Noting the fact that the unitary transformations $U$ and $V$ preserve the 2-norm, $\|Ax\|_{2}$ for any unit vector $x$ can be written as

\begin{align*} \frac{\|Ax\|_{2}}{\|x\|_{2}} = \|Ax\|_{2} &= \|U \Sigma V^\ast x\|_{2} \\ &= \| \Sigma V^\ast x\|_{2} \\ &= \| V^\ast \Sigma x\|_{2} \\ &= \|\Sigma x\|_{2} \end{align*}

Hence $\|Bx\|_{2} \leq \sigma_\max(B)$ and $\|Bx\|_{2} \geq \sigma_\min(B)$.

For $y = Bx$,

\begin{equation*} \|ABx\|_{2} = \|Ay\|_{2} \leq \sigma_\text{max}(A) \|y\|_{2} \leq \sigma_\max(A) \sigma_\max(B) \end{equation*}

Similarly,

\begin{equation*} \|ABx\|_{2} = \|Ay\|_{2} \geq \sigma_\min(A) \|y\|_{2} \geq \sigma_\min(A) \sigma_\min(B) \end{equation*}

Since the above statements are true for all $x$, they are true both for the minimum and maximum. Thus, \begin{equation*} \sigma_\max(AB) = \max \|ABx\|_{2} \leq \sigma_\max(A) \sigma_\max(B) \end{equation*}

and \begin{equation*} \sigma_\min(AB) = \min \|ABx\|_{2} \geq \sigma_\min(A) \sigma_\min(B) \end{equation*}

On dividing the above two equations, we obtain \begin{equation*} \operatorname{cond}_{2}(AB) \leq \operatorname{cond}_{2}(A) \operatorname{cond}_{2}(B) \end{equation*}

$\endgroup$
  • $\begingroup$ You can accept your own answer. $\endgroup$ – nicoguaro Apr 24 '16 at 3: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.