Sign patterns that require almost unique rank

A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive (respectively, negative, zero) entry of B by + (respectively, −, 0). For a sign pattern matrix A, the sign pattern class of A, denoted Q(A), is defined as {B:sgn(B)=A}. The minimum rank mr(A) (maximum rank MR(A)) of a sign pattern matrix A is the minimum (maximum) of the ranks of the real matrices in Q(A). Several results concerning sign patterns A that require almost unique rank, that is to say, the sign patterns A such that MR(A) = mr(A) + 1, are established and are extended to sign patterns A for which the spread is d=MR(A)-mr(A). A complete characterization of the sign patterns that require almost unique rank is obtained.     

Construction and nonnegativity of sign idempotent sign pattern matrices

In this paper, we modify Eschenbach’s algorithm for constructing sign idempotent sign pattern matrices so that it correctly constructs all of them. We find distinct classes of sign idempotent sign pattern matrices that are signature similar to an entrywise nonnegative sign pattern matrix. Additionally, if for a sign idempotent sign pattern matrix A there exists a signature matrix S such that SAS is nonnegative, we prove such S is unique up to multiplication by -1 if the signed digraph D(A) is not disconnected.     

The period and base of a reducible sign pattern matrix

A square sign pattern matrix A (whose entries are ) is said to be powerful if all the powers A,A²,A³,…, are unambiguously defined. For a powerful pattern A, if A^l=A^l+p with l and p minimal, then l is called the base of A and p is called the period of Li et al. [On the period and base of a sign pattern matrix, Linear Algebra Appl. 212/213 (1994) 101-120] characterized irreducible powerful sign pattern matrices. In this paper, we characterize reducible, powerful sign pattern matrices and give some new results on the period and base of a powerful sign pattern matrix.     

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.     

Spectrally arbitrary ray patterns

An n×n ray pattern A is said to be spectrally arbitrary if for every monic nth degree polynomial f(x) with coefficients from C, there is a matrix in the pattern class of A such that its characteristic polynomial is f(x). In this article the authors extend the nilpotent-Jacobi method for sign patterns to ray patterns, establishing a means to show that an irreducible ray pattern and all its superpatterns are spectrally arbitrary. They use this method to establish that a particular family of n×n irreducible ray patterns with exactly 3n nonzeros is spectrally arbitrary. They then show that every n×n irreducible, spectrally arbitrary ray pattern has at least 3n-1 nonzeros.     

Characterization of ray pattern matrix whose determinantal region has two components after deleting the origin

Ray nonsingular matrices are generalizations of sign nonsingular matrices. The problem of characterizing ray nonsingular matrices is still open. The study of the determinantal regions R_A of ray pattern matrices is closely related to the study of ray nonsingular matrices. It was proved that if R_A?{0} is disconnected, then it is a union of two opposite open sectors (or open rays). In this paper, we characterize those ray patterns whose determinantal regions become disconnected after deleting the origin. The characterization is based on three classes (F1), (F2) and (F3) of matrices, which can further be characterized in terms of the sets of the distinct signed transversal products of their ray patterns. Moreover, we show that in the fully indecomposable case, a matrix A is in the class (F1) (or (F2), respectively) if and only if A is ray permutation equivalent to a real SNS (or non-SNS, respectively) matrix.     

± 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.     

Rational realization of the minimum ranks of nonnegative sign pattern matrices

