# On the Minimal Polynomials and the Inverses of Multilevel Scaled Factor Circulant Matrices

Authors: Zhaolin Jiang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Circulant matrices have important applications in solving various differential equations. The level-k scaled factor circulant matrix over any field is introduced. Algorithms for finding the minimal polynomial of this kind of matrices over any field are presented by means of the algorithm for the Gröbner basis of the ideal in the polynomial ring. And two algorithms for finding the inverses of such matrices are also presented. Finally, an algorithm for computing the inverse of partitioned matrix with level-k scaled factor circulant matrix blocks over any field is given by using the Schur complement, which can be realized by CoCoA 4.0, an algebraic system, over the field of rational numbers or the field of residue classes of modulo prime number.


---

## Body

## 1. Introduction

Circulant matrices play an important role in solving many different differential equations, such as ordinary, partial, matrix, linear second-order partial, bi-Hamiltonian partial, parameterized delay, fractional order, and singular perturbation delay. Lee et al. investigated a high-order compact (HOC) scheme for the general two-dimensional (2D) linear partial differential equation in [1] with a mixed derivative. Meanwhile, in order to establish the CCD2 scheme, they rewrote equation (1.1) into (2.1) in [1]. To write the CCD2 system in a concise style, they employed circulant matrix to obtain the corresponding whole CCD2 linear system (2.10), whose entries are circulant block. Using circulant matrix, Karasözen and Şimşek [2] considered periodic boundary conditions such that no additional boundary terms will appear after semidiscretization. Guo et al. concerned generic Dn-Hopf bifurcation to a delayed Hopfield-Cohen-Grossberg model of neural networks (5.17) in [3], where T denoted an interconnection matrix. In particular, they assumed that T is a symmetric circulant matrix. Trench considered nonautonomous systems of linear differential equations (1) in [4] with some constraints on the coefficient matrix A(t). One case is that the A(t) is a variable block circulant matrix. In [5], some Routh-Hurwitz stability conditions are generalized to the fractional order case. Ahmed et al. considered the 1-system CML (10) in [5]. They selected a circulant matrix, which reads a tridiagonal matrix. In [6], Jin et al. proposed the GMRES method with the Strang-type block-circulant preconditioner for solving singular perturbation delay differential equations. In [7], Claeyssen and Leal introduce factor circulant matrices: matrices with the structure of circulants, but with the entries below the diagonal multiplied by the same factor. The diagonalization of a circulant matrix and spectral decomposition are conveniently generalized to block matrices with the structure of factor circulants. Matrix and partial differential equations involving factor circulants are considered. Wilde [8] developed a theory for the solution of ordinary and partial differential equations whose structure involves the algebra of circulants. He showed how the algebra of 2×2 circulants is related to the study of the harmonic oscillator, Cauchy-Riemann equations, Laplace’s equation, the Lorentz transformation, and the wave equation. And he used n×n circulants to suggest natural generalizations of these equations to higher dimensions.With the development of the mathematical research, multilevel circulant matrix had been defined. And it has been used on network engineering, approximate calculation, and Image processing [9–12]. Jiang and Liu [13] introduced the level-m scaled circulant factor matrix over the complex number field and discussed its diagonalization and spectral decomposition and representation. Zhang et al. [14] gave algorithms for the minimal polynomial and the inverse of a level-n(r1,r2,…,rn)-block circulant matrix over any field by means of the algorithm for the Gröbner basis for the ideal of the polynomial ring over the field. Morhac and Matousek [15] present an efficient algorithm to solve a one-dimensional as well as n-dimensional circulant convolution system. Rezghi and Elden [16] defined tensors with diagonal and circulant structure and developed a framework for the analysis of such tensors. Georgiou and Koukouvinos [17] presented a new method for constructing multilevel supersaturated designs. Trench [18, 19] considered properties of unilevel block circulants and multilevel block α-circulants. Block [20] considered the property of circulants of level-k. Baker et al. discussed the structure of multiblock circulants in [21]. More details on multilevel circulant matrix can be found in [22–24].This paper is devoted to study the level-k scaled factor circulant matrix, and it is organized as follows.In Section2, a level-k scaled factor circulant matrix over any field is introduced and its algebraic properties are given.In Section3, we first show that the ring of all level-k scaled factor circulant matrices over a field is isomorphic to a factor ring of a polynomial ring in k variables over the same field, and then we present an algorithm for finding the minimal polynomial of a level-k scaled factor circulant matrix by mean of the algorithm for the Gröbner basis for a kernel of a ring homomorphism.In Section4, we give a sufficient and necessary condition to determine whether a level-k scaled factor circulant matrix over a field is singular or not and then present an algorithm for finding the inverse of such a matrix over a field.In Section5, an algorithm for finding the inverse of partitioned matrix with level-k scaled factor circulant matrix blocks over a field is presented by using the Schur complement and Buchberger’s algorithm.We first introduce some terminologies and notations used in the equations. LetF be a field and F[x1,…,xk] the polynomial ring of k variables over field F. By Hilbert basis Theorem, we know that every ideal I in F[x1,…,xk] is finitely generated. Fixing a term order in F[x1,…,xk], a set of nonzero polynomials G={g1,…,gt} in an ideal I is called a Gröbner basis for I if and only if, for all nonzero f∈I, there exists i∈{1,…,t} such that lp(gi) divides lp(f), where lp(gi) and lp(f) are the leading power products of gi and f, respectively. A Gröbner basis G={g1,…,gt} is called a reduced Gröbner basis if and only if, for all i,lc(gi)=1 and gi is reduced with respect to G-gi; that is, for all i, no non-zero term in gi is divisible by any lp(gi) for any j≠i, where lc(gi) is the leading coefficient of gi.In this paper, we setA0=I for a square matrix A, and 〈f1,…,fm〉 denotes an ideal of F[x1,…,xk] generated by polynomials f1,…,fm.


