I am an engineer working in radar research. I came accross a problem on which I cannot seem to find literature. I can ask it in two different ways. Perhaps depending on the reader, the alternative question is easier to answer.

First way

  1. Assume I have a real symmetric matrix $\mathbf{C} \in \mathbb{R}^{M \times M}$.

  2. I know its eigenvalues that are non-negative: $\lambda_1, \ldots, \lambda_M$. And The trace of the matrix, i.e., the sum of all eigenvalues is $\lambda_1+\cdots+\lambda_M = M$.

  3. The diagonal matrix of eigenvalues is $\mathbf{\Lambda}$ and the matrix with eigenvectors in its colums is $\mathbf{V}$. The eigendecomposition is then $\mathbf{C} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^T$.

  4. Also the diagonal of the matrix is all ones, i.e., $\operatorname{diag}(\mathbf{C}) = [1,\ldots,1]$.

Define $$c_\max = \max\limits_{i\neq j}|c_{ij}|$$ where $c_{ij}$ is the element of $\mathbf{C}$ in the $i$-th row and $j$-th column. Given that I can choose $\mathbf{V}$ freely, i.e., any matrix with those eigenvalues, what is the minimum of the maximum of all off-diagonal elements that I can attain (in absolute value)? In other words what is the minimum of $c_\max$?

Second way

  1. Given that you have $M$ vectors $\{\mathbf{v}_1, \ldots, \mathbf{v}_M\}$.

  2. They are orthonormal $\mathbf{v}_i^T \mathbf{v}_j = \delta(i-j)$ by standard dot product definition.

  3. They have norm one $\| \mathbf{v}_i \|=1$ by standard dot product definition.

  4. Define the weighted inner product as $\mathbf{v}_i^T \mathbf{\Lambda} \mathbf{v}_j$, where $\mathbf{\Lambda} = \operatorname{Diag}(\lambda_1,\ldots,\lambda_M)$ and $\operatorname{trace}(\mathbf{\Lambda}) = M$.

  5. $\{\mathbf{v}_1,\ldots,\mathbf{v}_M\}$ also have norm one $\|\mathbf{v}_i\|_w=1$ by this new weighted inner product definition.

What is then the minimum value for the maximum inner product (in absolute value) among all vectors $\{\mathbf{v}_1,\ldots,\mathbf{v}_M\}$ given they can be chosen freely as far as they satisfy the conditions?

$$\min\limits_{\mathbf{v}_1,\ldots,\mathbf{v}_M} \left(\max\limits_{i\neq j}(\mathbf{v}_i^T\mathbf{\Lambda}\mathbf{v}_j)\right)$$

  • $\begingroup$ I think you should more tags like "linear algebra" to this question. $\endgroup$ Apr 25, 2012 at 13:37
  • $\begingroup$ Perhaps I am misunderstanding something... Given your description, the minimum absolute value among all the off-diagonals can be zero. For example, the identity matrix satisfies your hypothesis. Also, since the matrix that you have is a correlation matrix (positive semidefinite, ones on diagonal), we know that the off-diagonals must be bounded in absolute value by 1. $\endgroup$
    – Suvrit
    Apr 25, 2012 at 17:27
  • $\begingroup$ As far as I understand it, lambda's are prescribed, not free to choose. $\endgroup$
    – fedja
    Apr 25, 2012 at 19:27
  • $\begingroup$ I sort of forgot about this question. :) Yes, the eigenvalues are prescribed. Ahhh.. it seems nobody has an answer. $\endgroup$
    – mermeladeK
    May 17, 2013 at 18:38

2 Answers 2


I have a bound that will be of use to you. First, note that we can use the fact that the diagonal entries are all $1$s to relate $c_\mathrm{max}$ to the Frobenius norm of $C$: $$ \|C\|_F^2\leq M+M(M-1)c_\mathrm{max}^2. $$ This Frobenius norm is easy to work with, since it's just the 2-norm of the spectrum: $$ \|C\|_{F}^2 =\mathrm{Tr}[CC^\mathrm{T}] =\mathrm{Tr}[V\Lambda^2 V^\mathrm{T}] =\mathrm{Tr}[\Lambda^2] =\sum_{m=1}^M\lambda_m^2. $$ Rearranging then produces a lower bound on $c_\mathrm{max}$: $$ c_\mathrm{max}\geq\sqrt{\frac{1}{M(M-1)}\bigg(\sum_{m=1}^M\lambda_m^2-M\bigg)}. $$ Achieving equality in this lower bound certainly implies optimality. For example, consider the following matrix: $$ C =\left[\begin{array}{rrr}1~&-\frac{1}{2}&-\frac{1}{2}\\-\frac{1}{2}&1~&-\frac{1}{2}\\-\frac{1}{2}&-\frac{1}{2}&1~\end{array}\right]. $$ Here, $\Lambda=\mathrm{diag}(\frac{3}{2},\frac{3}{2},0)$, $c_\mathrm{max}=\frac{1}{2}$, and a quick calculation reveals that this achieves equality in our lower bound. But is this always possible?

