# Vector spaces, Linear mappings and a relation to the inclusion-exclusion principle

Exercise

Let $S$ be a set containing $n$ elements and $V$ be the $2^n$-dimensional vector space of all mappings $f : 2^S \rightarrow \mathbb{C}$. Let $\phi : V \rightarrow V$ be a linear map that for a map $f : 2^S \rightarrow \mathbb{C}$, the map $\phi(f) : 2^S \rightarrow \mathbb{C}$ is defined by $$(\phi(f))(T) = \sum_{T \subseteq Y \subseteq S}f(Y),\quad T \subseteq S .$$

i) Prove that $\phi$ is bijective and for a $g : 2^V \rightarrow \mathbb{C}$ the $\phi^{-1} : V \rightarrow V$ is defined by $$\phi^{-1}(g)(T) = \sum_{T \subseteq Y \subseteq S}(-1)^{\# (Y\setminus T)}g(Y), T \subseteq S .$$

ii) Reason the inclusion–exclusion principle from i).

Hi! I don't come along with this at all as I don't even understand the first part. Could you please help me understanding the exercise and finding a suitable solution?

-
I'm sorry, but are you copying this correctly? If $T$ is a subset of $S$, then how do you "add" subsets? And the value of $\phi(f)$ at $T$ should be a complex number, so it's not at all clear to me what it is you are writing in the first part. Please double check your formula! –  Arturo Magidin May 28 '11 at 21:42
Should it be$$(\phi(f))(T) = \sum_{T\subseteq Y\subseteq S}f(Y),\qquad T\subseteq S?$$ –  Arturo Magidin May 28 '11 at 21:44

With these kinds of things, it is useful to work out a few small examples to see how this is going.

Suppose $n=1$, so $S$ has one element, $S=\{a\}$. Then $2^S$ has two elements, corresponding to the two subsets of $S$, $\emptyset$ and $S$. You then have the vector space of all mappings $f\colon\{\emptyset, \{a\}\}\to\mathbb{C}$.

Let $f\colon\{\emptyset, \{a\}\}\to\mathbb{C}$ be a map. This is equivalent to having two complex numbers: one for the image of $\emptyset$, one for the image of $\{a\}$, say $(f(\emptyset),f(\{a\})) = (x,y)$. What is $\phi(f)$?

$\phi(f)$ should be a function with domain $\{\emptyset,\{a\}\}$ and codomain the complex numbers. So one way to specify what $\phi(f)$ is would be to say what it's value is at each subset of $S$. This is what the formula is giving. So, for instance, \begin{align*} \phi(f)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S} f(Y) = f(\emptyset) + f(\{a\}) = x+y.\\ \phi(f)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}f(Y) = f(\{a\}) = y. \end{align*} That is, the function $\phi$ takes the function corresponding to $(x,y)$ to the function corresponding to $(x+y,y)$. This is certainly an element of $V$.

Notice also that $\phi$ is linear: because $(f+\alpha g)(Y) = f(Y)+\alpha g(Y)$, so $$\sum_{T\subseteq Y\subseteq S}(f+\alpha g)(Y) = \sum_{T\subseteq Y\subseteq S}f(Y) + \alpha\sum_{T\subseteq Y\subseteq S}g(Y),$$ which tells you that for every subset $T$ of $S$, $\phi(f+\alpha g)(T) = \phi(f)(T) + \alpha\phi(g)(T)$, hence $$\phi(f+\alpha g) = \phi(f) + \alpha\phi(g)$$ proving linearity.

