A mean value theorem for orders of degree zero divisor class groups of quadratic extensions over a function field

Let k be a function field of one variable over a finite field with the characteristic not equal to two. In this paper, we consider the prehomogeneous representation of the space of binary quadratic forms over k. We have two main results. The first result is on the principal part of the global zeta function associated with the prehomogeneous vector space. The second result is on a mean value theorem for degree zero divisor class groups of quadratic extensions over k, which is a consequence of the first one.     

Preservers of pairs of bivectors with bounded distance

We extend Liu’s fundamental theorem of the geometry of alternate matrices to the second exterior power of an infinite dimensional vector space and also use her theorem to characterize surjective mappings T from the vector space V of all n×n alternate matrices over a field with at least three elements onto itself such that for any pair A, B in V, rank(A-B)?2k if and only if rank(T(A)-T(B))?2k, where k is a fixed positive integer such that n?2k+2 and k?2.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

The centro-invertible matrix: A new type of matrix arising in pseudo-random number generation

This paper defines a new type of matrix (which will be called a centro-invertible matrix) with the property that the inverse can be found by simply rotating all the elements of the matrix through 180 degrees about the mid-point of the matrix. Centro-invertible matrices have been demonstrated in a previous paper to arise in the analysis of a particular algorithm used for the generation of uniformly-distributed pseudo-random numbers.An involutory matrix is one for which the square of the matrix is equal to the identity. It is shown that there is a one-to-one correspondence between the centro-invertible matrices and the involutory matrices. When working in modular arithmetic this result allows all possible k by k centro-invertible matrices with integer entries modulo M to be enumerated by drawing on existing theoretical results for involutory matrices.Consider the k by k matrices over the integers modulo M. If M takes any specified finite integer value greater than or equal to two then there are only a finite number of such matrices and it is valid to consider the likelihood of such a matrix arising by chance. It is possible to derive both exact expressions and order-of-magnitude estimates for the number of k by k centro-invertible matrices that exist over the integers modulo M. It is shown that order (√N) of the N=M^(k2) different k by k matrices modulo M are centro-invertible, so that the proportion of these matrices that are centro-invertible is order (1/√N).     

Imbedding conditions for normal matrices

When can an (n-k)×(n-k) normal matrix B be imbedded in an n×n normal matrix A? This question was studied for the first time 50 years ago by Ky Fan and Gordon Pall, who gave the complete answer in the case k=1. Since then, a few authors obtained additional results. In this note, we show how an approach inspired by the Hermitian case can throw some light on the problem.     

On D. Hägele’s approach to the Bessis-Moussa-Villani conjecture

The reformulation of the Bessis-Moussa-Villani (BMV) conjecture given by Lieb and Seiringer asserts that the coefficient α_m,k(A,B) of t^k in the polynomial Tr(A+tB)^m, with A,B positive semidefinite matrices, is nonnegative for all m,k. We propose a natural extension of a method of attack on this problem due to Hägele, and investigate for what values of m,k the method is successful, obtaining a complete determination when either m or k is odd.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

Global solvability of real analytic complex vector fields in two variables

This paper deals with the global solvability of a complex vector field with real analytic coefficients in two real variables. The vector field is assumed to satisfy the Nirenberg-Treves condition (P) for local solvability. Normal forms for the vector field near the one-dimensional orbits are obtained and a generalization of the Riemann-Hilbert problem is considered.     

k-Hypermonogenic automorphic forms

In this paper we deal with monogenic and k-hypermonogenic automorphic forms on arithmetic subgroups of the Ahlfors-Vahlen group. Monogenic automorphic forms are exactly the 0-hypermonogenic automorphic forms. In the first part we establish an explicit relation between k-hypermonogenic automorphic forms and Maaß wave forms. In particular, we show how one can construct from any arbitrary non-vanishing monogenic automorphic form a Clifford algebra valued Maaß wave form. In the second part of the paper we compute the Fourier expansion of the k-hypermonogenic Eisenstein series which provide us with the simplest non-vanishing examples of k-hypermonogenic automorphic forms.     