## 2. Level-k Scaled Factor Circulant Matrices

IfR is an n×n matrix over field F which is the product of a diagonal matrix D and a circulant permutation matrix C, this is
(1)D=diag⁡(d1,d2,…,dn),C=(0100⋯00010⋯0⋮⋮⋮⋮⋮⋮0000⋯11000⋯0)n×n.Then, the matrixR=DC is called a scaled circulant permutation matrix over field F.When fieldF is the complex field, this kind of matrix is the same as in [25].For the remainder of the paper, the indices1,2,…,n are congruence classes modulo n. We will use 0 instead of n. For convenience, we will refer to such a matrix as an SCPMF.AsR=DC is a scaled circulant permutation matrix over field F, then
(2)det⁡R=(-1)n-1∏j=1n‍dj,Rn=(∏j=1n‍dj)In.In this paper, focus on the case whereRi=DiCi is nonsingular SCPMF, where
(3)Di=diag⁡(di1,di2,…,dini),Ci=(0100⋯00010⋯0⋮⋮⋮⋮⋮⋮0000⋯11000⋯0)ni×ni,i=1,2,…,k.
It is easy to show that the polynomial xini-∏ji=1nidiji is both the minimal polynomial and the characteristic polynomial of Ri.LetIni be the ni×ni unit matrix for i=1,2,…,k and N=n1n2⋯nk. Set
(4)σi=In1⊗⋯⊗Ini-1⊗Ri⊗Ini+1⊗⋯⊗Ink,
where ⊗ is a Kronecker product of matrices.Definition 1.
AnN×N maxtrix A over F is callled a level-k scaled factor circulant matrix if there exists a polynomial
(5)f(x1,…,xk)=∑i1=0n1-1‍∑i2=0n2-1‍⋯∑ik=0nk-1‍ai1⋯ikx1i1⋯xkikiiiiiiiiiiiiiiiiiiii∈F[x1,…,xk]
such that
(6)A=f(σ1,…,σk)iii=∑i1=0n1-1‍∑i2=0n2-1‍⋯∑ik=0nk-1‍ai1⋯ikσ1i1⋯σkik,
where f(x1,…,xk) will be called the representer of a level-k scaled factor circulant matrix A.Obviously, when fieldF is the complex field and k=1, this kind of matrix is same as in [25], and when the field F is the complex field, this kind of matrix is the same as in [13], and if Di=diag⁡(1,1,…,1,ri), i=1,2,…,k, this kind of matrix is as in [14, 18, 22], and if Di=Ini, i=1,2,…,k, then we obtain the multilevel circulant matrix [9–12, 15, 19–22].From the property of the Kronecker product of matrices, the level-k scaled factor circulant matrix A can also be expressed as
(7)A=∑i1=0n1-1‍∑i2=0n2-1‍⋯∑ik=0nk-1‍ai1⋯ikR1i1⊗R2i2⊗⋯⊗Rkik.For a matrixA over F,  A is a level-k scaled factor circulant matrix if and only if A commutes with (R1⊗R2⊗⋯⊗Rk); that is,
(8)A(R1⊗R2⊗⋯⊗Rk)=(R1⊗R2⊗⋯⊗Rk)A.In addition to the algebraic properties that can be easily derived from representation (6), we mention that level-k scaled factor circulant matrices have very nice structure. The product of two level-k scaled factor circulant matrices is also a level-k scaled factor circulant matrix. Furthermore, level-k scaled factor circulant matrices commute under multiplication and A-1 is also a level-k scaled factor circulant matrix.


