inner product of multisets

See inner product of multisets

**The following discussion began as a query box at multiset**

Eric: What is the motivation for the above definition of intersection? I’ve been doodling a lot lately and think a more natural definition for intersection would be

$\mathcal{X}\cap\mathcal{Y} = \langle X\cap Y,1_{X\cap Y}\rangle,$

i.e. the intersection of two multisets should just be a set.

When $\mathcal{X}$ and $\mathcal{Y}$ are just sets, we have

$\mathcal{X}+\mathcal{Y} = \mathcal{X}\backslash\mathcal{Y} + \mathcal{Y}\backslash\mathcal{X} + 2\mathcal{X}\cap\mathcal{Y}.$

A natural generalization of this would seem to be

$\mathcal{X}+\mathcal{Y} = \mathcal{X}\backslash\mathcal{Y} + \mathcal{Y}\backslash\mathcal{X} + (\mu_X+\mu_Y) \text{"}\mathcal{X}\cap\mathcal{Y}\text{"},$

where the above actually *defines* the intersection of multisets. However, if we define

$\mathcal{X}\cap\mathcal{Y} \coloneqq \frac{1}{\mu_X+\mu_Y} \left(\mathcal{X}+\mathcal{Y} - \mathcal{X}\backslash\mathcal{Y} - \mathcal{Y}\backslash\mathcal{X}\right) = \langle X\cap Y,1_{X\cap Y}\rangle,$

then the multiplicity is one and we are back to a simple set. If we were to define intersection this way, then the intersection of two multisets is always a set. This would mean that $\mathcal{X}\cap\mathcal{X}\ne\mathcal{X}$ EXCEPT when $\mathcal{X}$ is a set, in which case we do have $\mathcal{X}\cap\mathcal{X} = \mathcal{X}$.

However, instead of defining intersection in that convoluted way, I would just define

$\mathcal{X}\cap\mathcal{Y} \coloneqq \langle X\cap Y,1_{X\cap Y}\rangle.$

Then the result

$\mathcal{X} + \mathcal{Y} = \mathcal{X}\backslash\mathcal{Y} + \mathcal{Y}\backslash\mathcal{X} + (\mu_X+\mu_Y) \mathcal{X}\cap\mathcal{Y}$

would follow. Furthermore, when $\mathcal{X}$ and $\mathcal{Y}$ are just sets, we’d have

$\alpha\mathcal{X}+\beta\mathcal{Y} = \alpha\mathcal{X}\backslash\mathcal{Y} + \beta\mathcal{Y}\backslash\mathcal{X} + (\alpha+\beta)\mathcal{X}\cap\mathcal{Y},$

which has a certain intuitive feeling to it.

*Toby*: I have no idea what

$\mathcal{X}\cap\mathcal{Y} \coloneqq \frac{1}{\mu_X+\mu_Y} \left(\mathcal{X}+\mathcal{Y} - \mathcal{X}\backslash\mathcal{Y} - \mathcal{Y}\backslash\mathcal{X}\right) = \langle X\cap Y,1_{X\cap Y}\rangle,$

even means. In particular, I don't know how to divide (or even multiply) a multiset by a multiplicity function.

Can you work out your proposed definition of $\mathcal{X} \cap \mathcal{Y}$ for the case of $\mathcal{X} = \{1,1,2,3\}$ and $\mathcal{Y} = \{1,1,2,2\}$?

Eric: Ack. What I wrote only has a hope of being “ok” when $\mu_X$ and $\mu_Y$ are constant. When they are constant, I hope the equations make sense.

As far as your example. Good idea! I want to decompose the sum

$\begin{aligned}
X+Y
&= \{1,1,2,3\} + \{1,1,2,2\} \\
&= \{1,1,1,1,2,2,2,3\} \\
&= \{3\} + \{2\} + 2 \{1,1,2\}
\end{aligned}$

Thanks. This example illustrates the depths of my confusions. Sorry about that. Your example tells me that we want

$\mathcal{X}+\mathcal{Y} = \mathcal{X}\backslash\mathcal{Y} + \mathcal{Y}\backslash\mathcal{X} + 2\mathcal{X}\cap\mathcal{Y}.$

In other words,

$\mathcal{X}\backslash\mathcal{Y} = \{3\}$

$\mathcal{Y}\backslash\mathcal{X} = \{2\}$

$\mathcal{X}\cap\mathcal{Y} = \{1,1,2\}$

as expected from the original definition of $\cap$ for multisets.

$\begin{aligned}
\|3X\|^2
&= \langle 3X,3X\rangle \\
&= 9 \|X\|^2
\end{aligned}$

**Warning: This section is somewhat tentative and may need blessing.**

In this section, we develop the **law of cosines** for multisets.

Given the sum of disjoint multisets

$\mathcal{X} = \sum_i \mathcal{X}_i$

note that

$\|\mathcal{X}\|^2 = \sum_i \|\mathcal{X}_i\|^2.$

However, when $\mathcal{X}$ is merely a set $\langle X,\chi_X\rangle$, then

$\|\mathcal{X}\|^2 = |X|$

and we have the familiar expression

$|X| = \sum_i |X_i|.$

Furthermore, when $X$ and $Y$ are sets we can decompose their sum into three disjoint multisets

$X+Y = X\backslash Y + Y\backslash X + 2 X\cap Y$

resulting in

$\|X+Y\|^2 = \|X\backslash Y\|^2 + \|Y\backslash X\|^2 + \|2 X\cap Y\|^2,$

or

$\begin{aligned}
|X+Y|
&= |X\backslash Y| + |Y\backslash X| + 2 |X\cap Y| \\
&= |X\backslash Y| + |Y\backslash X| + 2 \|X\|\|Y\| \cos\theta_{X,Y},
\end{aligned}$

which is a **law of cosines** for sets.

This is different than the traditional way to derive the law of cosines because with multisets we have

$|X+Y| = |X| + |Y|$

and

$\|X+Y\|^2 = |XX + YY + 2XY| = \|X\|$

Revised on October 28, 2009 at 18:43:43
by
Toby Bartels