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.


1 Answer 1


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}$.

  • $\begingroup$ Can you provide me a proof ot this fact? Also what if $P$ is semidefinite positive? $\endgroup$
    – xanz
    Apr 13, 2016 at 13:51
  • $\begingroup$ @ xanz . If you are interested by my post, then upvote it. $\endgroup$
    – user91684
    Apr 14, 2016 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, 2016 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, 2016 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, 2016 at 21:37

You must log in to answer this question.

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