שיעור שני

אלגברת מטריצות

הגדרה: האיבר הij בכפל AB מוגדר להיות [math]\displaystyle{ [AB]_{ij}=\sum_{k=1}^na_{ik}b_{kj} }[/math]

ניתן לבצע את הכפל AB אם"ם מספר העמודות של A זהה למספר השורות של B (ונקרא n בנוסחא למעלה). אמנם פעולת הכפל נראית משונה, אך נראה בהמשך כי היא משמעותית למדי.

באופן כללי, כפל מטריצות אינו חייב להיות חילופי. כלומר, לא תמיד AB=BA !!

תרגיל 3.4 ג-ז

נתונה מערכת של m משוואות בn נעלמים: Ax=b (זה זמן טוב לראות דוגמא ראשונה של המשמעות של כפל מטריצות). נסמן ב [math]\displaystyle{ H=\{v\in\mathbb{F}^n:Av=0\} }[/math] את קבוצת הפתרונות של המערכת ההומוגנית המתאימה, וב[math]\displaystyle{ L=\{v\in\mathbb{F}^n:Av=b\} }[/math] את קבוצת הפתרונות של המערכת הלא-הומוגנית. הוכח את הטענות הבאות:

ג

אם L אינה קבוצה ריקה, אזי כמות הפתרונות בH שווה לכמות הפתרונות בL

פתרון

נוכיח את הטענה על ידי יצירת פונקציה חח"ע ועל בין H לבין L. יהיה [math]\displaystyle{ x\in L }[/math] כלשהו (הקיים לפי הנתון). נביט בהעתקה [math]\displaystyle{ f:L\rightarrow H }[/math] המוגדרת ע"י [math]\displaystyle{ f(y)=y-x }[/math]. יש להוכיח כי זו אכן פונקציה מוגדרת היטב (כלומר, y-x הוא פתרון של המערכת ההומוגנית) ואז יש להראות כי זה פונקציה חח"ע ועל.

דבר ראשון, נבדוק האם y-x הינו פתרון של המערכת ההומוגנית. [math]\displaystyle{ A(y-x)=Ay-Ax=b-b=0 }[/math] כפי שרצינו.

דבר שני, נניח כי [math]\displaystyle{ y_1\neq y_2 }[/math] לכן ברור ש[math]\displaystyle{ y_1-x\neq y_2-x }[/math] (במילים, לכל שני פתרונות שונים מL מתאימים שני פתרונות שונים בH).

דבר שלישי, נראה כי לכל פתרון y בH, יש פתרון בL הנשלח אליו. פתרון זה הינו כמובן y+x שכן [math]\displaystyle{ A(y+x)=Ay+Ax=0+b=b }[/math].

לכן סה"כ הראנו כי לכל פתרון בL מתאים פתרון יחיד בH ולכן הקבוצות הנ"ל הן באותו גודל.

ד

מצא מקרה שבו אין פתרונות למערכת הלא הומוגנית, אך יש פתרון יחיד למערכת ההומוגנית

פתרון

נביט במטריצה [math]\displaystyle{ A=\begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{pmatrix} }[/math] ובוקטור הפתרונות [math]\displaystyle{ A=\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} }[/math]. במערכת Ax=b ישנה שורת סתירה, ולכן אין לה פתרונות, ואילו למערכת ההומוגנית יש פתרון יחיד (0,0).

ה

מצא מקרה שבו אין פתרונות למערכת הלא הומוגנית, אך יש אינסוף פתרונות למערכת ההומוגנית

פתרון

נביט במטריצה [math]\displaystyle{ A=\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} }[/math] ובוקטור הפתרונות [math]\displaystyle{ A=\begin{pmatrix} 0 \\ 1 \end{pmatrix} }[/math]. במערכת Ax=b מעל הממשיים ישנה שורת סתירה, ולכן אין לה פתרונות, ואילו למערכת ההומוגנית יש אינסוף פתרונות.

ו

מצא מקרה שבו אין פתרונות למערכת הלא הומוגנית, אך יש 7 פתרונות למערכת ההומוגנית

פתרון

נביט במטריצה [math]\displaystyle{ A=\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} }[/math] ובוקטור הפתרונות [math]\displaystyle{ A=\begin{pmatrix} 0 \\ 1 \end{pmatrix} }[/math]. במערכת Ax=b מעל השדה [math]\displaystyle{ \mathbb{Z}_7 }[/math] ישנה שורת סתירה, ולכן אין לה פתרונות, ואילו למערכת ההומוגנית יש 7 פתרונות מכיוון שיש משתנה חופשי יחיד.

ז

