New methods for generating permutation polynomials over finite fields

We present two methods for generating linearized permutation polynomials over an extension of a finite field Fq. These polynomials are parameterized by an element of the extension field and are permutation polynomials for all nonzero values of the element. For the case of the extension degree being odd and the size of the ground field satisfying , these parameterized linearized permutation polynomials can be used to derive non-parameterized nonlinear permutation polynomials via a recent result of Ding et al.     

Distribution of matrices with restricted entries over finite fields

For a prime p, we consider some natural classes of matrices over a finite field F_p of p elements, such as matrices of given rank or with characteristic polynomial having irreducible divisors of prescribed degrees. We demonstrate two different techniques which allow us to show that the number of such matrices in each of these classes and also with components in a given subinterval [-H, H] [-(p - 1)/2, (p - 1)/2] is asymptotically close to the expected value.     

M-P invertible matrices and unitary groups over Fq2

The Moor-Penrose generalized inverses (M-P inverses for short) of matrices over a finite field Fq2, which is a generalization of the Moor-Penrose generalized inverses over the complex field, are studied in the present paper. Some necessary and sufficient conditions for an m×n matrix A over Fq2 having an M-P inverse are obtained, which make clear the set of m×n matrices over Fq2 having M-P inverses and reduce the problem of constructing and enumerating the M-P invertible matrices to that of constructing and enumerating the non-isotropic subspaces with respect to the unitary group. Based on this reduction, both the construction problem and the enumeration problem are solved by borrowing the results in geometry of unitary groups over finite fields.     

Singular, nonsingular, and bounded rank completions of ACI-matrices

An affine column independent matrix is a matrix whose entries are polynomials of degree at most 1 in a number of indeterminates where no indeterminate appears with a nonzero coefficient in two different columns. A completion is a matrix obtained by giving values to each of the indeterminates. Affine column independent matrices are more general than partial matrices where each entry is either a constant or a distinct indeterminate. We determine when the rank of all completions of an affine column independent matrix is bounded by a given number, generalizing known results for partial matrices. We also characterize the square partial matrices over a field all of whose completions are nonsingular. The maximum number of free entries in such matrices of a given order is determined as well as the partial matrices with this maximum number of free entries.     

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.     

Generalization of a theorem of Carlitz

We generalize Carlitz? result on the number of self-reciprocal monic irreducible polynomials over finite fields by showing that similar explicit formula holds for the number of irreducible polynomials obtained by a fixed quadratic transformation. Our main tools are a combinatorial argument and Hurwitz genus formula.     

A remark on the moduli field of a curve

We give a purely algebro-geometric proof of the fact that every nonsingular projective curve can be defined over a finite extension of its moduli field. This extends a result byWolfart [7] to curves over fields of arbitrary characteristic. Received: 30 November 2001     

Relatively prime polynomials and nonsingular Hankel matrices over finite fields

The probability for two monic polynomials of a positive degree n with coefficients in the finite field Fq to be relatively prime turns out to be identical with the probability for an n×n Hankel matrix over Fq to be nonsingular. Motivated by this, we give an explicit map from pairs of coprime polynomials to nonsingular Hankel matrices that explains this connection. A basic tool used here is the classical notion of Bezoutian of two polynomials. Moreover, we give simpler and direct proofs of the general formulae for the number of m-tuples of relatively prime polynomials over Fq of given degrees and for the number of n×n Hankel matrices over Fq of a given rank.     

Permutation polynomials over finite fields from a powerful lemma

Using a lemma proved by Akbary, Ghioca, and Wang, we derive several theorems on permutation polynomials over finite fields. These theorems give not only a unified treatment of some earlier constructions of permutation polynomials, but also new specific permutation polynomials over Fq. A number of earlier theorems and constructions of permutation polynomials are generalized. The results presented in this paper demonstrate the power of this lemma when it is employed together with other techniques.     

On tame weakly symmetric algebras having only periodic modules

We classify (up to Morita equivalence) all tame weakly symmetric finite dimensional algebras over an algebraically closed field having simply connected Galois coverings, nonsingular Cartan matrices and the stable Auslander-Reiten quivers consisting only of tubes. In particular, we prove that these algebras have at most four simple modules.Received: 25 February 2002     

Practical criteria for H-matrices

In this paper, a set of criteria of nonsingular H-matrices are discussed. The paper introduces the concept of α-bidiagonally dominant matrices and gives an equivalent condition of strictly α-bidiagonally dominant matrices. According to the given condition, some new practical criteria of nonsingular H-matrices are obtained. Finally, some numerical examples are given.     

