On the spectral and Frobenius norm of a generalized Fibonacci r-circulant matrix

Open Access. ©2018 Jorma K. Merikoski et al., published by De Gruyter Open. This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivs 4.0 License. Spec. Matrices 2018; 6:23–36 Research Article Open Access Jorma K. Merikoski, Pentti Haukkanen, Mika Mattila, and Timo Tossavainen* On the spectral and Frobenius norm of a generalized Fibonacci r-circulant matrix https://doi.org/10.1515/spma-2018-0003 Received October 9, 2017; accepted December 26, 2017 Abstract: Consider the recursion g0=a,g1=b,gn=gn−1+gn−2,n= 2,3,. . . . We compute the Frobenius norm of the r-circulant matrix corresponding to g0,. . . ,gn−1. We also give three lower bounds (with equality conditions) for the spectral norm of this matrix. For this purpose, we present three ways to estimate the spectral norm from below in general. Keywords: Euclidean norm, Frobenius norm, generalized Fibonacci numbers, r-circulant matrix, spectral norm 1Introduction Given a,b,p,q∈R, we define the Horadam sequence (hn) = (hn(a,b;p,q)) via h0=a,h1=b, hn=phn−1+qhn−2,n= 2,3,. . . . (It is often assumed that a,b,p,q∈Z, but real numbers apply as well.) We abbreviate (un) = (hn(a,b;p,1)),(gn) = (hn(a,b; 1,1)), (fn) = (hn(0,1; 1,1)),(ln) = (hn(2,1; 1,1)), and denote h= (h0,. . . ,hn−1),u= (u0,. . . ,un−1),g= (g0,. . . ,gn−1), f= (f0,. . . ,fn−1),l= (l0,. . . ,ln−1). Throughout, we let x= (x0,. . . ,xn−1)∈Rn,n≥2. Given r∈R, the r-circulant matrix Cr(x)is defined as Cr(x) =           x0x1. . . xn−2xn−1 rxn−1x0. . . xn−3xn−2 rxn−2rxn−1. . . xn−4xn−3 . . .. . .. . .. . .. . . rx2rx3. . . x0x1 rx1rx2. . . rxn−1x0           . Jorma K. Merikoski: Faculty of Natural Sciences, FI-33014 University of Tampere, Finland, E-mail: [email protected] Pentti Haukkanen: Faculty of Natural Sciences, FI-33014 University of Tampere, Finland, E-mail: pentti.haukk[email protected] Mika Mattila: Department of Mathematics, Tampere University of Technology, P.O. Box 553, FI-33101 Tampere, Finland, E-mail: [email protected] *Corresponding Author: Timo Tossavainen: Department of Arts, Communication and Education, Lulea University of Technology, SE-97187 Lulea, Sweden, E-mail: timo.tossa[email protected] Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM 24 |Jorma K. Merikoski, Pentti Haukkanen, Mika Mattila, and Timo Tossavainen (If r∈Z, the term “r-circulant” has also another meaning [4, p. 155]: each row is obtained from the preceding row by rshiftings.) We let k·kFstand for the Frobenius (or, equivalently, Euclidean) norm of a matrix, and k·k2for the spectral norm (or, equivalently, the largest singular value) of a matrix likewise for the Euclidean norm of a vector. Shen and Cen [12] presented bounds for kCr(f)kFand kCr(l)kF. Chandoul [3] extended them to kCr(g)kF, and Raza and Ali [11] to kCr(u)kF. Our first goal is to find kCr(g)kFexactly. We will do it in Section 2. The above-cited authors have also presented bounds for kCr(f)k2, etc. In this paper, we focus on examining lower bounds. Shen and Cen [12, Theorems 1–2] proved that kCr(f)k2≥min (|r|,1)pfn−1fn, kCr(l)k2≥min (|r|,1)p5fn−1fnif nis even, kCr(l)k2≥min (|r|,1)p5fn−1fn+ 4 if nis odd. Chandoul [3, Theorem 2.2] extended these inequalities to kCr(g)k2≥min (|r|,1)pgn−1gn−ab +a2.(1) More generally, Raza and Ali [11, Theorem 2.1] showed that kCr(u)k2≥min (|r|,1)run−1un−ab +pa2 p. They assume that a,b≥0but say nothing about p. However, it seems that they implicitly presume that p≥1. A couple of years earlier Yazik and Taskara [13, Theorem 5] found even more general, yet a quite complicated, lower bound for kCr(h)k2. If |r|is large (and nfixed), then the left-hand side of each of the above inequalities is large but the righthand side remains constant. If |r|is small, then the right-hand side is small but the left-hand side may be large (because Cr(g)TCr(g)has entries without factor r). Therefore, the right-hand sides are often poor lower bounds for the left-hand sides. In order to exceed the above results, in Section 3, we will cultivate three previously known ways to estimate kAk2from below, where A∈Cm×n. We will also give equality conditions. Because we find this topic interesting in itself, our approach is going to be more general than actually is needed. Applying the bounds so obtained, we will in Section 4 underestimate kCr(x)k2, where x∈Cn. Thereafter, in Section 5, we will attain our second goal: to find three lower bounds for kCr(g)k2. In Section 6, we will compare the found lower bounds with each others and with the right-hand side of (1), briefly “rhs(1)”. Finally, Section 7 completes our paper with some concluding remarks. Norms of generalized Fibonacci r-circulant matrices are widely studied. The above references are directly connected with our paper. For other references, see, e.g., [1, 2, 5, 7, 9]. 2Computation of kCr(g)kF We recall three sum formulas for the Fibonacci numbers. Lemma 2.1. Let n∈Z+. Then f2 1+· · · +f2 n=fnfn+1,(2) f1f2+· · · +fn−1fn=f2 n−ηn,(3) f2 1+ 2f2 2+· · · +nf2 n= (nfn+1 −fn)fn+ηn,(4) where ηn=1−(−1)n 2.(5) Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM On the spectral and Frobenius norm of a generalized Fibonacci r-circulant matrix |25 Proof. By induction. See also [8, Theorem 5.5] and [8, p. 90, Eqs. 57 and 60]. We also need two other sum formulas. Lemma 2.2. Let n∈Z+. Then 2f2 1+ 3f2 2+· · · + (n+ 1)f2 n=(n+ 1)fn+1 −fnfn+ηn.(6) Proof. By (4) and (2), 2f2 1+ 3f2 2+· · · + (n+ 1)f2 n= (f2 1+ 2f2 2+· · · +nf2 n) + (f2 1+· · · +f2 n) = nfnfn+1 −f2 n+ηn+fnfn+1 = (n+ 1)fnfn+1 −f2 n+ηn, and (6) follows. Lemma 2.3. Let n∈Z+. Then f0f1+ 2f1f2+ 3f2f3+· · · +nfn−1fn= (nfn−fn−1)fn+θn,(7) where θn= (−1)nn+ηn 2.(8) Proof. Denote sn=f0f1+f1f2+· · · +fn−1fn. Then, by (3) and (2), f0f1+ 2f1f2+ 3f2f3+· · · +nfn−1fn=sn+ (sn−s1) + (sn−s2) + · · · + (sn−sn−1) = f2 n+ (f2 n−f2 1) + (f2 n−f2 2) + · · · + (f2 n−f2 n−1)−ηn+ (ηn−η1) + (ηn−η2) + · · · + (ηn−ηn−1) = nf2 n−(f2 1+· · · +f2 n−1)−nηn+η1+η2+· · · +ηn−1=nf2 n−fn−1fn−nηn+η1+η2+· · · +ηn−1. If nis even, then −nηn+η1+η2+· · · +ηn−1= 0 + n 2=θn. If nis odd, then −nηn+η1+η2+· · · +ηn−1=−n+n−1 2=−n+ 1 2=θn, and the proof is complete. Now, we can compute kCr(g)k2 F. Applying the equation gn=afn−1+bfn,n= 1,2,. . . ,(9) and (2), (4), (6), (7), we have kCr(g)k2 F= n−1 X i=0 (n−i)g2 i+ n−1 X i=1 ir2g2 i=na2+n n−1 X i=1 g2 i+ (r2−1) n−1 X i=1 ig2 i= na2+n n−1 X i=1 (afi−1+bfi)2+ (r2−1) n−1 X i=1 i(afi−1+bfi)2= na2+n n−1 X i=1 (a2f2 i−1+ 2abfi−1fi+b2f2 i) + (r2−1) n−1 X i=1 i(a2f2 i−1+ 2abfi−1fi+b2f2 i) = na2+na2 n−1 X i=1 f2 i−1+ 2ab n−1 X i=1 fi−1fi+b2 n−1 X i=1 f2 i+ (r2−1)a2 n−1 X i=1 if2 i−1+ 2ab n−1 X i=1 ifi−1fi+b2 n−1 X i=1 if2 i= na2+na2fn−2fn−1+ 2ab(f2 n−1−ηn−1) + b2fn−1fn+ (r2−1)a2(n−1)fn−1−fn−2fn−2+ηn−2+ 2ab(n−1)fn−1−fn−2fn−1+θn−1+ Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM 26 |Jorma K. Merikoski, Pentti Haukkanen, Mika Mattila, and Timo Tossavainen b2(n−1)fn−fn−1fn−1+ηn−1= na2+n(a2fn−2fn−1+ 2abf2 n−1+b2fnfn−1) + n(r2−1)(a2fn−1fn−2+ 2abf2 n−1+b2fn−1fn) + (1 −r2)(a2fn−2fn−1+a2f2 n−2+ 2abf 2 n−1+ 2abfn−2fn−1+b2fn−1fn+b2f2 n−1) −2nabηn−1+ (r2−1)(a2ηn−2+ 2abθn−1+b2ηn−1) = na2+nr2(a2fn−2fn−1+ 2abf2 n−1+b2fn−1fn) + (1 −r2)(a2fn−2fn+ 2abfn−1fn+b2fn−1fn+1)− 2nabηn−1+ (r2−1)(a2ηn−2+ 2abθn−1+b2ηn−1). Furthermore, a2fn−2fn−1+ 2abf 2 n−1+b2fn−1fn=afn−1(afn−2+bfn−1) + bfn−1(afn−1+bfn) = afn−1gn−1+bfn−1gn and a2fn−2fn+ 2abfn−1fn+b2fn−1fn+1 =afn(afn−2+bfn−1) + bfn−1(afn+bfn+1) = afngn−1+bfn−1gn+1. We summarize our result as follows. Theorem 2.1. Let r,a,b∈R. Then kCr(g)kF=αr2+β(1 −r2) + γ1 2,(10) where α=n(afn−1gn−1+bfn−1gn), β=afngn−1+bfn−1gn+1 −a2ηn−2−2abθn−1−b2ηn−1, γ=n(a2−2abηn−1). 3Underestimating kAk2 Our first approach to estimate kAk2from below rests upon applying kAkF. Lemma 3.1. Let A∈Cm×n. Then kAk2≥1 √qkAkF,q= min (m,n).(11) Equality is attained if and only if all singular values of Aare equal. For A∈Cn×n, an equivalent condition is that Ais a scalar multiple of a unitary matrix. Proof. Let Ahave singular values σ1≥ · · · ≥ σq. Since kAk2 2=σ2 1,1 qkAk2 F=σ2 1+· · · +σ2 q q, we obtain (11) with equality condition; see also [6, Problem 5.6.P23], [6, p. 594]. For the last statement, see [6, Problem 2.6.P13]. In the other two alternative procedures which we study in this paper, we consider the spectral norm as the largest eigenvalue λ(·)of a suitable Hermitian matrix. Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM On the spectral and Frobenius norm of a generalized Fibonacci r-circulant matrix |27 Lemma 3.2. Given A∈Cm×n, define HA= O A A*O!∈C(m+n)×(m+n),KA=A*A∈Cn×n. Then kAk2=λ(HA),kAk2=λ(KA)1 2.(12) Proof. The first equation follows from [6, Theorem 7.3.3]. The second is obvious. Lemma 3.3. Let M∈Cn×nbe Hermitian. If 0=x∈Cn, then λ(M)≥x*Mx x*x.(13) Equality is attained if and only if xis an eigenvector corresponding to λ(M). Proof. See [6, Theorem 4.2.2]. Throughout, we let r1,. . . ,rm(respectively c1,. . . ,cn) denote the row (column) sums of A= (aij)∈Cm×n. We also denote r= (r1,. . . ,rm),c= (c1,. . . ,cn),1k= (1,. . . ,1) ∈Rk. Theorem 3.1. Let A∈Cm×n. Then kAk2≥2|r1+· · · +rm| m+n.(14) In particular, for A∈Cn×n, kAk2≥|r1+· · · +rn| n.(15) Proof. Let us denote 1=1m+nand s=|s|eiθ=r1+· · · +rm. By (12) and (13), kAk2=λ(HA)≥1*HA1 1*1=1 m+nm X i=1 n X j=1 aij + n X i=1 m X j=1 ¯ aji= 1 m+n m X i=1 n X j=1 (aij +¯ aij) = 2 m+n m X i=1 n X j=1 <aij =2 m+n< m X i=1 ri=2 m+n<s, where <stands for the real part. Applying this to e−iθA, we obtain kAk2=ke−iθAk2≥2 m+n<(e−iθs) = 2 m+n<(e−iθ|s|eiθ) = 2|s| m+n, verifying (14). Theorem 3.2. If m=nand A=O, then (14) is strict. Assuming m=nand A≥O(entrywise), equality is attained in (15) if and only if r1=· · · =rn=c1=· · · =cn. Proof. By Lemma 3.3, a necessary condition for equality is that 1is an eigenvector of HA. Since HA1= A1n A*1m!= r ¯ c! (where ¯ cis understood entrywise), this happens if and only if r1=· · · =rm=¯ c1=· · · =¯ cn.(16) Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM 28 |Jorma K. Merikoski, Pentti Haukkanen, Mika Mattila, and Timo Tossavainen Assume (16). Then s=mr1=m¯ c1but also s=nc1=n¯ r1. Writing r1=α+βi,c1=α−βi, we therefore have mα =nα,mβ =−nβ. So, m=n∨α= 0 by the first equation, and β= 0 by the second. We have now shown that a necessary condition for HAto have 1as an eigenvector is (α=β= 0) ∨(m=n)∧(r1=· · · =rn=c1=· · · =cn∈R). If α=β= 0, then the right-hand side of (14) is zero; so, to have equality in this case, necessarily A=O. Therefore, a necessary condition for equality in (14) is A=O∨(m=n)∧(r1=· · · =rn=c1=· · · =cn∈R). The first claim of the theorem is thus proved. The problem is that the corresponding eigenvalue is not necessarily λ(HA). However, there is no problem if A≥O. Because a positive eigenvector corresponds to the Perron root [6, Theorem 8.3.4], this eigenvalue is λ(HA), and the second claim follows. Theorem 3.3. Let A∈Cm×n. Then kAk2≥|r1|2+· · · +|rm|2 n1 2.(17) Assuming A≥O(or, more generally, A*A≥O), equality is attained if and only if all row sums of A*Aare equal. Proof. Denote 1=1n; then kAk2≥kA1k2 k1k2 =krk2 √n, verifying (17). To study equality, we have kA1k2 2 k1k2 2 =(A1)*A1 1*1=1*A*A1 1*1. Consequently, 1must be an eigenvector of K=A*Acorresponding to λ(K). Clearly, 1is an eigenvector if and only if all the row sums of Kare equal. As in the proof of Theorem 3.2, we see that the corresponding eigenvalue is λ(K)if K≥O. Proposition 3.4. Let A∈Rn×n. The bound rhs(17) is better than rhs(15). If A≥O, then rhs(17) is better than rhs(11), but rhs(11) and rhs(15) are not comparable. Proof. Easy and omitted. 4Underestimating kCr(x)k2 We first recall an exact expression of kC1(x)k2. Theorem 4.1. If x≥0, then kC1(x)k2=x0+· · · +xn−1. Proof. See [10, Corollary 2]. The assumption x≥0can be generalized, see [10, Theorem 4]. Now we apply our bounds to kCr(x)k2. Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM On the spectral and Frobenius norm of a generalized Fibonacci r-circulant matrix |29 Theorem 4.2. Let r,x0,. . . ,xn−1∈R. Then kCr(x)k2≥n−1 X i=0 x2 i+r2−1 n n−1 X i=1 ix2 i1 2.(18) Proof. Since kCr(x)k2 F= n−1 X i=0 (n−i)x2 i+r2 n−1 X i=1 ix2 i=n n−1 X i=0 x2 i+ (r2−1) n−1 X i=1 ix2 i, we have kCr(x)k2 F n= n−1 X i=0 x2 i+r2−1 n n−1 X i=1 ix2 i, and (18) follows from (11). Theorem 4.3. Let r,x0,. . . ,xn−1∈R. Then kCr(x)k2≥ n−1 X i=0 xi+r−1 n n−1 X i=1 ixi.(19) Proof. The sum of entries of Cr(x)equals n−1 X i=0 (n−i)xi+r n−1 X i=1 ixi=n n−1 X i=0 xi+ (r−1) n−1 X i=1 ixi, so (19) follows from (15). Theorem 4.4. Let r,x0,. . . ,xn−1∈R. Then kCr(x)k2≥h1 n n−1 X i=0 n−i−1 X j=0 xj+r n−1 X j=n−i xj2i1 2.(20) Proof. The (i+ 1)’st row sum of Cr(x)is n−i−1 X j=0 xj+r n−1 X j=n−i xj, hence (17) implies (20). Theorem 4.5. Equality is attained in (18) if and only if either r= ±1∧(x1=· · · =xn−1= 0) (21) or r= 1 ∧n−1 X i=0 xixi−j= 0,j= 1,. . . ,n−1,(22) or r=−1∧j−1 X i=0 xixi−j= n−1 X i=j xixi−j,j= 1,. . . ,n−1,(23) where the indices are mod n. Assuming r,x0,. . . ,xn−1≥0,(24) equality is attained in (19) and, respectively, in (20) if and only if r= 1 ∨(x1=· · · =xn−1= 0).(25) Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM 30 |Jorma K. Merikoski, Pentti Haukkanen, Mika Mattila, and Timo Tossavainen Proof. We divide the proof in three parts. 1. Equality condition of (18). By Lemma 3.1, equality holds if and only if the rows of Cr(x)form a scalar multiple of an orthonormal set. In particular, their Euclidean norms must be equal. Comparing the n’th and (n−1)’th rows, this means that r2(x2 1+· · · +x2 n−1) + x2 0=r2(x2 2+· · · +x2 n−1) + x2 0+x2 1, i.e., r2x2 1=x2 1. First, assume r= ±1; then x1= 0. Comparing the (n−1)’th and (n−2)’th rows, we have r2(x2 2+· · · +x2 n−1) + x2 0=r2(x2 3+· · · +x2 n−1) + x2 0+x2 2, i.e., r2x2 2=x2 2; so x2= 0. Continuing similarly, we see that necessarily x1=· · · =xn−1= 0. Since this condition is clearly sufficient, the condition (21) is verified. Second, assume r=±1; then the rows of Cr(x)have equal norms. Since their orthogonality condition is stated in (22) and (23), also this case is clear. 2. Equality condition of (19), assuming (24). By Theorem 3.2, equality holds in (15) if and only if all row sums of Cr(x)are equal. (Since r1=cn,r2=cn−1,. . . ,rn=c1, they are also equal to the column sums.) Comparing the n’th and (n−1)’th rows, we have r(x1+· · · +xn−1) + x0=r(x2+···+xn−1) + x0+x1, i.e., r= 1 or x1= 0. Continuing as above, we obtain (25). 3. Equality condition of (20), assuming (24). Let dbe the difference of the first and last row sum of CT r(x)Cr(x). If equality holds, then d= 0 by Theorem 3.3. A rather extensive computation, which we omit here, shows that d= (r2−1)n X i=1 x2 i+ n X i=1 i−1 X j=1 xixj. Therefore, (25) is necessary; obviously, it is a sufficient condition. Although rhs(11) and rhs(15) are not comparable even if A≥O, a question arises whether they are if A=Cr(x),x≥0. The answer is negative. For example, if x= (1,1,1), then rhs(19) ≥rhs(18) for all r≥ −1 2. On the other hand, if x= (0,1,0), then rhs(18) ≥rhs(19) for all r∈R. 5Underestimating kCr(g)k2 We are now ready to study kCr(g)k2. Theorem 5.1. Let r,a,b∈R. Then kCr(g)k2≥αr2+β1−r2 n+γ1 2,(26) where α=afn−1gn−1+bfn−1gn, β=afngn−1+bfn−1gn+1 −a2ηn−2−2abθn−1−b2ηn−1, γ=a2−2abηn−1, and ηmand θmare as in (5) and (8), respectively. Proof. The claim follows from (10), (11), and (18). Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM On the spectral and Frobenius norm of a generalized Fibonacci r-circulant matrix |31 In applying Theorems 4.3 and 4.4 in order to estimate kCr(g)k2, we also need the following three sum formulas. Lemma 5.1. Let m∈Z+. Then m X i=0 gi=gm+2 −b,(27) m X i=1 igi=mgm+2 −gm+3 +a+ 2b,(28) m X i=0 g2 i=gmgm+1 +a(a−b).(29) Proof. By induction. See also [8, p. 113, Eqs. 11, 17 and 14]. (Note that Gi=gi−1and that there is a typo in Eq. 17.) Theorem 5.2. Let r∈R. Then kCr(g)k2≥1 ngn+3 −a−(n+ 2)b+r(ngn+1 −gn+3 +a+ 2b).(30) Proof. By (27) and (28), n n−1 X i=0 gi+ (r−1) n−1 X i=0 igi=n(gn+1 −b) + (r−1)(n−1)gn+1 −gn+2 +a+ 2b= −nb +gn+1 +gn+2 −a−2b+r(n−1)gn+1 −gn+2 +a+ 2b= gn+3 −a−(n+ 2)b+r(ngn+1 −gn+3 +a+ 2b); so, (19) implies (30). In particular, if a,b≥0, then kC1(g)k2=gn+1 −b, which follows also from Theorem 4.1 and (27). Next, we apply Theorem 4.4. We denote σi=gn−(i−1) +· · · +gn−1,τi=g0+· · · +gn−i,si=σir+τi, where i= 1,. . . ,n. 1. Computing τiand σi. By (27), τi= n−i X j=0 gj=gn−i+2 −b and σi= n−1 X j=n−(i−1) gj= n−1 X j=0 gj− n−i X j=0 gj= (gn+1 −b)−(gn−i+2 −b) = gn+1 −gn−i+2. 2. Computing s2 i. Simply, observe that s2 i= (σir+τi)2=(gn+1 −gn−i+2)r+gn−i+2 −b2= (gn+1 −gn−i+2)2r2+ 2(gn+1 −gn−i+2)(gn−i+2 −b)r+ (gn−i+2 −b)2=: αir2+βir+γi. 3. Computing α1+· · · +αn. We have n X i=1 αi= n X i=1 (gn+1 −gn−i+2)2= n X i=1 g2 n+1 −2gn+1gn−i+2 +g2 n−i+2= Brought to you by | Tampere University Library Authenticated Download Date | 4/16/18 2:03 PM