נתון שמספר המשוואות זהה למספר הנעלמים. עוד נתון שאין פתרונות למערכת הלא-הומוגנית. מה ניתן לומר על מספר הפתרונות של המערכת ההומוגנית?

פתרון

נדרג את המטריצה A. מכיוון שאין פתרונות למערכת הלא-הומוגנית, חייבת להיות בצורה המדורגת של A שורת אפסים (אחרת יש אותו מספר של איברים מובילים ושל משתנים ולכן אין משתנים חופשיים וכל משתנה נקבע באופן יחיד על ידי וקטור הפתרונות). מכיוון שיש שורת אפסים בצורה המדורגת, יש משתנה חופשי ולכן יש יותר מפתרון אחד למערכת ההומוגנית (מספר הפתרונות הוא מספר האיברים בשדה בחזקה מספר המשתנים החופשיים, ובכל שדה יש לפחות שני איברים שונים).

סוגים שונים של כפל מטריצות

בנוסף לכפל הרגיל, חשוב מאד לדעת גם כפל-שורה וכפל-עמודה:

נביט במטריצה [math]\displaystyle{ A=\begin{pmatrix} -R_1- \\ -R_2- \\ \vdots \\ -R_n- \end{pmatrix} }[/math] ששורותיה הן [math]\displaystyle{ R_1,...,R_n }[/math], ונביט בוקטור השורה [math]\displaystyle{ x=(a_1,...,a_n) }[/math]. מתקיים ש[math]\displaystyle{ xA=\sum_{i=1}^na_iR_i }[/math]. במילים - הכפל של השורה x במטריצה A הינה סכום של שורות A כפול הקבועים מהשורה x. נובע בקלות שהשורה ה-j בכפל AB הינה סכום שורות B כפול הקבועים המתאימים מהשורה ה-j של A. למעשה זהו מקרה פרטי של הכפל הרגיל BA עבור מטריצה B=x מגודל 1על n ומטריצה A מגודל n על m, ולכן התוצאה שנקבל היא מטריצה 1 על m הלא הוא וקטור שורה.

באופן דומה, נביט במטריצה [math]\displaystyle{ A=\begin{pmatrix} C_1 & C_2 & \cdots & C_m \end{pmatrix} }[/math] שעמותודיה הן [math]\displaystyle{ C_1,...,C_m }[/math], ונביט בוקטור העמודה [math]\displaystyle{ x=\begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_m \end{pmatrix} }[/math]. מתקיים ש[math]\displaystyle{ Ax=\sum_{i=1}^ma_iC_i }[/math]. במילים - הכפל של מטריצה בעמודה שווה לסכום עמודות המטריצה כפול הקבועים מהעמודה. נובע בקלות שהעמודה ה-j בכפל AB שווה לסכום עמודות A כפול הקבועים המתאימים מהעמודה ה-j של B. שימו לב שמערכת משוואות הינה מקרה פרטי של כפל-עמודה. למעשה זהו מקרה פרטי של הכפל הרגיל AB עבור מטריצה A מגודל n על m ומטריצה B=x מגודל m על 1, ולכן התוצאה שנקבל היא מטריצה n על 1 הלא הוא וקטור עמודה כפי שאכן מתקבל במערכת משוואות.

מטריצת בלוקים. מטריצה בלוקים הינה מטריצה הבנוייה ממספר מטריצות קטנות יותר (המכונות בלוקים). לדוגמא, ניקח את המטריצה [math]\displaystyle{ A=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, B=\begin{pmatrix} 2 \\ 3 \end{pmatrix} }[/math]. אזי מטריצת הבלוקים מוגדרת להיות [math]\displaystyle{ C=(A|B)=\begin{pmatrix} 1 & 0 & 2 \\ 1 & 1 & 3 \end{pmatrix} }[/math]

משפט: לכל שלש מטריצות A,B,C כך שהכפל מוגדר, מתקיים ש[math]\displaystyle{ C(A|B)=(CA|CB) }[/math] כלומר כפל C במטריצת הבלוקים, הוא מטריצה הבלוקים המורכבת מהכפל של C בכל בלוק.

הוכחה: נובע בקלות מכפל עמודה-עמודה המוזכר לעיל.

תרגיל 3.7

תהא מערכת Ax=b, יהיה v פתרון למערכת הלא-הומוגנית ו-w פתרון למערכת ההומוגנית Ax=0. נגדיר [math]\displaystyle{ B=(v,w,v+w,v-w,w-v) }[/math] חשב את AB

פתרון

לפי כפל מטריצות בלוקים קל לוודא ש [math]\displaystyle{ AB=(b,0,b,b,-b) }[/math]

