שיעור שני

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

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

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

תרגיל 3.4 ג-ז

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

ג

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

פתרון

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

דבר ראשון, נבדוק האם y-x הינו פתרון של המערכת ההומוגנית. $A(y-x)=Ay-Ax=b-b=0$ כפי שרצינו.

דבר שני, נניח כי $y_1\neq y_2$ לכן ברור ש $y_1-x\neq y_2-x$ (במילים, לכל שני פתרונות שונים מL מתאימים שני פתרונות שונים בH).

דבר שלישי, נראה כי לכל פתרון y בH, יש פתרון בL הנשלח אליו. פתרון זה הינו כמובן y+x שכן $A(y+x)=Ay+Ax=0+b=b$ .

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

ד

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

פתרון

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

ה

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

פתרון

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

ו

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

פתרון

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

ז

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

פתרון

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

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

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

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

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

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

משפט: לכל שלשת מטריצות A,B,C כך שהכפל מוגדר, מתקיים ש $C(A|B)=(CA|CB)$ כלומר כפל C במטריצת הבלוקים, הוא מטריצה הבלוקים המורכבת מהכפל של C בכל בלוק.

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

תרגיל 3.7

תהא מערכת Ax=b, יהיה v פתרון למערכת הלא-הומוגנית ו-w פתרון למערכת ההומוגנית Ax=0. נגדיר $B=(v,w,v+w,v-w,w-v)$ חשב את AB

פתרון

לפי כפל מטריצות בלוקים קל לוודא ש $AB=(b,0,b,b,-b)$

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

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

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