MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have a real $n\times n$ matrix $\mathbf{C}$ that is Hermitian, positive-definite, and circulant. We know that its eigenvalues $\{\lambda_0,\ldots,\lambda_{n-1}\}$ are extraordinarily nice in that they are positive reals and are the output of the discrete Fourier transform of the top row of $\mathbf{C}$.

Consider the sum $\mathbf{C}+\mathbf{D}$ where $\mathbf{D}=\operatorname{diag}(d_0,\ldots,d_{n-1})$ such that $d_i>0$ for all $i$.

Is there a characterization of eigenvalues of $\mathbf{C}+\mathbf{D}$ in terms of $\{\lambda_0,\ldots,\lambda_{n-1}\}$ and $\{d_0,\ldots,d_{n-1}\}$?

From reading the previous MO questions on the similar topic here and here I understand that the chances of finding a nice characterization are pretty slim. However, I hold tepid hope due to the special structure of my particular problem.

The reason for this inquiry is that eventually I would like to minimize the trace of the inverse $\operatorname{Tr}[(\mathbf{C}+\mathbf{D})^{-1}]$ subject to various constraints on $\{d_0,\ldots,d_{n-1}\}$...

share|cite|improve this question

Not sure what you'd accept as a characterization.

Easy enough to work out the case $n=2$. We have $$C=\pmatrix{a&b\cr b&a\cr},\qquad D=\pmatrix{r&0\cr0&s\cr}$$ with $a\gt|b|$ and $r,s\gt0$. The eigenvalues of $C$ are $a\pm b$, the eigenvalues of $C+D$ are $$a+{r+s\over2}\pm\sqrt{\left({r-s\over2}\right)^2+b^2}$$ If we call the eigenvalues of $C$, $\lambda=a+b$ and $\mu=a-b$, the formula above becomes $${\lambda+\mu\over2}+{r+s\over2}\pm\sqrt{\left({r-s\over2}\right)^2+\left({\lambda-\mu\over2}\right)^2}$$ which has some pleasing symmetries.

share|cite|improve this answer
I imagine that the symmetries are due to the fact that, if you conjugate everything with the Fourier matrix $\Omega$, then $C$ becomes diagonal with entries $\lambda/\sqrt{2}$ and $\mu/{\sqrt{2}}$, while $D$ becomes circulant with entries $(r+s)/\sqrt{2}$ and $(r-s)/\sqrt{2}$ (I hope I am getting all the $\sqrt{2}$ factors right). So the two matrices play indeed a symmetric role. – Federico Poloni May 31 '12 at 12:41

Whatever ``characterize'' means will need to take account of the following construction: $C\otimes I$ has the same eigenvalues as $C$, $I\otimes D$ has the same eigenvalues as $D$, and $C\otimes I+I\otimes D\ $ has eigenvalues $\lambda_i+d_j$.

share|cite|improve this answer

This was too long to fit as a comment. I have no idea if this helps, but here's an observation.

Let $X$ denote the matrix which cyclicly permutes the columns in the standard basis by one unit, and $Z = FXF^*$ be it's Fourier transform (using a unitary normalization). Then $X$ and $Z$ form a representation of the Heisenberg group over the ring $\mathbb{Z}/n$. We have $X^n = Z^n = \omega^n = 1$, where $\omega = e^{2\pi i/n}$, and $XZ=\omega ZX$. The elements of the form $X^iZ^j$ form a basis for $n\times n$ matrices which is orthogonal in the trace inner product and is unitary. Your matrices $C$ and $D$ can be expanded as $C = \sum_{j\in\mathbb{Z}/n} \lambda_j X^j$ and $D = \sum_{k\in\mathbb{Z}/n} d_k Z^k = \sum_{k\in\mathbb{Z}/n} d_k F X^k F^*$. Perhaps there is some way to leverage this observation to generate constraints, maybe by estimating powers of $C+D$?

share|cite|improve this answer

If your constraints on the $d_i$ allow it and you are interested in numerical solutions, you can cast the problem as a semidefinite program. To do so, introduce scalar variables $t_1,\ldots, t_n$. Let $e_i$ denote the $i^{\text{th}}$ unit column vector. Then by Schur complements, \[ \begin{bmatrix} t_i & e_i' \\\ e_i & C+D\end{bmatrix}\succeq 0 \] if and only if $t_i \geq e_i'(C+D)^{-1}e_i \equiv \left[(C+D)^{-1}\right]_{ii}$. Putting in this semidefinite constraint for all $i$ and introducing $t = \sum_i t_i$ is thus equivalent to $t \geq \text{Tr} \left[(C+D)^{-1}\right]$.

Assuming your constraints on the $d_i$ are linear equations, inequalities, or otherwise expressible in terms of matrix positive semidefiniteness, you can minimize $t$ subject to these constraints and the above semidefiniteness constraints to solve the problem numerically using SeDuMi, SDPT3, etc. It is possible to include precisely the constraint $d_i >0$ in the semidefinite program by writing \[ \begin{bmatrix} d_i & 1 \\\ 1 & f_i\end{bmatrix}\succeq 0, \] for some auxiliary variables $f_i$, but things will be better behaved numerically if you are willing to change these constraints to $d_i\geq 0$.

share|cite|improve this answer
P.S.: While it is eluding me at the moment, I feel like there is a more efficient way of encoding the trace constraint in a semidefinite program than the one I have given. – Noah Stein Jun 6 '12 at 9:41

I'd like to suggest another approach to the problem. Consider this theorem of Bai & Golub (quoted as 2.1 in the paper

Theorem If $A$ is a symmetric real positive definite $n \times n$ matrix whose eigenvalues lie in $[a,b]$, $\mu_{1}=tr(A),\mu_{2}=||A||^{2}_{F}$, then:

$ \begin{bmatrix} \mu_{1} & n \end{bmatrix} \begin{bmatrix}\mu_{2} & \mu_{1} \\\\ b^{2} & b\end{bmatrix}^{-1} \begin{bmatrix} n \\\\ 1 \end{bmatrix} \leq Tr(A^{-1})$

I think you can use it together with Weyl's theorem to good effect.

share|cite|improve this answer
What does the $\alpha$ in $\mu_{\alpha}$ do? – Gerry Myerson Jun 6 '12 at 12:52
Nothing, it's a typo. Thanks for spotting it. – Felix Goldberg Jun 6 '12 at 12:55

Your Answer


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.