Extended integer rank reduction formulas and Smith normal form

We present an integer rank reduction formula for transforming the rows and columns of an integer matrix A. By repeatedly applying the formula to reduce rank, an extended integer rank reducing process is derived. The process provides a general finite iterative approach for constructing factorizations of A and A ^T under a common framework of a general decomposition V ^T AP?=?Ω. Then, we develop the integer Wedderburn rank reduction formula and its integer biconjugation process. Both the integer biconjugation process associated with the Wedderburn rank reduction process and the scaled extended integer Abaffy–Broyden–Spedicato (ABS) class of algorithms are shown to be in the integer rank reducing process. We also show that the integer biconjugation process can be derived from the scaled integer ABS class of algorithms applied to A or A ^T . Finally, we show that the integer biconjuagation process is a special case of our proposed ABS class of algorithms for computing the Smith normal form.     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

Each four-celled animal tiles the plane

An animal A is a set of unit squares in the plane, parallel to the axes, and with corners at integer lattice points. We show that any animal A with four cells tiles the plane, in the sense that infinitely many copies of A, translated by integer vectors and possibly rotated through 90°, 180°, or 270°, can be placed so as to fill plane exactly without overlap.     

On distance sets of large sets of integer points

Distance sets of large sets of integer points are studied in dimensions at least 5. To any ε > 0 a positive integer Q _ɛ is constructed with the following property; If A is any set of integer points of upper density at least ε, then all large multiples of Q _ɛ ² occur as squares of distances between the points of the set A. Research supported in part by NSF Grant DMS-0456490.     

On the Restricted Order of Asymptotic Bases of Order Two

The restricted order of an asymptotic basis A is the least integer h, if it exists, such that every sufficiently large integer is the sum of h or fewer distinct elements of A. We show that any asymptotic basis of order 2 has a restricted order at most equal to 4. We also provide an example of an additive basis of order 2 whose restricted order is 4.To Jean-Louis Nicolas2000 Mathematics Subject Classification: Primary—11B13     

Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs

A probabilistic result of Bollobás and Catlin concerning the largest integer p so that a subdivision of K_p is contained in a random graph is generalized to a result concerning the largest integer p so that a subdivision of A_p is contained in a random graph for some sequence A₁, A₂,… of graphs such that A_i+1 contains a subdivision of A_i. A similar result is proved for subdivisions with odd paths or cycles. The result is applied to disprove a conjecture of Chartrand, Geller, and Hedetniemi. The maximum number of edges in a graph without a subdivision of K_p, p = 4, 5, with odd paths or cycles is determined.     

Distributive and Semihereditary Rings

Let A be a right and left distributive ring. For a positive integer n, we obtain a criterion of projectivity of all n-generated right ideals of the ring A and a criterion of the right semi-heredity of the ring A.__________Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 1, pp. 253–258, 2003.     

Equivalence of Hadamard matrices

Supposem is a square-free odd integer, andA andB are any two Hadamard matrices of order 4m. We will show thatA andB are equivalent over the integers (that is,B can be obtained fromA using elementary row and column operations which involve only integers).     

Group inverse and group involutory Matrices ∗

In this work we deal with group involutory matrices, i.e.A ^#=A. We give necessary and sufficient conditions to characterize these matrices in terms of different representations of the group inverse. First, we give different expressions of the group inverse of a square matrix A. In addition, the special case of integer matrices is considered.     

Operations on orbits of unimodular vectors

Taking the m-power of an entry is a well-defined operation on the unimodular vectors in Aⁿ modulo addition operations, if n is at least 3, for an arbitrary commutative ring A and any integer m.     

Representing integers as linear combinations of power products

Let P be a finite set of at least two prime numbers and A the set of positive integers that are products of powers of primes from P. Let F(k) denote the smallest positive integer which cannot be presented as sum of less than k terms of A. In a recent paper Nathanson asked to determine the properties of the function F(k), in particular to estimate its growth rate. In this paper we derive several results on F(k) and on the related function F _±(k) which denotes the smallest positive integer which cannot be presented as sum of less than k terms of A è(-A){A \cup (-A)}.     

Some results on symplectic matrices

The principal results are that if A is an integral matrix such that AA^T is symplectic then A = CQ, where Q is a permutation matrix and C is symplectic; and that if A is a hermitian positive definite matrix which is symplectic, and B is the unique hermitian positive definite pth.root of A, where p is a positive integer, then B is also symplectic.     

Hall exponents of matrices,tournaments and their line digraphs

Let A be a square (0, 1)-matrix. Then A is a Hall matrix provided it has a nonzero permanent. The Hall exponent of A is the smallest positive integer k, if such exists, such that A ^k is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing A as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).     

On Codimension Growth of Finitely Generated Associative Algebras

LetAbe a PI-algebra over a fieldF. We study the asymptotic behavior of the sequence of codimensionsc_n(A) ofA. We show that ifAis finitely generated overFthenInv(A)=lim_n→∞ always exists and is an integer. We also obtain the following characterization of simple algebras:Ais finite dimensional central simple overFif and only ifInv(A)=dim=A.     

Gaps in the base set of primitive nonpowerful sign patterns

For a primitive nonpowerful square sign pattern A, the base of A, denoted by l(A), is the least positive integer l such that every entry of A ^l is #. In this article, we consider the base set of the primitive nonpowerful sign pattern matrices. Some useful results about the bases for the sign pattern matrices are presented there. Some special sign pattern matrices with given bases are characterized and more ‘gaps’ in the base set are shown.     

Borne générique pour le problème de Mordell-Lang

Given an abelian variety A over a number field and an integer D, we prove that there is only a finite number up to translation of curves on A with degree D with more than D^{7 dimA} rational points. We describe a more general result for higher dimensional varieties on semi-abelian varieties. This extends work of J.-H. Evertse on linear equations.     

On some local cohomology invariants of local rings

Let A be a commutative Noetherian local ring containing a field of characteristic p>0. The integer invariants λ _i,j (A) have been introduced in an old paper of ours. In this paper we completely describe λ _d,d (A) where d=dimA in terms of the topology of SpecA. NSF support through grant DMS-0202176 is gratefully acknowledged     

On the Witt Vectors of Perfect Rings in Positive Characteristic

The purpose of this article is to prove some results on the Witt vectors of perfect F _p -algebras. Let A be a perfect F _p -algebra for a prime integer p, and assume that A has the property P. Then does the ring of Witt vectors of A also have P? A main theorem gives an affirmative answer for P = ″integrally closed” under a very mild condition.     

Lower bounds on the dimension of the space of matrices transposed by a similarity transformation

Let B be a realn–by–n, invertible matrix. Sharp lower bounds are determined for the dimension of the space {A: A¹ = BAB^?1 } of real matrices A which are similar under B to their transposes A^′ . In particular, it is shown that this dimension is at least the greatest integer in (n + l)/2.     

Elements with prime and small indices in bicyclic biquadratic number fields

We give necessary and sufficient conditions for the existence of primitive algebraic integers with index A in totally complex bicyclic biquadratic number fields where A is an odd prime or a positive rational integer at most 10. We also determine all these elements and prove that there are infinitely many totally complex bicyclic biquadratic number fields containing elements with index A.