CMSV pdf

Transcription

1 COMMUN. MATH. SCI. Vol. 14, No. 4, c 2016 International Press POSITIVE SEMI-DEFINITENESS OF GENERALIZED ANTI-CIRCULANT TENSORS GUOYIN LI, LIQUN QI, AND QUN WANG Abstract. Anti-circulant tensors have alications in exonential data fitting. They are secial Hankel tensors. In this aer, we extend the definition of anti-circulant tensors to generalized anticirculant tensors by introducing a circulant index r such that the entries of the generating vector of a Hankel tensor are circulant with module r. In the secial case when r = n, wheren is the dimension of the Hankel tensor, the generalized anti-circulant tensor reduces to the anti-circulant tensor. Hence, generalized anti-circulant tensors are still secial Hankel tensors. For the cases that GCD(m,r)=1, GCD(m,r) = 2, some other cases, including the matrix case that m = 2, we give necessary sufficient conditions for ositive semi-definiteness of even-order generalized anti-circulant tensors show that, in these cases, they are sum-of-squares tensors. This shows that, in these cases, there are no PNS (ositive semi-definite tensors which are not sum-of-squares) Hankel tensors. Key words. Anti-circulant tensors, generalized anti-circulant tensor, generating vectors, circulant index, ositive semi-definiteness. AMS subect classifications. 15A18, 15A Introduction Anti-circulant tensors were introduced in [4]. They are extensions of anti-circulant matrices in matrix theory [3, 23]. They have alications in exonential data fitting [4]. Anti-circulant tensors are Hankel tensors. Hankel tensors arise from signal rocessing some other alications [1, 16, 18]. In this aer, we extend anti-circulant tensors to generalized anti-circulant tensors, which are still Hankel tensors, resent conditions for ositive semi-definiteness of generalized anti-circulant tensors. Let v =(v 0,...,v (n 1)m ) R (n 1)m+1,wherem,n 2. An mth order n dimensional Hankel tensor A =(a i1 i m ) is defined by a i1 i m = v i1+ +i m m, for i 1,...,i m =1,...,n. If v i = v i+r, (1.1) for i =0,...,(n 1)m r, where1 r n, thena is called a generalized anti-circulant tensor with circulant index r. If r = n, thena is an anti-circulant tensor according to [4]. For x =(x 1,...,x n ) R n, A uniquely define a homogeneous olynomial n n f(x) Ax m = a i1 i m x i1 x im = v i1+ +i m mx i1 x im. (1.2) i 1,...,i m=1 i 1,...,i m=1 Received: December 11, 2014; acceted (in revised form): Aril 18, Communicated by Shi Jin. Deartment of Alied Mathematics, University of New South Wales, Sydney 2052, Australia (g.li@unsw.edu.au). This author s work was artially suorted by an Australian Research Council Future Fellowshi (FT ). Deartment of Alied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong (maqilq@olyu.edu.hk). This author s work was artially suorted by the Hong Kong Research Grant Council (Grant No. PolyU , , , ). Deartment of Alied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong (wangqun876@gmail.com). 941