## 3.  Minimal Polynomials of Level-k Scaled Factor Circulant Matrices

LetF[σ1,…,σk]={A∣A=f(σ1,…,σk),f(x1,…,xk)∈F[x1,…,xk]}. It is a routine to prove that F[σ1,…,σk] is a commutative ring with the matrix addition and multiplication.Theorem 2.
ConsiderF[x1,…,xk]/〈x1n1-∏j1=1n1d1j1,…,xknk-∏jk=1nkdkjk〉≅F[σ1,…,σk].Proof.
Consider the followingF-algebra homomorphism:
(9)φ:F[x1,…,xk]⟶F[σ1,…,σk]iiiif(x1,…,xk)⟼A=f(σ1,…,σk)
for f(x1,…,xk)∈F[x1,…,xk]. It is clear that φ is an F-algebra epimorphism. So, we have
(10)F[x1,…,xk]ker⁡φ≅F[σ1,…,σk].
We can prove that(11)ker⁡φ=〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk〉.
In fact, for i=1,2,…,k,  xini-∏ji=1nidiji∈ker⁡φ because σini-∏ji=1nidijiIni=0. Hence, ker⁡φ⊇〈x1n1-∏j1=1n1d1j1,…,xknk-∏jk=1nkdkjk〉.
Conversely, for anyf(x1,…,xk)∈ker⁡φ, we have A=f(σ1,…,σk)=0. Fix the lexicographical order on F[x1,…,xk] with x1>x2>⋯>xk. Consider x1n1-∏j1=1n1d1j1 dividing f(x1,…,xk), and there exist
(12)u1(x1,…,xk),v1(x1,…,xk)∈F[x1,…,xk]
such that
(13)f(x1,…,xk)=u1(x1,…,xk)(x1n1-∏j1=1n1‍d1j1)iiiiiiiiiiiiiiiiiiiiiiii+v1(x1,…,xk),
where v1(x1,…,xk)=0 or the largest degree of x1 in v1(x1,…,xk) is less than n1. If v1(x1,…,xk)=0, then f(x1,…,xk)∈〈x1n1-∏j1=1n1d1j1,…,xknk-∏jk=1nkdkjk〉. Otherwise, x2n2-∏j2=1n2d2j2 dividing v1(x1,…,xk), and there exist u2(x1,…,xk),v2(x1,…,xk)∈F[x1,…,xk], such that
(14)v1(x1,…,xk)=u2(x1,…,xk)(x2n2-∏j2=1n2‍d2j2)iiiiiiiiiiiiiiiiiiiiiiii+v2(x1,…,xk),
where v2(x1,…,xk)=0 or the largest degree of x2 in v2(x1,…,xk) is less than n2. If v2(x1,…,xk)=0, then f(x1,…,xk)∈〈x1n1-∏j1=1n1d1j1,x2n2-∏j2=1n2d2j2,…,xknk-∏jk=1nkdkjk〉. Otherwise, the largest degree of x1 in v2(x1,…,xk) is less than n1 because x1 does not appear in x2n2-∏j2=1n2d2j2. Continuing this procedure, there exist u1(x1,…,xk),…,uk(x1,…,xk), and vk(x1,…,xk)∈F[x1,…,xk], such that f(x1,…,xk)=u1(x1,…,xk)(x1n1-∏j1=1n1d1j1)+⋯+uk(x1,…,xk)(xknk-∏jk=1nkdkjk)+vk(x1,…,xk), where vk(x1,…,xk)=0 or the degrees of x1,x2,…,xk in vk(x1,…,xk) are less than n1,n2,…,nk, respectively. Since f(σ1,…,σk)=0,σini-∏ji=1nidijiIni=0. For i=1,2,…,k,uk(σ1,…,σk)=0. The coefficients of all terms in vk(x1,…,xk) are the entries of the matrix vk(σ1,…,σk) because the degrees of x1,x2,…,xk in vk(x1,…,xk) are less than n1,n2,…,nk, respectively. Therefore, the coefficient of each term in vk(x1,…,xk) is 0; that is, vk(x1,…,xk)=0. Thus,
(15)f(x1,…,xk)∈〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk〉.Definition 3.
LetI be a nonzero ideal of the polynomial ring F[y1,…,yt]. Then, I is called an annihilation ideal of square matrices A1,…,At, denoted by I(A1,…,At), if f(A1,…,At)=0 for all f(y1,…,yt)∈I.Definition 4.
Suppose thatA1,…,At∈F[σ1,…,σk] are not all zero matrices. The unique monic polynomial g(x) of minimum degree that simultaneously annihilates A1,…,At is called the common minimal polynomial of A1,…,At.We give the special case of Theorem2.4.10 [26] here for the convenience of applications.Lemma 5.
LetI be an ideal of F[x1,…,xk]. Given f1,…,fm∈F[x1,…,xk], consider the following F-algebra homomorphism:
(16)ϕ:F[y1,…,ym]⟶F[x1,…,xk]Iiiiiiiiiiiiiiiiiiiiy1⟼f1+Iiiiiiiiiiiiiiiiiiiiiiiiiiiii⋮iiiiiiiiiiiiiiiiiiiym⟼fm+I.
Let E=〈I,y1-f1,…,ym-fm〉 be an ideal of F[x1,…,xk,y1,…,ym] generated by I,y1-f1,…,ym-fm. Then, kerϕ=E∩F[y1,…,ym].The following lemma is well known [27].Lemma 6.
LetA be a nonzero matrix over field F. If the minimal polynomial of A is
(17)p(x)=anxn+an-1xn-1+⋯+a1x+a0,a0≠0,
then
(18)A-1=1a0(-anAn-1-an-1An-2-⋯-a1).The following lemma is the Exercise 2.38 of [26].Lemma 7.
LetL1,L2,…,Lm be ideals of F[x1,…,xk] and let J=〈1-∑i=1mωi,ω1L1,ω2L2,…,ωmLm〉 be an ideal of F[x1,…,xk,ω1,…,ωm] generated by 1-∑i=1mωi,ω1L1,ω2L2,…,ωmLm. Then, ⋂i=1mLi=J∩F[x1,x2,…,xk].By Theorem2 and Lemma 5, we can prove the following theorem.Theorem 8.
The minimal polynomial of the level-k scaled factor circulant matrix A∈F[σ1,…,σk] is the monic polynomial that generates the ideal
(19)〈x1n1-∏j1=1n1‍d1j1,x2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk,iiiiiiiy-f(x1,x2,…,xk)∏j1=1n1‍〉>∩F[y],
where the polynomial f(x1,x2,…,xk) is the representer of A.Proof.
Consider the followingF-algebra homomorphism:
(20)ϕ:F[y]⟶F[x1,…,xk]〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk〉iiiiii>⟶F[σ1,…,σk],iiiiiiiiiy⟼f(x1,…,xk)iiiiiiiii+〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk〉iiii>⟼A=f(σ1,…,σk).
It is clear that q(y)∈ker⁡ϕ if and only if q(A)=0. In view of Lemma 5, we have
(21)ker⁡ϕ=〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk,iiiiiiiiiiiiiiiiiy-f(x1,x2,…,xk)∏jk=1nk‍〉>∩F[y].We know from Theorem8 and Lemma 6 that the minimal polynomial and the inverse of a level-k scaled factor circulant matrix A∈F[σ1,…,σk] is calculated by a Gröbner basis for a kernel of an F-algebra homomorphism. Therefore, we have the following algorithm to calculate the minimal polynomial and the inverse of a level-k scaled factor circulant matrix A=f(σ1,…,σk).Step 1.
Calculate the reduced Gröbner basisG for the ideal
(22)〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk,iiiiiiy-f(x1,x2,…,xk)∏j1=1n1‍〉>∩F[y]
by CoCoA 4.0, using an elimination order with x1>x2>⋯>xk>y.Step 2.
Find the polynomial inG in which the variables x1,x2,…,xk do not appear. This polynomial p(x) is the minimal polynomial of A.Step 3.
By Step2, if a0 in the minimal polynomial of A,
(23)p(x)=anxn+an-1xn-1+⋯+a1x+a0
is zero; stop. Otherwise, calculate
(24)A-1=1a0(-anAn-1-an-1An-2-⋯-a1).Example 9.
LetA=f(σ1,σ2) be a level-2 scaled factor circulant matrix, where
(25)f(x,y)=x3y2+3x3y+4x2y2iiiiiiiiiiiiii+2x3+7x2y+x2+xy2iiiiiiiiiiiiii+2y2+7xy+2x+5y+8,σ1=R1⊗I3,σ2=I4⊗R2,R1=(0-1200003500003-4000),R2=(013000-2500),I3=(100010001),I4=(1000010000100001).
We now calculate the minimal polynomial and the inverse of A with entries in field Z11.In fact, the reduced Gröbner basis for the ideal(26)〈x4-185,y3+103,z-f(x,y)〉
is
(27)G={z10-5z9-z8+2z7+2z6iiiiiiiii+5z5+z4-4z3-z2-5z-1,xiiiiiiiii-5yz-5y-2z9+5z8-3z7iiiiiiiii+5z6+3z5+z3+4z+2,y2iiiiiiiii+5y-5z9-4z8-4z7+3z6iiiiiiiii+5z5+3z3+3z2-5z+1,yz2iiiiiiiii-3yz+3y+3z9-5z8-5z7iiiiiiiii+5z6-2z5+3z4+3z3-z2-z}.
So, the minimal polynomial of A is
(28)z10-5z9-z8+2z7+2z6+5z5iiiii+z4-4z3-z2-5z-1,
and the inverse of A is
(29)A-1=A9-5A8-A7+2A6iiiiiiiiii+2A5+5A4+A3-4A2-A-5I.Theorem 10.
The annihilation ideal of the level-k scaled factor circulant matrices A1,…,At∈F[σ1,…,σk] is
(30)〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk,iiiiiiiy1-f1(x1,…,xk),…,yt-ft(x1,…,xk)∏j1=1n1‍〉iiii>∩F[y1,…,yt],
where the polynomial fi(x1,…,xk) is the representer of Ai,i=1,2,…,t.Proof.
Consider the followingF-algebra homomorphism:
(31)ϕ:F[y1,…,yt]⟶F[x1,…,xk]〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk〉>⟶F[σ1,…,σk],y1⟼f1(x1,…,xk)+〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk〉iiii>⟼A1=f1(σ1,…,σk),…,yt⟼ft(x1,…,xk)iiiiiiii+〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk〉iiii>⟼At=ft(σ1,…,σk).
It is clear that ϕ(g(y1,…,yt))=0 if and only if g(A1,…,At)=0. Hence, by Lemma 5(32)I(A1,…,At)=ker⁡ϕ=J∩F[y1,…,yt].According to Theorem10, we give the following algorithm for the annihilation ideal of the level-k scaled factor circulant matrices A1,…,At∈F[σ1,…,σk].Step 4 .
Calculate the reduced Gröbner basisG for the ideal
(33)〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk,iiiiiiy1-f1(x1,…,xk),…,yt-ft(x1,…,xk)∏j1=1n1‍〉
by CoCoA 4.0, using an elimination order with x1>⋯>xk>y1>⋯>yk.Step 5.
Find the polynomial inG in which the variables x1,x2,…,xk do not appear. Then, the ideal generated by these polynomials is the annihilation ideal of A1,…,At.Example 11.
LetA1=f1(σ1,σ2) and A2=f2(σ1,σ2) be both level-2 scaled circulant factor matrices, where
(34)f1(x,y)=7x2y2+5x2y+3x2iiiiiiiiiiiiiiiiii+xy2+8xy+4x+9y2+2y+9,f2(x,y)=10x2y2+4x2y+7x2iiiiiiiiiiiiiiiiii+xy2+3xy+9x+4y2+6y+1,σ1=R1⊗I3,σ2=I3⊗R2,R1=(0120006-300),R2=(0-1000-91300),I3=(100010001).
We calculate the annihilation ideal of A1 and A2 over field Z11 as follows.By CoCoA 4.0, we obtain that the reduced Gröbner basis for the ideal(35)〈x3+9,y3-3,z-f1(x,y),u-f2(x,y)〉
is
(36)G={u8+4u7+u6+5u5-4u3+3u2+4u-1,ii+3z+5u7+3u6-4u5ii-4u4+4u3-3u2+u-3,ii-4z-4u7-4u6-3u5-u4ii-u3+3u2+5u+2,ii-3z-5u7+3u5-2u4+5u3-4u2ii-u+3,zu-2z-u7-5u5ii-5u3+u2-4u+2}.
So, the annihilation ideal of A1 and A2 is
(37)〈u8+4u7+u6+5u5-4u3+3u2+4u-1,z2-3z-5u7+3u5-2u4+5u3-4u2-u+3,zu-2z-u7-5u5-5u3+u2-4u+2〉.To calculate the common minimal polynomial ofA1,…,At, we first prove the following theorem.Theorem 12.
Leth(x) be the least common multiple of p1(x),p2(x),…,pk(x). Then,
(38)⋂i=1k‍〈pi(x)〉=〈h(x)〉.Proof.
For anyf(x)∈⋂i=1k‍〈pi(x)〉, we have pi(x)∣f(x) for i=1,2,…,k. Since h(x) is the least common multiple of p1(x),p2(x),…,pk(x),h(x)∣f(x). So f(x)∈〈h(x)〉. Hence
(39)⋂i=1k‍〈pi(x)〉⊆〈h(x)〉.
Conversely,pi(x)∣f(x) for i=1,2,…,k because h(x) is the least common multiple of p1(x),p2(x),…,pk(x). Therefore,
(40)⋂i=1k‍〈pi(x)〉⊇〈h(x)〉.LetAi∈F[σ1,…,σk] be level-k scaled factor circulant matrix for i=1,2,…,t. If the minimal polynomial of Ai is pi(x) for i=1,2,…,t, then the common minimal polynomial of A1,…,At is the least common multiple of p1(x),p2(x),…,pt(x). By Theorem 12 and Lemma 7, we have the following algorithm for finding the common minimal polynomial of level-k scaled factor circulant matrices Ai=fi(σ1,…,σk) for i=1,2,…,t.Step 6 .
Calculate the Gröbner basisGi for the ideal 〈x1n1-∏j1=1n1‍d1j1,…,xknk-∏jk=1nk‍dkjk,y-fi(x1,x2,…,xk)〉 by CoCoA 4.0 for each i=1,2,…,t, using an elimination order with x1>⋯>xk>y.Step 7.
Find out the polynomialgi(y) in Gi in which the variables x1,…,xk do not appear for each i=1,2,…,t.Step 8.
Calculate the Gröbner basisG for the ideal
(41)〈1-∑i=1t‍ωi,ω1g1(y),…,ωtgt(y)〉
by CoCoA 4.0, using elimination with ω1>⋯>ωt>y.Step 9.
Find out the polynomialg(y) in G in which the variables ω1,…,ωt do not appear. Then, the polynomial g(y) is the common minimal polynomial of Ai=fi(σ1,…,σk) for i=1,2,…,t.Example 13.
We now calculate the common minimal polynomial ofA1 and A2 of Example 11 over field Z11 as follows.By CoCoA 4.0, we obtain that the reduced Gröbner basis for the ideal(42)〈x3+9,y3-3,z-f1(x,y)〉
is
(43)G1={z7-4z6-3z5+z4-3z2iiiiiiiiiii+4z+3,x+2y-5z6-2z4iiiiiiiiiii+2z3+4z2+3z+3,y2-5yziiiiiiiiiii+y+5z6+5z5+4z4+z3iiiiiiiiiii+z2-3z,yz2+y+5z6-4z5iiiiiiiiiii+4z4+2z3-5z+1}.
So, the minimal polynomial p1(z) of A1 is
(44)z7-4z6-3z5+z4-3z2+4z+3.Similarly, we get that the reduced Gröbner basis for the ideal(45)〈x3+9,y3-3,z-f2(x,y)〉
is
(46)G2={z8+4z7+z6+5z5-4z3iiiiiiiiiii+3z2+4z-1,x-2y+2z7iiiiiiiiiii+2z5-2z4-5z3+2z2iiiiiiiiiii+2z+4,y2-2y-2z7-z6iiiiiiiiiii-3z5-2z4+z3-3z2-5ziiiiiiiiiii+4,yz-2y+5z7-2z6+5z5iiiiiiiiiii+z4+2z3+4z2+3z}.
Thus, the minimal polynomial p2(z) of A2 is
(47)z8+4z7+z6+5z5-4z3+3z2+4z-1.
In addition, we obtain that the reduced Gröbner basis for the ideal
(48)〈1-u-v,up1(z),vp2(z)〉
is
(49)G={u+v-1,vz-2v-4z13iiiiiiiiii+5z12-3z11+2z10+3z9-2z8+2z7iiiiiiiiii+5z6-3z5-2z3-3z2+z+1,iiiiiiiiiiz14+2z13-3z12-5z11+4z10-2z9iiiiiiiiii+z8+4z6+4z5-2z4+3z3+5z2+5z-4}.
So, the common minimal polynomial p(z) of A1 and A2 is
(50)z14+2z13-3z12-5z11+4z10-2z9+z8+4z6+4z5-2z4+3z3+5z2+5z-4.


