# positiveness of the inverse solution to Sylvester equation

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.

-
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. – Federico Poloni Jun 11 '13 at 6:47
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. – Dmytro Jun 11 '13 at 10:28