Unfortunately, no. For example, it's impossible to achieve equality when $\Lambda=\mathrm{diag}(\frac{5}{3},\frac{5}{3},\frac{5}{3},0,0)$. But how do I know that?

Your question is intimately related to another problem that's of use in engineering: Design an ensemble of $M$ unit vectors in $\mathbb{R}^d$, where $M>d$, with the property that no two vectors have a large inner product in magnitude (i.e., you want the ensemble to be incoherent). For this problem, the Gram matrix of the vectors is playing the role of your $C$, and the Welch bound was developed to provide a lower bound on the coherence (your $c_\mathrm{max}$). For details, check out this blog entry.

Your problem has an important distinction from the incoherent design problem: you prescribe the spectrum of $C$. But there's a theorem that says achieving equality in the Welch bound necessitates that the spectrum of $C$ has $\frac{M}{d}$ with multiplicity $d$ and $0$ with multiplicity $M-d$. As such, you might as well consider the instance of your problem in which this is your spectrum (in this instance, the above bound on $c_\mathrm{max}$ is precisely the Welch bound).

The point of looking at this instance is to demonstrate how hard your problem actually is. While there are many Welch-bound achieving ensembles, it is also known that the Welch bound is not always achievable. For example, it is impossible to pack $5$ vectors in $\mathbb{R}^3$ with Welch-bound coherence (this was the source of my second example above, while the first example corresponded to the cube roots of unity in $\mathbb{R}^2$). It's also unknown in general which values of $M$ and $d$ enable Welch-bound equality (in fact, existence of such ensembles is equivalent to the existence of certain strongly regular graphs, and in many cases, existence is a long-standing problem).

For more information about this problem, google "equiangular tight frames" - you just opened a very interesting can of worms. :)

  • $\begingroup$ Very nice answer Dustin. I actually already checked the Welch bound but for some reason did not make the link to my problem. Ok, I was actually asking if all eigenvalues satisfying the Welch bound are feasible matrix of a matrix $C$, but since you said the Welch bound is not always reachable, that means they are not. $\endgroup$
    – mermeladeK
    May 18, 2013 at 4:47
  • $\begingroup$ I meant "I was going to ask". $\endgroup$
    – mermeladeK
    May 18, 2013 at 4:48
  • $\begingroup$ A quicker proof is that there are only finitely many matrices achieving the Welch bound, and infinitely many values of $\lambda_i$. $\endgroup$
    – Will Sawin
    May 21, 2013 at 2:45
  • $\begingroup$ Will, I disagree. There are infinitely many Welch-bound-achieving matrices, e.g.: arxiv.org/abs/1009.5730 $\endgroup$ May 21, 2013 at 3:32
  • $\begingroup$ Sorry, the corret thing to say is that of each dimension there are finitely many 1-dimensional spaces. Because each off-diagonal entry has to be $\pm c_{max}$. $\endgroup$
    – Will Sawin
    May 21, 2013 at 15:49

To add some insights into my discussion. I found out some stuff that might be interesting according to matrix perturbation theory.

So instead of asking as in the 1st question: given prescribed eigenvalues what is the minimum $c_{max}$? I tried to look into the problem of what is the possible eigenvalue densities given I have a prescribed $c_{max}$.

It goes like this... I compare my correlation matrix with the identity matrix. The diagonal elements of both matrices are 1's, therefore the perturbation is in the off-diagonal elements. The Weyl-Lidskii theorem states that:

$|\lambda_i-1|\leq ||\mathbf{C}-\mathbf{I}||_2$

where I write $|\lambda_i-1|$ because the eigenvalues of the identity matrix $(\mathbf{I})$ are $1$. But this just leads to some obvious bounds.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.