- Email: [email protected]

Contents lists available at ScienceDirect

Applied Mathematics and Computation journal homepage: www.elsevier.com/locate/amc

Singular value decomposition for comb ﬁlter matrices Jesús Gutiérrez-Gutiérrez CEIT and Tecnun (University of Navarra), Manuel Lardizábal 15, 20018 San Sebastián, Spain

a r t i c l e

i n f o

a b s t r a c t In this paper, we present an eigenvalue decomposition for any n n complex matrix with constant diagonals T n ¼ ðajk Þnj;k¼1 satisfying that there exists a positive integer m such that ak ¼ 0 for all k R fm; 0; mg. Moreover, from this eigenvalue decomposition we obtain a singular value decomposition for any comb ﬁlter matrix. Ó 2013 Elsevier Inc. All rights reserved.

Keywords: Eigenvalues Eigenvectors Pentadiagonal matrices Singular values Tridiagonal matrices

1. Introduction In [1,2] Rimas presented an eigenvalue decomposition for the n n pentadiagonal Toeplitz matrix pentadiagn ð1; 0; 0; 0; 1Þ, where

0

a0 B a1 B Ba B 2 B 0 pentadiagn ða2 ; a1 ; a0 ; a1 ; a2 Þ :¼ B B B0 B B . @ .. 0

a1 a0 a1 a2 0 .. . 0

a2 a1 a0 a1 a2 .. . 0

0 a2 a1 a0 a1 .. . 0

0 0 a2 a1 a0

0 0 0 0

1

C C C C C C; C C C .. .. C . . A a0

with a2 ; a1 ; a0 ; a1 ; a2 2 C, and where C denotes the set of (ﬁnite) complex numbers. In Section 2 of the present paper, we generalize that Rimas’ work to a much wider class of banded Toeplitz matrices, namely, we obtain an eigenvalue decomposition for any n n complex Toeplitz matrix T n ¼ ðajk Þnj;k¼1 satisfying that there exists a positive integer m such that ak ¼ 0 for all k R fm; 0; mg:

0

a0 B 0 B B 0 B B . B . B . B Tn ¼ B B 0 Ba B m B B 0 B B .. @ . 0

0 a0 0 .. . 0 0 am .. . 0

0 0 a0 .. . 0 0 0 .. . 0

0 0 0 .. . . .. a0 0 0

am 0 0 .. . 0 a0 0

0 am 0 .. . 0 0 a0

0 0 0

1

C C C C C C C C C: C C C C C C .. . C . . . A a0

E-mail address: [email protected] 0096-3003/$ - see front matter Ó 2013 Elsevier Inc. All rights reserved. http://dx.doi.org/10.1016/j.amc.2013.07.050

ð1Þ

J. Gutiérrez-Gutiérrez / Applied Mathematics and Computation 222 (2013) 472–477

473

To do that we use the eigenvalue decomposition that we gave in [3, Theorem 1] for the case m ¼ 1, i.e., for n n complex tridiagonal Toeplitz matrices

0

a0 Ba B 1 B B0 B tridiagn ða1 ; a0 ; a1 Þ :¼ B 0 B B . B . @ .

1

a1

0

0

0

a0

a1

0

a1

a0

a1

0 .. .

a1 .. .

a0 .. .

.. .

0C C C 0C C : 0C C C .. C . A

0

0

0

a0

0

In Section 3 we apply the eigenvalue decomposition obtained in Section 2 for the matrix T n in (1) to compute a singular value decomposition (SVD) for any n n þ m complex Toeplitz matrix of the form

0

Hnnþm

B B B B ¼B B B @

h0

0

0

hm

0

0

0

h0

0

0

hm

0

0 .. .

0 .. .

h0 .. .

0

0

hm

0

0

0

0

1

C 0 C C 0 C C; .. .. C C . . A hm

ð2Þ

