10
$\begingroup$

Suppose $X$, $Y$, and $Z$ are finite sets. If we have a function $$f : X \longrightarrow Y$$ and another $$g : Y \longrightarrow Z$$ then the composite function $g \circ f$ has the property that $$ |\mbox{Im} ( g \circ f )| \leq |Y|. $$

If we replace $f$ by a formal linear combination of functions $X \longrightarrow Y$, and $g$ by a formal linear combination of functions $Y \longrightarrow Z$, then we may "compose" these formal combinations (enforcing the distributive law) to obtain a linear combination of functions $X \longrightarrow Z$, none of which have image exceeding $|Y|$ in cardinality.

My question is the converse: can any such linear combination be obtained?

I posted this question at math.stackexchange, but there are no responses after a week: https://math.stackexchange.com/q/97513/22621

$\endgroup$
9
  • $\begingroup$ What do you mean by the "image" of a formal linear combination of functions? $\endgroup$
    – Goldstern
    Jan 16, 2012 at 21:35
  • 2
    $\begingroup$ He doesn't speak of such an image. He only mentions images of each of these functions. $\endgroup$ Jan 16, 2012 at 21:39
  • $\begingroup$ Right. Thanks. I need to work on my English. $\endgroup$
    – Goldstern
    Jan 16, 2012 at 22:00
  • $\begingroup$ I'm sorry, but I don't understand your notion of a formal linear combination in this context, since X, Y, and Z are just sets. Have you defined + and scalar multiplication on the set of maps from X to Y? Or are you really interested in formal linear combinations? For example, if $f_1$ and $f_2$ are two maps from X to Y, is $f_1 + f_2$ simply some other (unspecified) map from X to Y? $\endgroup$ Jan 16, 2012 at 23:14
  • $\begingroup$ By formalizing, he replaces a map f with a formal symbol F. There is no map f + g, but there is a formal sum: one of F plus one of G. (I thought of saying one times instead of one of, but that might get confused with the composition.) I am unclear if in his question the linear combination to be decompositioned is given as a formal sum of. H circle F terms, or if he has symbols K for maps k and rules that say K can be any one of (some set of)l these terms H ccircle F. Gerhard "Ask Me About System Design" Paseman, 2012.01.16 $\endgroup$ Jan 16, 2012 at 23:36

1 Answer 1

3
$\begingroup$

No. Consider e.g. the case $X = Z = \{1,2,3\}$, $Y = \{1,2\}$, and the formal linear combination $h_1 + h_2$ where $h_1(1) = h_1(2)=1$, $h_1(3)=2$, $h_2(1)=h_2(3)=2$, $h_2(2)=3$.
If $h_1 = g_1 \circ f_1$, we must have $f_1(1) = f_1(2) \ne f_3(3)$ and $\text{Im}(g_1) = \{1,2\}$. Similarly if $h_2 = g_2 \circ f_2$ we must have $f_2(1)=f_2(3) \ne f(2(2)$ and $\text{Im}(g_2) = \{2,3\}$. But $h_{12} = g_2 \circ f_1$, which would have $h_{12}(1) = h_{12}(2)$ and $\text{Im}(h_{12}) = \{2,3\}$, and similarly $h_{21} = g_1 \circ f_2$, are not part of this formal linear combination.

$\endgroup$
12
  • $\begingroup$ As I understand the question (but I misunderstood it already a few hours ago), he is asking if $h_1+h_2$ could perhaps be written in the form $(\sum_i \lambda_i g_i) \circ (\sum_j \mu_j f_j)$. $\endgroup$
    – Goldstern
    Jan 16, 2012 at 23:42
  • $\begingroup$ My computer tells me that this example is correct, i.e. h_1+h_2 cannot be factored in the manner Goldstern has written. $\endgroup$ Jan 17, 2012 at 0:04
  • $\begingroup$ I hesitate to accept the answer, though, since this argument only shows that the factorization cannot have the form (g_1+g_2)(f_1+f_2) where g_1 f_1 = h_1 and g_2 f_2 = h_2. $\endgroup$ Jan 17, 2012 at 0:12
  • 1
    $\begingroup$ ...you had a way to check it by computer? Man, I could have told you that was a probable counterexample... $\endgroup$ Jan 17, 2012 at 0:32
  • 1
    $\begingroup$ $$ \matrix{\lambda_1 \mu_1 + \lambda'_1 \mu'_1 &= 1\cr \lambda'_1 \mu_1 + \lambda_1 \mu'_1 &= 0\cr \lambda_2 \mu_2 + \lambda'_2 \mu'_2 &= 1\cr \lambda'_2 \mu_1 + \lambda_1 \mu'_1 &= 0\cr \lambda_1 \mu_2 + \lambda'_1 \mu'_2 &= 0\cr \lambda'_1 \mu_2 + \lambda_1 \mu'_2 &= 0\cr \lambda_2 \mu_1 + \lambda'_2 \mu'_2 &= 0\cr \lambda'_2 \mu_1 + \lambda_2 \mu'_2 &= 0\cr}$$ And this system has no solutions. $\endgroup$ Jan 17, 2012 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.