Inequality for matrix with rows summing to 1

Question

Let $A$ be real matrix with $M > 1$ rows and $K > 2$ columns, and each entry $a_{m,k} \in (0,1)$, with each row summing to $1$. For all $m$ $$ \sum_{k=1}^{K} a_{m,k} = 1 $$ I want to find out if for any row $m$ $$ \sum_{k=1}^{K} \frac{(a_{m,k})^2}{\sum_{i=1}^{M} a_{i,k}} \geq \frac{1}{M} $$ I believe that I have proof that it holds for $K = 2$ columns. For $K > 2$ I have tried to used gradient descent to find counterexamples but I have not found any.

• I notice $\sum_{k=1}^{K} \sum_{m=1}^{M} a_{m,k} = M$.
• It seems to be a quite tight bound without further assumptions, when looking at SGD cases. The next thing I want to look at is whether the left hand side is convex in $A$.
• Maybe I can reduce problems with $M > 2$ rows to a simpler problem with $M = 2$ rows, where some rows are summed. However, I think it is difficult to maintain the constraints on the values for the second row in that case.

I will be grateful for any pointers. Thanks.

(Context: I am thinking of the rows as agents having beliefs about a discrete rv with $K$ outcomes. Can they make a bet where they split a pot of $1$ dollar according to the fraction of probability mass they have assigned to the outcome, and if so what is the expected fraction for an agent $m$ and when if ever would it be less than $1/M$ dollar?)

Answer 1

If I am not missing something, this seems a direct application of Titu's lemma $$ \sum_{k=1}^K \frac{x_k^2}{y_k} \geq \frac{\left(\sum_{k=1}^K x_k \right)^2}{\sum_{k=1}^K y_k}, \quad x_k \geq 0, y_k > 0, $$ which is quickly proved using Cauchy-Schwarz's inequality (as shown in the link above). Just set $$ x_k = a_{m,k}, \quad y_k = \sum_{i=1}^M a_{i,k} $$ and simplify the RHS using the two relations you already wrote in your question.

Answer 2

$\renewcommand\bar\overline$We have this even stronger result: \begin{equation} g(A):=\sum_{m=1}^M \sum_{k=1}^K \frac{(a_{m,k})^2}{\sum_{i=1}^M a_{i,k}}\ge1. \tag{1}\label{1} \end{equation}

Indeed, the function $g$ is convex, since the second derivative of \begin{equation} \frac{(a+bt)^2}{A+Bt} \end{equation} in $t$ at $t=0$ is $2 (A b - a B)^2/A^3\ge0$ if $A>0$.

Also, $g(A)$ is invariant with respect to any permutations of the rows of $A$; that is, $g(A_\pi)=g(A)$ for any $\pi\in S_M$, where $S_M$ is the set of all permutations of the set $[M]:=\{1,\dots,M\}$ and $A_\pi$ is the matrix obtained from $A$ by applying the permutation $\pi$ to the row indices of $A$.

Consider the row-averaged version of matrix $A$: \begin{equation} \bar A:=\frac1{M!}\sum_{\pi\in S_M}A_\pi. \end{equation} By the convexity and the row-permutation invariance of $g$, \begin{equation} g(\bar A)\le\frac1{M!}\sum_{\pi\in S_M}g(A_\pi)=g(A). \end{equation} But all the rows of $\bar A$ are the same. So, $g(\bar A)=1$, and inequality \eqref{1} follows.