Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

I am en engineer working in radar research. I came accross a problem I cannot seem to find math literature on it.

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 which 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 eivenvalues 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}$ are the elements 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 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 contions?

$\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)$

Thank you

share|improve this question
    
I think you should more tags like "linear algebra" to this question. –  Felix Goldberg Apr 25 '12 at 13:37
    
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. –  Suvrit Apr 25 '12 at 17:27
    
As far as I understand it, lambda's are prescribed, not free to choose. –  fedja Apr 25 '12 at 19:27
    
I sort of forgot about this question. :) Yes, the eigenvalues are prescribed. Ahhh.. it seems nobody has an answer. –  mermeladeK May 17 '13 at 18:38
add comment

2 Answers

up vote 4 down vote accepted

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. :)

share|improve this answer
    
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. –  mermeladeK May 18 '13 at 4:47
    
I meant "I was going to ask". –  mermeladeK May 18 '13 at 4:48
    
A quicker proof is that there are only finitely many matrices achieving the Welch bound, and infinitely many values of $\lambda_i$. –  Will Sawin May 21 '13 at 2:45
    
Will, I disagree. There are infinitely many Welch-bound-achieving matrices, e.g.: arxiv.org/abs/1009.5730 –  Dustin G. Mixon May 21 '13 at 3:32
    
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}$. –  Will Sawin May 21 '13 at 15:49
show 3 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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