Study of proper circulant weighing matrices with weight 9

We provide the first theoretical proof of the spectrum of orders n for which circulant weighing matrices with weight 9 exist. This spectrum consists of those positive integers n, which are multiples of 13 or 24. We actually characterize the “minimal” examples which exist for orders 13, 26, or 24.     

Circulant weighing matrices of weight 22t

A weighing matrix of weight k is a square matrix M with entries 0, ± 1 such that MM ^T = kI _n . We study the case that M is a circulant and k = 2^2t for some positive integer t. New structural results are obtained. Based on these results, we make a complete computer search for all circulant weighing matrices of order 16.      

循环矩阵的两种特性的判定

揭示几类矩阵之间的紧密联系.借助于群的子群的判定以及循环布尔矩阵是本原矩阵的判定方法,得到循环模糊矩阵成为幂等矩阵的充要条件,反循环布尔矩阵成为本原矩阵的充要条件.并给出了循环模糊矩阵成为幂等矩阵的判定方法,反循环布尔矩阵成为本原矩阵的判定方法.     

Approximation of high-dimensional kernel matrices by multilevel circulant matrices

Kernels are important in developing a variety of numerical methods, such as approximation, interpolation, neural networks, machine learning and meshless methods for solving engineering problems. A common problem of these kernel-based methods is to calculate inverses of kernel matrices generated by a kernel function and a set of points. Due to the denseness of these matrices, finding their inverses is computationally costly. To overcome this difficulty, we introduce in this paper an approximation of the kernel matrices by appropriate multilevel circulant matrices so that the fast Fourier transform can be applied to reduce the computational cost. Convergence analysis for the proposed approximation is established based on certain decay properties of the kernels.     

Inversion of circulant matrices over

In this paper we consider the problem of inverting an circulant matrix with entries over . We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of FFT, has some drawbacks when working over . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of and , and their costs range, roughly, from to operations over . Moreover, for each algorithm we give the cost in terms of bit operations. We also present an algorithm for the inversion of finitely generated bi-infinite Toeplitz matrices. The problems considered in this paper have applications to the theory of linear cellular automata.

     

Proper circulant weighing matrices of weight p^2

A circulant weighing matrix \(CW(v,n)\) is a circulant matrix \(M\) of order \(v\) with \(0,\pm 1\) entries such that \(MM^T=nI_v\) . In this paper, we study proper circulant matrices with \(n=p^2\) where \(p\) is an odd prime divisor of \(v\) . For \(p\ge 5\) , it turns out that to search for such circulant matrices leads us to two group ring equations and by studying these two equations, we manage to prove that no proper \(CW(pw,p^2)\) exists when \(p\equiv 3\pmod {4}\) or \(p=5\) .     

Fast computation of two-level circulant preconditioners

In this paper we present an algorithm for the construction of the superoptimal circulant preconditioner for a two-level Toeplitz linear system. The algorithm is fast, in the sense that it operates in FFT time. Numerical results are given to assess its performance when applied to the solution of two-level Toeplitz systems by the conjugate gradient method, compared with the Strang and optimal circulant preconditioners.     

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.     

A comparison of lower bounds for the symmetric circulant traveling salesman problem

When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare different lower bounds on the optimal value that may be computed in polynomial time. We derive a new linear programming (LP) relaxation of the SCTSP from the semidefinite programming (SDP) relaxation in [E. de Klerk, D.V. Pasechnik, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559-1573]. Further, we discuss theoretical and empirical comparisons between this new bound and three well-known bounds from the literature, namely the Held-Karp bound [M. Held, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138-1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992].     

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.     

Toeplitz approximate inverse preconditioner for banded Toeplitz matrices

In this paper we introduce a new preconditioner for banded Toeplitz matrices, whose inverse is itself a Toeplitz matrix. Given a banded Hermitian positive definite Toeplitz matrixT, we construct a Toepliz matrixM such that the spectrum ofMT is clustered around one; specifically, if the bandwidth ofT is , all but eigenvalues ofMT are exactly one. Thus the preconditioned conjugate gradient method converges in +1 steps which is about half the iterations as required by other preconditioners for Toepliz systems that have been suggested in the literature. This idea has a natural extension to non-banded and non-Hermitian Toeplitz matrices, and to block Toeplitz matrices with Toeplitz blocks which arise in many two dimensional applications in signal processing. Convergence results are given for each scheme, as well as numerical experiments illustrating the good convergence properties of the new preconditioner.Partly supported by a travel fund from the Deutsche Forschungsgemeinschaft.Research supported in part by Oak Ridge Associated Universities grant no. 009707.     

Cyclic orthogonal double covers of 4-regular circulant graphs

An orthogonal double cover (ODC) of a graph H is a collection G={G_v:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members G_u and G_v in G, |E(G_u)∩E(G_v)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs.     

From random matrices to quasi-periodic Jacobi matrices via orthogonal polynomials

We present an informal review of results on asymptotics of orthogonal polynomials, stressing their spectral aspects and similarity in two cases considered. They are polynomials orthonormal on a finite union of disjoint intervals with respect to the Szegö weight and polynomials orthonormal on with respect to varying weights and having the same union of intervals as the set of oscillations of asymptotics. In both cases we construct double infinite Jacobi matrices with generically quasi-periodic coefficients and show that each of them is an isospectral deformation of another. Related results on asymptotic eigenvalue distribution of a class of random matrices of large size are also shortly discussed.     

New weighing matrices of weight 25

The existence of a weighing matrix of order 33 and weight 25 has been open so far. We actually construct such a circulant matrix, thereby obtaining circulant matrices of order 33t with weight 25, for each positive integer t. Consequently a missing entry in Craigen's table of weighing matrices can now be filled with a positive response. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 11–15, 1999     

On the determinants and inverses of circulant matrices with Fibonacci and Lucas numbers

Let A_n=Circ(F₁,F₂,…,F_n) and B_n=Circ(L₁,L₂,…,L_n) be circulant matrices, where F_n is the Fibonacci number and L_n is the Lucas number. We prove that A_n is invertible for n > 2, and B_n is invertible for any positive integer n. Afterwards, the values of the determinants of matrices A_n and B_n can be expressed by utilizing only the Fibonacci and Lucas numbers. In addition, the inverses of matrices A_n and B_n are derived.