Sparse inertially arbitrary patterns

An n-by-n sign pattern is a matrix with entries in {+,-,0}. An n-by-n nonzero pattern is a matrix with entries in {*,0} where * represents a nonzero entry. A pattern is inertially arbitrary if for every set of nonnegative integers n₁,n₂,n₃ with n₁+n₂+n₃=n there is a real matrix with pattern having inertia (n₁,n₂,n₃). We explore how the inertia of a matrix relates to the signs of the coefficients of its characteristic polynomial and describe the inertias allowed by certain sets of polynomials. This information is useful for describing the inertia of a pattern and can help show a pattern is inertially arbitrary. Britz et al. [T. Britz, J.J. McDonald, D.D. Olesky, P. van den Driessche, Minimal spectrally arbitrary sign patterns, SIAM J. Matrix Anal. Appl. 26 (2004) 257–271] conjectured that irreducible spectrally arbitrary patterns must have at least 2n nonzero entries; we demonstrate that irreducible inertially arbitrary patterns can have less than 2n nonzero entries.     

The solvability conditions for the inverse eigenproblems of symmetric and generalized centro-symmetric matrices and their approximations

Let ∥ · ∥ be the Frobenius norm of matrices. We consider (I) the set S_E of symmetric and generalized centro-symmetric real n × n matrices R_n with some given eigenpairs (λ_j, q_j) (j = 1, 2, … , m) and (II) the element in S_E which minimizes for a given real matrix R^∗. Necessary and sufficient conditions for S_E to be nonempty are presented. A general form of elements in S_E is given and an explicit expression of the minimizer is derived. Finally, a numerical example is reported.     

Zero-divisor semigroups and refinements of a star graph

Let G be a refinement of a star graph with center c. Let be the subgraph of G induced on the vertex set V(G)?{c or end vertices adjacent to c}. In this paper, we completely determine the structure of commutative zero-divisor semigroups S whose zero-divisor graph G=Γ(S) and S satisfy one of the following properties: (1) has at least two connected components, (2) is a cycle graph C_n of length n≥5, (3) is a path graph P_n with n≥6, (4) S is nilpotent and Γ(S) is a finite or an infinite star graph. For any finite or infinite cardinal number n≥2, we prove that for any nilpotent semigroup S with zero element 0, S⁴=0 if Γ(S) is a star graph K_1,n. We prove that there is exactly one nilpotent semigroup S such that S³≠0 and Γ(S)≅K_1,n. For several classes of finite graphs G which are refinements of a star graph, we also obtain formulas to count the number of non-isomorphic corresponding semigroups.     

New classes of spectrally arbitrary ray patterns

An n×n ray pattern matrix S is said to be spectrally arbitrary if for every monic nth degree polynomial f(λ) with coefficients from C, there is a complex matrix in the ray pattern class of S such that its characteristic polynomial is f(λ). In this article we give new classes of spectrally arbitrary ray pattern matrices.     

The eigenvalue distribution on Schur complements of H-matrices

The paper studies the eigenvalue distribution of some special matrices. Tong in Theorem 1.2 of [Wen-ting Tong, On the distribution of eigenvalues of some matrices, Acta Math. Sinica (China), 20 (4) (1977) 273-275] gives conditions for an n × n matrix A ∈ SD_n ∪ ID_n to have |J_R+(A)| eigenvalues with positive real part, and |J_R-(A)| eigenvalues with negative real part. A counter-example is given in this paper to show that the conditions of the theorem are not true. A corrected condition is then proposed under which the conclusion of the theorem holds. Then the corrected condition is applied to establish some results about the eigenvalue distribution of the Schur complements of H-matrices with complex diagonal entries. Several conditions on the n × n matrix A and the subset α ⊆ N = {1, 2, … , n} are presented such that the Schur complement matrix A/α of the matrix A has eigenvalues with positive real part and eigenvalues with negative real part.     

Dn,r is not potentially nilpotent for n ⩾ 4r − 2

An n × n sign pattern A is said to be potentially nilpotent if there exists a nilpotent real matrix B with the same sign pattern as A. Let D_n,r be an n × n sign pattern with 2 ≤ r ≤ n such that the superdiagonal and the (n, n) entries are positive, the (i, 1) (i = 1,..., r) and (i, i ? r + 1) (i = r + 1,..., n) entries are negative, and zeros elsewhere. We prove that for r ≥ 3 and n ≥ 4r ? 2, the sign pattern D_n,r is not potentially nilpotent, and so not spectrally arbitrary.     

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.     

A note on the perturbation of positive matrices by normal and unitary matrices

