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

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|improve this question
add comment

5 Answers 5

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|improve this answer
4  
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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|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
add comment

I'd like to suggest another approach to the problem. Consider this theorem of Bai & Golub (quoted as 2.1 in the paper http://gerard.meurant.pagesperso-orange.fr/trace_2009.pdf):

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