Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T08:24:55Z http://mathoverflow.net/feeds/question/98434 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98434/eigenvalues-of-a-sum-of-hermitian-positive-definite-circulant-matrix-and-a-positi Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix Bullmoose 2012-05-30T22:53:46Z 2012-06-06T12:54:54Z <p>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}$.</p> <p>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$. </p> <p>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}\}$?</p> <p>From reading the previous MO questions on the similar topic <a href="http://mathoverflow.net/questions/34252/eigenvalues-of-ab-where-a-is-symmetric-positive-definite-and-b-is-diagonal" rel="nofollow">here</a> and <a href="http://mathoverflow.net/questions/4224/eigenvalues-of-matrix-sums" rel="nofollow">here</a> 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.</p> <p>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}\}$...</p> http://mathoverflow.net/questions/98434/eigenvalues-of-a-sum-of-hermitian-positive-definite-circulant-matrix-and-a-positi/98464#98464 Answer by Gerry Myerson for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix Gerry Myerson 2012-05-31T06:54:37Z 2012-05-31T06:54:37Z <p>Not sure what you'd accept as a characterization. </p> <p>Easy enough to work out the case $n=2$. We have $$C=\pmatrix{a&amp;b\cr b&amp;a\cr},\qquad D=\pmatrix{r&amp;0\cr0&amp;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. </p> http://mathoverflow.net/questions/98434/eigenvalues-of-a-sum-of-hermitian-positive-definite-circulant-matrix-and-a-positi/98920#98920 Answer by Bob Terrell for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix Bob Terrell 2012-06-05T23:16:44Z 2012-06-05T23:16:44Z <p>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$.</p> http://mathoverflow.net/questions/98434/eigenvalues-of-a-sum-of-hermitian-positive-definite-circulant-matrix-and-a-positi/98923#98923 Answer by Steve Flammia for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix Steve Flammia 2012-06-06T00:28:43Z 2012-06-06T00:45:09Z <p>This was too long to fit as a comment. I have no idea if this helps, but here's an observation. </p> <p>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$?</p> http://mathoverflow.net/questions/98434/eigenvalues-of-a-sum-of-hermitian-positive-definite-circulant-matrix-and-a-positi/98938#98938 Answer by Noah Stein for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix Noah Stein 2012-06-06T09:40:01Z 2012-06-06T09:40:01Z <p>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 &amp; e_i' \\ e_i &amp; 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]$.</p> <p>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 &amp; 1 \\ 1 &amp; 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$.</p> http://mathoverflow.net/questions/98434/eigenvalues-of-a-sum-of-hermitian-positive-definite-circulant-matrix-and-a-positi/98948#98948 Answer by Felix Goldberg for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix Felix Goldberg 2012-06-06T12:46:35Z 2012-06-06T12:54:54Z <p>I'd like to suggest another approach to the problem. Consider this theorem of Bai &amp; Golub (quoted as 2.1 in the paper <a href="http://gerard.meurant.pagesperso-orange.fr/trace_2009.pdf" rel="nofollow">http://gerard.meurant.pagesperso-orange.fr/trace_2009.pdf</a>):</p> <p><strong>Theorem</strong> 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:</p> <p>$\begin{bmatrix} \mu_{1} &amp; n \end{bmatrix} \begin{bmatrix}\mu_{2} &amp; \mu_{1} \\ b^{2} &amp; b\end{bmatrix}^{-1} \begin{bmatrix} n \\ 1 \end{bmatrix} \leq Tr(A^{-1})$</p> <p>I think you can use it together with Weyl's theorem to good effect.</p>