Given is a real positive lower triangular matrix with sum 1 in each row. Proof that I do not have a solution, and I think that this question is quite hard.

Let (m_1,m_2,...,m_k) be the column representation of the matrix and let s_j=\sum_{i=j}^k\ 1/m_{i,j}. My guess is that the matrix giving the extreme value for the sum on the left hand side is of the form m_j=(0,...,0,1/j,1/(j+1),...,1/k) (i think if it's true the induction wrt k might be used to prove it). Then s_j=(k(k+1)-j(j-1))/2 and the expression on the left hand side becomes 2\sum_{j=1}^k\frac{1}{k+j} for any k\ge 2 and 1 for k=1. sum_{j=1}^k\frac{1}{k+j} is always less than one.

QuoteOriginally posted by: Justin2000....My guess is that the matrix giving the extreme value for the sum on the left hand side is of the form m_j=(0,...,0,1/j,1/(j+1),...,1/k) (i think if it's true the induction wrt k might be used to prove it)...For this choice of the matrix, the sum is 7/6 for k=2. However, also for k=2, consider the matrix with m_1 = (1,sqrt(2)-1) and m_2 = (0,2-sqrt(2)). Then we have that the sum is at about 1.1716 > 7/6. This is also the worst case for k=2, I got it simply by solving some equations. I also intuitively thought that evenly balancing the weight in each row should be the worst. But this example shows that in the worst case, we have to move the weight in each row a little "to the right". For this reason, I also think that it is really hard to find the exact upper bound, but 2 would be just fine. Anyhow, finding the worst case example for any k by solving some equations becomes very technical for bigger values of k, and as we saw, this worst case is not very regular. So I thought there should be a more elegant way if we only want to have the upper bound 2. I also tried induction, but got stuck even if we replace the upper bound 2 by any constant c.

The claim is wrong, I am sorry. I got a counterexample where the sum grows as sqrt( log(k) ). This counterexample can be constructed as follows: Simply fill only sqrt( log( k ) ) of the columns, and let the other ones empty. Then we only obtain cost for these sqrt( log(k) ) many columns. We can arrange the matrix such that we obtain constant cost in each of these columns, and hence we have sqrt( log(k) ) cost. The details are a little tricky.