1

Given some numbers, we may choose two of them, say $a$ and $b$, and replace them with the numbers $$a + \frac{b}{2} \ \text{ and } \ b-\frac{a}{2}.$$ If we start with a set of non-zero numbers $S$ and keep applying the operation, show that we can never again obtain the set $S$.

This is a problem related to monovariants and I couldn't figure out the monovariant they found. The solution was to first enumerate the elements of $S$ as $a_1, \dots, a_n$ and consider $$M =a_1^2 + \dots +a_n^2.$$ Now applying the operation for numbers $a$ and $b$ results in the following change of $M$ $$\left( a + \frac{b}{2}\right)^2 + \left( b- \frac{a}{2}\right)^2 -a^2-b^2 = \frac{a^2}{4} + \frac{b^2}{4} \ge 0$$ which causes $M$ to increase after every operation implying that $S$ cannot be achieved again.

My question is that was there some hint on the given expressions $a + \frac{b}{2}$ and $b-\frac{a}{2}$ to consider the sum of the squares since this did seem to come out of thin air in this problem?

Louie
  • 561
  • Observation: This solution assumes the Set $S$ to be finite. Instead, one should assume for the sake of contradiction, that it is possible to obtain $S$ after a finite number of steps (which only involve finitely many $a_i\in S$) and apply the solution to this finite subset. – Dr. Mathva Jul 22 '23 at 11:47
  • After reading @TomKern's answer below, one might say that the key idea is to view the set of numbers as a vector, and argue that applying this operation to a pair of its entries increases its length. From this point of view, "length" is one of the most obvious numerical invariants of a vector, so that is one reason to guess the initial squares formula that appeared to come out of nowhere. – Cheerful Parsnip Jul 22 '23 at 15:11
  • What do you mean exactly by "view the set of numbers as a vector"? Do you mean that we view the elements of $S$ as $1$ dimensional vectors or that we view the chosen $a$ and $b$ as the vector $(a,b)$? @CheerfulParsnip – Louie Jul 22 '23 at 21:38
  • I mean view the set $S$ as a vector with some arbitrary order imposed. – Cheerful Parsnip Jul 22 '23 at 21:41
  • I might not be understanding you correctly, but are you saying that we are viewing the set $S$ as a single vector of some vector space? @CheerfulParsnip – Louie Jul 22 '23 at 21:50
  • Yes. That's what I am saying. For example, if your set is $S={1,5,2.7,9.2}$, think of it instead as the vector $v_S=(1,5,2.7,9.2)$. Then the sum of squares is the square of the Euclidean length of the vector. – Cheerful Parsnip Jul 22 '23 at 22:03

1 Answers1

1

The matrix $\begin{pmatrix} 1 & \frac12 \\ -\frac12 & 1 \end{pmatrix}$ always increases the length of vectors. One can see this quickly by sketching out the column vectors on a grid.

TomKern
  • 2,977