# Looking for a proof of non tractability (or perhaps a definition of tractable)

Given $C=XF$, and only data for $C$, solving for $X$ and $F$ has been described as not tractable (which I'm content to believe, but others aren't). If that's the case, where does the following argument fall apart?

Suppose $C^i=XF^i$ is written: \begin{bmatrix} C_1^i \\ \vdots \\ C_m^i \end{bmatrix} = \begin{align}\begin{bmatrix} X_{1,1} & \dots & X_{1,n} \\ \vdots & & \vdots \\ X_{m,1} & \dots & X_{m,n} \end{bmatrix}\end{align}\begin{bmatrix} F_1^i \\ \vdots \\ F_n^i \end{bmatrix}

One instance of data for a given $i$ of $C^i$ would produce $m$ equations and $mn+n$ unknowns.

$q$ instances of data for $C^i$ would produce $qm$ equations and $mn+qn$ unknowns.

If the supposition that you need more equations than unknowns is sufficient, why can I contradict others statements of not tractability by choosing whole number values to satisfy the inequality:

$qm >= mn+qn$?

Using say $q=6,m=3,n=2$.

-
How do you get "instances of $C$"? If $X$ and $F$ are unknown but you are looking for a particular solution, then there is only one $C$; if by "instance" you mean an entry, then you can get at most $m$ instances. Finally, "More equations than unknowns" is a sufficient condition for the existence of nontrivial solutions to a homogenous system of linear equations. Here, you do not have a homogeneous system, and your equations are not homogeneous (unknowns are multiplying each other). So why would you believe that "more equations than unknowns is sufficient"? –  Arturo Magidin Sep 6 '10 at 5:01
Well, I did write "If". I didn't want to repeat the information in the linked question, but I'll edit for the casual reader. I hope that helps clear up the presentation of "instances of data". –  Jamie Sep 6 '10 at 5:12
It's ill-poised if you only know $C$; there are too many possible $(X, F)$ pairs that can be associated with your $C$ if at least one component of $C$ is nonzero. –  Ｊ. Ｍ. Sep 6 '10 at 5:28