M-P invertible matrices and unitary groups over Fq2

The Moor-Penrose generalized inverses (M-P inverses for short) of matrices over a finite field F_q ² which is a generalization of the Moor-Penrose generalized inverses over the complex field, are studied in the present paper. Some necessary and sufficient conditions for anm xn matrixA over F_q ² having an M-P inverse are obtained, which make clear the set ofm xn matrices over F_q ² having M-P inverses and reduce the problem of constructing and enumerating the M-P invertible matrices to that of constructing and enumerating the non-isotropic subspaces with respect to the unitary group. Based on this reduction, both the construction problem and the enumeration problem are solved by borrowing the results in geometry of unitary groups over finite fields.     

M-P invertible matrices and unitary groups over Fq 2

The Moor-Penrose generalized inverses (M-P inverses for short) of matrices over a finite field F_q ² which is a generalization of the Moor-Penrose generalized inverses over the complex field, are studied in the present paper. Some necessary and sufficient conditions for anm xn matrixA over F_q ² having an M-P inverse are obtained, which make clear the set ofm xn matrices over F_q ² having M-P inverses and reduce the problem of constructing and enumerating the M-P invertible matrices to that of constructing and enumerating the non-isotropic subspaces with respect to the unitary group. Based on this reduction, both the construction problem and the enumeration problem are solved by borrowing the results in geometry of unitary groups over finite fields.     

Computable torsion-free nilpotent groups of finite dimension

We find criteria for the computability (constructivizability) of torsion-free nilpotent groups of finite dimension. We prove the existence of a principal computable enumeration of the class of all computable torsion-free nilpotent groups of finite dimension. An example is constructed of a subgroup in the group of all unitriangular matrices of dimension 3 over the field of rationals that is not computable but the sections of any of its central series are computable.     

On the action of permutations on distances between values of rational functions mod p

For the finite field Fp one may consider the distance between r₁(n) and r₂(n), where r₁, r₂ are rational functions in Fp(x). We study the effect to such distances by applying all possible permutations to the elements.     

Improvements upon the Chevalley-Warning-Ax-Katz-type estimates

Let f be a polynomial over finite field Fq with q elements and let N(f=0) denote the number of zeros of f in Fq. The q-divisibility properties of N(f=0) have been studied by many authors, such as Chavelley, Warning, Ax, Katz, etc. In this paper, by reducing the degree of a given polynomial meanwhile remaining the number of its zeros unchanged, we present an improvement upon the Chevalley-Warning-Ax-Katz-type estimates in many cases. Furthermore, our result can improve Cao-Sun's reduction recently obtained on counting the number of zeros of general diagonal equations over finite fields.     

Controllability,inertia, and stability for tridiagonal matrices

Criteria are given for the controllability of certain pairs of tridiagonal matrices. These criteria may be used, with the Chen-Wimmer theorem, to obtain inertia results. Also, a characterization is given of those nonsingular tridiagonal matrices with certain principal minors nonnegative which are positive stable. This extends a previous characterization of the real D-stable tridiagonal matrices.     

Linear maps that preserve singular and nonsingular matrices

Let M (n,K) be the algebra of n × n matrices over an algebraically closed field K and T:M (n,K)→M (n,K) a linear transformation with the property that T maps nonsingular (singular) matrices to nonsingular (singular) matrices. Using some elementary facts from commutative algebra we show that T is nonsingular and maps singular matrices to singular matrices (T is nonsingular or T maps all matrices to singular matrices). Using these results we obtain Marcus and Moyl's characterization [T(x) = UXVorU^tXV for fixed U and V] from a result of Dieudonné's. Examples are given to show the hypothesis of algebraic closure in necessary.     

MULTI-VALUED CROSSCORRELATION FUNCTION FOR m-SEQUENCES

Based on the theory of exponential sums and quadratic forms over finite field, the crosscorrelation function values between two maximal linear recursive sequences are determined under some conditions.     

Rank properties of subspaces of symmetric and hermitian matrices over finite fields

We investigate constant rank subspaces of symmetric and hermitian matrices over finite fields, using a double counting method related to the number of common zeros of the corresponding subspaces of symmetric bilinear and hermitian forms. We obtain optimal bounds for the dimensions of constant rank subspaces of hermitian matrices, and good bounds for the dimensions of subspaces of symmetric and hermitian matrices whose non-zero elements all have odd rank.