with m 2 N, where N denotes the set of natural numbers (that is, the set of positive integers). Examples of such Hnnþm matrices are comb ﬁlter matrices, i.e., matrix representations of comb ﬁlters. A comb ﬁlter is a discrete-time causal ﬁnite impulse response (FIR) ﬁlter that has only two non-zero taps, that is, two non-zero values in its impulse response (see, e.g., [4, p. 20] or [5]). The SVD computed in the present paper ﬁnds application in Communications, namely, in vector coding. Vector coding (see, e.g., [6, p. 390]) is a channel partitioning technique whereby a discrete-time channel with a causal FIR ﬁlter and an additive white noise is decomposed into n channels without intersymbol interference using a SVD of its n n þ m channel matrix, which is a complex matrix of the form

0 B B B B B B B @

h0

h1

h2

0

h0

h1

0 .. .

0 .. .

0

0

hm

0

0

h1m

hm

0

h0 .. .

h2m

h1m

hm

0

0

1

C 0 C C 0 C C; .. .. C C . . A hm

where m is the channel memory. Therefore, the SVD computed in the present paper can be applied in vector coding for those channels whose ﬁlter is a comb ﬁlter. An example of those channels with a comb ﬁlter can be found in [6, Example 12.5]. 2. Eigenvalue decomposition for T n 2.1. The case m ¼ 1

Theorem 1 [3, Theorem 1]. Let n 2 N and a1 ; a0 ; a1 2 C, with a1 a1 – 0. Then W n Dn W 1 n is an eigenvalue decomposition of tridiagn ða1 ; a0 ; a1 Þ, where the entries of the eigenvector matrix W n are

½W n j;k

rﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃrﬃﬃﬃﬃﬃﬃﬃﬃj 2 a1 jkp ¼ sin ; nþ1 a1 nþ1

1 6 j; k 6 n

and Dn ¼ diagða1 ; . . . ; an Þ :¼ ðaj dj;k Þnj;k¼1 , with

aj ¼ a0 þ 2a1

rﬃﬃﬃﬃﬃﬃﬃﬃ a1 jp ; cos a1 nþ1

16j6n

and dj;k being the Kronecker delta. Moreover, W n can be written as

W n ¼ Kn !n ; where Kn is the diagonal matrix

Kn ¼ diag

rﬃﬃﬃﬃﬃﬃﬃﬃ rﬃﬃﬃﬃﬃﬃﬃﬃn ! a1 a1 ;...; a1 a1

474

J. Gutiérrez-Gutiérrez / Applied Mathematics and Computation 222 (2013) 472–477

and !n is the real symmetric orthogonal matrix

½!n j;k ¼

rﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ 2 jkp ; sin nþ1 nþ1

1 6 j; k 6 n:

qﬃﬃﬃﬃﬃﬃ qﬃﬃﬃﬃﬃﬃn 1 a1 a1 Since K1 ¼ diag ; . . . ; , the entries of the inverse of the eigenvector matrix W n of tridiagn ða1 ; a0 ; a1 Þ n a1 a1 given in Theorem 1 can be computed by the simple expression 1 1 > 1 1 1 ½W 1 n j;k ¼ ½!n Kn j;k ¼ ½!n Kn j;k ¼ ½!n Kn j;k ¼ ½!n j;k ½Kn k;k ¼

rﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃrﬃﬃﬃﬃﬃﬃﬃﬃk 2 a1 jkp sin nþ1 a1 nþ1

