13
$\begingroup$

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

$\endgroup$

4 Answers 4

2
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ May 31, 2012 at 12:41
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Noah Stein
    Jun 6, 2012 at 9:41
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What does the $\alpha$ in $\mu_{\alpha}$ do? $\endgroup$ Jun 6, 2012 at 12:52
  • $\begingroup$ Nothing, it's a typo. Thanks for spotting it. $\endgroup$ Jun 6, 2012 at 12:55
  • $\begingroup$ The link to your cited paper is broke. Could you please provide the title of the paper? Thank you. $\endgroup$
    – Hans
    Oct 23, 2019 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.