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.     

On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks

It is shown in this work that all n-dimensional hypercube networks for n ? 4 are maximally 3-restricted edge connected. Employing this observation, we analyze the reliability of hypercube networks and determine the first 3n − 5 coefficients of the reliability polynomial of n-cube networks.     

On block partial linearizations of the pfaffian

Amitsur’s formula, which expresses det(A + B) as a polynomial in coefficients of the characteristic polynomial of a matrix, is generalized for partial linearizations of the pfaffian of block matrices. As applications, in upcoming papers we determine generators for the SO(n)-invariants of several matrices and relations for the O(n)-invariants of several matrices over a field of arbitrary characteristic.     

On the rates of convergence of BBH-Kantorovich operators and their Bézier variant

In the present paper we consider the Bézier variant of BBH-Kantorovich operators J_n,αf for functions f measurable and locally bounded on the interval [0, ∞) with α ? 1. By using the Chanturiya modulus of variation we estimate the rate of pointwise convergence of J_n,αf(x) at those x > 0 at which the one-sided limits f(x+), f(x−) exist. The very recent result of Chen and Zeng (2009) [L. Chen, X.M. Zeng, Rate of convergence of a new type Kantorovich variant of Bleimann-Butzer-Hahn Operators, J. Inequal. Appl. 2009 (2009) 10. Article ID 852897] is extended to more general classes of functions.     

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.     

Representation of solutions of n-order Riccati equation via generalized trigonometric functions

In this work we suggest a systematic method of construction of solutions of the n-order Riccati equation with constant coefficients in a field from the set of generalized trigonometric functions. The generalized trigonometric functions satisfy the system of evolution equations generated by the companion matrix of n  -order polynomial. The set of trigonometric functions depend of (n−1)$(n-1)$ variables formally expressed by series of exponential functions. In a particular case, the second order Riccati equation with constant coefficients is isomorphic to the evolution equation generated by the companion matrix of the associated quadratic polynomial. It is shown that the n>2$n>2$ order Riccati equation with coefficients in a field is derived from a linear system of evolution equations generated by companion matrix of the associated n  -order polynomial under (n−2)$(n-2)$ constraints.     

A comparison between iterative methods by using the basins of attraction

There exists a real competition between authors to construct improved iterative methods for solving nonlinear equations. In this paper, by using computer experiment, we study the basins of attraction for some of the iterative methods for solving the equation P(z) = 0, where P:C→C is a complex coefficients polynomial, and this allows us to compare their performances (the area of convergence and theirs speed). The beauty fractal pictures generated by these methods are presented too.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

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.     

On the combinatorics of Galois numbers

We define interval decompositions of the lattice of subspaces of a finite-dimensional vector space. We show that such a decomposition exists if and only if there exists a family of linear forms with certain properties. As applications we prove that all finite-dimensional real vector spaces admit an interval decomposition, while GF(2)ⁿ has an interval decomposition if and only if n≤4. On the other hand, we present an interval decomposition of GF(3)⁵. This partially answers a question of Faigle and Kruse (2004) [1] and [4].     

Schwarzian derivative, integral means, and the affine and linear invariant families of biharmonic mappings

In this paper we discuss the properties of the Schwarzian derivative, integral means and the affine and linear invariant families of biharmonic mappings. First, we introduce the Schwarzian derivative S(F) for biharmonic mappings F = ∣z∣²G + H, and obtain several necessary and sufficient conditions for S(F) to be analytic. Second, we introduce the subordination of biharmonic mappings and obtain inequalities for integral means of subordinate biharmonic mappings. Finally, we introduce the affine and linear invariant families of biharmonic mappings and prove several estimates related to the Jacobian of functions in these invariant families.     

Zeros of a random algebraic polynomial with coefficient means in geometric progression

This paper provides the mathematical expectation for the number of real zeros of an algebraic polynomial with non-identical random coefficients. We assume that the coefficients {a_j}ⁿ⁻¹_j=0 of the polynomial T(x)=a₀+a₁x+a₂x²+?+a_n−1xⁿ⁻¹ are normally distributed, with mean E(a_j)=μ^j+1, where μ≠0, and constant non-zero variance. It is shown that the behaviour of the random polynomial is independent of the variance on the interval (−1,1); it differs, however, for the cases of |μ|<1 and |μ|>1. On the intervals (−∞,−1) and (1,∞) we find the expected number of real zeros is governed by an interesting relationship between the means of the coefficients and their common variance. Our result is consistent with those of previous works for identically distributed coefficients, in that the expected number of real zeros for μ≠0 is half of that for μ=0.     

On the monodromy fibration of polynomial functions with singularities at infinity

Let ƒ : ℂⁿ → ℂ be a polynomial function. We introduce two regularity conditions: the t-regularity and the θ-regularity, which insure topological triviality of ƒ at infinity and we use them to prove a Lê-Ramanujam type result for the global monodromy fibration within certain families of polynomial functions with singularities at infinity.     

A sufficient condition for a polynomial to be stable

A real polynomial is called Hurwitz (stable) if all its zeros have negative real parts. For a given n∈N we find the smallest possible constant dn>0 such that if the coefficients of F(z)=a₀+a₁z+?+anzn are positive and satisfy the inequalities akak+1>dnak−1ak+2 for k=1,2,…,n−2, then F(z) is Hurwitz.     

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.     

On arrangements of roots for a real hyperbolic polynomial and its derivatives

In this paper we count the number ?_n^(0,k), k?n−1, of connected components in the space Δ_n^(0,k) of all real degree n polynomials which a) have all their roots real and simple; and b) have no common root with their kth derivatives. In this case, we show that the only restriction on the arrangement of the roots of such a polynomial together with the roots of its kth derivative comes from the standard Rolle's theorem. On the other hand, we pose the general question of counting all possible root arrangements for a polynomial p(x) together with all its nonvanishing derivatives under the assumption that the roots of p(x) are real. Already the first nontrivial case n=4 shows that the obvious restrictions coming from the standard Rolle's theorem are insufficient. We prove a generalized Rolle's theorem which gives an additional restriction on root arrangements for polynomials.