Perturbation of the SVD in the presence of small singular values

This paper gives SVD perturbation bounds and expansions that are of use when an m × n, m ? n matrix A has small singular values. The first part of the paper gives subspace bounds that are closely related to those of Wedin but are stated so as to isolate the effect of any small singular values to the left singular subspace. In the second part first and second order approximations are given for perturbed singular values. The subspace bounds are used to show that all approximations retain accuracy when applied to small singular values. The paper concludes by deriving a subspace bound for multiplicative perturbations and using that bound to give a simple approximation to a singular value perturbed by a multiplicative perturbation.     

Classification of small (0, 1) matrices

Denote by A_n the set of square (0, 1) matrices of order n. The set A_n, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let D_n, S_n denote the set of absolute determinant values and Smith normal forms of matrices from A_n. Denote by a_n the smallest integer not in D_n. The sets D₉ and S₉ are obtained; especially, a₉ = 103. The lower bounds for a_n, 10 ? n ? 19 (exceeding the known lower bound a_n ? 2f_n − 1, where f_n is nth Fibonacci number) are obtained. Row/permutation equivalence classes of A_n correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible.     

Enhancements to the von Neumann trace inequality

Upper trace bounds for the product of two n × n complex matrices are presented. The real component of the trace inequality is tighter than von Neumann’s inequality, and the imaginary component is new.     

Error analysis of large-time approximations for decay chains

Consider a radioactive decay chain X₁ → ? → X_n→ and let N_n(t) be the amount of X_n at time t. This paper establishes error bounds for large-time approximations to N_n(t) that include and generalize the transient equilibrium approximations and other known approximations. The error bounds allow one to find the range of t for which these approximations can be used with a given degree of precision.     

The domination numbers of cylindrical grid graphs

Let γ(P_m □ C_n) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs P_m, the path of length m, m ? 2 and the graph C_n, the cycle of length n, n ? 3. In this paper, methods to find the domination numbers of graphs of the form P_m □ C_n with n ? 3 and m = 2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P₅ □ C_n, n ? 3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs.     

Bounds for increasing multi-state consecutive k-out-of-r-from-n: F system with equal components probabilities

The consecutive k-out-of-r-from-n: F system was generalized to multi-state case. This system consists of n linearly ordered components which are at state below j if and only if at least k_j components out of any r consecutive are in state below j. In this paper we suggest bounds of increasing multi-state consecutive-k-out-of-r-from-n: F system (k₁ ? k₂ ? ? ? k_M) by applying second order Boole–Bonferroni bounds and applying Hunter–Worsley upper bound. Also numerical results are given. The programs in V.B.6 of the algorithms are available upon request from the authors.     

On the bounds for the norms of r-circulant matrices with the Fibonacci and Lucas numbers

In this paper, we have found upper and lower bounds for the spectral norms of r-circulant matrices in the forms A = C_r(F₀, F₁, …, F_n−1), B = C_r(L₀, L₁, …, L_n−1), and we have obtained some bounds for the spectral norms of Kronecker and Hadamard products of A and B matrices.     

Neighborhood properties of certain classes of multivalently analytic functions associated with the convolution structure

In this paper, by making use of the familiar concept of neighborhoods of p-valently analytic functions, we prove coefficient bounds, distortion inequalities and associated inclusion relations for the (n, δ)-neighborhoods of a family of p-valently analytic functions and their derivatives, which is defined by means of a certain general family of non-homogenous Cauchy-Euler differential equations.     

A note on Tang and He’s paper

In this paper, we establish new Lyapunov-type inequalities for two classes of one-dimensional quasilinear elliptic systems of resonant type, which improve the recent results of Tang and He [X.H. Tang, X. He, Lower bounds for generalized eigenvalues of the quasilinear systems, J. Math. Anal. Appl. 385 (2012) 72-85] when 1 < p_i < 2 for i = 1, 2, … , n.     

Krull’s theory for the double gamma function