2 942 GENERALIZED ANTI-CIRCULANT TENSORS We call such a olynomial a Hankel olynomial. Suose that m =2k is even. In (1.2), if f(x) 0 for all x R n,thenf is called a PSD (ositive semi-definite) Hankel olynomial A is called a PSD Hankel tensor [17]. Denote 0 =(0,...,0) R n.iff(x) > 0 for all x R n,x 0, thenf A are called ositive definite. Clearly, the only odd-order PSD Hankel tensor is O there are no odd-order ositive definite Hankel tensors. Thus, we may assume that m is even in our discussion. If f can be decomosed to the sum of squares of olynomials of degree k, then f is called an SOS (sum of squares) Hankel olynomial A is called an SOS Hankel tensor [6, 7, 13, 15]. Clearly, an SOS Hankel tensor is a PSD Hankel tensor, but not vice versa. By [18], a necessary condition for A to be PSD is that v m 0, (1.3) for =0,...,n 1. Let e i be the ith unit vector in R n. Substitute them to (1.2). Then we get (1.3) directly. Vector v is called the generating vector of A. It may also generate a(nk k +1) (nk k +1) Hankel matrix A =(a i )by a i = v i+ 2 for i, =1,...,nk k +1. If the associated Hankel matrix A is PSD, then the Hankel tensor A is called a strong Hankel tensor [18]. In [13], it was roved that an even-order strong Hankel tensor is an SOS Hankel tensor. Then a necessary condition for A to be a strong Hankel tensor is that v 2 0 (1.4) for =0,...,(n 1)k. Let GCD(m,r) denote the greatest common divisor of the two nonnegative integers m r. When r is odd, for the case that m =2k, k 1, GCD(m,r) = 1, n r, weshow that A is PSD if only if v 0 = = v r 1 0. In this case, we show that f(x)=v 0 (x 1 + +x n ) m A is a strong Hankel tensor. We show that this result is still true for r =3,n r m =6,12,18,30,42. When r is even, for the case that m =2k, k 1, GCD(m,r) = 2, n r, weshow that A is PSD if only if v 0 = v 2 = = v r 2, v 1 = v 3 = = v r 1,v 0 v 1. In these cases, we may write v 1 = v 0 (2t 1), where t [0,1]. We show that f(x)=tv 0 (x 1 + x n ) m +(1 t)v 0 ( x1 x 2 +x 3 +( 1) n 1 x n ) m A is a strong Hankel tensor. We show that this result is still true in the case that m =4, r = 4 n 4. Note that these two results are true in the matrix case for all r 1. In fact, in the matrix case, for even r, we show the result is true as long as 2 r 2 2n 4. We believe that our results are new even in the matrix case. The significance of our results is twofold. On one h, they enrich the theory of ositive semi-definiteness of even-order symmetric tensors [2, 10, 11, 14, 17, 18, 19, 21, 22]. On the other h, they also contribute to the study of the Hilbert-Hankel roblem. In 1988, Hilbert [5] showed that a PSD symmetric homogeneous olynomial of n variables degree m =2k is always an SOS olynomial only in the following three

