Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: http://math.stackexchange.com/q/97513/22621

share|improve this question
What do you mean by the "image" of a formal linear combination of functions? –  Goldstern Jan 16 '12 at 21:35
He doesn't speak of such an image. He only mentions images of each of these functions. –  darij grinberg Jan 16 '12 at 21:39
Right. Thanks. I need to work on my English. –  Goldstern Jan 16 '12 at 22:00
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? –  William DeMeo Jan 16 '12 at 23:14
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 –  Gerhard Paseman Jan 16 '12 at 23:36
show 4 more comments

1 Answer

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.

share|improve this answer
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)$. –  Goldstern Jan 16 '12 at 23:42
My computer tells me that this example is correct, i.e. h_1+h_2 cannot be factored in the manner Goldstern has written. –  John Wiltshire-Gordon Jan 17 '12 at 0:04
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. –  John Wiltshire-Gordon Jan 17 '12 at 0:12
...you had a way to check it by computer? Man, I could have told you that was a probable counterexample... –  Harry Altman Jan 17 '12 at 0:32
$$ \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. –  Robert Israel Jan 17 '12 at 8:19
show 7 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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