1
$\begingroup$

See also StackExchange.

Setup. Let $n\in\Bbb N$. Let $a_{1,1}, a_{1,2},\dots, a_{1,n}\in\Bbb R$ be a given sequence of real numbers that sum to $0$, i.e. $a_{1,n}=-(a_{1,1}+a_{1,2}+\dots+a_{1,n-1})$. For $i=2,\dots,n$ define $$a_{i,j}=a_{1,j}+a_{1,j+1}+\dots+a_{1,j+i-1}=\sum_{k=j}^{j+i-1} a_{1,k}\quad(\text{for } j=1,\dots,n-i+1).$$ The "half-matrix" $(a_{i,j})_{i,j}$ can be visualized as follows: $$ \begin{pmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \dots & a_{1,n-2} & a_{1,n-1} & -(a_{1,1}+a_{1,2}+\dots+a_{1,n-1}) \\ a_{1,1}+a_{1,2} & a_{1,2}+ a_{1,3} & a_{1,3}+a_{1,4} & \dots & a_{1,n-2} + a_{1,n-1} & -(a_{1,1}+a_{1,2}+\dots+a_{1,n-2}) \\ a_{1,1}+a_{1,2}+a_{1,3} & a_{1,2}+a_{1,3}+a_{1,4} & a_{1,3}+a_{1,4}+a_{1,5} & \dots & -(a_{1,1}+a_{1,2}+\dots+a_{1,n-3}) \\ \vdots & \vdots & ⋰& ⋰ \\ a_{1,1}+a_{1,2}+\dots+a_{1,n-1} & -a_{1,1} \\ 0 \end{pmatrix} $$

Now I have the following proposition:

Proposition. Let $n, a_{i,j}$ be as in the setup. Then there are at least $n$ distinct pairs $(i,j)$ with $i\in\{1,\dots, n\}$ and $j\in\{1,\dots,n-i+1\}$ such that

  • $a_{i,j}=0$ or
  • $j\le n-i$ and $a_{i,j}\cdot a_{i,j+1} < 0$.

More informally, the number of zeros of the $a_{i,j}$ plus the number of "sign switches" between adjacent $a_{i,j}$ in all rows is at least $n$.

My question: How can we prove this propostion?.


Context. Proving this proposition would enable me to solve another problem about zeroes of special continuous functions that I found on StackExchange.

Example ($n=4$). Consider \begin{pmatrix} 1 & \frac12 & -\frac14 & -\frac54 \\ \frac32 & \frac14 & -\frac32 \\ \frac54 & -1 \\ 0 \end{pmatrix}

Then $a_{1,2}\cdot a_{1,2}<0$; $a_{2,2}\cdot a_{2,3}<0$; $a_{3,1}\cdot a_{3,2}<0$ and $a_{4,1}=0$. So in our example we have exactly $n$ zeros/sign switches.


My work. I tried using induction over $n$ which didn't work.

Edit: A rigorous proof of the Proposition can be found on StackExchange. It is based on the very nice idea by Ilya Bogdanov from below.

$\endgroup$
3
$\begingroup$

The cyclic sequence $a_1, a_2, \dots, a_n, a_1$ contains two occurrences of (zero or sign change), as it sums up to $0$. Each zero corresponds to a zero in either $1$st or $(n-1)$th row, or in both. Each sign change corresponds to a sign change in exactly one of the two rows (note that a sign change $a_n, a_1$ appears in the $(n-1)$th row!). So those two rows contain in total at least two occurrences.

Similarly, each occurrence in $a_1+a_2, a_2+a_3, \dots, a_n+a_1, a_1+a_2$ leads to an occurrence either in the $2$nd, or in the $(n-2)$th row (or in both), and so on. All in all, this gives $n-1$ occurrences in the first $n-1$ rows, as desired

$\endgroup$
  • $\begingroup$ Hi Ilya, thank you very much for your nice answer! I translated your sketch of proof into a very rigorous framework here on StackExchange. $\endgroup$ – Maximilian Janisch Sep 25 '19 at 22:35
0
$\begingroup$

EDIT: my answer below is wrong, as shown by Ilya Bogdanov's comment.

If there is no zero and no sign change on row $i$ among $a_{i,1}, \cdots, a_{i,i-1}$, then they are of the same sign and $a_{i,i}$ is of the opposite sign. Therefore there is some zero or sign change on every row.

$\endgroup$
  • 2
    $\begingroup$ Start with row $(1,-2,1)$; the second row will get no sign change. $\endgroup$ – Ilya Bogdanov Sep 25 '19 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.