An extended fast algorithm for constructing the Dixon resultant matrix

In recent years,the Dixon resultant matrix has been used widely in the re-sultant elimination to solve nonlinear polynomial equations and many researchers havestudied its efficient algorithms.The recursive algorithm is a very efficient algorithm,butwhich deals with the case of three polynomial equations with two variables at most.Inthis paper,we extend the algorithm to the general case of n 1 polynomial equations in nvariables.The algorithm has been implemented in Maple 9.By testing the random polyno-mial equations,the results demonstrate that the efficiency of our program is much betterthan the previous methods,and it is exciting that the necessary condition for the existenceof common intersection points on four general surfaces in which the degree with respectto every variable is not greater than 2 is given out in 48×48 Dixon matrix firstly by ourprogram.     

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.     

Principal minors, Part I: A method for computing all the principal minors of a matrix

An order O(2ⁿ) algorithm for computing all the principal minors of an arbitrary n × n complex matrix is motivated and presented, offering an improvement by a factor of n³ over direct computation. The algorithm uses recursive Schur complementation and submatrix extraction, storing the answer in a binary order. An implementation of the algorithm in MATLAB® is also given and practical considerations are discussed and treated accordingly.     

Parallel Dixon Matrices by Bracket

It is known that the Dixon matrix can be constructed in parallel either by entry or by diagonal. This paper presents another parallel matrix construction, this time by bracket. The parallel by bracket algorithm is the fastest among the three, but not surprisingly it requires the highest number of processors. The method also shows analytically that the Dixon matrix has a total of m(m+1)²(m+2)n(n+1)²(n+2)/36 brackets but only mn(m+1)(n+1)(mn+2m+2n+1)/6 of them are distinct.     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

An algorithm for computing Jordan chains and inverting analytic matrix functions

We present an efficient algorithm for obtaining a canonical system of Jordan chains for an n × n regular analytic matrix function A(λ) that is singular at the origin. For any analytic vector function b(λ), we show that each term in the Laurent expansion of A(λ)⁻¹b(λ) may be obtained from the previous terms by solving an (n + d) × (n+d) linear system, where d is the order of the zero of det A(λ) at λ = 0. The matrix representing this linear system contains A(0) as a principal submatrix, which can be useful if A(0) is sparse. The last several iterations can be eliminated if left Jordan chains are computed in addition to right Jordan chains. The performance of the algorithm in floating point and exact (rational) arithmetic is reported for several test cases. The method is shown to be forward stable in floating point arithmetic.     

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.     

Completion of a partial integral matrix to a unimodular matrix

We first characterize submatrices of a unimodular integral matrix. We then prove that if n entries of an n × n partial integral matrix are prescribed and these n entries do not constitute a row or a column, then this matrix can be completed to a unimodular matrix. Consequently an n × n partial integral matrix with n − 1 prescribed entries can always be completed to a unimodular matrix.     

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.     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

On the completion of a partial integral matrix to a unimodular matrix

We prove that if a partial integral matrix has a free diagonal then this matrix can be completed to a unimodular matrix. Such a condition is necessary in a general sense. Consequently if an n × n (n ? 2) partial integral matrix has 2n − 3 prescribed entries and any n entries of these do not constitute a row or a column then it can be completed to a unimodular matrix. This improves a recent result of Zhan.     

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.     

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.     

Reliability of a consecutive (r, s)-out-of-(m, n):F lattice system with conditions on the number of failed components in the system

A consecutive(r, s)-out-of-(m, n):F lattice system which is defined as a two-dimensional version of a consecutive k-out-of-n:F system is used as a reliability evaluation model for a sensor system, an X-ray diagnostic system, a pattern search system, etc. This system consists of m × n components arranged like an (m, n) matrix and fails iff the system has an (r, s) submatrix that contains all failed components. In this paper we deal a combined model of a k-out-of-mn:F and a consecutive (r, s)-out-of-(m, n):F lattice system. Namely, the system has one more condition of system down, that is the total number of failed components, in addition to that of a consecutive (r, s)-out-of-(m, n):F lattice system. We present a method to obtain reliability of the system. The proposed method obtains the reliability by using a combinatorial equation that does not depend on the system size. Some numerical examples are presented to show the relationship between component reliability and system reliability.     

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.     

An algorithm for mean residual life computation of (n − k + 1)-out-of-n systems: An application of exponentiated Weibull distribution

In this paper, we establish an algorithm for the computation of the mean residual life of a (n − k + 1)-out-of-n system in the case of independent but not necessarily identically distributed lifetimes of the components. An application for the exponentiated Weibull distribution is given to study the effect of various parameters on the mean residual life of the system. Also the relationship between the mean residual life for the system and that of its components is investigated.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

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.