Condition Number of Rectangular Matrices

Question

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)$

Answer 1

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*}