for all 1 6 j; k 6 n, where > denotes transpose. That eigenvector matrix W n of tridiagn ða1 ; a0 ; a1 Þ is unitary if and only if ja1 j ¼ ja1 j (see [3, p. 888]). Thus, W n is unitary, e.g., when tridiagn ða1 ; a0 ; a1 Þ is Hermitian. Observe that if tridiagn ða1 ; a0 ; a1 Þ is Hermitian, from Theorem 1 we obtain [7, Theorem 1]. 2.2. The general case We begin by introducing some notation. The symbol denotes the Kronecker product, and 0mn and In are the m n zero matrix and the n n identity matrix, respectively. Let A be an n n matrix. If 1 6 j1 6 j2 6 n and 1 6 k1 6 k2 6 n, then ½Aj1 :j2 ;k1 :k2 denotes the j2 j1 þ 1 k2 k1 þ 1 submatrix of A formed by the entries ½Aj;k with j1 6 j 6 j2 and k1 6 k 6 k2 . If j1 ¼ j2 or k1 ¼ k2 , then ½Aj1 :j2 ;k1 :k2 is also denoted by ½Aj1 ;k1 :k2 or ½Aj1 :j2 ;k1 , respectively. We can now obtain an eigenvalue decomposition for the matrix T n in (1). Theorem 2. Given m; n 2 N with m < n, let c and r be the quotient and the remainder of the division of n by m, respectively. Consider the n n matrix T n in (1) with am ; a0 ; am 2 C and am am – 0. Let W j Dj W 1 be the eigenvalue decomposition for j tridiagj ðam ; a0 ; am Þ obtained from Theorem 1, with j 2 fc; c þ 1g. Then T n ¼ V n Dn V 1 n is an eigenvalue decomposition of T n where

ð3Þ and

ð4Þ Moreover,

ð5Þ

Proof. The equality W cþ1 W 1 cþ1 ¼ Icþ1 can be written as

Consequently,

and (5) is proved. To ﬁnish the proof we need to show that V n Dn V 1 n ¼ T n . We have

J. Gutiérrez-Gutiérrez / Applied Mathematics and Computation 222 (2013) 472–477

475

We denote by Aj the matrix tridiagj ðam ; a0 ; am Þ with j 2 fc; c þ 1g. Since the equality W cþ1 Dcþ1 W 1 cþ1 ¼ Acþ1 can be expressed as

we conclude that

Observe that 1 1 V 1 n ¼ V n () W c ¼ W c and W cþ1 ¼ W cþ1 ;

where denotes conjugate transpose. Therefore, the eigenvector matrix V n of T n is unitary if and only if jam j ¼ jam j. Thus, V n is unitary, for instance, when T n is Hermitian. From Theorem 2 we obtain

detðT n Þ ¼

rﬃﬃﬃﬃﬃﬃﬃﬃ rﬃﬃﬃﬃﬃﬃﬃﬃ !mr Y !r c cþ1 Y am jp am kp a0 þ 2am a0 þ 2am : cos cos am cþ1 am cþ2 j¼1 k¼1

ð6Þ

The eigenvalues of T n were already known for the case m ¼ 2 (see [8, Theorems 4 and 5]), that is, for T n ¼ pentadiagn ða2 ; 0; a0 ; 0; a2 Þ. Moreover, for that case m ¼ 2 we can ﬁnd in [8, Theorem 2] and [9, Lemma 8.1] two interesting expressions for detðT n Þ different from (6). We also mention here that if the matrix T n in (1) is real [10, Corollary 2] provides an interesting expression for detðT n Þ different from (6). 2.3. Natural powers of T n We ﬁnish this section with a result that gives a general expression for the natural powers of the matrix T n in (1) in terms of the natural powers of tridiagj ðam ; a0 ; am Þ with j 6 n. Theorem 3. Given m; n 2 N with 1 < m < n, let c and r be the quotient and the remainder of the division of n by m, respectively. Consider the n n matrix T n in (1) with am ; a0 ; am 2 C and am am – 0. Let Aj ¼ tridiagj ðam ; a0 ; am Þ with j 2 fc; c þ 1g, then T qn is given by

ð7Þ

for all q 2 N. Proof. Fix q 2 N. From Theorem 2 we know that T n ¼ V n Dn V 1 n . Consequently, to prove Theorem 3 is equivalent to prove that V n Dqn V 1 can be written as (7). We have n

and therefore,

476

J. Gutiérrez-Gutiérrez / Applied Mathematics and Computation 222 (2013) 472–477

q Since the equality W cþ1 Dqcþ1 W 1 cþ1 ¼ Acþ1 can be expressed as

