1
$\begingroup$

I need to construct a non-negative matrix with desired eigenvalues. To that end, I came up with a block matrix of the following form:

$$ \mathbf{M} = \begin{vmatrix} \mathbf{A} & \mathbf{b} \\\ \mathbf{c^T} & \it{d} \end{vmatrix} $$

Where matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ is free parameter, and vectors $\mathbf{b}$, $\mathbf{c} \in \mathbb{R}^{n}$ and scalar $\it{d}$ depend on $\mathbf{A}$ and a set of desired eigenvalues (given as diagonal elements of matrix $\mathbf{\Lambda} \in \mathbb{R}^{n \times n}$)

Equation that relates $\mathbf{c}$ to $\mathbf{A}$ and $\mathbf{\Lambda}$ is quite complicated and involves an inverse of the solution to a Sylvester equation. Namely

$$ \mathbf{c^T} = \left[\text{diag}(\mathbf{\Lambda}) - \mathbf{1^T}(\text{tr}(\mathbf{\Lambda}-\mathbf{A}) + \sigma)\right]\mathbf{K^{-1}} $$

where $\mathbf{K}$ is a solution to a following Sylvester equation:

$$ \mathbf{A}\mathbf{K}-\mathbf{K}\mathbf{\Lambda} = (\mathbf{A}-\sigma\mathbf{I}_n)\mathbf{1} \cdot\mathbf{1^T} $$

Now, I want to find constraints on parameter $\mathbf{A}$ which will render $\mathbf{M}$ non-negative. $\mathbf{A}$ itself must be non-negative of course, and $\mathbf{b}$ and $d$ have a straightforward dependence on $\mathbf{A}$, so it's easy. I have no idea, however, what to do with $\mathbf{c}$, because there's this $\mathbf{K^{-1}}$ which I don't have a solution for (only for $\text{vec}(\mathbf{K})$). How could I approach the question?


If needed, here's the dependence of $\mathbf{b}$ and $d$ on $\mathbf{A}$ and $\mathbf{\Lambda}$:

$$ \mathbf{b} = (\sigma \mathbf{I}_n - \mathbf{A})\mathbf{1} $$

$$ d = \text{tr}(\mathbf{\Lambda} - \mathbf{A}) + \sigma $$

and a solution for $\mathbf{K}$

$$ \text{vec}(\mathbf{K}) = (\mathbf{I}_n \otimes\mathbf{A} - \mathbf{\Lambda} \otimes \mathbf{I}_n)^{-1}(\mathbf{1} \otimes \mathbf{b}) $$

Given these relations, the resulting matrix $\mathbf{M}$ is equivalent to $$ \begin{vmatrix} \mathbf{A} & \mathbf{b} \\\ \mathbf{c^T} & \it{d} \end{vmatrix} = \begin{vmatrix} \mathbf{K} & \mathbf{1} \\\ \mathbf{1^T} & 1 \end{vmatrix} \begin{vmatrix} \mathbf{\Lambda} & \mathbf{0} \\\ \mathbf{0} & \sigma \end{vmatrix} \begin{vmatrix} \mathbf{K} & \mathbf{1} \\\ \mathbf{1^T} & 1 \end{vmatrix}^{-1} $$

As a last remark, $\mathbf{\Lambda}$ need not be diagonal, but its eigenvalues must be chosen as an input argument.

$\endgroup$
2
  • 1
    $\begingroup$ I think it's still an open problem to get a good characterization of the lists of complex numbers that can be the eigenvalues of a nonnegative matrices (google keywords: "nonnegative inverse eigenvalue problem"). As a consequence, you won't find an easy algorithm for this construction. $\endgroup$ Jun 11, 2013 at 6:47
  • $\begingroup$ D'oh! Thanks for pointing out the existing research, I was struggling to find that one. This is very sad indeed, cuz I had a very nice solution for 2x2 case (a is a scalar then), and thought it'll have a nice generalization to NxN, but apparently it's quite tough. $\endgroup$
    – Dmytro
    Jun 11, 2013 at 10:28

0

Your Answer

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

Browse other questions tagged or ask your own question.