שחלוף וסמטריות

הגדרה: תהי מטריצה A. אזי המטריצה המשוחלפת [math]\displaystyle{ A^t }[/math] מוגדרת ע"י [math]\displaystyle{ [A^t]_{ij}=[A]_{ji} }[/math]. כלומר, האיבר בשורה ה-i והעמודה ה-j של המטריצה המשוחלפת הוא האיבר בשורה ה-j והעמודה ה-i של המטריצה המקורית - הפכנו את השורות לעמודות, ואת העמודות לשורות.

דוגמא: אם [math]\displaystyle{ A=\begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{pmatrix} }[/math] אזי [math]\displaystyle{ A^t=\begin{pmatrix}1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9\end{pmatrix} }[/math]

הגדרה: מטריצה נקראת סמטרית אם היא שווה למשוחלפת של עצמה [math]\displaystyle{ A=A^t }[/math] (השורות והעמודות שלה זהות). מטריצה נקראת אנטי-סימטרית אם [math]\displaystyle{ A=-A^t }[/math]

תכונות:

לכל שתי מטריצות A,B כך שהכפל מוגדר ש [math]\displaystyle{ (AB)^t=B^tA^t }[/math].
[math]\displaystyle{ (A^t)^t=A }[/math]
לכל שתי מטריצות A,B באותו גודל מתקיים [math]\displaystyle{ (A+B)^t = A^t+B^t }[/math]
לכל מטריצה A, ולכל קבוע מהשדה c מתקיים ש [math]\displaystyle{ (cA)^t= c(A^t) }[/math]

תרגיל 4.4

א. הוכח שלכל מטריצה [math]\displaystyle{ A\in\mathbb{F}^{m\times n} }[/math] המטריצה [math]\displaystyle{ AA^t }[/math] הינה סימטרית.

ב. הוכח שלכל מטריצה ריבועית A מתקיים שהמטריצה [math]\displaystyle{ A+A^t }[/math] סימטרית, ואילו המטריצה [math]\displaystyle{ A-A^t }[/math] אנטי סימטרית.

פתרון

א. נסמן [math]\displaystyle{ B=A^t }[/math]. לפי התכונות לעיל קל לראות ש [math]\displaystyle{ (AA^t)^t= (AB)^t =B^tA^t = (A^t)^tA^t= AA^t }[/math] והוכחנו שהמטריצה סימטרית.

ב. [math]\displaystyle{ (A+A^t)^t = A^t + (A^t)^t = A^t+A = A+ A^t }[/math] (הרי חיבור מטריצות הוא חילופי). כמו כן, [math]\displaystyle{ (A-A^t)^t = A^t - A = -(A-A^t) }[/math] כפי שרצינו.

תרגיל 4.5

א. תהי A מטריצה ריבועית ממשית (כלומר שאיבריה משדה הממשיים) אנטי סימטרית. הוכח שכל איברי האלכסון שלה שווים לאפס. ב. האם הטענה נכונה למטריצות ריבועיות אנטי סימטריות מעל שדות אחרים? אפיין בדיוק את השדות מעליהם הטענה נכונה

פתרון

נביט באיבר אלכסון [math]\displaystyle{ [A]_{ii} }[/math]. מתוך אנטי סימטריות מתקיים ש[math]\displaystyle{ [A]_{ii}=-[A]_{ii} }[/math] (החלפנו את השורה והעמודה, מכיוון שהן שוות קיבלנו בדיוק את אותו האיבר).

לפי תכונות השדה שלמדנו, ניתן לחבר לשני האגפים את הנגדי ולקבל [math]\displaystyle{ [A]_{ii}+[A]_{ii}=0 }[/math]. ולכן [math]\displaystyle{ (1+1)[A]_{ii}=0 }[/math]. מכיוון שבשדה אין מחלקי אפס, יש שתי אפשרויות:

[math]\displaystyle{ [A]_{ii}=0 }[/math]
[math]\displaystyle{ 1+1=0 }[/math]

לכן, בכל שדה ממאפיין שונה מ-2 (כלומר סכום שתי אחדות אינו אפס) קל לראות שאיברי האלכסון חייבים להיות אפס. לעומת זאת, בכל שדה ממאפיין שתים קל לראות שהמטריצה [math]\displaystyle{ \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix} }[/math] הינה אנטי סימטרית שכן אם [math]\displaystyle{ 1+1=0 }[/math] נובע ש[math]\displaystyle{ 1=-1 }[/math] ולכן מתקיים ש [math]\displaystyle{ \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}=\begin{pmatrix} -1 & 0 \\ 0 & -1\end{pmatrix} }[/math]. כמו כן, ברור שאיברי האלכסון של המטריצה הנ"ל שונים מאפס.

