# Linearization of a fact about functions between finite sets

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

-
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

## 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.

-
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