In a recent paper, Neumann and Sze considered for an n × n nonnegative matrix A, the minimization and maximization of ρ(A + S), the spectral radius of (A + S), as S ranges over all the doubly stochastic matrices. They showed that both extremal values are always attained at an n × n permutation matrix. As a permutation matrix is a particular case of a normal matrix whose spectral radius is 1, we consider here, for positive matrices A such that (A + N) is a nonnegative matrix, for all normal matrices N whose spectral radius is 1, the minimization and maximization problems of ρ(A + N) as N ranges over all such matrices. We show that the extremal values always occur at an n × n real unitary matrix. We compare our results with a less recent work of Han, Neumann, and Tastsomeros in which the maximum value of ρ(A + X) over all n × n real matrices X of Frobenius norm was sought.     

On single and double Soules matrices

Until now the concept of a Soules basis matrix of sign patternN consisted of an orthogonal matrix R∈R^n,n, generated in a certain way from a positive n-vector, which has the property that for any diagonal matrix Λ = diag(λ₁, … , λ_n), with λ₁ ? ? ? λ_n ? 0, the symmetric matrix A = RΛR^T has nonnegative entries only. In the present paper we introduce the notion of a pair of double Soules basis matrices of sign patternN which is a pair of matrices (P, Q), each in R^n,n, which are not necessarily orthogonal and which are generated in a certain way from two positive vectors, but such that PQ^T = I and such that for any of the aforementioned diagonal matrices Λ, the matrix A = PΛQ^T (also) has nonnegative entries only. We investigate the interesting properties which such matrices A have.As a preamble to the above investigation we show that the iterates, , generated in the course of the QR-algorithm when it is applied to A = RΛR^T, where R is a Soules basis matrix of sign pattern N, are again symmetric matrices generated by the Soules basis matrices R_k of sign pattern N which are themselves modified as the algorithm progresses.Our work here extends earlier works by Soules and Elsner et al.     

Distributing vertices along a Hamiltonian cycle in Dirac graphs

A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are ω,n₀>0 such that if G is a Dirac graph on n≥n₀ vertices, d is an arbitrary integer with 3≤d≤ωn/2 and S is an arbitrary subset of the vertices of G with 2≤|S|=k≤ωn/d, then for every sequence d_i of integers with 3≤d_i≤d,1≤i≤k−1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a₁,a₂,…,a_k, such that the vertices of S are visited in this order on C and we have

     

Extremal and Barabanov semi-norms of a semigroup generated by a bounded family of matrices

Let S={Si}_i∈I be an arbitrary family of complex n-by-n matrices, where 1?n<∞. Let denote the joint spectral radius of S, defined as

     

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.     

Solution of a tridiagonal operator equation

Let H be a separable Hilbert space with an orthonormal basis {e_n/n∈N}, T be a bounded tridiagonal operator on H and T_n be its truncation on span ({e₁, e₂, … , e_n}). We study the operator equation Tx = y through its finite dimensional truncations T_nxⁿ = y_n. It is shown that if and are bounded, then T is invertible and the solution of Tx = y can be obtained as a limit in the norm topology of the solutions of its finite dimensional truncations. This leads to uniform boundedness of the sequence . We also give sufficient conditions for the boundedness of and in terms of the entries of the matrix of T.     

A note on complex matrices that are unitarily congruent to real matrices

Every square complex matrix is known to be consimilar to a real matrix. Unitary congruence is a particular type of consimilarity. We prove that a matrix A∈M_n(C) is unitarily congruent to a real matrix if and only if A is unitarily congruent to via a symmetric unitary matrix. It is shown by an example that there exist matrices that are congruent, but not unitarily congruent, to real matrices.     

Laplacian energy of a graph

Let G be a graph with n vertices and m edges. Let λ₁, λ₂, … , λ_n be the eigenvalues of the adjacency matrix of G, and let μ₁, μ₂, … , μ_n be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences.     

Transition matrices for well-conditioned Markov chains

Let T∈R^n×n be an irreducible stochastic matrix with stationary distribution vector π. Set A = I − T, and define the quantity , where A_j, j = 1, … , n, are the (n − 1) × (n − 1) principal submatrices of A obtained by deleting the jth row and column of A. Results of Cho and Meyer, and of Kirkland show that κ₃ provides a sensitive measure of the conditioning of π under perturbation of T. Moreover, it is known that .In this paper, we investigate the class of irreducible stochastic matrices T of order n such that , for such matrices correspond to Markov chains with desirable conditioning properties. We identify some restrictions on the zero-nonzero patterns of such matrices, and construct several infinite classes of matrices for which κ₃ is as small as possible.