검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

KYUNGPOOK Math. J. 2019; 59(3): 505-513

Published online September 23, 2019

Copyright © Kyungpook Mathematical Journal.

A New Aspect of Comrade Matrices by Reachability Matrices

Maryam Shams Solary

Department of Mathematics, Payame Noor University, P. O. Box 19395-3697 Tehran, Iran
e-mail : shamssolary@pnu.ac.ir, shamssolary@gmail.com

Received: February 22, 2018; Revised: January 22, 2019; Accepted: January 26, 2019

In this paper, we study orthanogonal polynomials by looking at their comrade matrices and reachability matrices. First, we focus on the algebraic structure that is exhibited by comrade matrices. Then, we explain some properties of this algebraic structure which helps us to find a connection between comrade matrices and reachability matrices. In the last section, we use this connection to determine the determinant, eigenvalues, and eigenvectors of these matrices. Finally, we derive a factorization for det R(A, x), where R(A, x) is the reachability matrix for a comrade matrix A and x is a vector of indeterminates.

Some recurrence relations from the general theory of orthogonal polynomials are shown in [1, 2, 4], these relations are given in terms of comrade matrices. Comrade matrices have regular form and may be used in finding the roots of a polynomial that an important problem in the numerical analysis.

As we know, Frobenius’s original idea used of companion matrices to find the zeros of a polynomial or a function. It can be expressed by some limitations and conditions for the condition number and floating point arithmetic [3, 4].

Specht, Boyd and Good et al. [5, 8] used this structure for finding the roots of a polynomial in Chebyshev form, for their method of rootfinding-by-proxy, and for Chebyshev interpolation. They derived these works using the Chebyshev-Frobenius matrix, which is also known as a colleague matrix.

The colleague matrix and companion matrix are known to be special cases of comrade matrices. In this paper, we try to use their algebraic structures to explain a connection between comrade matrices and reachability matrices. Using this connection, we then find the determinant, eigenvalues, and eigenvectors of their algebraic structures.

This paper is organized as follows: Some necessary details about comrade matrices and orthogonal polynomials are presented in Section 2. A connection between comrade matrices and reachability matrices is introduced in Section 3. Some results of this connection are given in Section 4. Finally, a summary is given in Section 5.

p(x)=xncn1xn1c1xc0F[x].We can find a companion matrix C=(00000c010000c100000cn200001cn1).We limit ourselves to the case that is ℝ or ℂ, the fields of real and complex numbers respectively. If the polynomial is in generalized form, i.e. has a basis of orthogonal polynomials {qi(x)}. Then we have an analogue to the companion matrix that is called the comrade matrix. Let an orthogonal basis {qi(x)}, be defined by the standard relations q0(x)=1,q1(x)=a1x+b1,qi(x)=(aix+bi)qi1(x)ciqi2(x),i=2,3,,with ai > 0, ci > 0. We write an nth degree generalized polynomial as d(x)=dnqn(x)dn1qn1(x)d1q1(x)d0q0(x).If we write qi(x)=j=0iqijxi, i = 1, 2, . . . , n, then the leading coefficient of qi(x) is qii = a1a2 . . . ai > 0.

Assume, without loss of generality, that q00 = 1 and dn = 1, then the corresponding relationship between p(x) in (2.1) and d(x) in (2.4) will be d˜(x)=d(x)/(a1an)=xnd˜n1xn1d˜1xd˜0=p(x).Then, the relationship between the coefficients in (2.4) and (2.5) will be (a1a2an)[c0,c1,,cn1,1]=[d0,d1,,dn1,1]Qn+1where Qn+1=(100q10q1100q20q21q220qn0qn1qn2qnn).By properties associated with d(x) in (2.4) without using (2.6), the comrade matrix is introduced by: A=(b1a11a10d0anc2a2b2a21a20d1an0c3a3b3a31a3dn2+cnan0cn1an1bn1an11an1dn1bnan).When ai = 1, bi = ci = 0, for all 1 ≤ i ≤ n then (2.8) reduces to the companion matrix from (2.2).

The colleague matrix deduced from Chebyshev polynomials in (2.3) and matrix A in (2.8).

Let , . Then the matrix R(A,b)=[b,Ab,,An1b]Fn×n,is the reachability matrix of the pair (A, b). Also, the Krylov matrix of A and b is defined by K(A, b) := [bAbA2b . . . An−1b], so this is a reachability matrix. Krylov matrices of CT are Hankel matrices, see [6, 9]. Let p(x) = xn − 1. Then Krylov matrices of C would be Circulant matrices.

