I need upper and lower bounds as tight as possible for the following expression of the elements of a $n$ x $n$ matrix: $$ \sum_{i,j}\rho_{ij}^2-\frac{2}{n}\sum_i(\sum_j\rho_{ij})^2+\frac{(\sum\rho_{ij})^2}{n^2} $$

Assuming that $\rho_{i,i}=1$, that $0\leq \rho_{ij}=\rho_{ji}\leq 1$ and that i know the average of matrix entries $\mu=\frac{\sum_{i,j}\rho_{ij}}{n^2}$.

I don't know the individual elements $\rho_{ij}$.

Basically I'm tring to derive bounds (as a function of the average of the $\rho_{ij})$ for the trace of the matrix $(P(I_n-\textbf{1}/n))^2$ where $\textbf{1}$ is a nxn matrix of all ones, and $I_n$ is the identity matrix, and P is a positive semidefinite matrix.

What I'm expecting is that as the average tends to $1/n$, the upper bound should tend to coincide with the lower bound, but I cannot express that bound as a function of $\mu$ in a way that can prove this.


Let $m(\mu),M(\mu)$ be the $\min$ and the $\max$ as function of $\mu$. Note that $\mu\in[1/n,1]$ and $m(1/n)=M(1/n)=n-1$ and $m(1)=M(1)=0$. Yet, the curves associated to $m,M$ are very different; indeed, the curve for $m$ is decreasing and the curve for $M$ is as a parabola $y=-x^2$ with the top for $\mu \approx 0.6$.

EDIT. About the curve $m(\mu)$. The minimum is reached when the $(\rho_{ij})_{i<j}$ are equal to $\dfrac{\mu n-1}{n-1}$ and its value is $\dfrac{n^2(\mu-1)^2}{n-1}$.

The curve $M(\mu)$ is much more complicated. In particular, it is not derivable -there are many angular points (the left derivative is not equal to the right one). That follows is a conjecture based on experiments with Maple.

In the sequel, the $\rho_{ij}(\mu)$ realize $M(\mu)$ and $\mu$ increases from $1/n$ to $1$. Thus we begin with $\rho_{ij}=0$ and the sequence $\rho_{ij}(\mu)$ is non-decreasing (each component $(ij)$ is non-decreasing) as follows: only one $\rho_{ij}$ increases; when this $\rho_{ij}$ reaches $1$, it remains in $1$; after, another unique $\rho_{ij}$ increases until $1$, and so on. We stop when all the $\rho_{ij}$ are $1$. Thus it remains to see what is the ordering of the $\rho_{ij}$ (about the departure), that is not obvious...Indeed, the big problem is that the $\rho_{ij}$ do not play the same role!! -in other words, the studied expression is not symmetric in the $\rho_{ij}$.

For $n=4$, Maple uses this ordering: $\begin{pmatrix}*&1&3&5\\*&*&6&4\\*&*&*&2\\*&*&*&*\end{pmatrix}$ and for $n=5$, this one: $\begin{pmatrix}*&1&3&5&8\\*&*&4&9&6\\*&*&*&7&10\\*&*&*&*&2\\*&*&*&*&*\end{pmatrix}$.

| cite | improve this answer | |
  • $\begingroup$ Can you provide me a proof ot this fact? Also what if $P$ is semidefinite positive? $\endgroup$ – xanz Apr 13 '16 at 13:51
  • $\begingroup$ @ xanz . If you are interested by my post, then upvote it. $\endgroup$ – user91684 Apr 14 '16 at 12:29
  • $\begingroup$ I've upvoted since I'm surely interested, and I believe you have a proof. But in general, I don't like to upvote statements like this without proof because in case they are wrong my upvote might mislead other users. $\endgroup$ – xanz Apr 14 '16 at 13:45
  • 1
    $\begingroup$ @ xanz I see that the fans are not rushing to answer your question ...you need to encourage them; moreover , the cost for you is $0$ dollar. See my edit. $\endgroup$ – user91684 Apr 14 '16 at 13:56
  • $\begingroup$ Your comments are interesting. I indeed carried on several simulations on my own and I got similar conclusion as you.. As you said the solution for the max is not smooth at all, and the number of spikes within $\mu=(0;1)$ seems to be equal to $n-2$. The ordering is important, but several different configurations might lead to the same maximum value. I found an upper bound but not the optimal one. I don't have my notes with me now, so I'll post it as a separate answer asap. Thank you for spending your time on this rather specific problem. $\endgroup$ – xanz Apr 14 '16 at 21:37

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.