0
$\begingroup$

Given vectors ${\bf v}, {\bf w} \in [0,1]^n$ , where $n \in \mathbb{N} \setminus \{0\}$, and $\alpha > 0$, I would like to find the eigenvalues of the following matrix.

$$\operatorname{diag}({\bf v}) - {\bf v} {\bf v}^\top - \alpha({\bf v} - {\bf w})({\bf v} - {\bf w})^\top$$

I can have the eigenvalues of ${\bf v} {\bf v}^\top - \operatorname{diag}({\bf v})$ and $\alpha({\bf v}-{\bf w})({\bf v}-{\bf w})^\top$ separately to maybe bound the eigenvalues, but I am seeking for a closed form, especially for the smallest one.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I don't believe that such a closed form formula can exist, at least for what I would consider any reasonable definition of "closed form". For example, if $\mathbf{v} = (1,-1,2,-1,1)$ and $\mathbf{w} = (-1,1,0,-1,1)$ and $\alpha = 1$ then this matrix has characteristic polynomial $x^5 + 18x^4 + 6x^3 - 56x^2 + 9x + 6$, which I believe (I haven't checked super carefully) has Galois group $S_5$ and so the roots cannot be expressed in terms of radicals. $\endgroup$
    – Nathaniel Johnston
    Commented May 16, 2023 at 12:50
  • $\begingroup$ yes, it's a rank-1 or rank-2 update of the diagonal matrix. $\endgroup$
    – CereIssou
    Commented May 16, 2023 at 13:16
  • 1
    $\begingroup$ @CereIssou Then, using the matrix determinant lemma, you may find the characteristic polynomial in closed-form. Finding the roots in closed-form, however... $\endgroup$
    – Rodrigo de Azevedo
    Commented May 16, 2023 at 13:17

1 Answer 1

Reset to default
0
$\begingroup$

The smallest eigenvalue can be found (approximately) via the following semidefinite program (SDP).

$$ \begin{array}{ll} \underset {t} {\text{maximize}} & t \\ \text{subject to} & \operatorname{diag}({\bf v}) - {\bf v} {\bf v}^\top - \alpha({\bf v} - {\bf w})({\bf v} - {\bf w})^\top \succeq t \, {\bf I}_n \end{array} $$

Improve this answer
$\endgroup$
7
  • $\begingroup$ It can also be found by minimizing the Rayleigh quotient, no need to use something more complicated. $\endgroup$
    – Federico Poloni
    Commented Jun 9, 2023 at 14:22
  • $\begingroup$ @FedericoPoloni Do you mean the following? $$\min_{ \| {\bf x} \|_2 = 1} {\bf x}^\top {\bf A} \, {\bf x}$$ $\endgroup$
    – Rodrigo de Azevedo
    Commented Jun 9, 2023 at 14:59
  • $\begingroup$ Yes! en.wikipedia.org/wiki/Rayleigh_quotient . $\endgroup$
    – Federico Poloni
    Commented Jun 9, 2023 at 15:22
  • $\begingroup$ @FedericoPoloni But it's a non-convex QCQP. I can use a Lagrange multiplier and obtain $\bf (A - \mu I) x = 0$, but how do I find the minimal $\mu$? $\endgroup$
    – Rodrigo de Azevedo
    Commented Jun 9, 2023 at 15:29
  • $\begingroup$ You can remove the constraint by minimizing $\frac{x^TAx}{x^Tx}$, and convert it to the largest eigenvalue by shifting the matrix (by an amount that you can determine via norm estimates). Then there are various methods in linear algebra literature, the simplest one being the power method. But even minimizing the Rayleigh quotient with standard optimization techniques works fine, I have given similar problems to students as final projects in the past. $\endgroup$
    – Federico Poloni
    Commented Jun 9, 2023 at 17:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .