The inverse of circulant matrix

A direct method is proposed to get the inverse matrix of circulant matrix that find important application in engineering, the elements of the inverse matrix are functions of zero points of the characteristic polynomial g(z) and g′(z) of circulant matrix, four examples to get the inverse matrix are presented in the paper.     

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.     

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.     

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.

     

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.     

Scalable and Systolic Architecture for Computing Double Exponentiation Over GF(2 m )

Double-exponentiation is a crucial arithmetic operation for many cryptographic protocols. Several efficient double-exponentiation algorithms based on systolic architecture have been proposed. However, systolic architectures require large circuit space, thus increasing the cost of the protocol. This would be a drawback when designing circuits in systems requiring low cost and low power consumption. However, some cost savings can be attained by compromising speed, as in portable devices and many embedded systems. This study proposes a scalable and systolic AB ² and a scalable and systolic A × B, which are the core circuit modules of double-exponentiation. A scalable and systolic double-exponentiation can thus be obtained based on the proposed scalable AB ² and A × B architecture. Embedded system engineers may specify a target double-exponentiation with appropriate scaling systolic circuits. The proposed circuit has lower circuit space/cost and low time/propagation than other circuits.     

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

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

Triangularizing matrices over GF(2) by congruence

Necessary and sufficient conditions are presented for a square matrix over GF(2) to be triangulable by congruence.     

The computation of the square roots of circulant matrices

In the first part of this paper, we investigate the reduced forms of circulant matrices and quasi-skew circulant matrices. By using their properties we present two efficient algorithms to compute the square roots of circulant matrices and quasi-skew circulant matrices, respectively. Those methods are faster than the traditional algorithm which is based on the Schur decomposition. In the second part, we further consider circulant H-matrices with positive diagonal entries and develop two algorithms for computing their principal square roots. Those two algorithms have the common advantage that is they only need matrix-matrix multiplications in their iterative sequences, an operation which can be done very efficiently on modern high performance computers.     

An efficient method for computing the inverse of arrowhead matrices

In this paper we propose a simple and effective method to find the inverse of arrowhead matrices which often appear in wide areas of applied science and engineering such as wireless communications systems, molecular physics, oscillators vibrationally coupled with Fermi liquid, and eigenvalue problems. A modified Sherman–Morrison inverse matrix method is proposed for computing the inverse of an arrowhead matrix. The effectiveness of the proposed method is illustrated and numerical results are presented along with comparative results.     

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.     

The inverse eigenvalue problem for symmetric quasi anti-bidiagonal matrices

In this paper we construct the symmetric quasi anti-bidiagonal matrix that its eigenvalues are given, and show that the problem is also equivalent to the inverse eigenvalue problem for a certain symmetric tridiagonal matrix which has the same eigenvalues. Not only elements of the tridiagonal matrix come from quasi anti-bidiagonal matrix, but also the places of elements exchange based on some conditions.     

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.     

Bit-Parallel Arithmetic Implementations over Finite Fields GF(2 m ) with Reconfigurable Hardware

Galois (or finite) fields are used in a wide number of technical applications, playing an important role in several areas such as cryptographic schemes and algebraic codes, used in modern digital communication systems. Finite field arithmetic must be fast, due to the increasing performance needed by communication systems, so it might be necessary for the implementation of the modules performing arithmetic over Galois fields on semiconductor integrated circuits. Galois field multiplication is the most costly arithmetic operation and different approaches can be used. In this paper, the fundamentals of Galois fields are reviewed and multiplication of finite-field elements using three different representation bases are considered. These three multipliers have been implemented using a bit-parallel architecture over reconfigurable hardware and experimental results are presented to compare the performance of these multipliers.     

Polynomial Basis Multiplication over GF(2 m )

In this paper, we describe, analyze and compare various multipliers. Particularly, we investigate the standard modular multiplication, the Montgomery multiplication, and the matrix–vector multiplication techniques.     

The inverse eigenvalue problem of generalized reflexive matrices and its approximation

This paper studies inverse eigenvalue problems of generalized reflexive matrices and their optimal approximations. Necessary and sufficient conditions for the solvability of the problems are derived, the solutions and their optimal approximations are provided.     

Combinatorial properties of some classes of matrices over GF(2)

We study several classes of matrices of GF(2) constructed from lists of subsets of finite sets In this paper. We show that all matrices in these classes are representations of connected equicardinal matrix over GF(2). In Matrix terms, these irreducible (defined below) matrices all have the property that every minimal dependent set of column has the same cardinality over GF(2). This fact is shown directly in this paper by elementary matrix considerations. In a subsequent paper, we shall show that these classes of matrices are in fact the classes of canonical forms for all representations of nontrivial binary connected equicardinal matroids.     

The primitive matrices of sandwich semigroups of generalized circulant Boolean matrices

Let Gn（C） be the sandwich semigroup of generalized circulant Boolean matrices with the sandwich matrix C and Gc（Jr~） the set of all primitive matrices in Gn（C）. In this paper, some necessary and sufficient conditions for A in the semigroup Gn（C） to be primitive are given. We also show that Gc（Jn） is a subsemigroup of Gn（C）.     

Galois groups of polynomials arising from circulant matrices

Circulant matrices are used to construct polynomials, associated with Chebyshev polynomials of the first kind, whose roots are real and made explicit. Then the Galois groups of the polynomials are computed, giving rise to new examples of polynomials with cyclic Galois groups and Galois groups of order p(p−1) that are generated by a cycle of length p and a cycle of length p−1.