6
$\begingroup$

Given $A=BC$ where $A\in\mathbb{R}^{m\times n}$ and for some $B\in\mathbb{R}^{m\times k}, C\in\mathbb{R}^{k\times n}$. We assume that $k>=\min(m,n)$ so that this decomposition always exists for any matrix $A\in\mathbb{R}^{m\times n}.$

Can we prove that any perturbation $\bar{A}$ of $A$ can be represented as the product of two perturbations of $B$ and $C$ ?

Intuitively i think it should be possible but i cannot prove/disprove it. If not possible then what conditions are needed?

Improve this question
$\endgroup$
4
  • $\begingroup$ The way you phrased it, I understand that you are trying to prove that, given $\tilde A$ there exist $\tilde B$ and $\tilde C$ such that $$A+\epsilon \tilde A= (B+\epsilon \tilde B)(C+\epsilon \tilde C).$$While this is true to first order in $\epsilon$, with $\tilde A = B\tilde C + \tilde B C$, it is not true in general. Anyway, I don't know if I correctly interpreted the question; I guess not. $\endgroup$
    – Giuseppe Negro
    Commented Mar 14, 2017 at 14:32
  • $\begingroup$ a perturbation here means, for instance, $||\bar{A}-A|| < \epsilon$ for some norm and arbitrary $\epsilon>0.$ So given $\epsilon>0$ and a matrix $\bar{A}$ satisfying $||\bar{A}-A|| < \epsilon$, can we find two matrices $\bar{B},\bar{C}$ so that $\bar{A}=\bar{B} \bar{C}$ and one can bound the distances $||\bar{B}-B||$ and $||\bar{C}-C||$ in terms of $\epsilon$ ? sorry for any confusion. $\endgroup$
    – jayki
    Commented Mar 14, 2017 at 14:41
  • 1
    $\begingroup$ The two matrices $\tilde{B}$ and $\tilde{C}$ can surely be found since in the given hypothesis any matrix in $\mathbb{R}^{m\times n}$ (and so in particular $\tilde{A}$) can be written in the form $\tilde{B}\tilde{C}$. So the real question is on the bound. $\endgroup$
    – domenico fiorenza
    Commented Mar 14, 2017 at 20:43
  • 1
    $\begingroup$ @domenico fiorenza: exactly! The hard part is to show that $\bar{B},\bar{C}$ can be also chosen to be sufficiently close to $B,C$ as $\bar{A}$ is sufficiently close to $A.$ $\endgroup$
    – jayki
    Commented Mar 14, 2017 at 22:27

2 Answers 2

Reset to default
9
$\begingroup$

The condition you want is exactly that the matrix multiplication map be locally open at the pair $(B,C)$. This is the topic of the recent paper Where is matrix multiplication locally open? by Behrends. The paper contains a complete characterization in Theorem 2.5. According to that theorem, if we let $s$ and $t$ be the ranks of $B$ and $C$, respectively, and let $t = t_1 + t_2$ where $t_1 = \dim (\operatorname{range} C \cap \ker B)$, then matrix multiplication is open at $(B,C)$ iff $t_2\leq k-m$ or $n-t_1\leq k-s$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ My impression is that the question asks for more than a topological information. For instance, when $n=m=k=1$ consider $B=C=0$. Then the image of the neighborhood $|\tilde{B}|,|\tilde{C}|<\epsilon$ of $(0,0)$ via the multiplication contains an open neighborhood of $0$. But how big? This clearly is $|\tilde{A}|<\epsilon^2$. That is, if we choose an arbitary $\tilde{A}$ with $|\tilde{A}|<\epsilon<1$, we can surely write $\tilde{A}=\tilde{B}\tilde{C}$, with $|\tilde{B}|,|\tilde{C}|<\delta_\epsilon$ for some $\delta_\epsilon$, but we need $\delta_\epsilon\geq\sqrt{\epsilon}>\epsilon$. $\endgroup$
    – domenico fiorenza
    Commented Mar 15, 2017 at 6:53
  • $\begingroup$ so i guess the real question is: can an a priori bound $\delta_{B,C,|\tilde{A}-BC|}$ in terms of $B,C$ and $|\tilde{A}-BC|$ given such that there exist $\tilde{B}$ and $\tilde{C}$ with $\tilde{B}\tilde{C}=\tilde{A}$ and $|\tilde{B}-B|,|\tilde{C}-C|<\delta_{B,C,|\tilde{A}-BC|}$ $\endgroup$
    – domenico fiorenza
    Commented Mar 15, 2017 at 6:58
  • 1
    $\begingroup$ Given that the OP only asked for two perturbations and in the comments only asked to bound their distance from $B$ and $C$ in terms of $\epsilon$ without specifying any particular desired dependence, it seemed reasonable to interpret the question topologically. But I'll let the OP clarify if he wants something stronger. It's also possible that a quantitative bound could be extracted from the paper, but I have not read it in detail. $\endgroup$
    – Noah Stein
    Commented Mar 15, 2017 at 10:33
  • $\begingroup$ I think this has been almost the answer. Since it turns out that there always exist a sufficiently small perturbation $A'$ of $A$ such that the corresponding matrices $B'$ and $C'$ can always be chosen within any arbitrary small neighborhood of $B$ and $C.$ But this does not mean that any perturbation of $A$ would directly imply an upper-bound on perturbation of $B$ and $C.$ Thanks everyone!! $\endgroup$
    – jayki
    Commented Mar 15, 2017 at 12:35
3
$\begingroup$

In numerical analysis lingo, you are more or less asking if matrix multiplication is backward stable. The answer seems to be no: see Section 3.5 of Higham, Accuracy and stability of numerical algorithms. I am unable to locate an explicit counterexample quickly, though.

Improve this answer
$\endgroup$

You must log in to answer this question.

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