What is the sum of the nth roots of unity? What is their product if n is odd? If n is even?

Short Answer

Expert verified

Sum of nth root of unity =0

Product of nth root of unity, when number of terms are even =-1

Product of nth root of unity, when number of terms are odd =1

Step by step solution

01

Sum of  n th root of unity

Thenthrootsofunityare1,W,W2,W3,....WN-1Where,W=e2πn=cos2πnθ+isin2πnθ

The sum of nth roots of unity is:

1,W,W2,W3,.....WN-1 …… (1)

As per the geometric series, the sum of n terms of 1,W,W2,W3,.....WN-1is represented as .

So, equation (1) can be represented as follows:

Sum of nth root of unity= 1-wn1-w

=1-cos2πn+isin2πn1-cos2πn+isin2πn=1-cos2π+isin2π1-cos2πn+isin2πn=1-1+01-cos2πn+isin2πn=1-11-cos2πn+isin2πn=0

02

Product of nth root of unity 

The production of th root unity are following: 1,W,W2,W3,....WN-1...3... (3)

As per the arithmetic series, the product of n terms of 1,W,W2,W3,....WN-1is

represented as role="math" localid="1658921404734" Wnn-12

So, calculation (3) is present as follows:

Product of th root of unity =Wnn-12

=cos2n+isin2nnn-12 ... (4)

If is even, then

Product of nth root of unity =-1 … (5)

If n is odd, then

Product of nth root of unity =1 … (6)

Moreover,

  • This summation of such nth component of unity is given by Equation (2), is equal to 0.
  • If "n" is even, this products of both the nth root for unity is obtained from Equation (5), is equal to -1.
  • If "n" is odd, the composite of nth roots of unity may be calculated using Equation (6), is equal to 1.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

How many lines, as a function of n (in (.)form), does the following program print? Write a recurrence and solve it. You may assume is a power of . function f (n) if n > 1:

print_line (‘‘still going’’)

f (n/2)

f (n/2)

In Section 2.1 we described an algorithm that multiplies two n-bit binary integers x and y in time na, where a=log23. Call this procedure fast multiply (x,y).

(a) We want to convert the decimal integer 10n(a 1 followed by n zeros) into binary. Here is the algorithm (assume n is a power of 2):

function pwr2bin(n)

if n = 1: return10102

else:

z= ???

return fastmultiply(z,z)

Fill in the missing details. Then give a recurrence relation for the running time of the algorithm, and solve the recurrence.

(b) Next, we want to convert any decimal integer x with n digits (where n is a power of 2) into binary. The algorithm is the following:

function dec2bin(x)

if n=1: return binary [ x ]

else:

split x into two decimal numbers xt,xRwith n/2 digits each

return ???

Here binary [.] is a vector that contains the binary representation of all one-digit integers. That is, binary role="math" localid="1659333641173" [0]=02, binary [1]=12, up to binary [9]=10012. Assume that a lookup in binary takes 0(1) time. Fill in the missing details. Once again, give a recurrence for the running time of the algorithm, and solve it.

Suppose we want to evaluate the polynomial P(x) = a0 + a1x + a2x2 + ... + anxn at point x.

  1. Show that the following simple routine, known as Horner’s rule, does the job and leaves the answer in z.
    z = an
    for I = n-1 down to 0 :
    z = zx + ai
  2. How many additions and multiplications does this routine use, as a function of n ? Can you find a polynomial for which an alternative method is substantially better?

Practice with the fast Fourier transform.

(a) What is the FFT of (1,0,0,0)? What is the appropriate value of ωin this case? And of which sequence is (1,0,0,0)the FFT?

(b)Repeat for (1,0,1,-1).

Find the unique polynomial of degree 4 that takes on values p(1)=2,p(2)=1,p(3)=0,p(4)=4,andp(5)=0. Write your answer in the coefficient representation.

See all solutions

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free