Double circulant matrices

Double circulant matrices are introduced and studied. By a matrix-theoretic method, the rank r of a double circulant matrix is computed, and it is shown that any consecutive r rows of the double circulant matrix are linearly independent. As a generalization, multiple circulant matrices are also introduced. Two questions on square double circulant matrices are posed.     

Integral circulant graphs

In this note we characterize integral graphs among circulant graphs. It is conjectured that there are exactly 2^τ(n)-1 non-isomorphic integral circulant graphs on n vertices, where τ(n) is the number of divisors of n.     

A variant of the Johnson-Lindenstrauss lemma for circulant matrices

We continue our study of the Johnson-Lindenstrauss lemma and its connection to circulant matrices started in Hinrichs and Vybíral (in press) [7]. We reduce the bound on k from k=Ω(ε−2log³n) proven there to k=Ω(ε−2log²n). Our technique differs essentially from the one used in Hinrichs and Vybíral (in press) [7]. We employ the discrete Fourier transform and singular value decomposition to deal with the dependency caused by the circulant structure.     

Coefficient estimates for bi-univalent Ma-Minda starlike and convex functions

Estimates on the initial coefficients are obtained for normalized analytic functions f in the open unit disk with f and its inverse g=f⁻¹ satisfying the conditions that zf^′(z)/f(z) and zg^′(z)/g(z) are both subordinate to a univalent function whose range is symmetric with respect to the real axis. Several related classes of functions are also considered, and connections to earlier known results are made.     

The nonidealness index of rank-ideal matrices

A polyhedron is integral if all its extreme points have 0, 1 components and in this case the matrix M is called ideal. When Q has fractional extreme points, there are different ways of classifying how far M is away from being ideal, through the polyhedral structure of Q. In this sense, Argiroffo, Bianchi and Nasini (2006) [1] defined a nonidealness index analogous to an imperfection index due to Gerke and McDiarmid (2001) [10].In this work we determine the nonidealness index of rank-ideal matrices (introduced by the authors (2008)). It is known that evaluating this index is NP-hard for any matrix. We provide a tractable way of evaluating it for most circulant matrices, whose blockers are a particular class of rank-ideal matrices, thereby following similar lines as done for the imperfection ratio of webs due to Coulonges, Pêcher and Wagler (2009) [7].Finally, exploiting the properties of this nonidealness index, we identify the facets of the set covering polyhedron of circulant matrices, having maximum strength with respect to the linear relaxation, according to a measure defined by Goemans (1995) [9].     

On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

A note on inversion of Toeplitz matrices

It is shown that the invertibility of a Toeplitz matrix can be determined through the solvability of two standard equations. The inverse matrix can be denoted as a sum of products of circulant matrices and upper triangular Toeplitz matrices. The stability of the inversion formula for a Toeplitz matrix is also considered.     

Finiteness of circulant weighing matrices of fixed weight

Let n be a fixed positive integer. Every circulant weighing matrix of weight n arises from what we call an irreducible orthogonal family of weight n. We show that the number of irreducible orthogonal families of weight n is finite and thus obtain a finite algorithm for classifying all circulant weighing matrices of weight n. We also show that, for every odd prime power q, there are at most finitely many proper circulant weighing matrices of weight q.     

Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T _m,n x=b by preconditioned conjugate gradient methods where T _m,n is an m×m block Toeplitz matrix with n×n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q ₁(T _m,n ) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q ₂(T _m,n ) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.     

The chromatic number of 5-valent circulants

A circulant C(n;S) with connection set S={a₁,a₂,…,a_m} is the graph with vertex set Z_n, the cyclic group of order n, and edge set E={{i,j}:|i−j|∈S}. The chromatic number of connected circulants of degree at most four has been previously determined completely by Heuberger [C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153-169]. In this paper, we determine completely the chromatic number of connected circulants C(n;a,b,n/2) of degree 5. The methods used are essentially extensions of Heuberger’s method but the formulae developed are much more complex.     

A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks

A fast solution algorithm is proposed for solving block banded block Toeplitz systems with non-banded Toeplitz blocks. The algorithm constructs the circulant transformation of a given Toeplitz system and then by means of the Sherman-Morrison-Woodbury formula transforms its inverse to an inverse of the original matrix. The block circulant matrix with Toeplitz blocks is converted to a block diagonal matrix with Toeplitz blocks, and the resulting Toeplitz systems are solved by means of a fast Toeplitz solver.The computational complexity in the case one uses fast Toeplitz solvers is equal to ξ(m,n,k)=O(mn³)+O(k³n³) flops, there are m block rows and m block columns in the matrix, n is the order of blocks, 2k+1 is the bandwidth. The validity of the approach is illustrated by numerical experiments.     

A note on certain matrices with h(x) – Fibonacci quaternion polynomials

In this paper we consider a g – circulant, right circulant, left circulant and a special kind of a tridiagonal matrices whose entries are h(x) – Fibonacci quaternion polynomials. We present the determinant of these matrices and with the tridiagonal matrices we show that the determinant is equal to the nth term of the h(x) – Fibonacci quaternion polynomial sequences.     

Products of Hecke eigenforms

Let f(z) and g(z) be Hecke eigenforms for Γ₀(p), where p is a prime. If both f(z) and g(z) are non-cuspidal forms and p?7, then the product is a Hecke eigenform only if it comes trivially from a level 1 solution. If g(z) is a cuspform and p?5, then in addition to the level 1 solutions, there are 8 new cases where the product of Hecke eigenforms is a Hecke eigenform.     

On zeros and fixed points of differences of meromorphic functions

Let f be a transcendental meromorphic function and g(z)=f(z+1)−f(z). A number of results are proved concerning the existences of zeros and fixed points of g(z) or g(z)/f(z) which expand results of Bergweiler and Langley [W. Bergweiler, J.K. Langley, Zeros of differences of meromorphic functions, Math. Proc. Cambridge Philos. Soc. 142 (2007) 133-147].     

Algorithms for Finding the Inverses of Factor Block Circulant Matrices

In this paper,algorithms for finding the inverse of a factor block circulant matrix, a factor block retrocirculant matrix and partitioned matrix with factor block circulant blocks over the complex field are presented respectively.In addition,two algorithms for the inverse of a factor block circulant matrix over the quaternion division algebra are proposed.     

Integral means of analytic functions

For analytic functions f(z) and g(z) which satisfy the subordination f(z)?g(z), J.E. Littlewood [Proc. London Math. Soc. 23 (1925) 481-519] has shown some interesting results for integral means of f(z) and g(z). The object of the present paper is to derive some applications of integral means by J.E. Littlewood. We also show interesting examples for our theorems.     

Generalized inverses of circulant and generalized circulant matrices

An expression for the Moore-Penrose inverse of certain singular circulants by S.R. Searle is generalized to include all circulants. Similar expressions are given for the Moore-Penrose inverse of block circulants with circulant blocks, level-q circulants, k-circulants where |k|=1, and certain other matrices which are the product of a permutation matrix and a circulant. Expressions for other generalized inverses are given.     

Enumeration of 2-regular circulant graphs and directed double networks

We present a formula to enumerate non-isomorphic circulant digraphs of order n with connection sets of cardinality 2. This formula simplifies to C(n,2)=3×2^a−1−4 in the case when n=2^a(a≥3), and when n=p^a(where p is an odd prime and a≥1). The number of non-isomorphic directed double networks are also enumerated.     

Universality and asymptotics of graph counting problems in non-orientable surfaces

Bender-Canfield showed that a plethora of graph counting problems in orientable/non-orientable surfaces involve two constants tg and pg for the orientable and the non-orientable case, respectively. T.T.Q. Le and the authors recently discovered a hidden relation between the sequence tg and a formal power series solution u(z) of the Painlevé I equation which, among other things, allows to give exact asymptotic expansion of tg to all orders in 1/g for large g. The paper introduces a formal power series solution v(z) of a Riccati equation, gives a non-linear recursion for its coefficients and an exact asymptotic expansion to all orders in g for large g, using the theory of Borel transforms. In addition, we conjecture a precise relation between the sequence pg and v(z). Our conjecture is motivated by the enumerative aspects of a quartic matrix model for real symmetric matrices, and the analytic properties of its double scaling limit. In particular, the matrix model provides a computation of the number of rooted quadrangulations in the 2-dimensional projective plane. Our conjecture implies analyticity of the O(N)- and Sp(N)-types of free energy of an arbitrary closed 3-manifold in a neighborhood of zero. Finally, we give a matrix model calculation of the Stokes constants, pose several problems that can be answered by the Riemann-Hilbert approach, and provide ample numerical evidence for our results.