The Barnes’ G-function G(x) = 1/Γ₂, satisfies the functional equation logG(x + 1) − logG(x) = logΓ(x). We complement W. Krull’s work in Bemerkungen zur Differenzengleichung g(x + 1) − g(x) = φ(x), Math. Nachrichten 1 (1948), 365-376 with additional results that yield a different characterization of the function G, new expansions and sharp bounds for G on x > 0 in terms of Gamma and Digamma functions, a new expansion for the Gamma function and summation formulae with Polygamma functions.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.     

A reduction approach to the repeated assignment problem

We consider the repeated assignment problem (RAP), which is a K-fold repetition of the n × n linear assignment problem (LAP), with the additional requirement that no assignment can be repeated more than once. In actual applications K is typically much smaller than n. First, we derive upper and lower bounds respectively by a heuristic together with local search, and an efficient method solving the continuous relaxation. The latter also solves a Lagrangian relaxation, such that the related pegging test, to fix variables at zero or one, decomposes into K independent pegging tests to LAPs. These can be solved exactly by transforming them into all-pairs shortest path problems. Together with these procedures, we also employ a virtual pegging test and reduce RAP in size. Numerical experiments show that the reduced instances, with K ? n, can be solved exactly using standard MIP solvers.     

On the logarithmic coefficients of Bazilevic? functions

The objective of the present paper is to study the logarithmic coefficients of Bazilevic? functions. We obtain the inequality ∣γ_n∣ ? An⁻¹logn (A is an absolute constant) which holds for Bazilevic? functions.     

Blow-up and global solutions for a class of nonlinear parabolic equations with different kinds of boundary conditions

By constructing different auxiliary functions and using Hopf’s maximum principle, the sufficient conditions for the blow-up and global solutions are presented for nonlinear parabolic equation u_t = ∇(a(u)b(x)c(t)∇u) + f(x, u, q, t) with different kinds of boundary conditions. The upper bounds of the “blow-up time” and the “upper estimates” of global solutions are provided. Finally, some examples are presented as the application of the obtained results.     

A two-unit general parallel system with (n − 2) cold standbys—Analytic and simulation approach

A parallel (2, n − 2)-system is investigated here where two units start their operation simultaneously and any one of them is replaced instantaneously upon its failure by one of the (n − 2) cold standbys. We assume availability of n non-identical, non-repairable units for replacement or support. The system reliability is evaluated by recursive relations with unit-lifetimes T_i (i = 1, … , n) that have a general joint distribution function F(t). On the basis of the derived expression, simulation techniques have been developed for the evaluation of the system reliability and the mean time to failure, useful when dealing with large systems or correlated unit-lifetimes and less mathematically manageable distributions. Simulation results are presented for various lifetime distributions and comparisons are made with derived analytic results for some special distributions and moderate values of n.     

Meromorphic Functions That Share Fixed-Points

In this paper, we prove the following result: Let f(z) and g(z) be two nonconstant meromorphic(entire) functions, n ≥ 11(n ≥ 6) a positive integer. If fⁿ(z)f′(z) and gⁿ(z)g′(z) have the same fixed-points, then either f(z) = c₁e^cz2, g(z) = c₂e^− cz2, where c₁, c₂, and c are three constants satisfying 4(c₁c₂)^n + 1c² = −1, or f(z) ≡ tg(z) for a constant t such that t^n + 1 = 1.     

On extremal matrices of second largest exponent by Boolean rank

Let b = b(A) be the Boolean rank of an n × n primitive Boolean matrix A and exp(A) be the exponent of A. Then exp(A) ? (b − 1)² + 2, and the matrices for which equality occurs have been determined in [D.A. Gregory, S.J. Kirkland, N.J. Pullman, A bound on the exponent of a primitive matrix using Boolean rank, Linear Algebra Appl. 217 (1995) 101-116]. In this paper, we show that for each 3 ? b ? n − 1, there are n × n primitive Boolean matrices A with b(A) = b such that exp(A) = (b − 1)² + 1, and we explicitly describe all such matrices.     

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.     

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.     

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.