3 G. LI, L. QI, AND Q. WANG 943 cases: (1) m =2; (2) n =2; (3) m =4, n = 3. For the other airs of m =2k 4 n 3, there are always PSD olynomials which are not SOS olynomials. We may call such olynomials PNS (PSD non-sos) olynomials. Later, various PNS olynomials were found [20]. Since each homogeneous olynomial of n variables degree m is uniquely corresonding to an mth-order n-dimensional symmetric tensor, the discovery of Hilbert may also be stated in the tensor language. In [13], a question is raised: Are all the PSD Hankel tensors SOS tensors? If the answer to this question is yes, then the roblem for determining whether a given even-order Hankel tensor is a PSD tensor or not can be solved by a linear semi-definite rogramming roblem [8, 9] so can be solved in olynomial time. In [12], a conecture is made that there are no sixthorder three-dimensional PNS Hankel tensors. Since generalized anti-circulant tensors are Hankel tensors, our results are related to this Hilbert-Hankel roblem. In Section 2, we rove a theorem for circulant numbers. This will be useful for our further discussion. In sections 3 4, we discuss the roblems for the cases where r is odd r is even, resectively. Some final remarks are made in Section 5. Throughout the aer, we use e i to denote the ith unit vector in R n. 2. A theorem on circulant numbers We have the following theorem. Theorem 2.1. Let M 1 2. Suose that we have a sequence {u : =0,1,, satisfying for =0,1,... If for i =0,..., 1, orif M M u + = u ( ) M ( 1) u i+ 0 (2.1) ( ) M ( 1) u i+ 0 (2.2) for i =0,..., 1, thenu 0 = u 1 = = u 1. Proof. We can rove this theorem by induction on M. Obviously, it is true for M =1,2. Suose that it is true for M =2,...,k. We now rove that it is true for M = k +1. Define k ( ) k w i = ( 1) u i+ for i =0,..., 1. Then w i+ = w i for i =0,..., 1. Suose that (2.1) holds for M = k +1. Note that k ( ) k 1 k ( ) w i w i+1 = u 0 + ( 1) u i+ k ( 1) u i++1 +( 1) k u i+k+1 =1 k (( ) ( )) = u 0 + k k + ( 1) u i+ +( 1) k+1 u i+k+1 1 =1

4 944 GENERALIZED ANTI-CIRCULANT TENSORS k ( ) = u 0 + k +1 ( 1) u i+ +( 1) k+1 u i+k+1 =1 k+1 ( ) k +1 = ( 1) u i+. Then (2.1) is equivalent to w i w i+1 0 for i =0,..., 1. This imlies that w 0 = w 1 = w 1. Thus, either (2.1) or (2.2) holds for M = k. By our induction assumtion, we have u 0 = u 1 = = u 1. Similarly, if (2.2) holds for M = k +1, we can show that u 0 = u 1 = = u 1.Thisrovesthetheorem. 3. The case that r is odd 3.1. The case that r =1. This case is trivial. However, we resent the statement of the result for the reader s convenience here, as it covers the sufficiency art of the results for the cases that r is an odd number with r 3. Proosition 3.1. Suose that A is an mth-order n-dimensional generalized anticirculant tensor with circulant index 1, wherem =2k 2 n 2. ThenA is PSD if only if v 0 0. In this case, we have f(x)=v 0 (x 1 + +x n ) m (3.1) y ( ) 2 Ay = v 0 y1 + +y (nk k+1), (3.2) where A is the associated Hankel matrix, which imlies that A is a strong Hankel tensor hence an SOS Hankel tensor. The roof is trivial, so we omit it here The case that GCD(m,r)=1. We have the following theorem. Theorem 3.1. Suose that A is an mth-order n-dimensional generalized anticirculant tensor with m =2k, GCD(m,r)=1, 1 r n, k 1. Then A is PSD if only if v 0 = = v r 1 0. In this case, we still have (3.1) (3.2), which imlies that A is a strong Hankel tensor hence an SOS Hankel tensor. Proof. Suose that A is PSD. Let x = e q e q+1 for q =1,...,n,withe n+1 e 1. From f(x) 0, we have m ( ) m ( 1) v (q 1)m+ 0 (3.3) for q =1,...,n. SinceGCD(m,r) = 1, for each i =0,...,r 1, there is an integer q, 1 q n such that (q 1)m = i, mod(r). Then v i+ = v (q 1)m+ for such i, q =0,...,m. Thus, (3.3) imlies that m ( ) m ( 1) v i+ 0 for i =0,...,r 1. Alying Theorem 2.1 with M = m, u = v, = r, wehavev 0 = = v r 1. By (1.3), v 0 0. Thus, we have v 0 = = v r 1 0. The if art follows from Proosition 3.1.

5 G. LI, L. QI, AND Q. WANG The case that GCD(m,r) 1. ThecasethatGCD(m,r) 1 r is odd includes the case that r =3, m =6l for l 1, the case that r =5, m =10l for l 1; etc. By [12]; Theorem 3.1 still holds for the case that m = 6 r = 3. We can see that Theorem 3.1 still holds for more cases that GCD(m,r) 1 r is odd. We now assume that m =6l, r =3 for l 1. In this case, (1.1) (1.2) have the form v i = v i+3 (3.4) for i =0,...,(n 1)m 3, for x =(x 1,...,x n ) R n, the form where f(x) Ax m = n i 1,...,i m=1 v i1+ +i m x i1 x im = v 0 f 0 (x)+v 1 f 1 (x)+v 2 f 2 (x), (3.5) f (x)= {x i1 x im : i 1 + +i m =, mod(3),i 1,...,i m =1,...,n, (3.6) for =0,1,2. We can see that f 0 (x)+f 1 (x)+f 2 (x)=(x 1 + +x n ) m. (3.7) Since we are concerned with PSD generalized anti-circulant tensors, we may assume that (1.3) holds (i.e., v 0 0). Proosition 3.2. Suose that A is an mth-order n-dimensional generalized anticirculant tensor with circulant index 3, wherem =6,12,18,30,42 n 3. Assume that v 0 0. IfA is PSD, then v 1 +v 2 =2v 0. (3.8) Proof. that Suose that A is PSD v 0 0. Then we have f(1, 1,0,...,0) 0. Note f 0 (1, 1,0,...,0) = {x i1 x im : i 1 + +i m =0, mod(3), i 1,...,i m =1,2, x 1 =1,x 2 = 1 Similarly, we can rove that = {x i1 x im :the number of i =1 is m, the number of i =2 is, =0,3,...,m, x 1 =1,x 2 = 1 = { ( ) m ( 1) : =0,3,...,m. f 1 (1, 1,0,...,0) = { ( 1) ( m ) : =1,4,...,m 2, f 2 (1, 1,0,...,0) = { ( 1) ( m ) : =2,5,...,m 1. By direct calculation, for m =6,18,30,42, we have f 0 (1, 1,0,...,0) < 0. (3.9)

6 946 GENERALIZED ANTI-CIRCULANT TENSORS Since ( ) ( m m m ),wehave By (3.7), f 1 (1, 1,0,...,0) = f 2 (1, 1,0,...,0). (3.10) f 0 (1, 1,0,...,0)+f 1 (1, 1,0,...,0)+f 2 (1, 1,0,...,0) = 0. (3.11) By (3.5), (3.9) (3.11), f(1, 1,0,...,0) 0, we have v 1 +v 2 2v 0 0. On the other h, for m =6,18,30,42, f 0 (1,1, 2,0,...,0) = {x i1 x im : i 1 + +i m =0, mod(3), i 1,...,i m =1,2,3, x 1 =1,x 2 =1,x 3 = 2 = {x i1 x im :the number of i =1 is m q, the number of i =2 is q, the number of i =3 is, 2+q =0, mod(3), 0,q m, x 1 =1,x 2 =1,x 3 = 2 m = {xi1 x im :the number of i =1 is m q, the number of i =2 is q, =0 the number of i =3 is, 2+q =0, mod(3), 0 q m, x 1 =1,x 2 =1,x 3 = 2 m { ( )( ) m m = ( 2) :2+q =0, mod(3), 0 q m. q =0 Similarly, we can rove that f 1 (1,1, 2,0,...,0) = f 2 (1,1, 2,0,...,0) = m =0 m =0 By direct calculation, for m =6,18,30,42, we have { ( )( ) m m ( 2) :2+q =1, mod(3), 0 q m q { ( )( ) m m ( 2) :2+q =2, mod(3), 0 q m. q f 0 (1,1, 2,0,...,0) > 0. (3.12) Note that ( ) ( m q m q). Also, 2+q = 2, mod(3) is equivalent to 2+m q =1, mod(3). Thus, By (3.7), f 1 (1,1, 2,0,...,0) = f 2 (1,1, 2,0,...,0). (3.13) f 0 (1,1, 2,0,...,0)+f 1 (1,1, 2,0,...,0)+f 2 (1,1, 2,0,...,0) = 0. (3.14) By f(1,1, 2,0,...,0) 0, (3.5), (3.12) (3.14), we can derive v 1 +v 2 2v 0 0. This roves (3.8). For the case that m = 12, (3.10) still holds. By direct comutation, we have f 0 (1, 1,0,0,...,0) > 0. (3.15)

7 G. LI, L. QI, AND Q. WANG 947 By (3.5), (3.10) (3.11) (3.15), we have v 1 +v 2 2v 0 0. On the other h, consider f(1, 3,2,0,...,0) f(1,2, 3,0,...,0). By direct comutation, we have We have that =0 f 0 (1, 3,2,0,...,0) < 0. (3.16) f 0 (1, 3,2,0,...,0) m { ( )( ) m m = 2 ( 3) q :2+q =0, mod(3), 0 q m q f 0 (1,2, 3,0,...,0) m { ( )( ) m m = 2 q ( 3) :2+q =0, mod(3), 0 q m q =0 We can see that 2+q = 0, mod(3) if only if +2q = 0, mod(3). Thus, Similarly, we may show that f 0 (1,2, 3,0,...,0) = f 0 (1, 3,2,0,...,0) < 0. (3.17) f 1 (1,2, 3,0,...,0) f 2 (1,2, 3,0,...,0) = f 2 (1, 3,2,0,...,0) f 1 (1, 3,2,0,...,0). (3.18) By f(1, 3,2,0,...,0)+f(1,2, 3,0,...,0) 0, (3.5), (3.17) (3.18) we can derive v 1 + v 2 2v 0 0. This roves that (3.8) still holds for m = 12. We now have the following theorem. Theorem 3.2. Suose that A is an mth-order n-dimensional generalized anticirculant tensor with m =6,12,18,30,42, r =3 n r. ThenA is PSD if only if v 0 = v 1 = v 2 0. In this case, we still have (3.1) (3.2), which imlies that A is a strong Hankel tensor hence an SOS Hankel tensor. Proof. Suose that A is PSD. Then v 0 0. Without loss of generality, assume that v 0 > 0. By Proosition 3.2, v 1 +v 2 =2v 0. Let v 1 = v 0 (1+α). Then v 2 = v 0 (1 α) f(x)=v 0 (x 1 + +x n ) m +v 0 α(f 1 (x) f 2 (x)), (3.19) where f 1 f 2 are defined as in (3.6). We can see that f 1 (1,2, 3,0,...,0) f 2 (1,2, 3,0,...,0) = f 2 (1, 3,2,0,...,0) f 1 (1, 3,2,0,...,0) 0. Then from this, (3.19), f(1,2, 3,0,...,0) 0, f(1, 3,2,0,...,0) 0, we have α =0. This roves that v 0 = v 1 = v 2 0. The remaining conclusions now follow from Proosition 3.1. In the roof of Proosition 3.2, we use direct calculation to show (3.9), (3.12), (3.15) (3.16). Are (3.9) (3.12) still true for m =12l +6 with l 4? Are (3.15) (3.16) still true for m =12l with l 2? How can we rove these by some analytical technique? Thecasethatm =2k, r =2+1, GCD(m,r) 1 for k 2 2also remains unknown. These are some toics for further research.

8 948 GENERALIZED ANTI-CIRCULANT TENSORS 4. The case that r is even 4.1. The case that r =2. We see that the results in [12] for m = 6 n =3 can be extended to this case. In this case, (1.1) (1.2) have the form for i =0,...,(n 1)m 2, for x =(x 1,...,x n ) R n, where f(x) Ax m = n i 1,...,i m=1 v i = v i+2 (4.1) v i1+ +i m mx i1 x im = v 0 f 0 (x)+v 1 f 1 (x), (4.2) f (x)= {x i1 x im : i 1 + +i m =, mod(2),i 1,...,i m =1,...,n, (4.3) for =0,1. We can see that f 0 (x)+f 1 (x)=(x 1 + +x n ) m. (4.4) Since we are concerned with PSD generalized anti-circulant tensors, we may assume that (1.3) holds (i.e., v 0 0). Theorem 4.1. Suose that A is an mth-order n-dimensional generalized anticirculant tensor with circulant index r =2,wherem =2k 2 n 2. ThenA is PSD if only if v 1 v 0. In these cases, we may write v 1 = v 0 (2t 1), wheret [0,1]. We have that f(x)=tv 0 (x 1 + x n ) m +(1 t)v 0 ( x1 x 2 +x 3 +( 1) n 1 x n ) m, A is a strong Hankel tensor. Proof. Suose that A is PSD v 0 0. Then we have f(1,1,0,...,0) 0. Note that f 0 (1,1,0,...,0) = {x i1 x im : i 1 + +i m =0, mod(2), i 1,...,i m =1,2, x 1 =1,x 2 =1 Similarly, we can rove that = {x i1 x im :the number of i =1 is m, the number of i =2 is, =0,2,...,m, x 1 =1,x 2 =1 = {( ) m : =0,2,...,m. f 1 (1,1,0,...,0) = {( m ) : =1,3,...,m 1, f 0 (1, 1,0,...,0) = {( ) m : =0,2,...,m f 1 (1, 1,0,...,0) = { ( 1) ( m ) : =1,3,...,m 1.

9 G. LI, L. QI, AND Q. WANG 949 We may see that f 0 (1, 1,0,...,0)+f 1 (1, 1,0,...,0) = 0, f 0 (1,1,0,...,0) = f 0 (1, 1,0,...,0) > 0, f 1 (1,1,0,...,0) = f 1 (1, 1,0,...,0) > 0. (4.5) By (4.2), we have v 0 +v 1 0. From f(1, 1,0,...,0) 0 (4.2), we have v 0 v 1 0. This imlies that v 0 v 1. On the other h, suose that v 0 v 1. We may write v 1 = v 0 (2t 1), where t [0,1]. Write f(x)=v 0 f 0 (x)+v 1 f 1 (x) such that f 0 (x)+ f 1 (x)=(x 1 + +x n ) m f 0 (x) f 1 (x)=(x 1 x 2 +x 3 +( 1) n 1 x n ) m for all x = (x 1,...,x n ) R n. It then follows from (4.2) that f(x)=v 0 f 0 (x)+v 1 f 1 (x)=v 0 f 0 (x)+(2t 1)v 0 f 1 (x) = tv 0 (f 0 (x)+f 1 (x))+(1 t)v 0 (f 0 (x) f 1 (x)) = tv 0 (x 1 + +x n ) m +(1 t)v 0 (x 1 x 2 +x 3 +( 1) n 1 x n ) m. Similarly, we have g(y)=y Ay = tv 0 (y 1 + +y nk k+1 ) 2 +(1 t)v 0 (y 1 y 2 +y 3 +( 1) nk k y nk k+1 ) 2, (4.6) where A is the associated Hankel matrix of A. The conclusions now follow from the definitions of PSD, SOS, strong Hankel tensors The case that GCD(m,r)=2. In this section, we allow r 2n 4 instead of r n still call such a tensor a generalized anti-circulant tensor. We have the following theorem. Theorem 4.2. Suose that A is an mth-order n-dimensional generalized anticirculant tensor with m =2k, k 1, 4 r =2 2n 4. If GCD(m,r)=2,thenA is PSD if only if v 0 = v 2 = = v r 2, v 1 = v 3 = = v r 1 v 0 v 1. In this case, we may write v 1 = v 0 (2t 1), wheret [0,1]. Thenwehave f(x)=tv 0 (x 1 + x n ) m +(1 t)v 0 ( x1 x 2 +x 3 +( 1) n 1 x n ) m. This imlies that A is PSD if only if it is SOS. Furthermore, in this case, A is a strong Hankel tensor. Proof. Suose that A is PSD. Let x = e q e q+2 for q =1,...,n with e n+1 e 1 e n+2 e 2.Byf(x) 0, we have that m ( ) m ( 1) v (q 1)m+2 0 (4.7) for q =1,...,n. Since GCD(m,r) = 2, for each i =0,..., 1, there is an integer q, 1 q n such that (q 1)m =2i, mod(r). Then v 2(i+) = v (q 1)m+2 for such i, q = 0,...,m. Thus, (4.7) imlies that m ( ) m ( 1) v 2(i+) 0,

10 950 GENERALIZED ANTI-CIRCULANT TENSORS for i =0,..., 1. Alying Theorem 2.1 with M = m u = v 2,wehavev 0 = v 2 = = v r 2. Let x = αe q 1 +e q αe q+1 for q =1,...,n with e 0 e n.sincev 0 = v 2 = = v r 2,in the exression of f(x), the coefficient for ower α m is zero. Hence, the highest ower of α in f(x) is the term for ower α m 1,whichis m 1 ( ) mα m 1 m 1 ( 1) v mq 2m+1+2. From f(x) 0, letting α,wehave m 1 ( ) m 1 ( 1) v mq 2m (4.8) for q =1,...,n. SinceGCD(m,r) = 2, as in the first art of this roof, (4.8) imlies that m 1 ( ) m 1 ( 1) v 2i for i =0,..., 1. Alying Theorem 2.1 with M = m 1 u = v 2+1,wehavev 1 = v 3 = = v r 1. The remaining conclusions now follow from Theorem The case that GCD(m,r)=2l for l 2. In this case, we have the following theorem for m =4, n r =4. Theorem 4.3. Suose that A is a fourth-order n-dimensional generalized anticirculant tensor with circulant index r =4,wheren 4. Then A is PSD if only if v 0 = v 2,v 1 = v 3 v 1 v 0. In these cases, we may write v 1 = v 0 (2t 1), wheret [0,1]. We have that f(x)=tv 0 (x 1 + x n ) 4 +(1 t)v 0 ( x1 x 2 +x 3 +( 1) n 1 x n ) 4 A is a strong Hankel tensor. Proof. In this case, (1.1) (1.2) have the form v i = v i+4 (4.9) for i =0,...,4n 8. From (1.2), for x =(x 1,...,x n ) R n,wehave where f(x) Ax 4 n = i 1,...,i 4=1 v i1+ +i 4 x i1 x i4 = v 0 f 0 (x)+v 1 f 1 (x)+v 2 f 2 (x)+v 3 f 3 (x), (4.10) f (x)= {x i1 x i4 : i 1 + +i 4 =, mod(4),i 1,...,i 4 =1,...,n (4.11) for =0,1,2,3. Furthermore, we have f 0 (x 1,x 2,x 3,x 4,0,...,0)

11 G. LI, L. QI, AND Q. WANG 951 = x 4 1 +x 4 2 +x 4 3 +x (x 2 1x 2 3 +x 2 2x 2 4)+12(x 2 1x 2 x 4 +x 1 x 2 2x 3 +x 2 x 2 3x 4 +x 1 x 3 x 2 4), (4.12) f 1 (x 1,x 2,x 3,x 4,0, 0) =4(x 3 1x 2 +x 3 2x 3 +x 3 3x 4 +x 1 x 3 4)+12(x 2 1x 3 x 4 +x 1 x 2 2x 4 +x 1 x 2 x 2 3 +x 2 x 3 x 2 4), (4.13) f 2 (x 1,x 2,x 3,x 4,0, 0) =4(x 3 1x 3 +x 1 x 3 3 +x 3 2x 4 +x 2 x 3 4)+6(x 2 1x 2 2 +x 2 2x 2 3 +x 2 3x 2 4 +x 2 1x 2 4)+24x 1 x 2 x 3 x 4, (4.14) f 3 (x 1,x 2,x 3,x 4,0, 0) =4(x 1 x 3 2 +x 2 x 3 3 +x 3 x 3 4 +x 3 1x 4 )+12(x 2 1x 2 x 3 +x 2 2x 3 x 4 +x 1 x 2 3x 4 +x 1 x 2 x 2 4). (4.15) Suose now that A is PSD. From (4.13) (4.15), we see that From (4.12) (4.14), we have f 1 (1,0, 1,0,...,0) = f 3 (1,0, 1,0,...,0) = 0. f 0 (1,0, 1,0,...,0) = f 2 (1,0, 1,0,...,0) > 0. Then, by f(1,0, 1,0,...,0) 0, we have v 0 v 2. Similarly, from (4.12) (4.15), we have f 1 (1, 1, 1,1,0,...,0) = f 3 (1, 1, 1,1,0,0,...,0) = 0 f 0 (1, 1, 1,1,0,...,0) = f 2 (1, 1, 1,1,0,...,0) < 0. Then by f(1, 1, 1,1,0,...,0) 0, we have v 0 v 2.Thus,wederivethatv 0 = v 2. From f(α,1, α,0,...,0) 0, f(α, 1, α,0,...,0) 0, (4.11), we derive that v 0 φ(α) v 3 v 1,whereφ(α) if α. Letting α tend to, wehavev 1 = v 3. The remaining conclusions now follow from Theorem 4.1. An interesting question would be: Can we extend this theorem to m =4l for l 2? 5. Final remarks The matrix case is covered in subsections , as the roofs of theorems need to use Proosition 3.1 (r =1) Theorem 4.1 (r = 2), resectively. This shows that the matrix case (m = 2) the higher-order tensor case (m 3) are connected to each other. In Subsection 4.2, we allow r 2n 4 instead of r n. Is this a general situation for even r? Further investigation is needed. From subsections , we see that Theorem 3.1 may still hold as long as r is odd, even if GCD(m,r) > 1 that Theorem 4.2 may still hold as long as r is even, even if GCD(m,r) > 2. Are these true in general? How can we rove these? We may see that the roofs of theorems rely on Theorem 2.1, but the roofs of theorems do not use a unified technique like Theorem 2.1. Can we have a unified technique to study the case that r is odd, GCD(m,r) > 1, the case that r is even, GCD(m,r) > 2? These remain for further investigation.

12 952 GENERALIZED ANTI-CIRCULANT TENSORS REFERENCES [1] R. Badeau R. Boyer, Fast multilinear singular value decomosition for structured tensors, SIAM Journal on Matrix Analysis Alications, 30, , [2] H. Chen L. Qi, Positive definiteness semi-definiteness of even order symmetric Cauchy tensors, Journal of Industrial Management Otimization, 11, , [3] P.J. Davis, Circulant Matrices, John Wiley & Sons, New York, [4] W. Ding, L. Qi, Y. Wei, Fast Hankel tensor-vector roducts alication to exonential data fitting, Numerical Linear Algebra with Alications, 22, , [5] D. Hilbert, Über die Darstellung definiter Formen als Summe von Formenquadraten, Mathematical Annals, 32, , [6] S. Hu, G. Li, L. Qi, A tensor analogy of Yuan s alternative theorem olynomial otimization with sign structure, Journal of Otimization Theory Alications, DOI: /s , [7] S. Hu, G. Li, L. Qi, Y. Song, Finding the maximum eigenvalue of essentially nonnegative symmetric tensors via sum of squares rogramming, Journal of Otimization Theory Alications, 158, , [8] J.B. Lasserre, Global otimization with olynomials the roblem of moments, SIAM Journal on Otimization, 11, , [9] M. Laurent, Sums of squares, moment matrices otimization over olynomials, Emerging Alications of Algebraic Geometry, The IMA Volumes in Mathematics its Alications, M. Putinar S. Sullivant (eds.), Sringer, 149, , [10] C. Li Y. Li, Double B-tensor quasi-double B-tensor, Linear Algebra Its Alications, 466, , [11] C. Li, F. Wang, J. Zhao, Y. Zhu, Y. Li, Criterions for the ositive definiteness of real suersymmetric tensors, J. Comut. Al. Math., 255, 1 14, [12] G. Li, L. Qi, Q. Wang, Are there sixth order three dimensional PNS Hankel tensors? arxiv: , November [13] G. Li, L. Qi, Y. Xu, SOS-Hankel Tensors: Theory Alication, arxiv: , October [14] G. Li, L. Qi, G. Yu, The Z-eigenvalues of a symmetric tensor its alication to sectral hyergrah theory, Numerical Linear Algebra with Alications, 20, , [15] Z. Luo, L. Qi, Y. Ye, Linear oerators ositive semidefiniteness of symmetric tensor saces, Science China Mathematics, 58, , [16] J.M. Pay, L. De Lauauwer, S. Van Huffel, Exonential data fitting using multilinear algebra: The single-channel multi-channel case, Numerical Linear Algebra with Alications, 12, , [17] L. Qi, Eigenvalues of a real suersymmetric tensor, Journal of Symbolic Comutation, 40, , [18] L. Qi, Hankel tensors: Associated Hankel matrices Vermonde decomosition, Commun. Math. Sci., 13, , [19] L. Qi Y. Song, An even order symmetric B tensor is ositive definite, Linear Algebra Its Alications, 457, , [20] B. Reznick, Some concrete asects of Hilbert s 17th roblem, Contemorary Mathematics, 253, , [21] Y. Song L. Qi, Infinite finite dimensional Hilbert tensors, Linear Algebra Its Alications, 451, 1 14, [22] L. Zhang, L. Qi, G. Zhou, M-tensors some alications, SIAM Journal on Matrix Analysis Alications, 35, , [23] W. Zhao, The inverse roblem of anti-circulant matrices in signal rocessing, Pacific-Asia Conf. on Knowledge Engineering Software Engineering-KESE, Shenzhen, 47 50, 2009.