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)$
2
$\begingroup$
$\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$
$\endgroup$
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*}
