# Let r be a rank function of a matroid M. Prove $(r^*)^*=r$

This is from Algebraic Graph theory, by Godsil.

Let $$r$$ be a function on the subsets of a finite set $$\Omega$$ and define

$$r^*(A)=|A| +r(\Omega \setminus A) - r(\Omega)$$

It follows that if $$r(\emptyset)=0$$ then $$(r^*)^*=r$$.

I don't see how this follows. $$r$$ is a function from the subsets of $$\Omega$$ to nonnegative integers. If I apply $$^*$$ to a subset of $$\Omega$$ I get a positive integer and I don't see how I can apply $$^*$$ to that.

I don't think I understand correctly how the dual function is defined.

When you apply $$*$$ you don't get an integer, you can a new function which happens to be a function plus an integer.
Let $$f(A)=r^*(A)=\vert A\vert + r(\Omega\setminus A) - r(\Omega)$$
Then $$(r^*)^*(A)=f^*(A)$$ so that
\begin{align*} (r^*)^*(A)&=\vert A\vert + f(\Omega\setminus A) - f(\Omega)\\ &=\vert A\vert + \vert \Omega\setminus A\vert + r(A) - r(\Omega) - \vert \Omega\vert - r(\emptyset) + r(\Omega)\\ &= r(A)-r(\emptyset) \end{align*} So that if $$r(\emptyset)=0$$, then $$(r^*)^*=r$$
• Thanks. I failed to realize that integers are not in the domain of $^*$ and so they get “ignored” by $^*$. – ak87 Mar 20 at 16:29