For any matrix polynomial \(P(\lambda ) = \sum _{j=0}^d \lambda ^j A_j \;,\; A_j \in \mathbb {F}^{m \times n}\), there is a multiset¹ \(\mathcal {S}\) comprising the key structural data of \(P\) relevant for applications. This structural data consists of the elementary divisors (finite and infinite) of \(P\), together with its left and right minimal indices. The basic inverse problem for matrix polynomials, then, consists of two parts:

Given a multiset \(\mathcal {S}\) of structural data and a choice of degree \(d\),

• (a) does there exist any matrix polynomial \(P\) of degree \(d\) (of any size \(m \times n\)) whose structural data multiset is exactly \(\mathcal {S}\)?

• (b) if such a matrix polynomial \(P\) exists, can one be explicitly constructed, especially in such a way that the structural data in \(\mathcal {S}\) is transparently visible in that \(P\) (e.g., in the spirit of the Kronecker canonical form), or at least can be exactly recovered from \(P\) without any numerical computation, only combinatorial manipulations?

Analogous questions can be immediately posed for matrix polynomials restricted to various classes of structured matrix polynomials important in applications, e.g., palindromic, alternating, or Hermitian matrix polynomials.

Much progress has been made on these questions in the last decade, although much remains to be understood. Some of the earliest results on these questions were for general quadratic [3] and quadratic palindromic matrix polynomials [4], where Kronecker-like quasi-canonical forms were found. In the 2015 paper [5], De Terán, Dopico, and Van Dooren completely solved the existence question (in part (a)) for general matrix polynomials of arbitrary degree over any infinite field \(\mathbb {F}\), giving simple necessary and sufficient conditions for realizability of a structural data multiset. However, the construction used to prove sufficiency in [5] produces a matrix polynomial realization in which the given data \(\mathcal {S}\) is usually not transparently visible anymore. Recent work in [8] has substantially remedied this deficiency, giving a complete solution for part (b) of the inverse problem for general matrix polynomials, but only over algebraically closed fields.

This talk, however, focuses more specifically on the inverse problem for Hermitian matrix polynomials. This class of matrix polynomials has an additional element in its structural data multiset, the sign characteristic, that is relevant for both theory and applications, playing an important role in the bifurcations of dynamical systems, as well as the behavior of eigenvalues under structured perturbations. First recognized and investigated in the seminal paper [7] as an important invariant of Hermitian polynomials under unimodular congruence, the sign characteristic consists of a plus or minus sign attached to each elementary divisor associated with a real or infinite eigenvalue. In [7], the authors considered sign characteristic only for regular Hermitian polynomials with no eigenvalues at \(\infty \). But more recently, the concepts and results in [7] concerning sign characteristic have been extended in [12] to include all Hermitian polynomials, both regular and singular, with or without eigenvalues at \(\infty \).

Now for general Hermitian matrix polynomials, there are several well-known (pairing) constraints on elementary divisors and minimal indices; e.g., for any Hermitian polynomial \(H(\lambda )\), the multiset of left minimal indices of \(H\) is identical to the multiset of the right minimal indices of \(H\). But are there any constraints on how signs can be attached to real and infinite elementary divisors? For Hermitian pencils it is known that there are no constraints on signs; any real or infinite elementary divisor may have any sign, in any combination with the signs of all of the pencil’s other elementary divisors. This follows immediately from the canonical form for Hermitian pencils found in [10].

For higher degree Hermitian polynomials, though, there is one known constraint on signs. This is the so-called signature constraint, first proved in [7] for regular Hermitian polynomials without any infinite elementary divisors, and extended to all Hermitian polynomials in [12]. For even degree Hermitian polynomials, the signature constraint says that the sum of the signs attached to all of the odd degree real and infinite elementary divisors is zero. The constraint is somewhat more complicated to state when the Hermitian polynomial \(H(\lambda )\) has odd degree — in this case the sum of the signs for odd degree elementary divisors of real eigenvalues together with those of the even degree elementary divisors of an infinite eigenvalue must equal the signature of the leading coefficient of \(H\) (hence the name of the condition).

Is the signature constraint the only condition on the sign characteristic? In the quadratic case, this has recently been shown to be true [11]. But for all degrees higher than \(2\), this is not so. Starting with degree \(3\), there are additional conditions on the sign characteristic that are independent of the signature constraint. Unfortunately, the techniques used in [11] to solve the quadratic Hermitian inverse problem do not easily extend to higher degrees, even to degree \(3\); there is a combinatorial explosion of cases that make this approach intractable. Thus it is reasonable to restrict the problem to something more manageable, yet still of some significance. Motivated by the recent investigations into the generic behavior in various structured classes of matrix polynomials [1, 2], it is sensible to restrict the question to Hermitian matrix polynomials in which all eigenvalues (including \(\infty \)) are simple. It is in this class that one can expect to find the structural data multisets that are generic for all Hermitian polynomials. Going forward, then, we make the simple eigenvalue assumption.

When a Hermitian polynomial has all simple eigenvalues, the signs attached to these eigenvalues can be naturally ordered to form a sign sequence. For an \(n \times n\) Hermitian polynomial of degree \(d\) with the maximum number (\(dn\)) of simple real eigenvalues, there are \(2^{dn}\) conceivable sign sequences, most of which cannot be realized by any degree \(d\)  Hermitian polynomial. Perhaps surprisingly, it is the order of the signs in a sign sequence that turns out to be crucial for Hermitian realizability, but in ways that are not immediately apparent. For example, consider a \(3 \times 3\) Hermitian matrix polynomial of degree \(4\), with \(12\) simple real eigenvalues. It is easy to see that the sign sequence \(\;\; ++++++------ \;\;\) satisfies the signature constraint for degree \(4\), but it can be shown that this sign sequence cannot be realized by any \(3 \times 3\) Hermitian polynomial of degree \(4\).

Is it possible to determine exactly which sign sequences are realizable and which are not? And what role, if any, the degree might play in the story? This talk answers these questions, introducing several new constraints on signs beyond the signature constraint, as well as an underlying group of symmetries acting on the collection of all sign sequences, that sheds additional light on this issue. The result of this analysis is a characterization of the sign sequences that are realizable by a Hermitian matrix polynomial with all simple eigenvalues, as well as a solution of the inverse problem for this class of Hermitian polynomials.

This characterization also allows us to get a quantitative sense for just how few of the possible sign sequences are actually realizable. Consider again the scenario above, i.e., \(n \times n\) Hermitian polynomials of degree \(d\) with the maximum number (\(dn\)) of simple real eigenvalues, in particular the special case of \(n=2\) with any even degree \(d \ge 4\). In this case the fraction of the \(2^{2d}\) possible sign sequences that satisfy the signature constraint is asymptotically \(O (\frac {1}{\,\sqrt {\pi d\,}\,})\) as \(d \rightarrow \infty \). By contrast, however, the characterization implies that the fraction of possible sign sequences that are actually Hermitian realizable is asymptotically \(O (\frac {1}{\,\,\mystrut {2.7mm} 2^{d}\,\,})\) as \(d \rightarrow \infty \). A reasonable conjecture is that this asymptotic behavior will persist for other values of \(n\) and \(d\). But this does at least show that the number of realizable sign sequences can not only be exponentially smaller than the number of all possible sign sequences, it can also even be exponentially smaller than the number of sign sequences that satisfy the signature constraint. Hence we see that the signature constraint is by itself very far from capturing the property of Hermitian realizability of sign sequences.

Finally, it is worth noting that the key tool for proving the necessity of these new constraints on the sign characteristic is an old theorem of Rellich on analytic decompositions of analytic Hermitian matrix-valued functions (see [12, Thm.2.1]). On the other hand, sufficiency of these new constraints is proved using the new technique of product realizations of matrix polynomials [6].

References

• [1]  F. De Terán, A. Dmytryshyn and F. M. Dopico, Generic symmetric matrix polynomials with bounded rank and fixed odd grade. SIAM J. Matrix Anal. Appl., 41 (2020), p.1033–1058.

• [2]  F. De Terán, A. Dmytryshyn and F. M. Dopico, Generic eigenstructures of Hermitian pencils. SIAM J. Matrix Anal. Appl., 45 (2024), p.260–283.

• [3]  F. De Terán, F.M. Dopico, and D.S. Mackey. A quasi-canonical form for quadratic matrix polynomials. In preparation.

• [4]  F. De Terán, F.M. Dopico, D.S. Mackey, and V. Perović. Quadratic realizability of palindromic matrix polynomials. Linear Algebra Appl., 567 (2019), p.202–262.

• [5]  F. De Terán, F.M. Dopico, and P. Van Dooren. Matrix polynomials with completely prescribed eigenstructure. SIAM J. Matrix Anal. Appl., 36 (2015), p.302–328.

• [6]  F.M. Dopico, D.S. Mackey, and P. Van Dooren. Product realizations of structural data for matrix polynomials. In preparation.

• [7]  I. Gohberg, P. Lancaster, and L. Rodman. Spectral analysis of self-adjoint matrix polynomials. Annals of Math., 112, no.1 (1980), p.33–71.

• [8]  R. Hollister. Inverse Problems for Polynomial and Rational Matrices. PhD Thesis, Western Michigan University, 2020.

• [9]  D.E. Knuth. The Art of Computer Programming. Vol. 2: Seminumerical Algorithms. Addison-Wesley, Reading, Massachusetts, 1981, 2nd Ed.

• [10]  P. Lancaster and L. Rodman. Canonical forms for Hermitian matrix pairs under strict equivalence and congruence. SIAM Rev, 47, no.3 (2005), p.407–443.

• [11]  D.S. Mackey and F. Tisseur, The Hermitian quadratic realizability problem. In preparation.

• [12]  V. Mehrmann, V. Noferini, F. Tisseur, and H. Xu, On the sign characteristics of Hermitian matrix polynomials. Linear Algebra Appl., 511 (2016), pp. 328–364.