/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q7P What is the sum of the nth roots... [FREE SOLUTION] | 91影视

91影视

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=e2n=cos2n+isin2n

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-cos2n+isin2n1-cos2n+isin2n=1-cos2+isin21-cos2n+isin2n=1-1+01-cos2n+isin2n=1-11-cos2n+isin2n=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 91影视!

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

A binary tree is full if all of its vertices have either zero or two children. Let Bndenote the number of full binary trees with n vertices. (a)By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of B3, B5, and B7. Why have we left out even numbers of vertices, like B4?

(b) For general n, derive a recurrence relation for Bn.

(c) Show by induction that Bnis (2n).

Thesquare of a matrix A is its product with itself, AA.

(a) Show that five multiplications are sufficient to compute the square of a 2 x 2 matrix.

(b) What is wrong with the following algorithm for computing the square of an n x n matrix?

鈥淯se a divide-and-conquer approach as in Strassen鈥檚 algorithm, except that instead of getting 7 subproblems of size n2, we now get 5 subproblems of size n2 thanks to part (a). Using the same analysis as in Strassen鈥檚 algorithm, we can conclude that the algorithm runs in time O (nc) .鈥

(c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n x n matrices can be squared in time S(n) = O(nc), then any two n x n matrices can be multiplied in time O(nc) .

  1. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n2 ) .
  2. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B,L as follows:
    A=X000andB=0Y00
    What is AB + BA, in terms of X and Y?
  3. Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n2 ). Conclude that matrix multiplication takes time O(nc ).

In justifying our matrix multiplication algorithm (Section 2.5), we claimed the following block wise property: if X and Y are nnn matrices, and

X=[ABCD],Y=[EFGH],

where A,B,C,D,E,F,G, and H are n/2n/2 sub-matrices, then the product XY can be expressed in terms of these blocks:

XY=[ABCD][EFGH]=[AE+BGAF+BHCE+DGCF+DH]

Prove this property.

In Section 1.2.3, we studied Euclid鈥檚 algorithm for computing the greatest common divisor (gcd) of two positive integers: the largest integer which divides them both. Here we will look at an alternative algorithm based on divide-and-conquer.

(a) Show that the following rule is true.

gcd(a,b)={2gcd(a2,b2)ifa,bareevengcd(ab2)ifaisodd,bisevengcd(a-b2,b)ifa,bareodd

(b) Give an efficient divide-and-conquer algorithm for greatest common divisor.

(c) How does the efficiency of your algorithm compare to Euclid鈥檚 algorithm if a and b are n-bit -bit integers? (In particular, since n might be large you cannot assume that basic arithmetic operations like addition take constant time.)

You are given an array of nelements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(nlogn) .

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.