שורש יחידה – הבדלי גרסאות

ה[[מטריצה]] U מסדר <math>n \times n</math> שהמקום ה-(i,j) שלו הוא: <math>U_{j,k}=n^{-\frac{1}{2}}\cdot z^{j\cdot k}</math> מגדירה התמרת פורייה דיסקרטית. חישוב הטרנספורמציה ההופכית באמצעות שיטת [[האלימינציה של גאוס]] דורש שימוש ב-''[[סימון<math>\ אסימפטוטי|O]]''(''n''<sup>^3)</supmath>) אופרציותפעולות. ככל הנראה, נובע מהאורתוגונליות ש-U היא [[מטריצה יוניטרית]]. היא בעצם:

<math>\sum_{k=1}^{n} \overline{U_{j,k}} \cdot U_{k,j'} = \delta_{j,j'} ,</math> ולכן ההופכי של U הוא פשוט הצמוד המרוכב. (הראשון ששם לב לעובדה זו הוא [[קרל פרידריך גאוס]] כאשר הוא פתר את הבעיה של [[אינטרפולציה טריגונומטרית]]). היישום המתקדם יותר של U או ההופכי שלו ל[[וקטור (אלגברה)|ווקטור]] נתון דורש שימוש ב-''[[סימון<math>\ אסימפטוטי|O]]''(''n''<sup>^2)</supmath>) אופרציותפעולות. [[התמרת פורייה המהירה]] מקטינה את מספר האופרציותהפעולות ל-''<math>\ O''(''n''&nbsp;\log&nbsp;''{n''})</math>.