The comrade matrix in (2.8) is nonderogatory and cyclic with the monic characteristic polynomial of (2.4), i.e., det(xIA)=d(x)/(a1a2an).Also, A is similar to C associated with (2.7), i.e. A=QnCQn1.Easily, we can determine R(C,b)=Qn1R(A,Qnb).Let us define the generating polynomial of b=[b0,b1,,bn1]TFn×1byb(x)=k=0n1bkxk.Then R(C,b)=k=0n1bkR(C,ek)=k=0n1bkCk=b(C)=Qn1R(A,Qnb),where ek stands for the (k + 1)th unit vector in the standard basis of .

Theorem 3.1

If C be the companion matrix of p(x) similar to(2.2), A be the comrade matrix of d(x) similar to(2.8)anda(x)=k=0n1akxkbe the generating polynomial ofthen the reachability matrix of the pair (C, a) will be similar as the generating polynomial A.

Proof

From (3.2) and (3.4), we have R(C,a)=a(C)=i=0n1aiR(C,ei)=i=0n1aiCi=i=0n1aiQn1AiQn=Qn1i=0n1aiAiQn=Qn1a(A)Qn.

Now, we introduce an algebraic structure of the set S(A)={Qn1R(A,Qnb)|bFn×1}.For any a, and from (3.4), we derive Qn1R(A,Qna)+Qn1R(A,Qnb)=R(Qn1AQn,a)+R(Qn1AQn,b)=R(C,a)+R(C,b)=R(C,a+b)=Qn1R(A,Qn(a+b)).From (3.3) and (3.4), we have Qn1R(A,Qna)b=R(Qn1AQn,a)b=R(C,a)b=R(C,b)a=Qn1R(A,Qnb)a.Also Qn1R(A,Qna)Qn1R(A,Qnb)=Qn1R(A,b(A)Qna),Qn1R(A,Qne0) is unity element of commutative ring .

Theorem 3.2

Let polynomialbe the same as (2.4). ThenS(A)F[x]/d(x).Also, if d(x) is irreducible over then is a field.

Proof

Let . We can easily see, is isomorphism with , then ideal ≺d(x)≻ of is generated by d(x) is similar as ideal ≺p(x)≻ of , see relations (2.5) and (3.1). Then by Theorem 2.1 and Corollary 2.2 in [6], the proof is completed.

Theorem 3.3

Letbe the same as (2.4). A reachability matrix similar to R(A, Qna) is invertible if and only if gcd(a(x), d(x)) = 1, thenR(A,Qna)1=Qn1R(A,Qnb)Qn1andbis determined by the generating polynomialb(x) such thatd(x)q(x)+a(x)b(x)=1,q(x)F[x].

Proof

For proof see Theorem 3.2. in this paper and Theorem 2.3 in [6].

Let λ0, . . . , λn−1 be the distinct eigenvalues of the companion matrix C in (2.2) and m0, . . . , mn−1 be the eigenvectors of C associated with the eigenvalues λi’s. Then λi’s will be the eigenvalues of the comrade matrix A in (2.8) with the eigenvectors u(λi)=[1,q1(λi),,qn1(λi)]T,i=0,1,,n1.MC = [m0, m1, . . . , mn−1], will be modal matrix of C, D = diag[a(λ0) . . .a(λn−1)] and N = [u(λ0), u(λ1), . . . , u(λn−1)] will be the generalized Vandermonde matrix. Then from [1, 6], we obtain: MC1CMC=DandN1AN=D.

Theorem 4.1

Let A be the comrade matrix of the generalized polynomial d(x) similar to (2.8) anda(x)=k=0n1akxkbe the generating polynomial of and Qn1R(A,Qna)be an element of. Thena(λ0), . . . , an−1) are the eigenvalues of R(A, a) with eigenvectorsu(λ0), . . . , u(λn−1).

Proof

If a(x) will be the generating polynomial of a = [a0, . . . , an−1]T, then R(C,a)mi=a(λi)mi,and R(A,Qna)MC=QnDMC.Namely diagonal elements of matrix: QnD=(a(λ0)00q10a(λ0)q11a(λ1)0qn10a(λ0)qn11a(λ1)qnna(λn1),)are eigenvalues of matrix R(A, Qna), then MC will be the modal matrix of C. We have a(λi) = aT Λi, that Λi=[1,λi,,λin1]T. MCT = [Λ1, . . . , Λn−1] is the modal matrix of CT and N = QnMCT. If we write: R(A,a)u(λi)=Qna(C)Qn1u(λi)=Qna(C)Qn1QnMCTei=a(λi)QnΛi=a(λi)u(λi)then a(λ0), . . . , a(λn−1) are the eigenvalues of R(A, a) with eigenvectors u(λ0), . . . , u(λn−1).

Now we derive: detR(A,a)=i=0n1aTΛiordetR(A,a)=i=0n1a(λi).If S be the companion matrix of xn and MCT be the modal matrix of CT, then MC = R(ST, w)MCT, that w = [−c1, . . . , −cn−2, −cn−1, 1]T.

