# Singular value decomposition for comb filter matrices

## Singular value decomposition for comb filter matrices

Applied Mathematics and Computation 222 (2013) 472–477 Contents lists available at ScienceDirect Applied Mathematics and Computation journal homepag...
Applied Mathematics and Computation 222 (2013) 472–477

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 ¼ ðajk Þnj;k¼1 satisfying that there exists a positive integer m such that ak ¼ 0 for all k R fm; 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 ; a1 ; a2 Þ :¼ B B B0 B B . @ .. 0

a1 a0 a1 a2 0 .. . 0

a2 a1 a0 a1 a2 .. . 0

0 a2 a1 a0 a1 .. . 0

0 0 a2 a1 a0

   

0 0 0 0

1

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

with a2 ; a1 ; a0 ; a1 ; a2 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 ¼ ðajk Þnj;k¼1 satisfying that there exists a positive integer m such that ak ¼ 0 for all k R fm; 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

am 0 0 .. . 0 a0 0

0 am 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

ð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 ; a1 Þ :¼ B 0 B B . B . @ .

1

a1

0

0



0

a0

a1

0



a1

a0

a1



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

Hnnþm

B B B B ¼B B B @

h0

0

0

   hm

0

0



0

h0

0



0

hm

0



0 .. .

0 .. .

h0 .. .



0

0

hm

0

0

0



0

1

C 0 C C  0 C C; .. .. C C . . A    hm

ð2Þ

with m 2 N, where N denotes the set of natural numbers (that is, the set of positive integers). Examples of such Hnnþ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 ). 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

h1

h2



0

h0

h1

0 .. .

0 .. .

0

0

hm

0

0



   h1m

hm

0



h0 .. .

   h2m

h1m

hm

0



0

1

C 0 C C  0 C C; .. .. C C . . A    hm

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 ; a1 2 C, with a1 a1 – 0. Then W n Dn W 1 n is an eigenvalue decomposition of tridiagn ða1 ; a0 ; a1 Þ, where the entries of the eigenvector matrix W n are

½W n j;k

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

1 6 j; k 6 n

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

aj ¼ a0 þ 2a1

rﬃﬃﬃﬃﬃﬃﬃﬃ a1 jp ; cos a1 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 ;...; a1 a1

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 K1 ¼ diag ; . . . ; , the entries of the inverse of the eigenvector matrix W n of tridiagn ða1 ; a0 ; a1 Þ n a1 a1 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 a1 nþ1

for all 1 6 j; k 6 n, where > denotes transpose. That eigenvector matrix W n of tridiagn ða1 ; a0 ; a1 Þ is unitary if and only if ja1 j ¼ ja1 j (see [3, p. 888]). Thus, W n is unitary, e.g., when tridiagn ða1 ; a0 ; a1 Þ is Hermitian. Observe that if tridiagn ða1 ; a0 ; a1 Þ 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 0mn 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 ½Aj1 :j2 ;k1 :k2 denotes the j2  j1 þ 1  k2  k1 þ 1 submatrix of A formed by the entries ½Aj;k with j1 6 j 6 j2 and k1 6 k 6 k2 . If j1 ¼ j2 or k1 ¼ k2 , then ½Aj1 :j2 ;k1 :k2 is also denoted by ½Aj1 ;k1 :k2 or ½Aj1 :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 ; am 2 C and am am – 0. Let W j Dj W 1 be the eigenvalue decomposition for j tridiagj ðam ; a0 ; am Þ 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 ; am Þ 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 ¼ jam j. Thus, V n is unitary, for instance, when T n is Hermitian. From Theorem 2 we obtain

detðT n Þ ¼

rﬃﬃﬃﬃﬃﬃﬃﬃ rﬃﬃﬃﬃﬃﬃﬃﬃ !mr Y !r c  cþ1  Y am jp am kp a0 þ 2am a0 þ 2am : cos cos am cþ1 am 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; a2 Þ. 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 ; am Þ 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 ; am 2 C and am am – 0. Let Aj ¼ tridiagj ðam ; a0 ; am Þ 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 ; am ÞÞ  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 nnþm We begin this section with a result that we will use to obtain a SVD for the matrix Hnnþm in (2). Lemma 4. Let m; n 2 N with m < n. Suppose that a0 is a (ﬁnite) real number and am ; am 2 C, with am ¼ 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 Hnnþm in (2). Theorem 5. Let m; n 2 N and h0 ; hm 2 C n f0g, with m < n. Consider the n  n þ m matrix Hnnþm given by (2). Let T n be the n  n matrix in (1) with a0 ¼ jh0 j2 þ jhm j2 and am ¼ am ¼ h0 hm , 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 Hnnþ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 ¼ Hnnþm Hnnþ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 Hnnþm be the n  n þ m matrix in (2) with n ¼ 8; m ¼ h0 ¼ 1, and h1 ¼ 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  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  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.  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.  J. Gutiérrez-Gutiérrez, Powers of tridiagonal matrices with constant diagonals, Applied Mathematics and Computation 206 (2008) 885–891.  F.W. Isen, DSP for MATLAB and LabVIEW: Digital Filter Design, Morgan & Claypool, 2009.  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.  A. Goldsmith, Wireless Communications, Cambridge University Press, 2005.  J. Gutiérrez-Gutiérrez, Positive integer powers of certain tridiagonal matrices, Applied Mathematics and Computation 202 (2008) 133–140.  E. Kilic, On a constant-diagonals matrix, Applied Mathematics and Computation 204 (2008) 184–190.  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.  E. Kilic, P. Stanica, The inverse of banded matrices, Journal of Computational and Applied Mathematics 237 (2013) 126–135.  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.  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.  R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1994.