## 4.  Inverses of Level-k Scaled Factor Circulant Matrices

In this section, we discuss the nonsingularity and the inverse of a level-k scaled factor circulant matrix.Theorem 14.
LetA∈F[σ1,…,σk] be an N×N level-k scaled factor circulant matrix. Then, A is nonsingular if and only if
(51)1∈〈f(x1,…,xk),x1n1-∏j1=1n1‍d1j1,iiiiiiiiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉,
where the polynomial f(x1,…,xk) is the representer of A.Proof.
A is nonsingular if and only if
(52)f(x1,…,xk)+〈x1n1-∏j1=1n1‍d1j1,iiiiiiiiiiiiiiiiiiiiiiiiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉
is an invertible element in
(53)F[x1,…,xk]〈x1n1-∏j1=1n1‍d1j1,x2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉.
By Theorem 2, if and only if there exists h(x1,…,xk)+〈x1n1-∏j1=1n1d1j1,…,xknk-∏jk=1nkdkjk〉∈F[x1,…,xk]/〈x1n1-∏j1=1n1d1j1,…,xknk-∏jk=1nkdkjk〉 such that f(x1,…,xk)h(x1,…,xk)+〈x1n1-∏j1=1n1d1j1,…,xknk-∏jk=1nkdkjk〉≡1+〈x1n1-∏j1=1n1d1j1,…,xknk-∏jk=1nkdkjk〉 if and only if there exist h,u1,…,uk∈F[x1,…,xk] such that
(54)hf+u1(x1n1-∏j1=1n1‍d1j1)+u2(x2n2-∏j2=1n2‍d2j2)iiii+⋯+uk(xknk-∏jk=1nk‍dkjk)=1
if and only if
(55)1∈〈f(x1,…,xk),x1n1-∏j1=1n1‍d1j1,iiiiiiiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉.LetA∈F[σ1,…,σk] be an N×N level-k scaled factor circulant matrix. By Theorem 14, we have the following algorithm which can find the inverse of the matrix A.Step 10 .
Calculate the reduced Gröbner basisG for the ideal
(56)〈f(x1,…,xk),x1n1-∏j1=1n1‍d1j1,iiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉,
where the polynomial f(x1,…,xk) is the representer of A, by CoCoA 4.0, using a given term order with x1>⋯>xk. If G≠{1}, then A is singular. Stop. Otherwise, go to Step 11.Step 11.
Using Buchberger’s algorithm for computing Gröbner bases, by keeping track of linear combinations that give rise to the new polynomials in the generating set, we geth,u1,…,uk∈F[x1,…,xk] such that
(57)hf+u1(x1n1-∏j1=1n1‍d1j1)+u2(x2n2-∏j2=1n2‍d2j2)iiiiii+⋯+uk(xknk-∏jk=1nk‍dkjk)=1.Step 12.
The variablesx1,…,xk in formula (57) are replaced by σ1,…,σk, respectively. We have
(58)A-1=h(σ1,…,σk).


## 5. Inverse of Partitioned Matrix with Level-k Scaled Factor Circulant Matrix Blocks

LetA1,A2,A3, and A4 be level-k scaled factor circulant matrices with the representers f1,f2,f3, and f4, respectively. If A1 is nonsingular, let
(59)iiΣ=(A1A2A3A4),Π1=(I0-A3A1-1I),Π2=(I-A1-1A20I).
Then,
(60)Π1ΣΠ2=(A100A4-A3A1-1A2).
So, Σ is nonsingular if and only if A4-A3A1-1A2 is nonsingular. Since A1,A2,A3,andA4 are all level-k scaled factor circulant matrices, then Ai commutes with Aj if i≠j. Thus,
(61)A1(A4-A3A1-1A2)=A1A4-A2A3.
From (61), we conclude that Σ is nonsingular if and only if A1A4-A2A3 is nonsingular. Since f1f4-f2f3 is the representer of A1A4-A2A3, then Σ is nonsingular if and only if
(62)1∈〈f1f4-f2f3,x1n1-∏j1=1n1‍d1j1,iiiiiiiiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉.
Furthermore, if Σ is nonsingular, by (60), we have
(63)Σ-1=(I-A1-1A20I)(A1-100(A4-A3A1-1A2)-1)ii×(I0-A3A1-1I)ii=(A1-1+Δ1-1A2A3A1-1-Δ1-1A2-Δ1-1A3Δ1-1A1),
where Δ1=A1A4-A2A3.We summarize our discussion as the following.Theorem 15.
Let(64)Σ=(A1A2A3A4),
where A1,A2,A3, and A4 are all level-k scaled factor circulant matrices with the representers f1,f2,f3, and f4, respectively. If A1 is nonsingular, then Σ is nonsingular if and only if
(65)1∈〈f1f4-f2f3,x1n1-∏j1=1n1‍d1j1,iiiiiiiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉.
Moreover, if Σ is nonsingular, then
(66)Σ-1=(A1-1+Δ1-1A2A3A1-1-Δ1-1A2-Δ1-1A3Δ1-1A1),
where Δ1=A1A4-A2A3.Theorem 16.
Let(67)Σ=(A1A2A3A4),
where A1,A2,A3, and A4 are all level-k scaled factor circulant matrices with the representers f1,f2,f3, and f4, respectively. If A4 is nonsingular, then Σ is nonsingular if and only if
(68)1∈〈f1f4-f2f3,x1n1-∏j1=1n1‍d1j1,iiiiiiiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉.
In addition, if Σ is nonsingular, then
(69)Σ-1=(Δ1-1A4-Δ1-1A2-Δ1-1A3A4-1+Δ1-1A2A3A4-1),
where Δ1=A1A4-A2A3.Proof.
SinceA4 is nonsingular, then
(70)(I-A2A4-10I)Σ(I0-A4-1A3I)=(A1-A2A4-1A300A4).
So. Σ is nonsingular if and only if A1-A2A4-1A3 is nonsingular. Since A1,A2,A3, and A4 are all level-k scaled factor circulant matrices, then Ai commutes with Aj if i≠j. Thus,
(71)A4(A1-A2A4-1A3)=A1A4-A2A3.
By (71), we conclude that Σ is nonsingular if and only if A1A4-A2A3 is nonsingular. Since f1f4-f2f3 is the representer of A1A4-A2A3, then Σ is nonsingular if and only if
(72)1∈〈f1f4-f2f3,x1n1-∏j1=1n1‍d1j1,iiiiiiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉.
If Σ is nonsingular, by (70), we have
(73)Σ-1=(I0-A4-1A3I)((A1-A2A4-1A3)-100A4-1)iiiiiiiiii×(I-A2A4-10I)iiiii=(Δ1-1A4-Δ1-1A2-Δ1-1A3A4-1+Δ1-1A2A3A4),
where Δ1=A1A4-A2A3.We have the following algorithm for determining the nonsingularity and computing the inverse ofΣ if it is nonsingular.Step 13 .
Calculate the basesG1,G4 for the ideals
(74)〈f1,x1n1-∏j1=1n1‍d1j1,x2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉,〈f4,x1n1-∏j1=1n1‍d1j1,x2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉,
respectively. If G1≠{1},G4≠{1} Stop. Otherwise, go to Step 14.Step 14.
IfG1={1}, find u1,u2,…,uk,h1∈F[x1,x2,…,xk] such that
(75)h1f1+u1(x1n1-∏j1=1n1‍d1j1)+u2(x2n2-∏j2=1n2‍d2j2)+⋯+uk(xknk-∏jk=1nk‍dkjk)=1.
Then, h1 is the representer of A1-1, and go to Step 16. Otherwise, go to Step 15.Step 15.
IfG4={1}, find u1′,u2′,…,uk′,h4∈F[x1,x2,…,xk] such that
(76)h4f4+u1′(x1n1-∏j1=1n1‍d1j1)+u2′(x2n2-∏j2=1n2‍d2j2)iii+⋯+uk′(xknk-∏jk=1nk‍dkjk)=1.
Then, h4 is the representer of A4-1, and go to Step 16.Step 16.
Calculate the Gröbner basesG for the ideal
(77)〈f1f4-f2f3,x1n1-∏j1=1n1‍d1j1,iiiiiix2n2-∏j2=1n2‍d2j2,…,xknk-∏jk=1nk‍dkjk〉.
If G≠{1}, then A1A4-A2A3 is singular, Stop. Otherwise, go to Step 17.Step 17.
Findv1,v2,…,vk,h∈F[x1,x2,…,xk] such that
(78)h(f1f4-f2f3)+v1(x1n1-∏j1=1n1‍d1j1)+v2(x2n2-∏j2=1n2‍d2j2)iiiii+⋯+vk(xknk-∏jknk‍dkjk)=1.
Then, h is the representer of (A1A4-A2A3)-1. Thus, we obtain that
ifA1 is nonsingular, then
(79)Σ-1=(μ1-h(σ1,σ2,…,σk)A2-h(σ1,σ2,…,σk)A3h(σ1,σ2,…,σk)A1),
where μ1=h1(σ1,σ2,…,σk)[I+h(σ1,σ2,…,σk)×A2A3].
IfA4 is nonsingular, then
(80)Σ-1=(h(σ1,σ2,…,σk)A4-h(σ1,σ2,…,σk)A2-h(σ1,σ2,…,σk)A3μ2),
where μ2=h4(σ1,σ2,…,σk)[I+h(σ1,σ2,…,σk)×A2A3].


## 6. Conclusion

Algorithms for finding the minimal polynomial of the level-k scaled factor circulant matrices over any field are presented. And two algorithms for finding the inverses of such matrices are also presented. Finally, an algorithm for computing the inverse of partitioned matrix with level-k scaled factor circulant matrix blocks over any field is given. In the future, we will investigate the application in solving various differential equations based on multilevel circulant matrices.



---

*Source: 521643-2014-06-05.xml*