Vrftsjtryk

I have a set $X = X_1 times X_2 times dots times X_n$.

I have metrics that satisfy triangular inequality "per component"
$$
rho_i: X_i times X_i to mathbb{R}
$$

for each $i=1,2,dots,n$.

I want to know what are possible ways to combine $rho_i$ for $i=1,2,dots,n$ into
$$rho:Xtimes X to mathbb{R}$$

Specifically:

• Would weighted $max$ work?


• Would weighted sum work?


• Would rooted weighed sum of squares of components work?

All 3 would work.

First, you reduce the weighted problems to the unweighted ones by pre-scaling the initial metrics. That means to prove that e.g.
$$rho ((x_1,x_2), (y_1,y_2)) = max (alpha_1rho_1(x_1,y1), alpha_2rho_2(x_2,y_2))$$
is a metric for any $rho_1,rho_2$ it is enough to prove that

$$rho^* ((x_1,x_2), (y_1,y_2)) = max (rho_1^*(x_1,y1), rho_2^*(x_2,y_2))$$

is a metric for any $rho_1^*,rho_2^*$ and then set

$$rho_1^*(x_1,y_1)=alpha_1rho(x_1,y_1),quad rho_2^*(x_2,y_2)=alpha_2rho(x_2,y_2),$$

which are metrics on $X_1$ and $X_2$ resp., if $alpha_i > 0, i=1,2$.

So the 3 'combination functions' you considered are

$$f_m(d_1,ldots,d_n) = max(d_1,ldots,d_n)$$
$$f_s(d_1,ldots,d_n) = d_1+ldots+d_n$$
$$f_e(d_1,ldots,d_n) = sqrt{d_1^2+ldots+d_n^2}$$

Those are the well known maximum, sum and euclidean norms on $mathbb R^n$. I'll show that any such norm that is also increasing in each component under the assumption that all components are non-negative will work.

Let $f_r$ be such a norm. Then you define

$$rho((x_1,ldots,x_n), (y_1,ldots,y_n)) = f_r(rho_1(x_1,y_1),ldots,rho_n(x_,y_n))$$

This $rho$ is $0$ iff $(x_1,ldots,x_n)=(y_1,ldots,y_n)$ because that is true for each component's $rho_i$ and also $f_r$ is zero only for the null vector.

This $rho$ is symmtric because your component $rho_i$'s are symmetric (nothing needed from $f_r$).

Of course, the triangle inequality is the most problematic thing to prove usually.
Define

$$r_i=rho_i(x_i,y_i),quad s_i=rho_i(y_i,z_i),quad t_i=rho_i(x_i,z_i), forall i=1,ldots,n$$
We then have

$$rho((x_1,ldots,x_n), (z_1,ldots,z_n))=f_r(t_1,ldots,t_n)$$
Because I assumed that $f_r$ was increasing in each component for non-negative values, we can replace each $t_i$ with $r_i+s_i$ and we have $r_i+s_i ge t_i$ because of the triangle inequality of $rho_i$ between $x_i,y_i$ and $z_i$:

$$rho((x_1,ldots,x_n), (z_1,ldots,z_n)) le f_r(r_1+s_1,ldots,r_n+s_n)$$ Because $f_r$ is a norm, the norm-version of the triangle inequality applies here:

$$f_r(r_1+s_1,ldots,r_n+s_n) le f_r(r_1,ldots,r_n) + f_r(s_1,ldots,s_n) = rho((x_1,ldots,x_n), (y_1,ldots,y_n)) + rho((y_1,ldots,y_n), (z_1,ldots,z_n)),$$

which finally proves that $rho$ is indeed a metric.

That means that any such norms can be used to combine the component's metrics into a new one for the product set.