Possible numbers of positive entries of imprimitive nonnegative matrices

Zhan, X., Extremal numbers of positive entries of imprimitive nonnegative matrix, Linear Algebra Appl. (in press) has determined the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices with a given imprimitivity index. Let σ( A ) denote the number of positive entries of a matrix A. Let M(n,?k) and m(n,?k) denote the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices of order n with a given imprimitivity index k, respectively. In this article, we prove that for any positive integer d with m(n,k)≤ d?≤?M(n,k), there exists an n?×?n irreducible nonnegative matrix A with imprimitivity index k such that?σ?(A)=d.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

Irreducibility of associated matrices

For an n by n matrix A, let K(A) be the associated matrix corresponding to a permutation group (of degree m) and one of its characters. Let D_r(A) be the coefficient of x^m?r in K(A+xI). If A is reducible, then D_r(A) is reducible. If A is irreducible and the character is identically one, then D₁(A) is irreducible. If A is row stochastic and the character is identically one, then D_r(A) is essentially row stochastic. Finally, the results motivate the definition of group induced diagraphs.     

A rank characterization of the number of final classes of a nonnegative matrix

Let A be a nonnegative square matrix, and let D be a diagonal matrix whose iith element is $\text{(Ax)}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}$, where x is a (fixed) positive vector. It is shown that the number of final classes of A equals n?rank(A?D). We also show that null(A?D) = null(A?D)², and that this subspace is spanned by a set of nonnegative elements. Our proof uses a characterization of nonnegative matrices having a positive eigenvector corresponding to their spectral radius.     

Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

The Inertia Set of Nonnegative Symmetric Sign Pattern with Zero Diagonal

The inertia set of a symmetric sign pattern A is the set i(A) = {i(B) | B = B ^T ∈ Q(A)}, where i(B) denotes the inertia of real symmetric matrix B, and Q(A) denotes the sign pattern class of A. In this paper, a complete characterization on the inertia set of the nonnegative symmetric sign pattern A in which each diagonal entry is zero and all off-diagonal entries are positive is obtained. Further, we also consider the bound for the numbers of nonzero entries in the nonnegative symmetric sign patterns A with zero diagonal that require unique inertia.     

On the numerical characterization of the reachability cone for an essentially nonnegative matrix

Given an n×n real matrix A with nonnegative off-diagonal entries, the solution to , x₀=x(0), t?0 is x(t)=e^tAx₀. The problem of identifying the initial points x₀ for which x(t) becomes and remains entrywise nonnegative is considered. It is known that such x₀ are exactly those vectors for which the iterates x^(k)=(I+hA)^kx₀ become and remain nonnegative, where h is a positive, not necessarily small parameter that depends on the diagonal entries of A. In this paper, this characterization of initial points is extended to a numerical test when A is irreducible: if x^(k) becomes and remains positive, then so does x(t); if x(t) fails to become and remain positive, then either x^(k) becomes and remains negative or it always has a negative and a positive entry. Due to round-off errors, the latter case manifests itself numerically by x^(k) converging with a relatively small convergence ratio to a positive or a negative vector. An algorithm implementing this test is provided, along with its numerical analysis and examples. The reducible case is also discussed and a similar test is described.     

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.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

Searching monotone multi-dimensional arrays

A d-dimensional array of real numbers is called monotone increasing if its entries are increasing along each dimension. Given A_n,d, a monotone increasing d-dimensional array with n entries along each dimension, and a real number x, we want to decide whether x∈A_n,d, by performing a sequence of comparisons between x and some entries of A_n,d. We want to minimize the number of comparisons used. In this paper we investigate this search problem, we generalize Linial and Saks’ search algorithm [N. Linial, M. Saks, Searching ordered structures, J. Algorithms 6 (1985) 86-103] for monotone three-dimensional arrays to d-dimensions for d?4. For d=4, our new algorithm is optimal up to the lower order terms.     

On convexity properties of the spectral radius of nonnegative matrices

Elementary matrix-theoretic proofs are given for the following well-known results: r(D) = max{Re λ : λ an eigenvalue of A + D} and s(D) = lnρ(e^DA) are convex. Here D is diagonal, A a nonnegative n × n matrix, and ρ the spectral radius.     

A note on an open question on ω- and τ- Matrices

