KYUNGPOOK Math. J. 2019; 59(3): 505-513
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
Orthogonal polynomials; companion matrix, comrade matrix, reachability matrix.
Received: February 22, 2018; Revised: January 22, 2019; Accepted: January 26, 2019; Published online: September 23, 2019.

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

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.

Introduction

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.

Preliminaries

$p(x)=xn−cn−1xn−1−…−c1x−c0∈F[x].$We can find a companion matrix $C=(000⋯00c0100⋯00c1⋮⋮⋮⋮⋮⋮000…00cn−2000…01cn−1).$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)qi−1(x)−ciqi−2(x), i=2,3,…,$with ai > 0, ci > 0. We write an nth degree generalized polynomial as $d(x)=dnqn(x)−dn−1qn−1(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)/(a1…an)=xn−d˜n−1xn−1−…−d˜1x−d˜0=p(x).$Then, the relationship between the coefficients in (2.4) and (2.5) will be $(a1a2…an)[c0,c1,…,cn−1,1]=[d0,d1,…,dn−1,1]Qn+1$where $Qn+1=(10⋯0q10q110⋯0q20q21q22⋯0⋮⋮⋱⋮qn0qn1qn2…qnn).$By properties associated with d(x) in (2.4) without using (2.6), the comrade matrix is introduced by: $A=(−b1a11a10⋯d0anc2a2−b2a21a20⋯d1an0c3a3−b3a31a3⋮⋮⋱⋱⋱dn−2+cnan0⋯cn−1an−1−bn−1an−11an−1dn−1−bnan).$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,…,An−1b]∈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(xI−A)=d(x)/(a1a2…an).$Also, A is similar to C associated with (2.7), i.e. $A=QnCQn−1.$Easily, we can determine $R(C,b)=Qn−1R(A,Qnb).$Let us define the generating polynomial of $b=[b0,b1,…,bn−1]T∈Fn×1 by b(x)=∑k=0n−1bkxk.$Then $R(C,b)=∑k=0n−1bkR(C,ek)=∑k=0n−1bkCk=b(C)=Qn−1R(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)and$a(x)=∑k=0n−1akxk$be the generating polynomial of then 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=0n−1aiR(C,ei)=∑i=0n−1aiCi=∑i=0n−1aiQn−1AiQn=Qn−1∑i=0n−1aiAiQn=Qn−1a(A)Qn.$

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

### Theorem 3.2

Let polynomial be the same as (2.4). Then$S(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 , the proof is completed.

### Theorem 3.3

Let be 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, then$R(A,Qna)−1=Qn−1R(A,Qnb)Qn−1$andbis determined by the generating polynomialb(x) such that$d(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 .

Some Results

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),…,qn−1(λi)]T, i=0,1,…,n−1.$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: $MC−1CMC=D and N−1AN=D.$

### Theorem 4.1

Let A be the comrade matrix of the generalized polynomial d(x) similar to (2.8) and$a(x)=∑k=0n−1akxk$be the generating polynomial of and $Qn−1R(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)0⋯0q10a(λ0)q11a(λ1)⋯0⋮⋮⋱⋮qn−10a(λ0)qn−11a(λ1)…qnna(λn−1),)$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,…,λin−1]T$. MCT = [Λ1, . . . , Λn−1] is the modal matrix of CT and N = QnMCT. If we write: $R(A,a)u(λi)=Qna(C)Qn−1u(λi)=Qna(C)Qn−1QnMCTei=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: $det R(A,a)=∏i=0n−1aTΛi or det R(A,a)=∏i=0n−1a(λ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)Qn−1N.$Also, we obtain $det R(A,y)=det Qn det R(C,a),$we know that $det Qn=q11q22…qn−1n−1 and det R(C,a)=∏i=0n−1aTΛi.$Then $det R(A,y)=∏i=0n−1qiiaTΛi.$From det$R(ST,w)=(−1)⌊n2⌋$ and relation (13) in , we have: $det R(AT,a)=(−1)⌊n2⌋∏i=0n−1qiiaTmi.$Let Z = Qn/det Qn from (3.5), we have: $R(A,a)=Z−1Qn−1Za(A)Qn=Z−1(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) that$d˜(x)=d1(x)m1…dr(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) and$det R(A,x)=(f1(x))m1…(fr(x))mr$that f1(x), . . . , fr(x) are irreducible and homogeneous of degree l1, . . . , lr, respectively.

