Eric Forgy
inner product of multisets

Law of Cosines

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

𝒳∩𝒴=⟨X∩Y,1 X∩Y⟩,\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

𝒳+𝒴=𝒳\𝒴+𝒴\𝒳+2𝒳∩𝒴.\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

𝒳+𝒴=𝒳\𝒴+𝒴\𝒳+(μ X+μ Y)"𝒳∩𝒴",\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

𝒳∩𝒴≔1μ X+μ Y(𝒳+𝒴−𝒳\𝒴−𝒴\𝒳)=⟨X∩Y,1 X∩Y⟩,\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

𝒳∩𝒴≔⟨X∩Y,1 X∩Y⟩.\mathcal{X}\cap\mathcal{Y} \coloneqq \langle X\cap Y,1_{X\cap Y}\rangle.

Then the result

𝒳+𝒴=𝒳\𝒴+𝒴\𝒳+(μ X+μ Y)𝒳∩𝒴\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

𝒳∩𝒴≔1μ X+μ Y(𝒳+𝒴−𝒳\𝒴−𝒴\𝒳)=⟨X∩Y,1 X∩Y⟩,\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 𝒳={1,1,2,3}\mathcal{X} = \{1,1,2,3\} and 𝒴={1,1,2,2}\mathcal{Y} = \{1,1,2,2\}?

Eric: Ack. What I wrote only has a hope of being “ok” when μ X\mu_X and μ Y\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

X+Y ={1,1,2,3}+{1,1,2,2} ={1,1,1,1,2,2,2,3} ={3}+{2}+2{1,1,2}\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

𝒳+𝒴=𝒳\𝒴+𝒴\𝒳+2𝒳∩𝒴.\mathcal{X}+\mathcal{Y} = \mathcal{X}\backslash\mathcal{Y} + \mathcal{Y}\backslash\mathcal{X} + 2\mathcal{X}\cap\mathcal{Y}.

In other words,

𝒳\𝒴={3}\mathcal{X}\backslash\mathcal{Y} = \{3\}
𝒴\𝒳={2}\mathcal{Y}\backslash\mathcal{X} = \{2\}
𝒳∩𝒴={1,1,2}\mathcal{X}\cap\mathcal{Y} = \{1,1,2\}

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


‖3X‖ 2 =⟨3X,3X⟩ =9‖X‖ 2\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

𝒳=∑ i𝒳 i\mathcal{X} = \sum_i \mathcal{X}_i

note that

‖𝒳‖ 2=∑ i‖𝒳 i‖ 2.\|\mathcal{X}\|^2 = \sum_i \|\mathcal{X}_i\|^2.

However, when 𝒳\mathcal{X} is merely a set ⟨X,χ X⟩\langle X,\chi_X\rangle, then

‖𝒳‖ 2=|X|\|\mathcal{X}\|^2 = |X|

and we have the familiar expression

|X|=∑ i|X i|.|X| = \sum_i |X_i|.

Furthermore, when XX and YY are sets we can decompose their sum into three disjoint multisets

X+Y=X\Y+Y\X+2X∩YX+Y = X\backslash Y + Y\backslash X + 2 X\cap Y

resulting in

‖X+Y‖ 2=‖X\Y‖ 2+‖Y\X‖ 2+‖2X∩Y‖ 2,\|X+Y\|^2 = \|X\backslash Y\|^2 + \|Y\backslash X\|^2 + \|2 X\cap Y\|^2,

or

|X+Y| =|X\Y|+|Y\X|+2|X∩Y| =|X\Y|+|Y\X|+2‖X‖‖Y‖cosθ X,Y,\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||X+Y| = |X| + |Y|

and

‖X+Y‖ 2=|XX+YY+2XY|=‖X‖\|X+Y\|^2 = |XX + YY + 2XY| = \|X\|
Revised on October 28, 2009 at 18:43:43 by Toby Bartels