we conclude that V n Dqn V 1 h n is given by (7). In [3, Theorem 2] we gave a general expression for the entries of the natural powers of a tridiagonal Toeplitz matrix in terms of the Chebyshev polynomials of the second kind.1 Consequently, combining Theorem 3 with [3, Theorem 2] we directly obtain a general expression for the entries of the natural powers of T n in terms of the Chebyshev polynomials of the second kind that generalizes the general expression given by Rimas in [1,2] for the entries of the natural powers of pentadiagn ð1; 0; 0; 0; 1Þ. q Observe that if r ¼ 0 in Theorems 2 and 3 then T qn ¼ ðtridiagc ðam ; a0 ; am ÞÞ Im for all q 2 N, and T n ¼ V n Dn V 1 with n 1 1 V n ¼ W c Im ; Dn ¼ Dc Im , and V n ¼ W c Im . 3. SVD for H nnþm We begin this section with a result that we will use to obtain a SVD for the matrix Hnnþm in (2). Lemma 4. Let m; n 2 N with m < n. Suppose that a0 is a (ﬁnite) real number and am ; am 2 C, with am ¼ am – 0. Consider the n n matrices T n ; V n , and Dn given by (1), (3), and (4), respectively. Let r : f1; . . . ; ng ! f1; . . . ; ng be a bijection satisfying that ½Dn rðjÞ;rðjÞ ¼ kj ðT n Þ for all 1 6 j 6 n, where kj ðT n Þ; 1 6 j 6 n, are the eigenvalues of the Hermitian matrix T n numbered in a nonincreasing order. Then T n ¼ U n diagðk1 ðT n Þ; . . . ; kn ðT n ÞÞU 1 n , where U n is the n n unitary matrix given by ½U n j;k ¼ ½V n j;rðkÞ for all 1 6 j; k 6 n. Proof. Since V n is unitary we have n n X X ½In j;k ¼ V n V n j;k ¼ ½V n j;h V n h;k ¼ ½V n j;h ½V n k;h h¼1

h¼1

n n n X X X ¼ ½V n j;rðhÞ ½V n k;rðhÞ ¼ ½U n j;h ½U n k;h ¼ ½U n j;h U n h;k ¼ U n U n j;k h¼1

h¼1

h¼1

for all 1 6 j; k 6 n. Therefore, U n is unitary, and applying Theorem 2 yields

h i ½T n j;k ¼ V n Dn V 1 n

j;k

n n n X X X ¼ V n Dn V n j;k ¼ ½V n j;h Dn V n h;k ¼ ½V n j;h ½Dn h;l V n l;k h¼1

h¼1

l¼1

n n n X X X ¼ ½V n j;h ½Dn h;h V n h;k ¼ ½V n j;h ½Dn h;h ½V n k;h ¼ ½V n j;rðhÞ ½Dn rðhÞ;rðhÞ ½V n k;rðhÞ h¼1

h¼1

h¼1

n n X X ¼ ½U n j;h kh ðT n Þ½U n k;h ¼ ½U n j;h kh ðT n Þ U n h;k h¼1

h¼1

n n n X X X ¼ ½U n j;h ½diagðk1 ðT n Þ; . . . ; kn ðT n ÞÞh;l U n l;k ¼ ½U n j;h diagðk1 ðT n Þ; . . . ; kn ðT n ÞÞU n h;k h¼1

l¼1

h¼1

h i ¼ U n diagðk1 ðT n Þ; . . . ; kn ðT n ÞÞU n j;k ¼ U n diagðk1 ðT n Þ; . . . ; kn ðT n ÞÞU 1 n

j;k

for all 1 6 j; k 6 n. h