Proof

$(Zx)(Cdj)=b(Cdj)=∑i=0n−1biCdji=∑i=0n−1biQdj−1AdjiQdj=Qdj−1∑i=0n−1biAdjiQdj=Qdj−1b(Adj)Qdj=Qdj−1(Zx)(Adj)Qdj,$then fj(x) = det (Zx)(Cdj) = det (Zx)(Adj), j = 1, . . . , r. Now let $C(dj,mj)=(CdjIlj0⋅00CdjIlj⋅0⋅⋅⋅⋅⋅⋅⋅⋅CdjIlj⋅⋅⋅⋅Cdj)mjlj×mjlj=(Qdj−1AdjQdjIlj0⋅00Qdj−1AdjQdjIlj⋅0⋅⋅⋅⋅⋅⋅⋅⋅Qdj−1AdjQdjIlj⋅⋅⋅⋅Qdj−1AdjQdj)=(Qdj−10⋅00Qdj−1⋅0⋅⋅⋅⋅⋅⋅Qdj−10⋅⋅⋅Qdj−1)︸Qdj−1(AdjIlj⋅00AdjIlj⋅⋅⋅⋅⋅⋅⋅AdjIlj⋅⋅⋅Adj)︸Adj(Qdj0⋅00Qdj⋅0⋅⋅⋅⋅⋅⋅Qdj0⋅⋅⋅Qdj)︸Qdj.$Then for some : $TCT−1=diag(C(d1,m),…,C(dr,mr))=diag(Qd1−1Ad1Qd1,…,Qdr−1AdrQdr)=(Qd1−10⋅00Q2−1⋅0⋅⋅⋅⋅⋅⋅⋅Qr−1)︸Q−1(Ad10⋅00Ad2⋅0⋅⋅⋅⋅⋅⋅⋅Adr)︸A(Qd10⋅00Qd2⋅0⋅⋅⋅⋅⋅⋅⋅Qdr)︸Q,$will be the rational canonical form (the Frobenius canonical form) of C. If then $R(C,b^)=b^(C)=T−1b^[diag(C(d1,m1),…,C(dr,mr))]T=T−1Q−1b^[diag(Ad1,…,Adr)]QT,$and $det b^(C)=(det b^(Ad1))m1⋯(det b^(Adr))mr.$Then proof is completed by Theorem 3.2 in .

Summary

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.

References
1. S. Barnett. Congenial matrices. Linear Algebra Appl.., 41(1981), 277-298.
2. DS. Bernstein. Matrix mathematics: theory, facts, and formulas, , Princeton university press, Prenceton, 2009.
3. JP. Boyd. Computing real roots of a polynomial in Chebyshev series form through subdivision. Appl. Numer Math., 56(2006), 1077-1091.
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.
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.
6. G-S. Cheon, and H. Kim. A new aspect of Hankel matrices via Krylov matrix. Linear Algebra Appl., 438(2013), 361-373.
7. A. Ferrante, and HK. Wimmer. Reachability matrices and cyclic matrices. Electron. J. Linear Algebra., 20(2010), 95-102.
8. IJ. Good. The colleague matrix, a Chebyshev analogue of the companion matrix. Quart J Math. Oxford Ser. (2), 12, 1961:61-68.
9. Shams Solary. M. A connection between comrade matrices and reachability matrices. SIAM Conference on Applied Linear Algebra (LA15); 2015 p. 72-73. 