# Eric Forgy inner product of multisets

Law of Cosines

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}

## Law of Cosines

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