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

43 Views Asked by At

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.

1

There are 1 best solutions below

1
On BEST ANSWER

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$