In a recent paper by Engel and Schneider, it was asked if, for every n ? 1, A ∈ τ_<n> implies (A+D) ∈ τ_<n> for every D = diag[d₁, d₂,… d_n] with d_i ? 0, 1 ? i ? n. We answer this question in the negative. More precisely, we show that for, any n ? 3, the set

(τ _{< n>}): = {D ∈C^n,n:(A+D)∈τ < n> for all A∈τ_<n>} is exactly given by

(Gt_<n>) = {γI_n:γ ? 0}.     

On the distribution of values of certain divisor functions

Let {?_d} be a sequence of nonnegative numbers and f(n) = Σ?_d, the sum being over divisors d of n. We say that f has the distribution function F if for all c ≥ 0, the number of integers n ≤ x for which f(n) > c is asymptotic to xF(c), and we investigate when F exists and when it is continuous.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

Two inequalities for the Perron Root

If A,B are irreducible, nonnegative n×n matrices with a common right eigenvector and a common left eigenvector corresponding to their respective spectral radii r(A), r(B), then it is shown that for any tϵ[0, 1], r(tA+(1−t)B^t)⩾tr(A)+ (1−t)r(B), where B^t is the transpose of B. Another inequality is proved that involves r(A) and r(Σ_lD^lAE^l), where A is a nonnegative, irreducible matrix and D^l, E^l are positive definite diagonal matrices. These inequalities generalize previous results due to Levinger and due to Friedland and Karlin.     

Density of sets of natural numbers and the Lévy group

Let N denote the set of positive integers. The asymptotic density of the set A⊆N is d(A)=limn→∞|A∩[1,n]|/n, if this limit exists. Let AD denote the set of all sets of positive integers that have asymptotic density, and let SN denote the set of all permutations of the positive integers N. The group L^? consists of all permutations f∈SN such that A∈AD if and only if f(A)∈AD, and the group L^* consists of all permutations f∈L^? such that d(f(A))=d(A) for all A∈AD. Let be a one-to-one function such that d(f(N))=1 and, if A∈AD, then f(A)∈AD. It is proved that f must also preserve density, that is, d(f(A))=d(A) for all A∈AD. Thus, the groups L^? and L^* coincide.     

On the index of maximum density for irreducible Boolean matrices

The index of maximum density of a Boolean (or nonnegative) matrix A is defined as the least positive integer h=h(A) such that the number of ones (or positive entries) in A^h is maximized in all powers of A. Our main results are the following: (1) Let IB_n,p be the set of n × n irreducible Boolean matrices with period p. We give the largest value of h(A) for A ϵ IB_n,p. (2) Let H_n,p be the set of h(A) for A ϵ IB_n,p. We exhibit a system of gaps in H_n,p. (3) We completely determine the set of h(A) for all n × n symmetric irreducible Boolean matrices.     

A general theory of measures for nonnegative matrices

By a measure μ on the set N of m × n nonnegative matrices we mean that μ is a function from N to the nonnegative reals such that (i) μ(λA)=λμ(A) for all nonnegative λ and all A ∈ N, and (ii) μ(A + B) ? μ(A) for all A,B ? N. This paper develops a theory of such measures and shows how this theory can be applied to particular problems.     

Characterization of the trace by monotonicity inequalities

Let ?be a positive linear functional on the algebra of n × n complex matrices and p be a number greater than 1. The main result of the paper says that if for any pair A, B of positive semi-definite n × n matrices with A ? B the inequality ?(A^p) ? ?(B^p) holds true, then ?is a nonnegative scalar multiple of the trace.     

New oscillation criteria for third order nonlinear neutral difference equations

In this paper, we are concerned with oscillation of the third-order nonlinear neutral difference equation $\Delta (c_n [\Delta (d_n \Delta (x_n + p_n x_{n - \tau } ))]^\gamma ) + q_n f(x_{g(n)} ) = 0,n \geqslant n_0 ,$ where γ > 0 is the quotient of odd positive integers, c _n , d _n , p _n and q _n are positive sequences of real numbers, τ is a nonnegative integer, g(n) is a sequence of nonnegative integers and f ∈ C(?,?) such that uf(u) > 0 for u ≠ 0. Our results extend and improve some previously obtained ones. Some examples are considered to illustrate the main results.