Counter example or proof that $\kappa(AB) \leq \kappa(A)\kappa(B) $

Question

I am stuggling to find a counter example or either proof (for general matrices $A, B \in \mathbb{C}^{m \times n}$) that $$\kappa(AB) \leq \kappa(A)\kappa(B)\,,$$ where the condition number $\kappa(\cdot)$ is evaluated with respect to any submultiplicative norm $$\|AB\| \leq \|A\|\|B\|$$ and is given by

$$ \kappa(A) = \|A\|\|A^\dagger\|\,, $$ with $A^\dagger$ the Moore–Penrose pseudoinverse of $A$.

---

If the matrices $A, B$ are non singular the result can be easily proved, indeed

$$ \|AB\|\|(AB)^\dagger\| = \|AB\|\|(AB)^{-1}\| = \|AB\|\|B^{-1}A^{-1}\|\leq \|A\|\|A^{-1}\|\|B\|\|B^{-1}\| = \kappa(A)\kappa(B)\,. $$

But what about other cases?

---

Added later:

Similar problem is considered in this question, but no answer to a more general setting is given there.

Answer 1

A counterexample is $A = \left (\begin{matrix} 1& 2& 3\\4&5&6\\7&8&9 \end{matrix}\right)$, $B = \left (\begin{matrix} 1&1&1\\1&1&1\\2&2&3 \end{matrix}\right)$.

Take norm to be 1-norm of matrix, i.e. biggest absolute sum of each column.

Then $\kappa(AB) = 297 > 275 = \kappa(A)\kappa(B)$. Python code is showed below.

import numpy as np
A = np.array([[1,2,3],[4,5,6],[7,8,9]])
B = np.array([[1,1,1],[1,1,1],[2,2,3]])

A_pi = np.linalg.pinv(A)
B_pi = np.linalg.pinv(B)
AB_pi = np.linalg.pinv(A@B)

n = 1

print(np.linalg.norm(A@B,n) * np.linalg.norm(AB_pi,n))

print(np.linalg.norm(A,n) * np.linalg.norm(A_pi,n) * np.linalg.norm(B,n) * np.linalg.norm(B_pi,n))

Answer 2

Let $U\in M_{p,n}$, $\sigma_1\geq \cdots\geq \sigma_k > 0,\cdots,0$ be its singular values and $U^+$ be its pseudoinverse. We use only the matricial norm $||.||_2$. Then $||U||=\sigma_1,||U^+||=1/\sigma_k$ and (with respect to the definition above) $cond(U)=\sigma_1/\sigma_k$.

Remark: Assume that $n\leq p$, $rank(U)=n$ and consider the least square problem $Ux=b$ where $b\in \mathbb{R}^p,x\in\mathbb{R}^n$; the solution is $x=U^+b=(U^TU)^{-1}U^Tb$. Then the accuracy of the calculation of $x$ depends on $cond(U^TU)$, that is $\sigma_1^2/\sigma_n^2=(cond(U))^2$. In other words, if $cond(U)=10^k$, then, when we calculate $x$, we lose $2k$ significant digits (and not only $k$).

Assume that (*) $A\in M_{np},B\in M_{pn}$ where $n\leq p$ and that $AB$ is invertible, that is, $A$ is onto and $B$ is injective; thus $A^T$ is injective, $im(B)\bigoplus \ker(A)=\mathbb{R}^p$ and $\ker(B^T)\cap im(A^T)=\{0\}$. Note that $A,B$ have $rank(A)=rank(B)=n$ non-zero singular values;

One has $x^TABB^TA^Tx=(A^Tx)^T(BB^T)(A^Tx)\leq \rho(BB^T)x^T(AA^T)x\leq \rho(BB^T)\rho(AA^T)||x||^2$; then $\rho(ABB^TA^T)\leq \rho(BB^T)\rho(AA^T)$, that is $\sigma_1(AB)\leq \sigma_1(A)\sigma_1(B)$.

Let $x\not= 0$; then $B^TA^Tx\not= 0$ and $(A^Tx)^T(BB^T)(A^Tx)\geq \sigma_n^2(B)x^TAA^Tx\geq \sigma_n^2(B)\sigma_n^2(A)x^Tx$, that implies $\sigma_n(AB)\geq \sigma_n(A)\sigma_n(B)$.

EDIT and MEA CULPA. Unfortunately, the inequality concerning $\sigma_n$, is, in general, false; indeed $u^T(BB^T)u\not\geq \sigma_n^2(B)u^Tu$ (because $BB^T$ is not invertible and $u$ may have a component on $\ker(BB^T))$. That follows is a counter-example to the conjecture $cond(AB)\leq cond(A)cond(B)$.

Counter-example. Take $n=2,p=4$ and $A=\begin{pmatrix}99&-95.001&-25&76\\99&-95&-25&76\end{pmatrix},B=\begin{pmatrix}10&-62\\-44&-83\\26&9\\-3&88\end{pmatrix}$.

Under my above hypothesis (*) (concerning $A,B$), in general, $(AB)^+\not= B^+A^+$, but $(BA)^+=A^+B^+$. More generally, (**) let $n\leq m,n\leq p$ and $A\in M_{m,n},B\in M_{n,p}$ s.t. $rank(A)=rank(B)=n$. Then $(AB)^+=B^+A^+$

Proposition. Under the hypothesis (**), the inequality $cond(AB)\leq cond(A)cond(B)$ is valid for any sub-multiplicative norm.

The proof is straightforward; $cond(AB)=||AB||||B^+A^+||\leq ||A||||B||||B^+||||A^+||=cond(A)cond(B).$

Remark. Let $A,B\in M_n$. Then $(AB)^+=B^+A^+$ IFF $BB^*(im(A^*))\subset im(A^*)$ AND if $K=im(A^*)\cap \ker(B^*)$, then $A^*A(K)\subset K$.