שינויים

קפיצה אל: ניווט, חיפוש

מבנים אלגבריים למדעי המחשב - ארז שיינר

נוספו 1,773 בתים, 16:44, 27 באוקטובר 2018
/* הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מהספר */
*עבור <math>f\in S_n</math> נגדיר את הסימן <math>\mathrm{sign}(f):=\Pi_{i\neq j}\frac{x_{f(i)}-x_{f(j)}}{i-j}</math>.
*הסימן של תמורה הוא תמיד פלוס או מינוס 1.
*אם סימן התמורה הוא מינוס אחד אומרים שהיא '''אי-זוגית''' או '''שלילית''', ואם הסימן הוא אחד אומרים שהיא '''זוגית''' או '''חיובית'''.
===מחזורים===
*מחזור <math>(a_1\ a_2\ \cdots \ a_k)</math> מייצג את התמורה f המקיימת <math>f(a_1)=a_2,...,f(a_{k-1})=a_k,f(a_k)=a_1</math> ולכל איבר אחר <math>f(a)=a</math>.
*לדוגמא: <math>\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}=(1\ 4\ 3\ 5)\in S_5</math>
*הגדרת סימן של כל תמורה לפי חלוקת פולינומיםניתן להציג כהרכבה של מחזורים זרים, הוכחת כפליות הסימןואת תמורה הזהות ניתן להציג כ<math>(1)</math>.  *הצגת חילוף הוא מחזור באורך 2.*חילוף הוא תמורה כמחזורים זרים, הצגת מחזורים אי זוגית.**נוכיח עבור <math>f=(1\ 2)\in S_n</math>. (זה מספיק כיוון שהשם של האיברים לא משנה.)**<math>\mathrm{sign}(f)=\left(\frac{x_2-x_1}{x_1-x_2}\cdot\frac{x_2-x_3}{x_1-x_3}\cdots \frac{x_2-x_n}{x_1-x_n}\right)\cdot\left(\frac{x_1-x_3}{x_2-x_3}\cdots\frac{x_1-x_n}{x_2-x_n}\right)\left(\cdot\frac{x_3-x_4}{x_3-x_4}\cdots\frac{x_{n-1}-x_n}{x_{n-1}-x_n}\right)=-1</math>   *כל מחזור ניתן להציג כהרכבה של חילופים:**<math>(a_1\ a_2\ \cdots \ a_k)=(a_1\ a_2)(a_2\ a_3)\cdot (a_{k-1}\ a_k)</math>**כל איבר שלא מוזכר במחזור נשלח לעצמו, סימן ונציב בשני הצדדים את <math>a_1,...,a_{k-1}</math> ונראה כי הפונקציות שוות.**כיוון שמדובר בפונקציה הפיכה, אין צורך לבדוק את האיבר האחרון <math>a_k</math>.   *מסקנה: כיוון שסימן כל חילוף הוא שליליולפי כפליות הסימן, הסימן של מחזור באורך k הוא <math>(-1)^{k-1}</math>.*דוגמא:**<math>f=\begin{pmatrix}1&2&3&4&5&6&7\\4&2&5&3&1&7&6\end{pmatrix}=(1\ 4\ 3\ 5)(6\ 7)</math>.**לכן <math>\mathrm{sign}(f)=(-1)\cdot(-1)=1</math>, כלומר מדובר בתמורה זוגית.
==הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מ[http://abstract.ups.edu/aata/ הספר] ==