A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set {+,?, 0} ({+, 0}, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix A is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of A. Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in R^r?1 and Steinitz’s theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every d-polytope determines a nonnegative sign pattern with minimum rank d + 1 that has a (d + 1) × (d + 1) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min{3m, 3n} zero entries in any condensed nonnegative m × n sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.     

The minimum upper bound on the first ambiguous power of an irreducible, nonpowerful ray or sign pattern

Let A be an n×n irreducible ray or sign pattern matrix. If A is a sign pattern, it is shown that either A is powerful or else A^k has an ambiguous entry for some , and further, sign patterns based on the Wielandt graph show that this bound is the best possible. If A is a ray pattern, partial results for the same bound are given.     

A Hamiltonian property for nilpotent algebras

In this paper we show that any finite algebra A satisfying a weak left nilpotence condition has the property that all maximal subuniverses are congruence blocks. Conversely, if every subalgebra of A ² has the property that all maximal subuniverses are congruence blocks, then A satisfies the aforementioned nilpotence condition. Received August 3, 1994; accepted in final form June 27, 1996.     

Congruence of Hermitian matrices by Hermitian matrices

Two Hermitian matrices A,B∈M_n(C) are said to be Hermitian-congruent if there exists a nonsingular Hermitian matrix C∈M_n(C) such that B=CAC. In this paper, we give necessary and sufficient conditions for two nonsingular simultaneously unitarily diagonalizable Hermitian matrices A and B to be Hermitian-congruent. Moreover, when A and B are Hermitian-congruent, we describe the possible inertias of the Hermitian matrices C that carry the congruence. We also give necessary and sufficient conditions for any 2-by-2 nonsingular Hermitian matrices to be Hermitian-congruent. In both of the studied cases, we show that if A and B are real and Hermitian-congruent, then they are congruent by a real symmetric matrix. Finally we note that if A and B are 2-by-2 nonsingular real symmetric matrices having the same sign pattern, then there is always a real symmetric matrix C satisfying B=CAC. Moreover, if both matrices are positive, then C can be picked with arbitrary inertia.     

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.     

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.     

When the positivity of the leading principal minors implies the positivity of all principal minors of a matrix

An n-by-n real matrix A enjoys the “leading implies all” (LIA) property, if, whenever D   is a diagonal matrix such that A+D$A+D$ has positive leading principal minors (PMs), all PMs of A are positive. Symmetric and Z-matrices are known to have this property. We give a new class of matrices (“mixed matrices”) that both unifies and generalizes these two classes and their special diagonal equivalences by also having the LIA property. “Nested implies all” (NIA) is also enjoyed by this new class.     

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.     

Palindromic matrix polynomials, matrix functions and integral representations

We study the properties of palindromic quadratic matrix polynomials φ(z)=P+Qz+Pz², i.e., quadratic polynomials where the coefficients P and Q are square matrices, and where the constant and the leading coefficients are equal. We show that, for suitable choices of the matrix coefficients P and Q, it is possible to characterize by means of φ(z) well known matrix functions, namely the matrix square root, the matrix polar factor, the matrix sign and the geometric mean of two matrices. Finally we provide some integral representations of these matrix functions.     

G-matrices,J-orthogonal matrices,and their sign patterns

A real matrix A is a G-matrix if A is nonsingular and there exist nonsingular diagonal matrices D₁ and D₂ such that A^?T = D₁AD₂, where A^?T denotes the transpose of the inverse of A. Denote by J = diag(±1) a diagonal (signature) matrix, each of whose diagonal entries is +1 or ?1. A nonsingular real matrix Q is called J-orthogonal if Q^TJQ = J. Many connections are established between these matrices. In particular, a matrix A is a G-matrix if and only if A is diagonally (with positive diagonals) equivalent to a column permutation of a J-orthogonal matrix. An investigation into the sign patterns of the J-orthogonal matrices is initiated. It is observed that the sign patterns of the G-matrices are exactly the column permutations of the sign patterns of the J-orthogonal matrices. Some interesting constructions of certain J-orthogonal matrices are exhibited. It is shown that every symmetric staircase sign pattern matrix allows a J-orthogonal matrix. Sign potentially J-orthogonal conditions are also considered. Some examples and open questions are provided.     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

On 0-1 matrices and small excluded submatrices

We say that a 0-1 matrix A avoids another 0-1 matrix (pattern) P if no matrix P^′ obtained from P by increasing some of the entries is a submatrix of A. Following the lead of (SIAM J. Discrete Math. 4 (1991) 17-27; J. Combin. Theory Ser. A 55 (1990) 316-320; Discrete Math. 103 (1992) 233-251) and other papers we investigate n by n 0-1 matrices avoiding a pattern P and the maximal number ex(n,P) of 1 entries they can have. Finishing the work of [8] we find the order of magnitude of ex(n,P) for all patterns P with four 1 entries. We also investigate certain collections of excluded patterns. These sets often yield interesting extremal functions different from the functions obtained from any one of the patterns considered.