מטריצות ריבועיות

הגדרה: העקבה (trace) של מטריצה ריבועית הינה סכום איברי האלכסון של המטריצה.

תכונות:

[math]\displaystyle{ tr(A+B)=tr(A)+tr(B) }[/math]
[math]\displaystyle{ tr(AB)=tr(BA) }[/math]

הגדרה: מטריצת היחידה [math]\displaystyle{ I }[/math] הינה המטריצה שעל האלכסון שלה יש אחדות, ואפס בכל מקום אחר. לכל מטריצה ריבועית A מתקיים AI=IA=A.

תרגיל 5.10 וחצי

הוכח שלא קיימות מטריצות ריבועיות ממשיות כך ש [math]\displaystyle{ AB-BA=I }[/math]. האם הדבר נכון לכל שדה?

פתרון

נפעיל עקבה על שני האגפים, ונקבל מצד אחד [math]\displaystyle{ trace(AB-BA)=trace(AB)-trace(BA)=0 }[/math] ומצד שני [math]\displaystyle{ trace(I)=1+1+...+1 }[/math]. מעל הממשיים סכום אחדות לעולם אינו מתאפס ולכן השיוויון הנ"ל לא ייתכן.

מעל שדה עם מאפיין סופי השיוויון אפשרי, לדוגמא מעל [math]\displaystyle{ \mathbb{Z}_2 }[/math] עבור המטריצות [math]\displaystyle{ A=\begin{pmatrix}0 & 1 \\ 0 & 0\end{pmatrix},B=\begin{pmatrix}0 & 0 \\ 1 & 0\end{pmatrix} }[/math] מתקיים ש [math]\displaystyle{ AB-BA = A=\begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}=I }[/math] (מכיוון ש[math]\displaystyle{ 1=-1 }[/math]).

תרגיל 5.11

א. תהא A מטריצה ממשית כך ש [math]\displaystyle{ tr(AA^t)=0 }[/math] הוכח ש-A הינה מטריצת האפס.

ב. תהא A מטריצה מרוכבת כך ש [math]\displaystyle{ tr(AA^*)=0 }[/math] הוכח ש-A הינה מטריצת האפס. ([math]\displaystyle{ A^*:=\overline{A^t} }[/math])

פתרון

א. נסמן ב [math]\displaystyle{ R_i(A) }[/math] את השורה ה-i של המטריצה A וב [math]\displaystyle{ C_i(A) }[/math] את העמודה ה-i של המטריצה A. מכיוון שהמטריצה המשוחלפת מתקבלת על ידי החלפת שורות ועמודות של המטריצה המקורית תמיד מתקיים ש [math]\displaystyle{ [R_i(A)]^t=C_i(A^t) }[/math] (השחלוף החיצוני הינו על מנת להפוך את וקטור השורה לוקטור עמודה).

כמו כן, נשים לב שבכפל מטריצות מתקיים תמיד [math]\displaystyle{ [AB]_{ij}=R_i(A)B_j(B) }[/math].

כעת, [math]\displaystyle{ tr(AA^t)=\sum_{i=1}^m[AA^t]_{ii}=\sum_{i=1}^mR_i(A)C_i(A^t)=\sum_{i=1}^mR_i(A)(R_i(A))^t }[/math]

נשים לב שבאופן כללי, בהנתן [math]\displaystyle{ v=(x_1,...,x_n) }[/math] מתקיים ש [math]\displaystyle{ vv^t = (x_1)^2+(x_2)^2+...+(x^n)^2 }[/math].

ביחד ניתן להסיק ש[math]\displaystyle{ tr(AA^t) }[/math] שווה לסכום הריבועים של כל איברי המטריצה. מכיוון שריבוע גדול או שווה לאפס, מתקיים שסכום ריבועים הוא אפס אם"ם כל האיברים הם אפס, ולכן המטריצה הינה מטריצת האפס.

ב. עבור המרוכבים ההוכחה הינה דומה, פשוט מקבלים עבור וקטור מרוכב כללי [math]\displaystyle{ v=(z_1,...,z_n) }[/math] מתקיים ש [math]\displaystyle{ vv^*=|z_1|^2+...+|z_n|^2 }[/math] ואז בעזרת טענה דומה מקבלים שכל איברי המטריצה הינם אפס.

מטריצות הפיכות

הגדרה: מטריצה A נקראת הפיכה אם קיימת מטריצה B כך ש [math]\displaystyle{ AB=BA=I }[/math]. במקרה זה, מטריצה B נקראת ההופכית של A ומסומנת [math]\displaystyle{ B=A^{-1} }[/math].

