3

I have a set of integers $\{e_1, e_2, ..., e_n\}$ in which subsets of elements are taken, and operations are applied to each element so that the sum of elements in a set equals the mean of all subsets, $x$.

For example, the sets $A = \{e_1, e_2, e_3, e_4\}$ and $B = \{e_5, e_6, e_7, e_8\}$. The sum of $A + B$ divided by the number of sets gives $x$, and the sum of any individual set divided by $x$ gives the amount by which I should multiply each element of that set for it to add to $x$. I felt this was quite a trivial problem until I realized subsets may contain elements from other subsets, e.g. The example above may have the third set, $C = \{e_1, e_9, e_{10}, e_8\}$, noting that $e_1 ∈ A$ and $e_8 ∈ B$. This has left me stumped as I can no longer proceed through sets linearly as subsequent operations on the same variable will invalidate the sum of prior sets the variable is a member of.

Can anyone share ideas, or theorems or solutions that can help me find an operation I can apply to elements so that each set is equal to $x$?

I'm sorry if my set notation is lacking as it really has been a while since my studies. Furthermore, I know my question may be confusing, but it is assumed in this use case that each set should (but will not) have the same sum, and by operating on elements to achieve the average of all elements, the validity of each element increases. I just don't know what to do about elements appearing in >1 set.

A. P.
  • 5,978
Ricil
  • 33

1 Answers1

2

I’m not sure what would be a good generalization of your approach that uses multiplicative corrections – the way you’re mixing addition and multiplication makes it complicated to decouple the constraints. I’ll provide a solution that deals with the overlaps between the subsets in the case where you correct additively, i.e. you subtract the difference between the actual average of the subset and the desired average from each element; I hope that this will also be useful to you.

Your problem in that case is that orthogonal projections onto non-orthogonal spaces don’t commute. To solve that problem, you can construct an orthogonal basis of the space you want to orthogonalize against.

Let $\vec e$ be the vector whose entries are the elements $e_1,\ldots,e_n$. Then the constraint that subset $S_k$ should sum to $x$ can be written as $\vec s_k\cdot \vec e=x$, where $\vec s_k$ is a vector with entries $1$ corresponding to the elements of $S_k$ and $0$ elsewhere. For instance, in your example the vectors for the sets $S_1=A$, $S_2=B$ and $S_3=C$ are

$$ \vec s_1=\pmatrix{1\\1\\1\\1\\0\\0\\0\\0\\0\\0}\;,\quad \vec s_2=\pmatrix{0\\0\\0\\0\\1\\1\\1\\1\\0\\0}\;,\quad \vec s_3=\pmatrix{1\\0\\0\\0\\0\\0\\0\\1\\1\\1}\;. $$

If the $S_k$ were disjoint, these vectors would all be orthogonal, and you could orthogonally project onto the affine spaces defined by the constraints $\vec s_k\cdot \vec e=x$ one by one without messing up the constraints already imposed.

To deal with this, find an orthonormal basis for the space spanned by the $\vec s_k$, for instance using the Gram–Schmidt process. In your example, this would yield

$$ \vec s_1'=\frac12\vec s_1=\frac12\cdot\pmatrix{1\\1\\1\\1\\0\\0\\0\\0\\0\\0}\;,\quad \vec s_2'=\frac12\vec s_1=\frac12\cdot\pmatrix{0\\0\\0\\0\\1\\1\\1\\1\\0\\0}\;,\\ \vec s_3'=\sqrt{\frac{8}{13}}\left(\vec s_3-\frac12s_1'-\frac12s_2'\right)=\frac1{\sqrt{26}}\cdot\pmatrix{3\\-1\\-1\\-1\\-1\\-1\\-1\\3\\1\\1}\;. $$

Since you know the $\vec s_k'$ as linear combinations of the $\vec s_k$, you can get the corresponding constraints as the corresponding linear combinations of the original constraints:

\begin{eqnarray} \vec s_1'\cdot\vec e &=& \frac12x\;,\\ \vec s_2'\cdot\vec e &=& \frac12x\;,\\ \vec s_3'\cdot\vec e &=& \left(\sqrt{\frac{8}{13}}-\frac12\right)x\;. \end{eqnarray}

Now you can orthogonally project onto these orthonormal constraints one by one without undoing the progress from previous steps. For each constraint $\vec s_k'\cdot\vec e=\alpha_kx$, add the required multiple of $\vec s_k'$:

$$ \vec e\to\vec e+\left(\alpha_kx-\vec s_k'\cdot\vec e\right)\vec s_k' $$

(You can check by forming the scalar product with $\vec s_k'$ that this does indeed fulfil the constraint.)

joriki
  • 238,052