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,3}<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$: If the Proposition is true for some $n-1\in\Bbb N$, fix some $(a_{i,j})_{i,j}$ as in the setup.
- If $a_{1,1}=0$, then the matrix obtained by cancelling the first column and last row of the $a_{i,j}$ matrix satisfies all assumptions of the Proposition and thus has at least $n-1$ zeros/sign switches. Since $a_{1,1}=0$, we have at least $n+1$ sign switches in the "full" matrix.
- If $a_{1,1}\neq 0$ I don't know how to proceed.
Best Answer
Here is a very rigorous proof of this Proposition based on the nice answer to this question by Ilya Bogdanov on MathOverflow. For his much easier to read sketch of proof, see here.
Lemma 1. If $n\in\Bbb N\setminus \{1\}$ and $a_1,a_2,\dots, a_n\in\Bbb R$ is such that $a_1\cdot a_n< 0$, then there is a $i\in\{1,2,\dots,n-1\}$ such that $a_i=0$ or $a_{i}\cdot a_{i+1}<0$.
Proof. Suppose otherwise. Let $\operatorname{sign}$ be the Sign function. Then $$-1=\operatorname{sign}(a_1\cdot a_n)=\operatorname{sign}\big(a_1\cdot a_n\cdot\prod_{j=2}^{n-1} a_j^2\big) = \operatorname{sign}\big(\prod_{j=1}^{n-1} a_j\cdot a_{j+1}\big)=1.$$ Contradiction. $\square$
Lemma 2. Let $n\in\Bbb N\setminus\{1\}$ and $a_1,a_2,\dots, a_n\in\Bbb R$ such that $\sum_{i=1}^n a_i=0$. For $j\in\{1,2,\dots,n\}$ define $$c(j) = \begin{cases}j+1, & j\neq n\\1, & j=n\end{cases}.$$ Then there are two indices $i_1\neq i_2\in\{1,\dots,n\}$ such that $\forall j\in\{i_1,i_2\}\colon a_j=0\lor a_j\cdot a_{c(j)}<0$.
Proof. If all the $a_i$ are $0$ then we are done. Otherwise let $i$ be an index such that $a_i\neq 0$. Since the $a_i$ sum to $0$, there is an index $j\neq i$ such that $a_i\cdot a_j<0$. Suppose WLOG that $j>i$. By Lemma 1 there is a $i\le i_1< j$ such that $a_{i_1}=0$ or $a_{i_1}\cdot a_{i_1+1}<0$. If $\operatorname{sign}(a_i)=\operatorname{sign}(a_1)$ then by Lemma 1 (applied to $a_j,a_{j+1}, \dots, a_n,a_1$) there is a $j\le i_2\le n$ such that $a_{i_2}=0$ or $a_{i_2}\cdot a_{c(i_2)}<0$. Same reasoning (on the "left side") gives us an $i_2$ if $\operatorname{sign}(a_i)\neq\operatorname{sign}(a_1)$. Clearly, $i_1\neq i_2$. $\square$
Proof of the Proposition. Let $i\in\{1,2,\dots,n-1\}$. Define for $j=1,2,\dots,n$ a "natural continuation of the $a_{i,j}$" $$d_{i,j} = \sum_{k=0}^{i-1} a_{1,\operatorname{mod}(j+k,n)}$$ where we use a modified $\operatorname{mod}$ function: $$\operatorname{mod}(n_1,n_2):=\begin{cases}n_1\mod n_2, & \text{if }n_1\mod n_2\neq 0 \\ n_2, & \text{if }n_1\mod n_2=0\end{cases}.$$
Some important observations (for all $i=1,2,\dots, n-1$): \begin{align} \tag 1 \label 1 d_{i,j} &= a_{i,j}, \text{ if } j\le n-i+1; \\ \tag 2 \label 2 d_{i,j} &=a_{1,j}+a_{1,j+1}+\dots+a_{1,n}+a_{1,1}+a_{1,2}+\dots+a_{1,j+i-1-n} \\ &= -(a_{1,j+i-n}+a_{1,j+i-n+1}+\dots + a_{1,j-1}) = -a_{n-i,j+i-n}, \text{ if } j > n-i+1; \\ \tag 3 \label 3 a_{i,n-i+1}&=a_{1,n-i+1}+a_{1,n-i+2}+\dots a_{1,n}=-a_{n-i,1} \\ \tag 4 \label 4 \sum_{j=1}^n d_{i,j} &= i\cdot\sum_{j=1}^n a_{1,j} = 0. \end{align}
Because of \eqref{3}, we can apply Lemma 2 to the $d_{i,j}$ for each $i$ and get that:
There are two functions $h_1,h_2\colon\{1,\dots,n-1\}\to \{1,\dots,n\}$ such that for all $i\in\{1,\dots,n-1\}$ we have $$ \big(d_{i,h_1(i)}=0 \lor d_{i,h_1(i)}\cdot d_{i,\operatorname{mod}(h_1(i)+1,n)}<0\big) \land \big(d_{i,h_2(i)}=0 \lor d_{i,h_2(i)}\cdot d_{i,\operatorname{mod}(h_2(i)+1,n)}<0\big) \land h_1(i)\neq h_2(i). $$
For every $i\in\{1,\dots,n-1\}$ we now use the following result:
The same reasoning applies to the function $h_2$. Let $$S:=\{(i,h_1(i))\mid i=1,\dots,\lceil (n-1)/2\rceil\}\cup \{(i,h_2(i))\mid i=1,\dots,\lceil (n-1)/2\rceil\}.$$ By the properties of $h_1,h_2$ (namely $h_1(i)\neq h_2(i)$), we know that the cardinality of $S$ is at least $n-1$. By using the above four reasonings, we can get a distinct pair $(\tilde i, \tilde j)$ corresponding to a zero or a sign switch for every pair $(i,j)\in S$.
So there are at least $n-1$ zeros/sign switches in the first $n-1$ rows. It follows that, since $a_{n,1}=0$, there are at least $n$ zeros/sign switches in total. $\square$