תכונות:

מטריצה הפיכה היא בהכרח ריבועית
אם A ריבועית ו[math]\displaystyle{ AB=I }[/math] אזי גם [math]\displaystyle{ AB=BA=I }[/math] וB הינה ההופכית של A
[math]\displaystyle{ (AB)^{-1}=B^{-1}A^{-1} }[/math]

תרגיל 6.1 וחצי

הוכח שאם A הפיכה גם המשוחלפת שלה הפיכה ומתקיים ש [math]\displaystyle{ (A^t)^{-1}=(A^{-1})^t }[/math]. הסק שאם A הפיכה וסמטרית אזי גם ההופכית שלה סימטרית.

פתרון

נניח A הפיכה, אזי קיימת לה הופכית כך ש [math]\displaystyle{ AA^{-1}=I }[/math]. נשחלף את שני האגפים ונקבל [math]\displaystyle{ (A^{-1})^tA^t=I^t=I }[/math] ומכאן המש"ל כיוון שA ריבועית וכך גם המשוחלפת שלה.

אם A הפיכה וסימטרית מתקיים [math]\displaystyle{ (A^{-1})^t=(A^t)^{-1}=A^{-1} }[/math] כלומר ההופכית גם סימטרית.

מטריצות אלמנטריות

דיברנו כבר על פעולות שורה אלמנטריות כאשר דיברנו על פעולות שלא משנות את מרחב הפתרונות של המערכת המתאימה למטריצה. נזכיר מהן פעולות השורה האלמנטריות:

[math]\displaystyle{ R_i \leftrightarrow R_j }[/math]
[math]\displaystyle{ R_i \rightarrow \alpha R_i }[/math], כאשר [math]\displaystyle{ 0\neq\alpha\in\mathbb{F} }[/math]
[math]\displaystyle{ R_i \rightarrow R_i+\alpha R_j }[/math] כאשר [math]\displaystyle{ i\neq j }[/math]

פעולת שורה היא למעשה פונקציה שניתן להפעיל על כל מטריצה. למשל נסמן את פעולת השורה [math]\displaystyle{ R_1\rightarrow R_1-R_2 }[/math] באות [math]\displaystyle{ \rho }[/math] אזי מתקיים לדוגמא:

[math]\displaystyle{ \rho\begin{pmatrix}1 & 1 \\ 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix} }[/math]

[math]\displaystyle{ \rho\begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}=\begin{pmatrix}-2 & -2 \\ 3 & 4\end{pmatrix} }[/math]

מטריצות אלמנטריות

מטריצת שורה אלמנטרית היא מטריצה המתקבלת מהפעלת פעולת שורה אלמנטרית על מטריצת היחידה.

משפט: לכל מטריצה A מתקיים ש [math]\displaystyle{ \rho(A) = \rho(I)A }[/math].

כלומר, הפעלת פעולת שורה אלמנטרית שקולה לכפל במטריצת השורה האלמנטרית המתאימה.

יש משפט והגדרה דומים עבור מטריצות עמודה אלמנטריות עם כפל בצד השני. כמו כן, כל מטריצת שורה אלמנטרית הינה מטריצת עמודה אלמנטרית עבור פעולה מתאימה. מטריצות אלה נקראות ביחד מטריצות אלמנטריות.

מסקנה - אלגוריתם למציאת מטריצה הופכית

דירוג מטריצה שקול לכפל במטריצות אלמנטריות המתאימות לפעולות הדירוג. לכן, אם דירגנו מטריצה ריבועית לצורת מטריצה היחידה קיבלנו [math]\displaystyle{ \rho_1(I)\cdots\rho_k(I)A=I }[/math] ולפיכך מתקיים שהמטריצה A הפיכה וההופכית שלה הינה [math]\displaystyle{ \rho_1(I)\cdots\rho_k(I) }[/math].

אם נדרג קנונית את מטריצת הבלוקים [math]\displaystyle{ (A|I) }[/math] נקבל מטריצה מהצורה [math]\displaystyle{ (I|\rho_1(I)\cdots\rho_k(I)) }[/math] (שכן לפי כפל מטריצת בלוקים, כפל במטריצה האלמנטרית מופעל במקביל על כל אחד מהבלוקים). לכן כאשר אנחנו מדרגים את [math]\displaystyle{ (A|I) }[/math] עד שנקבל את מטריצת היחידה משמאל, מימין נקבל את המטריצה ההופכית [math]\displaystyle{ (I|A^{-1}) }[/math].