Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix - MathOverflow

Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix

2012-05-30T22:53:46Z

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}\}$...

Answer by Gerry Myerson for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix

2012-05-31T06:54:37Z

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.

Answer by Bob Terrell for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix

2012-06-05T23:16:44Z

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

Answer by Steve Flammia for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix

2012-06-06T00:28:43Z

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

Answer by Noah Stein for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix

2012-06-06T09:40:01Z

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

Answer by Felix Goldberg for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix

2012-06-06T12:46:35Z

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.