Number of walks and degree powers in a graph

This note deals with the relationship between the total number of k-walks in a graph, and the sum of the k-th powers of its vertex degrees. In particular, it is shown that the the number of all k-walks is upper bounded by the sum of the k-th powers of the degrees.     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

Canonical matrices of bilinear and sesquilinear forms

Canonical matrices are given for

(i)

bilinear forms over an algebraically closed or real closed field;

(ii)

sesquilinear forms over an algebraically closed field and over real quaternions with any nonidentity involution; and

(iii)

sesquilinear forms over a field F of characteristic different from 2 with involution (possibly, the identity) up to classification of Hermitian forms over finite extensions of F; the canonical matrices are based on any given set of canonical matrices for similarity over F.

A method for reducing the problem of classifying systems of forms and linear mappings to the problem of classifying systems of linear mappings is used to construct the canonical matrices. This method has its origins in representation theory and was devised in [V.V. Sergeichuk, Classification problems for systems of forms and linear mappings, Math. USSR-Izv. 31 (1988) 481-501].     

Abelian repetitions in partial words

We study abelian repetitions in partial words, or sequences that may contain some unknown positions or holes. First, we look at the avoidance of abelian pth powers in infinite partial words, where p>2, extending recent results regarding the case where p=2. We investigate, for a given p, the smallest alphabet size needed to construct an infinite partial word with finitely or infinitely many holes that avoids abelian pth powers. We construct in particular an infinite binary partial word with infinitely many holes that avoids 6th powers. Then we show, in a number of cases, that the number of abelian p-free partial words of length n with h holes over a given alphabet grows exponentially as n increases. Finally, we prove that we cannot avoid abelian pth powers under arbitrary insertion of holes in an infinite word.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

Thue-Morse at multiples of an integer

Let t=(tn)_n?0 be the classical Thue-Morse sequence defined by , where s₂ is the sum of the bits in the binary representation of n. It is well known that for any integer k?1 the frequency of the letter “1” in the subsequence t₀,tk,t2k,… is asymptotically 1/2. Here we prove that for any k there is an n?k+4 such that tkn=1. Moreover, we show that n can be chosen to have Hamming weight ?3. This is best in a twofold sense. First, there are infinitely many k such that tkn=1 implies that n has Hamming weight ?3. Second, we characterize all k where the minimal n equals k, k+1, k+2, k+3, or k+4. Finally, we present some results and conjectures for the generalized problem, where s₂ is replaced by sb for an arbitrary base b?2.     

Decomposition of a scalar operator into a product of unitary operators with two points in spectrum

We consider products of unitary operators with at most two points in their spectra, 1 and e^iα. We prove that the scalar operator e^iγI is a product of k such operators if α(1+1/(k-3))?γ?α(k-1-1/(k-3)) for k?5. Also we prove that for e^iα≠-1, only a countable number of scalar operators can be decomposed in a product of four operators from the mentioned class. As a corollary we show that every unitary operator on an infinite-dimensional space is a product of finitely many such operators.     

Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes

In max algebra it is well known that the sequence of max algebraic powers A^k, with A an irreducible square matrix, becomes periodic after a finite transient time T(A), and the ultimate period γ is equal to the cyclicity of the critical graph of A.In this connection, we study computational complexity of the following problems: (1) for a given k, compute a periodic power A^r with and r?T(A), (2) for a given x, find the ultimate period of {A^l⊗x}. We show that both problems can be solved by matrix squaring in O(n³logn) operations. The main idea is to apply an appropriate diagonal similarity scaling A?X^-1AX, called visualization scaling, and to study the role of cyclic classes of the critical graph.     

Surjections on Grassmannians preserving pairs of elements with bounded distance

Let m and k be two fixed positive integers such that m>k?2. Let V be a left vector space over a division ring with dimension at least m+k+1. Let G_m(V) be the Grassmannian consisting of all m-dimensional subspaces of V. We characterize surjective mappings T from G_m(V) onto itself such that for any A,B in G_m(V), the distance between A and B is not greater than k if and only if the distance between T(A) and T(B) is not greater than k.