# Minimum off-diagonal elements of a matrix with fixed eigenvalues

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

• 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

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

• 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

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.