If we use the given formula for $\phi^{-1}$, what do we get when we plug in $g$, with values $(r,s)$ (that is, $g(\emptyset) = r$, $g({a}) = s$)? We have: \begin{align*} \phi^{-1}(g)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S}(-1)^{\#(Y-\emptyset)}g(Y)\\ &= (-1)^{0}g(\emptyset) + (-1)^1g(\{a\}) = r-s,\\ \phi^{-1}(g)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{a\})}g(Y)\\ &= (-1)^0g(\{a\}) = s. \end{align*} So $\phi(g)$ is the function $(r-s,s)$.

Note that if we start with $f$ that corresponds to $(x,y)$ and apply $\phi$, we get the function that corresponds to $(x+y,y)$; if we then apply $\phi^{-1}$, we get the function that corresponds tO $(x,y)$, i.e. $f$; likewise, if we start with the function $(r,s)$ and apply $\phi^{-1}$, we get $(r-s,s)$; then apply $\phi$ and we get $(r,s)$. So all is well.

What if $S$ has two elements, $S=\{a,b\}$. Then $2^S$ has four elements. Say $f$ is a function from $2^S = \{\emptyset,\{a\},\{b\},\{a,b\}\}$ to $\mathbb{C}$. What is $\phi(f)$?

To quote Leibnitz, let us calculate: \begin{align*} \phi(f)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S}f(Y)\\ &= f(\emptyset) + f(\{a\}) + f(\{b\}) + f(\{a,b\}).\\ \phi(f)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}f(Y)\\ &= f(\{a\}) + f(\{a,b\}).\\ \phi(f)(\{b\}) &= \sum_{\{b\}\subseteq Y\subseteq S}f(Y)\\ &= f(\{b\}) + f(\{a,b\}).\\ \phi(f)(\{a,b\}) &= \sum_{\{a,b\}\subseteq Y\subseteq S}f(Y)\\ &= f(\{a,b\}). \end{align*} What about $\phi^{-1}(f)$? \begin{align*} \phi^{-1}(f)(\emptyset) &= \sum_{\emptyset\subseteq Y\subseteq S}(-1)^{\#(Y-\emptyset)}f(Y)\\ &= (-1)^0f(\emptyset) + (-1)^1f(\{a\}) + (-1)^1f(\{b\}) + (-1)^2f(\{a,b\})\\ &= f(\emptyset) - (f(\{a\}) + f(\{b\})) + f(\{a,b\}).\\ \phi^{-1}(f)(\{a\}) &= \sum_{\{a\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{a\})}f(Y)\\ &= (-1)^0f(\{a\}) + (-1)^1f(\{a,b\})\\ &= f(\{a\}) - f(\{a,b\}).\\ \phi^{-1}(f)(\{a,b\}) &= \sum_{\{b\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{b\})}f(Y)\\ &= (-1)^0f(\{b\}) + (-1)^1f(\{a,b\})\\ &= f(\{b\}) - f(\{a,b\}).\\ \phi^{-1}(f)(\{a,b\}) &= \sum_{\{a,b\}\subseteq Y\subseteq S}(-1)^{\#(Y-\{a,b\})}f(Y)\\ &= f(\{a,b\}). \end{align*}

So, for example, if $f(\emptyset) = 2$, $f(\{a\}) = i$, $f(\{b\}) = \frac{1}{3}+\sqrt{2}i$, and $f(\{a,b\}) = e+\pi i$ (values chosen entirely arbitrarily), then $\phi(f)$ is the function with values: \begin{align*} \phi(f)(\emptyset) &= 2 + i + \frac{1}{3}+\sqrt{2}i + e+\pi i = \left(2+\frac{1}{3}+e\right) + \left(\sqrt{2}+\pi\right)i.\\ \phi(f)(\{a\}) &= i + e+\pi i = e + (\pi+1)i.\\ \phi(f)(\{b\}) &= \frac{1}{3}+\sqrt{2}i + e+\pi i = \left(\frac{1}{3}+e\right) + \left(\sqrt{2}+\pi\right)i.\\ \phi(f)(\{a,b\}) &= e + \pi i.\\ \phi^{-1}(f)(\emptyset)&= 2 -\left( i + \frac{1}{3}+\sqrt{2}i\right) + e+\pi i\\ &= \left(2 - \frac{1}{3} + e\right) + \left(-1 - \sqrt{2}+\pi\right)i.\\ \phi^{-1}(f)(\{a\}) &= i - (e+\pi i) = -e + (1-\pi)i.\\ \phi^{-1}(f)(\{b\}) &= \frac{1}{3} + \sqrt{2}i - (e+\pi i)\\ &= \left(\frac{1}{3}-e\right) + \left(\sqrt{2}-\pi\right)i.\\ \phi^{-1}f(\{a,b\}) &= e+\pi i. \end{align*}

If we represent a function from $\{\emptyset,\{a\},\{b\},\{a,b\}\}$ to $\mathbb{C}$ with a $4$-tuple of complex numbers (corresponding to the values at $\emptyset$, at $\{a\}$, at $\{b\}$, and at $\{a,b\}$, respectively), then $\phi$ sends the function corresponding to $(x,y,z,w)$ to the function $(x+y+z+w, y+w, z+w, w)$, while $\phi^{-1}$ sends the function corresponding to $(r,s,t,u)$ to $(r-s-t+u, s-u, t-u, u)$. You can now verify easily that $\phi$ and $\phi^{-1}$ are inverses of each other.

As far as finding a suitable solution, I would not recommend trying to think of the functions as tuples. Instead, I would suggest trying induction on $n$.

You might also notice how similar to "inclusion-exclusion" the formula for $\phi^{-1}$ looks; that suggests trying to find a suitable $f$ so that, on the one hand, the value of $f$ counts something, while the value of $\phi^{-1}(\phi(f))$ gives you the inclusion-exclusion way of counting it.

-
Thank you very much for taking so much time explaining this to me! I do now understand what to do and try to solve it on my own :) –  muffel May 30 '11 at 7:53