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

formallinear 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