2

Let $A$ be a set, $X:=\{x_1,...x_k\}$,$Y:=\{y_1,...,y_{k}\}$ $\subset \frak{P}$$(A)\setminus \emptyset$ subsets of the power set of $A$, both with cardinality $k$ and $d$ be a metric on $\frak{P}$$(A)\setminus \emptyset$. With $Per(k)$ I denote the set of all permutations of the index set $\{1, ... ,k\}$.

I now would like to define a new metric:

$D_k(X,Y):= argmin_{\sigma \in Per(k)}\sum_{i=1}^{k}d(x_{i},y_{\sigma(i)})$

$D_k(X,Y)=0 \iff X=Y$ is fullfilled.

$D(X,Y)=D(Y,X)$ holds as $d$ is a metric.

I have the feeling that $D_k$ is not fulfilling the subadditivity and is hence not a metric. However, I am not able to find a counterexample, nor can I proof that $D_k$ is a metric. Could anyone provide me with a proof or a proof idea?

ahbon
  • 23

1 Answers1

1

It is a metric. For the triangular inequality, let $\sigma, \sigma'\in Per(k)$ and $X,Y,Z\subset A$ with cardinality $k$. Then $$ \sum_{i=1}^k d(x_i,z_{\sigma(i)})\leq \sum_{i=1}^k d(x_i,y_{\sigma'(i)})+\sum_{i=1}^k d(y_{\sigma'(i)},z_{\sigma(i)}) $$

and since $D_k(X,Z)\leq \sum_{i=1}^k d(x_i,z_{\sigma(i)})$ we deduce $$ D_k(X,Z)\leq \sum_{i=1}^k d(x_i,y_{\sigma'(i)})+\sum_{i=1}^k d(y_{\sigma'(i)},z_{\sigma(i)}) $$

Let's fix $\sigma'\in Per(k)$. Then, for all $\sigma\in Per(k)$ we have
$$ D_k(X,Z)\leq \sum_{i=1}^k d(x_i,y_{\sigma'(i)})+\sum_{i=1}^k d(y_{\sigma'(i)},z_{\sigma(i)}) $$ hence, taking minimum over $\sigma$ we deduce $$ D_k(X,Z)\leq \sum_{i=1}^k d(x_i,y_{\sigma'(i)})+D_k(Y,Z) $$ for all $\sigma'$. Again, minimizing w.r.t $\sigma'$ we deduce $$ D_k(X,Z)\leq D_k(X,Y)+D_k(Y,Z) $$

Nate River
  • 2,530