Consider two vectors $x=(x_1,x_2,\ldots,x_n)$, $y= (y_1,y_2,\ldots,y_n)$ such that all $x_i,y_i>0$ and \begin{align} \frac{y_1}{x_1}\le \frac{y_2}{x_2}\le\cdots\le \frac{y_n}{x_n} \end{align}

Now consider an upper triangular matrix $A$ with elements $a_{ij}\ge 0$ I want to prove (or come up with conditions on $A$ so) that \begin{align} \frac{[yA]_1}{[xA]_1}\le \frac{[yA]_2}{[xA]_2}\le\cdots\le \frac{[yA]_n}{[xA]_n} \end{align}

For example, for $n=3$, \begin{align} A = \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ 0 & a_{22} & a_{23} \\ 0 & 0 & a_{33} \end{array} \right) \end{align} We would want to show \begin{align} \frac{a_{11}y_1}{a_{11}x_1}\le \frac{a_{12}y_1 + a_{22}y_2}{a_{12}x_1+a_{22}x_2}\le \frac{a_{13}y_1 + a_{23}y_2 + a_{33}y_3}{a_{13}x_1 + a_{23}x_2 + a_{33}x_3} \end{align}

I am interested in proving this for general $n$.

Update: I'm thinking that a sufficient condition for this to hold is that the column sums are increasing in the column index. That is, for $n=3$, $a_{11} \le a_{12} + a_{22} \le a_{13}+a_{23}+a_{33}$. Is this true?

  • 3
    $\begingroup$ Your conjectured condition is not sufficient. Take $n=3$, $x=(2,1,1)$, $y=(1,1,1)$, and all entries of $A$ are zero except $a_{2,2}=1$ and $a_{1,3}=2$. Then $y/x=(1/2,1,1)$ is nondecreasing, as are the column sums $(0,1,2)$, but $yA/xA=(1/2,1,1/2)$ has a decrease. $\endgroup$
    – Tad
    Commented May 7, 2016 at 15:57

1 Answer 1


Necessarily, (*) each column of $A$ must be a non-zero vector.

The conditions when $n\leq 3$ are simple. When $n=2$, each $\geq 0$ matrix satisfying (*) answers the question. When $n=3$, and $A=\begin{pmatrix}a&b&c\\0&d&e\\0&0&f\end{pmatrix}\geq 0$, the NS condition is $\det(\begin{pmatrix}b&c\\d&e\end{pmatrix})\geq 0$. I think that we can generalize this result.

EDIT. Proposition. The required condition is: for every $i,j,l$ satisfying $i<l\leq j$, one has $\det(\begin{pmatrix}a_{i,j}&a_{i,j+1}\\a_{lj}&a_{l,j+1}\end{pmatrix})\geq 0$.

Outline of the proof. Let $C_i$ be the $i^{th}$ column of $A$, $(e_j)_j$ be the canonical basis of $\mathbb{R}^n$. The reasoning is by recurrence. Thus, it suffices to show that $y^TC_{n-1}/x^TC_{n-1}\leq y^TC_{n}/x^TC_{n}$, that is $f(x,y)=y^TC_{n-1}x^TC_n-x^TC_{n-1}y^TC_n\leq 0$. Note that $C_n=D+a_{nn}e_n$ where $d_n=0$; in the sequel, $C$ denotes $C_{n-1}$.

Thus $f(x,y)=(y^TCx^TD-x^TCy^TD)+a_{nn}(y^TCx_n-x^TCy_n)$. The key is that the first part does not depend on $x_n,y_n$ and the second one is always $\leq 0$. Finally, it remains to find the ad hoc condition ensuring that $g(x,y)=y^TCx^TD-x^TCy^TD\leq 0$. One has $g(x,y)=y^T(CD^T-DC^T)x$; the matrix $CD^T-DC^T$ is skew symmetric and its entries above the diagonal are the $\det(.)$ cited in the proposition. After, it's easy. You can convince yourself by expanding $g(.)$ with hand...

  • $\begingroup$ Late to the party here, but what is $D$? And $d_n$? $\endgroup$
    – Erik M
    Commented Feb 18, 2017 at 1:25
  • $\begingroup$ @ Erik M , $D$ is the vector $[d_1,\cdots,d_{n-1},d_n]^T$. $\endgroup$
    – user91684
    Commented Feb 19, 2017 at 22:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .