Sign patterns that require real, nonreal or pure imaginary eigenvalues

We characterize the n-by-n sign pattern matrices that require all real, all nonreal, and all pure imaginary eigenvalues. Characterization of sign patterns that allow a real eigenvalue and those that allow a nonreal eigenvalue then follow. Some related specialized results and a characterization of sign patterns that allow a positive real eigenvalue are included.     

Allow problems concerning spectral properties of sign pattern matrices: A survey

An n×n sign pattern matrix has entries in {+,-,0}. This paper surveys the following problems concerning spectral properties of sign pattern matrices: sign patterns that allow all possible spectra (spectrally arbitrary sign patterns); sign patterns that allow all inertias (inertially arbitrary sign patterns); sign patterns that allow nilpotency (potentially nilpotent sign patterns); and sign patterns that allow stability (potentially stable sign patterns). Relationships between these four classes of sign patterns are given, and several open problems are identified.     

± sign pattern matrices that allow orthogonality

A sign pattern A is a ± sign pattern if A has no zero entries. A allows orthogonality if there exists a real orthogonal matrix B whose sign pattern equals A. Some sufficient conditions are given for a sign pattern matrix to allow orthogonality, and a complete characterization is given for ± sign patterns with n − 1 ⩽ N₋(A) ⩽ n + 1 to allow orthogonality.     

On the number of real critical points of logarithmic derivatives and the Hawaii conjecture

For a given real entire function φ in the class U _2n ^*, n ≥ 0, with finitely many nonreal zeroes, we establish a connection between the number of real zeroes of the functions Q[φ] = (φ′/φ)′ and Q ₁[φ] = (φ″/φ′)′. This connection leads to a proof of the Hawaii Conjecture (T. Craven, G. Csordas, and W. Smith [5]), which states that if φ is a real polynomial, then the number of real zeroes of Q[φ] does not exceed the number of nonreal zeroes of φ.     

Sign patterns allowing nilpotence of index 3

Suppose P is a property referring to a real matrix. We say that a sign pattern A allows P if there exists at least one matrix with the same sign pattern as A that has the property P. In this paper, we study sign patterns allowing nilpotence of index 3. Four methods for constructing sign patterns that allow nilpotence of index 3 are obtained. All tree sign patterns that allow nilpotence of index 3 are characterized. Sign patterns of order 3 that allow nilpotence are identified.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.     

Required nonzero patterns for nonsingular sign regular matrices

An n×n real matrix is called sign regular if, for each k(1?k?n), all its minors of order k have the same nonstrict sign. The zero entries which can appear in a nonsingular sign regular matrix depend on its signature because the signature can imply that certain entries are necessarily nonzero. The patterns for the required nonzero entries of nonsingular sign regular matrices are analyzed.     

When does the inverse have the same sign pattern as the transpose?

By a sign pattern (matrix) we mean an array whose entries are from the set {+, –, 0}. The sign patterns A for which every real matrix with sign pattern A has the property that its inverse has sign pattern A ^T are characterized. Sign patterns A for which some real matrix with sign pattern A has that property are investigated. Some fundamental results as well as constructions concerning such sign pattern matrices are provided. The relation between these sign patterns and the sign patterns of orthogonal matrices is examined.     

Eigenvalue distribution of certain ray patterns

In this paper, the eigenvalue distribution of complex matrices with certain ray patterns is investigated. Cyclically real ray patterns and ray patterns that are signature similar to real sign patterns are characterized, and their eigenvalue distribution is discussed. Among other results, the following classes of ray patterns are characterized: ray patterns that require eigenvalues along a fixed line in the complex plane, ray patterns that require eigenvalues symmetric about a fixed line, and ray patterns that require eigenvalues to be in a half-plane. Finally, some generalizations and open questions related to eigenvalue distribution are mentioned.     

Hermite—Fejér Interpolation for Rational Systems

This paper considers Hermite—Fejér and Grünwald interpolation based on the zeros of the Chebyshev polynomials for the real rational system P _n (a ₁ , . . . , a _n ) with the nonreal poles in {a}ⁿ _k=1 C\[-1,1] paired by complex conjugation. This extends some well-known results of Fejér and Grünwald for the classical polynomial case. July 11, 1996. Dates revised: January 6, 1997 and July 30, 1997.     

The double sign of a real division algebra of finite dimension greater than one

For any real division algebra A of finite dimension greater than one, the signs of the determinants of left multiplication and right multiplication by an element a ∈ A?{0} are shown to form an invariant of A, called its double sign. For each n ∈ {2, 4, 8}, the double sign causes the category $\mathbb {D}_nFor any real division algebra A of finite dimension greater than one, the signs of the determinants of left multiplication and right multiplication by an element a ∈ A?{0} are shown to form an invariant of A, called its double sign. For each n ∈ {2, 4, 8}, the double sign causes the category $\mathbb {D}_n$ of all n‐dimensional real division algebras to decompose into four blocks. The structures of these blocks are closely related, and their relationship is made precise for a sample of full subcategories of $\mathscr {D}_n$.     

On the Spectra of Striped Sign Patterns

Sign patterns consisting of some positive and some negative columns, with at least one of each kind, are shown to allow any self-conjugate spectrum, and thus to allow any inertia. In the case of the n ×n sign pattern with all columns positive, given any self-conjugate multiset consisting of n -1 complex numbers supplemented by a sufficiently large positive number, it is shown how to construct a positive normal matrix whose spectrum is this multiset. Thus, the positive sign pattern allows any inertia with at least one positive eigenvalue.     

On the Spectra of Striped Sign Patterns

Sign patterns consisting of some positive and some negative columns, with at least one of each kind, are shown to allow any self-conjugate spectrum, and thus to allow any inertia. In the case of the n × n sign pattern with all columns positive, given any self-conjugate multiset consisting of n m 1 complex numbers supplemented by a sufficiently large positive number, it is shown how to construct a positive normal matrix whose spectrum is this multiset. Thus, the positive sign pattern allows any inertia with at least one positive eigenvalue.     

Inverse problem and the trace formula for the Hill operator, II

Consider the Hill operator on where is a 1-periodic real potential and The spectrum of T is absolutely continuous and consists of intervals separated by gaps . Let be the Dirichlet eigenvalue of the equation on the interval [0,1]. Introduce the vector with components and where the sign or for all . Using nonlinear functional analysis in Hilbert spaces we show, that the mapping is a real analytic isomorphism. In the second part a trace formula for is proved. Received December 22, 1997; in final form July 7, 1998     

Symmetric sign patterns with maximal inertias

The inertia of an n by n symmetric sign pattern is called maximal when it is not a proper subset of the inertia of another symmetric sign pattern of order n. In this note we classify all the maximal inertias for symmetric sign patterns of order n, and identify symmetric sign patterns with maximal inertias by using a rank-one perturbation.     

Potentially nilpotent and spectrally arbitrary even cycle sign patterns

An n × n sign pattern S_n is potentially nilpotent if there is a real matrix having sign pattern S_n and characteristic polynomial xⁿ. A new family of sign patterns C_n with a cycle of every even length is introduced and shown to be potentially nilpotent by explicitly determining the entries of a nilpotent matrix with sign pattern C_n. These nilpotent matrices are used together with a Jacobian argument to show that C_n is spectrally arbitrary, i.e., there is a real matrix having sign pattern C_n and characteristic polynomial for any real μ_i. Some results and a conjecture on minimality of these spectrally arbitrary sign patterns are given.     

Size of nodal domains of the eigenvectors of a graph

Consider an eigenvector of the adjacency matrix of a G(n,p) graph. A nodal domain is a connected component of the set of vertices where this eigenvector has a constant sign. It is known that with high probability, there are exactly two nodal domains for each eigenvector corresponding to a nonleading eigenvalue. We prove that with high probability, the sizes of these nodal domains are approximately equal to each other.     

Sums of exponential functions having only real zeros

Let H_n(z) be the function of a complex variable z defined by where the summation is over all 2ⁿ possible plus and minus sign combinations, the same sign combination being used in both the argument of G and in the exponent. The numbers and are assumed to be positive, and G is an entire function of genus 0 or 1 that is real on the real axis and has only real zeros. Then the function H_n(z) has only real zeros.     

Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns

In this work, we study the kth local base, which is a generalization of the base, of a primitive non-powerful nearly reducible sign pattern of order n ≥ 7. We obtain the sharp bound together with a complete characterization of the equality case, of the kth local bases for primitive non-powerful nearly reducible sign patterns. We also show that there exist “gaps” in the kth local base set of primitive non-powerful nearly reducible sign patterns.     

Sign patterns for eigenmatrices of nonnegative matrices

For a square (0,?1,??1) sign pattern matrix S, denote the qualitative class of S by Q(S). In this article, we investigate the relationship between sign patterns and matrices that diagonalize an irreducible nonnegative matrix. We explicitly describe the sign patterns S such that every matrix in Q(S) diagonalizes some irreducible nonnegative matrix. Further, we characterize the sign patterns S such that some member of Q(S) diagonalizes an irreducible nonnegative matrix. Finally, we provide necessary and sufficient conditions for a multiset of real numbers to be realized as the spectrum of an irreducible nonnegative matrix M that is diagonalized by a matrix in the qualitative class of some S ² NS sign pattern.