Let y = Qna, easily we can see R(A,y)MC=QnR(C,a)R(ST,v)Qn1N.Also, we obtain detR(A,y)=detQndetR(C,a),we know that detQn=q11q22qn1n1anddetR(C,a)=i=0n1aTΛi.Then detR(A,y)=i=0n1qiiaTΛi.From detR(ST,w)=(1)n2 and relation (13) in [6], we have: detR(AT,a)=(1)n2i=0n1qiiaTmi.Let Z = Qn/det Qn from (3.5), we have: R(A,a)=Z1Qn1Za(A)Qn=Z1(Za)(C).Then det R(A, a) = det Za(C).

Now we derive the following theorem:

Theorem 4.2

Let A be a comrade matrix with distinct eigenvalues and characteristic polynomial d̃(x) in (2.5) thatd˜(x)=d1(x)m1dr(x)mr,be the prime factorization of d̃(x) and Z1AZ = C, (let C be the companion matrix similar as(2.2)and Z = Qn/det Qn). Set fj(x) = det (Zx)(Cdj), j = 1, . . . , r. Then fj(x) = det (Zx)(Adj) anddetR(A,x)=(f1(x))m1(fr(x))mrthat f1(x), . . . , fr(x) are irreducible and homogeneous of degree l1, . . . , lr, respectively.

Proof

(Zx)(Cdj)=b(Cdj)=i=0n1biCdji=i=0n1biQdj1AdjiQdj=Qdj1i=0n1biAdjiQdj=Qdj1b(Adj)Qdj=Qdj1(Zx)(Adj)Qdj,then fj(x) = det (Zx)(Cdj) = det (Zx)(Adj), j = 1, . . . , r. Now let C(dj,mj)=(CdjIlj000CdjIlj0CdjIljCdj)mjlj×mjlj=(Qdj1AdjQdjIlj000Qdj1AdjQdjIlj0Qdj1AdjQdjIljQdj1AdjQdj)=(Qdj1000Qdj10Qdj10Qdj1)Qdj1(AdjIlj00AdjIljAdjIljAdj)Adj(Qdj000Qdj0Qdj0Qdj)Qdj.Then for some : TCT1=diag(C(d1,m),,C(dr,mr))=diag(Qd11Ad1Qd1,,Qdr1AdrQdr)=(Qd11000Q210Qr1)Q1(Ad1000Ad20Adr)A(Qd1000Qd20Qdr)Q,will be the rational canonical form (the Frobenius canonical form) of C. If then R(C,b^)=b^(C)=T1b^[diag(C(d1,m1),,C(dr,mr))]T=T1Q1b^[diag(Ad1,,Adr)]QT,and detb^(C)=(detb^(Ad1))m1(detb^(Adr))mr.Then proof is completed by Theorem 3.2 in [7].

We try to show a connection between comrade matrices and reachability matrices. For this work, we introduce an algebraic structure and some properties of this structure. Then, using this structure, we find the determinant, eigenvalues, and eigenvectors of the reachability matrices. Also, we derive a factorization of the polynomial det R(A, x), for a comrade matrix A and a vector of indeterminates x. We can refer to Chebyshev polynomials and the colleague matrices for an experimental investigation of this connection.

  1. S. Barnett. Congenial matrices. Linear Algebra Appl.., 41(1981), 277-298.
    CrossRef
  2. DS. Bernstein. Matrix mathematics: theory, facts, and formulas, , Princeton university press, Prenceton, 2009.
    CrossRef
  3. JP. Boyd. Computing real roots of a polynomial in Chebyshev series form through subdivision. Appl. Numer Math., 56(2006), 1077-1091.
    CrossRef
  4. JP. Boyd. Finding the zeros of a univariate equation: proxy rootfinders, Chebyshev interpolation, and the companion matrix. SIAM Rev.., 55(2)(2013), 375-396.
    CrossRef
  5. JP. Boyd, and DH. Gally. Numerical experiments on the accuracy of the ChebyshevFrobenius companion matrix method for finding the zeros of a truncated series of Chebyshev polynomials. J. Comput. Appl. Math., 205(2007), 281-295.
    CrossRef
  6. G-S. Cheon, and H. Kim. A new aspect of Hankel matrices via Krylov matrix. Linear Algebra Appl., 438(2013), 361-373.
    CrossRef
  7. A. Ferrante, and HK. Wimmer. Reachability matrices and cyclic matrices. Electron. J. Linear Algebra., 20(2010), 95-102.
    CrossRef
  8. IJ. Good. The colleague matrix, a Chebyshev analogue of the companion matrix. Quart J Math. Oxford Ser. (2), 12, 1961:61-68.
    CrossRef
  9. Shams Solary. M. A connection between comrade matrices and reachability matrices. SIAM Conference on Applied Linear Algebra (LA15); 2015 p. 72-73.