2
$\begingroup$

The Routh-Hurwitz criterion explicitly specifies a finite set of inequalities on the coefficients of a polynomial, necessary and sufficient that all zeros lie in the unit circle or in the left half complex plane.

Is there a similar set of explicit inequalities on the coefficients of a (real or complex) matrix, necessary and sufficient that all eigenvalues lie in the unit circle or in the left half complex plane? I am not looking for a decision algorithm (one could just compute the eigenvalues...). Instead, I'd like to have explicit inequalities for 2 x 2 and 3 x 3 matrices (with an elegant proof), and a scheme to generate the inequalities for larger matrices.

(The related page Routh-Hurwitz for eigenvalues is very old and less specific. It gives no explicit inequalities, hence does not answer my question.)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Hmm, a "similar set". Is the following similar enough? I do not know. But it has to be pointed out that there are of course very nice and largely tractable numerical tests for stability of matrices (and much better than attempting to compute the eigenvalues). Let $I$ denote the identity matrix. The spectrum of a (real or complex) matrix $A$ is in the left half plane, if and only if there is a positive definite, Hermitian $P$ such that $$A^* P + PA = -I.$$ For the unit circle the respective equation is $$ A^*PA - P = -I.$$ These are the so-called Lyapunov equations. The answer is a bit tongue in cheek, but still. First you have a bunch of linear equalities for the entries of $P$ using the coefficients in $A$. Then you need to check positive definiteness. To do this numerically, as an example Cholesky factorization has been proposed.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are these equations uniquely solvable for a Hermitian $P$? If always yes, this would be a sensible solution of my problem. If not, one would have to test infinitely many matrices $P$ to see whether one of them is positive definite.... $\endgroup$
    – Arnold Neumaier
    Commented Dec 12, 2022 at 9:46
  • 1
    $\begingroup$ The eigenvalues of the Lyapunov operator $P\mapsto A^*P+PA$ (on the space of square matrices) are of the form $\lambda + \bar{\mu}$, where$\lambda,\mu \in \sigma(A)$. By standard linear equations theory, there is a unique solution if and only if none of these eigenvalues is $0$. So if $A$ has eigenvalues in the left half plane, then the solution is unique and if you happen to have no or no unique solution it is clear that $A$ is not Hurwitz. Similar, for the discrete-time case. $\endgroup$
    – Fabian Wirth
    Commented Dec 12, 2022 at 9:58
1
$\begingroup$

The very boring answer, of course, is:

  1. write down the characteristic polynomial $p(x) = \det(A-xI)$
  2. write down the Routh-Hurwitz criterion for $p$, expanding everything in terms of the matrix coefficients.

This is a scheme to generate them. I don't think there is a simple form for it in terms of the matrix coefficients for a general $n$, though.

For real $2\times 2$ matrices, I can tell you the explicit form because I used it very recently in a preprint: \begin{align} Tr(A) &\leq 0,\\ \det(A) &\geq 0 \end{align} is a necessary and sufficient condition for the eigenvalues of a $2\times 2$ matrix to be in the (closed) left half-plane, and \begin{align} \det(A) &\leq 1,\\
Tr(A) &\leq 1 +\det(A),\\ -Tr(A) &\leq 1 +\det(A)\\ \end{align} for the unit disc.

Just as a bonus, I find this picture particularly pretty: enter image description here

The cyan fat cross is the set of real $2\times 2$ matrices with eigenvalues in the unit disc and $A_{11}=A_{22}$, intersected with $[-2,2]^3$ (the four arms extend to infinity). The lines where two surfaces of the boundary cross correspond to matrices of the form $\begin{bmatrix}0 & a\\ 1/a & 0\end{bmatrix}$, $\pm \begin{bmatrix}1 & a\\ 0 & 1\end{bmatrix}$, $\pm \begin{bmatrix}1 & 0\\ a & 1\end{bmatrix}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The final formulas in the 2x2 case don't suggest that nothing reasonably elegant can be found in higher dimensions. Of course the whole point of the question is that i want nice expressions to work with. Not the detour over the characteristic polynomial, which produces something numerically unstable. $\endgroup$
    – Arnold Neumaier
    Commented Apr 20, 2021 at 18:36
  • $\begingroup$ ''I don't think there is a simple form for it in terms of the matrix coefficients for a general n, though.'' Since I think the opposite, could you please explain why you think so? $\endgroup$
    – Arnold Neumaier
    Commented Apr 21, 2021 at 11:32
  • 1
    $\begingroup$ @ArnoldNeumaier I cannot really formulate a reason; you are right in pointing that out. Note that the formulas I wrote for the 2x2 case are also expressed naturally in terms of the entries of the characteristic polynomial, rather than the matrix entries. I'd be (pleasantly) surprised if there is a simple formula that has not been found already, since the result for polynomials has been out for more than a century; but sometimes egregious results go unnoticed. $\endgroup$
    – Federico Poloni
    Commented Apr 21, 2021 at 11:39
  • 1
    $\begingroup$ Anyhow, "nice expressions to work with" and "numerically stable" usually don't go hand in hand: for instance, Gaussian elimination with partial pivoting or QR vs. Cramer's rule, or the classical formula to solve quadratic equations vs. its stable variant. So you might need to choose one or the other in the end. $\endgroup$
    – Federico Poloni
    Commented Apr 21, 2021 at 11:49

You must log in to answer this question.

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