# Can we make a matrix stable by changing its upper-left submatrix?

A matrix $A$ is called strictly stable if its eigenvalues have negative real parts. Given a matrix $A \in \mathbb{R}^{n \times n}$, suppose we can change its upper-left $k \times k$ submatrix at will (i.e., we can change the entries $a_{ij}, 1 \leq i,j \leq k$). Can we make it strictly stable?

Example: if $$A = \begin{pmatrix} 1 & 1 \\ 2 & -1 \end{pmatrix}$$ and we allow ourselves to change the upper-left $1 \times 1$ submatrix (i.e., just the top-left entry) one can verify that the answer is yes. Changing the top left entry to $-3$ we obtain $$\begin{pmatrix} -3 & 1 \\ 2 & -1 \end{pmatrix}$$ and one can verify that this is indeed strictly stable. On the other hand, if $$A = \begin{pmatrix} 1 & 1 \\ 2 & 0 \end{pmatrix}$$ then the answer is negative. No matter what we put in the top-left entry, the matrix will not be strictly stable, because its determinant will be negative (which rules out strict stability for $2 \times 2$ matrices).

Question: is there a polynomial-time algorithm to decide on a yes/no answer?

In the case where the matrix $A$ is symmetric, I believe the answer is that the principal submatrix corresponding to the rows and columns $k+1,\ldots,n$ should be negative definite. However, I'm not sure what the answer is if we do not assume $A$ is symmetric.