We can now proceed to compute a SVD for the matrix Hnnþm in (2). Theorem 5. Let m; n 2 N and h0 ; hm 2 C n f0g, with m < n. Consider the n n þ m matrix Hnnþm given by (2). Let T n be the n n matrix in (1) with a0 ¼ jh0 j2 þ jhm j2 and am ¼ am ¼ h0 hm , and let T n ¼ U n diagðk1 ðT n Þ; . . . ; kn ðT n ÞÞU 1 n be the eigenvalue decomposition for T n obtained from Lemma 4. Then

1

In [11, Theorem 3] a different general expression can be found, where those entries are written in terms of binomial coefﬁcients.

J. Gutiérrez-Gutiérrez / Applied Mathematics and Computation 222 (2013) 472–477

477

is a SVD of Hnnþm , where rn is the rank of T n and Z nþm is any n þ m n þ m unitary matrix satisfying that

Proof. Applying [12, Lemma 4.5] yields T n ¼ Hnnþm Hnnþm . Consequently, the theorem now follows from the proof of the SVD theorem based on the spectral theorem for Hermitian matrices (see, e.g., [13, p. 157]). h

Example. Finally, we obtain the singular values of the comb ﬁlter matrix considered in [6, Example 12.5]. Let Hnnþm be the n n þ m matrix in (2) with n ¼ 8; m ¼ h0 ¼ 1, and h1 ¼ 0:9. From Theorem 5 its singular values are 1:871 ; 1:785 ; 1:646 ; 1:456 ; 1:223 ; 0:953 ; 0:656 , and 0:344 . Unlike in the present paper, in [6] these singular values were computed via a standard mathematical software. 4. Conclusions Using the Kronecker product and [3, Theorem 1] we have obtained in the present paper an eigenvalue decomposition for the matrix T n in (1). From this eigenvalue decomposition we have also obtained in the present paper a SVD for any comb ﬁlter matrix. Acknowledgements The author thanks the three anonymous reviewers for their helpful comments. This work was supported in part by the Basque Government through the INFOLIMITS project (PI2012–10), and by the Spanish Ministry of Science and Innovation through the projects COSIMA (TEC2010–19545-C04–02) and COMONSENS (CSD2008–00010). References [1] J. Rimas, On computing of arbitrary positive integer powers for one type of symmetric pentadiagonal matrices of even order, Applied Mathematics and Computation 203 (2008) 582–591. [2] J. Rimas, On computing of arbitrary positive integer powers for one type of symmetric pentadiagonal matrices of odd order, Applied Mathematics and Computation 204 (2008) 120–129. [3] J. Gutiérrez-Gutiérrez, Powers of tridiagonal matrices with constant diagonals, Applied Mathematics and Computation 206 (2008) 885–891. [4] F.W. Isen, DSP for MATLAB and LabVIEW: Digital Filter Design, Morgan & Claypool, 2009. [5] J. Gutiérrez-Gutiérrez, Entries of continuous functions of large Hermitian tridiagonal 2-Toeplitz matrices, Linear Algebra and its Applications 439 (2013) 34–54. [6] A. Goldsmith, Wireless Communications, Cambridge University Press, 2005. [7] J. Gutiérrez-Gutiérrez, Positive integer powers of certain tridiagonal matrices, Applied Mathematics and Computation 202 (2008) 133–140. [8] E. Kilic, On a constant-diagonals matrix, Applied Mathematics and Computation 204 (2008) 184–190. [9] R. Wituła, D. Słota, On computing the determinants and inverses of some special type of tridiagonal and constant-diagonals matrices, Applied Mathematics and Computation 189 (2007) 514–527. [10] E. Kilic, P. Stanica, The inverse of banded matrices, Journal of Computational and Applied Mathematics 237 (2013) 126–135. [11] J. Gutiérrez-Gutiérrez, Binomial coefﬁcients and powers of large tridiagonal matrices with constant diagonals, Applied Mathematics and Computation 219 (2013) 9219–9222. [12] J. Gutiérrez-Gutiérrez, P.M. Crespo, Block Toeplitz matrices: asymptotic results and applications, Foundations and Trends in Communications and Information Theory 8 (3) (2011) 179–257. [13] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1994.