מטריצות, דירוג מטריצות ומשוואות לינאריות

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

בואו ניקח לדוגמה מערכת של שתי משוואות לינאריות בשני נעלמים:

\( 2x+7y=21 \)

\( 2x-4y=10 \)

לאלו שממש ממש במתח, הפתרון של המערכת הוא \( x=7,y=1 \), אבל זה לא מה שמעניין אותנו כרגע, ואפילו לא איך פותרים אותה כי ראינו את השיטה לכך בפוסט הקודם, אלא פשוט איך אפשר לכתוב את המערכת הזו בצורה קצת פחות טרחנית מזו שבה כתבתי אותה. בצורת הכתיבה שלי יש הרבה טקסט מיותר - ה-\( x,y \) מיותרים כי אני יודע שבכל משוואה לינארית יהיו משתנים; וסימן השווה מיותר; וגם הפלוס שלפני ה-7 מיותר למרות שהמינוס שלפני הארבע לא. זה לא נראה כמו משהו גרוע עד כדי כך, אבל צריך לזכור שאנחנו חושבים על פתרון משוואות עוד יותר כלליות, כאלו שיש בהן גם שבעה נעלמים ושבע משוואות. בסיטואציות כאלו כבר מפסיקים לתת אות מיוחדת לכל משתנה ופשוט קוראים להם \( x_{1},x_{2},\dots,x_{7} \) וכדומה. די ברור שהשמות הללו הם חסרי משמעות עבורנו והיינו שמחים להימנע מהצורך להשתמש בהם.

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

\( \begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array} \)

טוב. חייבים להודות שזה לא נראה משהו. אז כדי שיהיה ברור שכל המספרים הללו קשורים אחד לשני, מקיפים אותם בסוגריים:

\( \left[\begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array}\right] \)

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

פורמלית, עבור מספרים טבעיים \( n,m \), מטריצה מסדר \( n\times m \) (בעלת \( n \) שורות ו-\( m \) עמודות) היא אוסף של איברים (“איברים”, בכל הקשר שנזדקק לו, פירושו כאן “מספרים”) כך שלכל איבר יש שני אינדקסים שמציינים באיזו שורה ובאיזו עמודה הוא נמצא במטריצה. למשל, במטריצה שהצגתי למעלה, האיבר בשורה 1 ועמודה 1 הוא 2, וגם האיבר בשורה 2 ועמודה 1 הוא 2; ואילו האיבר בשורה 2 ועמודה 3 הוא 10. לרוב משתמשים באותיות לטיניות גדולות כמו \( A,B,C \) כדי לתאר מטריצות, ואז \( A_{11} \) מסמן את האיבר בשורה 1 ובעמודה 1 במטריצה \( A \) (ה”כניסה” ה-\( 1,1 \) במטריצה), וכדומה. כלומר, אם

\( A=\left[\begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array}\right] \)

אז \( A_{12}=-4 \) ו-\( A_{23}=10 \) וכדומה.

מה קורה אם יש במטריצה מספר דו ספרתי של שורות או עמודות? ובכן, אפשר לכתוב משהו כמו \( A_{10,3} \) עם פסיק ואז לא יהיו בלבולים. בכל מקרה הסימון שאני מציג כאן הוא לא קדוש ויש עוד הרבה וריאציות עליו שבהן משתמשים.

בפוסט הקודם הצגתי שתי מניפולציות שאפשר היה לעשות על משוואות במערכת משוואות - לכפול משוואה במספר, ולחבר שתי משוואות - מה שחיש קל הפך ל”לחבר למשוואה אחת משוואה אחרת כשהיא מוכפלת במספר כלשהו”. דבר אחד שלא התייחסתי אליו אז כי הוא היה כמעט מובן מאליו הוא שבמערכת משוואות אפשר להחליף את הסדר שבו משוואות מופיעות מבלי לשנות את הפתרונות של המערכת. כל זה מוביל אותנו לשלוש פעולות שאפשר לבצע על מטריצה שמייצגת מערכת משוואות אחת כדי לקבל מטריצה שמייצגת מערכת משוואות שונה עם בדיוק אותם פתרונות:

1. אפשר להחליף שתי שורות.
2. אפשר לכפול שורה במספר שונה מאפס.
3. אפשר להוסיף לשורה אחת שורה אחרת שמוכפלת במספר כלשהו.

שלוש הפעולות הללו נקראות פעולות אלמנטריות. שימו לב שכולן הפיכות - אם החלפנו שתי שורות פשוט נחליף אותן שוב ונחזור למטריצה שממנה התחלנו; אם כפלנו שורה במספר שונה מאפס, אפשר לכפול את השורה גם במספר ההפוך לו ולחזור למטריצה שממנה התחלנו; ואם הוספנו לשורה אחת שורה אחת כפול מספר, אפשר עכשיו להוסיף לה את השורה האחרת כפול מינוס אותו המספר.

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

\( \left[\begin{array}{ccc}2 & 7 & 21\\2 & -4 & 10\end{array}\right]\overset{r_{2}-r_{1}}{\to}\left[\begin{array}{ccc}2 & 7 & 21\\0 & -11 & -11\end{array}\right]\overset{-\frac{1}{11}r_{2}}{\to}\left[\begin{array}{ccc}2 & 7 & 21\\0 & 1 & 1\end{array}\right]\overset{r_{1}-7r_{2}}{\to}\left[\begin{array}{ccc}2 & 0 & 14\\0 & 1 & 1\end{array}\right]\overset{\frac{1}{2}r_{1}}{\to}\left[\begin{array}{ccc}1 & 0 & 7\\0 & 1 & 1\end{array}\right] \)

כשאני כותב \( r_{2}-r_{1} \) אני מתכוון “משנים את \( r_{2} \) - שורה 2 - על ידי כך שמחסירים ממנה את \( r_{1} \)”. כשאני כותב “\( -\frac{1}{11}r_{2} \)” אני מתכוון “כופלים את \( r_{2} \) ב-\( -\frac{1}{11} \)”, וכדומה. גם זה לא ממש סימון סטנדרטי אבל אני מקווה שהוא מספיק ברור כאן.

המטריצה שקיבלנו לבסוף, \( \left[\begin{array}{ccc}1 & 0 & 7\\0 & 1 & 1\end{array}\right] \), מייצגת את מערכת המשוואות הבאה:

\( x=7 \)

\( y=1 \)

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

מדוע המטריצה \( \left[\begin{array}{ccc}1 & 0 & 7\\0 & 1 & 1\end{array}\right] \) היא נקודת סיום טובה כל כך עבורנו? מכיוון שבכל שורה מופיע רק אחד המשתנים, והוא מופיע עם המקדם 1. זה אומר שאותה השורה בעצם אומרת “המשתנה כך וכך שווה ל…” ותו לא. אבל איך הצלחנו להגיע אליה? הפתרון טמון דווקא בעמודות. שימו לב שכבר הפעולה הראשונה שביצעתי בשרשרת המטריצות למעלה יועדה לגרום לכך שבעמודה הראשונה במטריצה, בשורה השניה, יהיה 0. מה שזה אומר בפועל הוא שמחקתי את המשתנה \( x \) מהמשוואה השניה והשארתי אותו רק בראשונה. אחר כך, כשחיברתי את השורה השניה לראשונה, זה כבר לא יכל להשפיע על המשתנה \( x \), כלומר על העמודה הראשונה, כי בשורה השניה היה שם 0.

זה מתווה את השיטה הכללית שלנו: אנחנו רוצים לקחת את העמודה הראשונה במטריצה, ולגרום לכך שבשורה הראשונה יהיה שם 1, ובשאר השורות יהיה 0. אחר כך אנחנו רוצים לקחת את העמודה השניה במטריצה ולגרום לכך שבשורה השניה יהיה שם 1, ובשאר השורות 0. כך זה במערכת של שתי משוואות בשני נעלמים אבל גם במערכות גדולות יותר.

אלא מה, לא תמיד אפשר לעשות את זה בכלל. למשל, מה עם המטריצה \( \left[\begin{array}{ccc}1 & 0 & 7\\0 & 0 & 0\end{array}\right] \)? לא משנה מה נעשה, העמודה השניה תמיד תכיל 0. ומה עם המטריצה \( \left[\begin{array}{ccc}1 & 1 & 1\\1 & 1 & 1\end{array}\right] \)? אנחנו לא יכולים לאפס את הכניסה בשורה 2 ועמודה 1 מבלי לאפס גם את הכניסה בשורה 2 ועמודה 2. לכן צריך להיות קצת יותר זהירים ביחס ליעד שלנו. זה המקום שבו צצה ההגדרה של מטריצה מצומצמת. זו הגדרה מדויקת של “מה שאנחנו יכולים לצפות לו תמיד מהתהליך שתיארנו”, אבל לא קריטי להבין אותה במלואה בינתיים. בכל זאת אביא אותה פה, כמובן. מטריצה היא מצומצמת אם היא מקיימת ש:

1. בכל שורה שלה, הכניסה הראשונה שאיננה 0 היא 1.
2. בכל עמודה שלה, אם יש כניסה שהיא הכניסה הראשונה שאינה 0 בשורה כלשהי, אז שאר הכניסות בעמודה הן 0.
3. כל השורות שמכילות רק אפסים נמצאות מתחת לכל השורות האחרות.
4. בהינתן שתי שורות שאינן שורות אפסים, הכניסה הראשונה שאיננה אפס בשורה העליונה יותר מופיעה בעמודה מוקדמת יותר מאשר הכניסה הראשונה שאיננה אפס בעמודה השניה.

אולי הכי ברור להבין את ההגדרה הזו על ידי דוגמאות שלא מתאימות לה:

המטריצה \( \left[\begin{array}{cc}1 & 0\\0 & 2\end{array}\right] \) לא עונה לדרישה 1, כי הכניסה הראשונה שאיננה 0 בשורה 2 היא 2.

המטריצה \( \left[\begin{array}{cc}1 & 0\\1 & 1\end{array}\right] \) לא עונה לדרישה 2 כי העמודה הראשונה מפירה את התנאי: יש שתי כניסות שהן הכניסות הראשונות שאינן 0. גם \( \left[\begin{array}{cc}1 & 1\\0 & 1\end{array}\right] \) מפירה את התנאי בצורה דומה - כאן הכניסה \( A_{12} \) אמנם איננה הכניסה הראשונה שאיננה 0 בשורה הראשונה, אבל \( A_{22} \) היא כן הכניסה הראשונה שאיננה 0 בשורה 2, ולכן שאר העמודה צריכה להכיל אפסים.

דוגמה נגדית ל-3 זה קל מאוד: \( \left[\begin{array}{cc}0 & 0\\1 & 0\end{array}\right] \).

ההגדרה של 4 מסובכת אבל דוגמה נגדית היא פשוטה גם כאן: \( \left[\begin{array}{cc}0 & 1\\1 & 0\end{array}\right] \) היא דוגמה נגדית, כי השורה של ה-01 באה לפני השורה של ה-10 אבל הכניסה הראשונה שאיננה 0 בשורה 01 היא בעמודה 2, ואילו הכניסה הראשונה שאיננה 0 בשורה 10 היא בעמודה 1.

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

כעת אפשר להבין למה כל ארבע התכונות שתיארתי למעלה הן הכרחיות בשביל שהמטריצה המצומצמת תהיה יחידה: כל הדוגמאות הנגדיות שנתתי עונות על כל שלוש הדרישות פרט לדרישה שהן באות לנגוד, כך שאם נשמיט ולו אחת מהדרישות, כבר יהיו שתי מטריצות מצומצמת אפשריות. במקרה הראשון \( \left[\begin{array}{cc}1 & 0\\0 & 2\end{array}\right] \) ניתנת לצמצום אל \( \left[\begin{array}{cc}1 & 0\\0 & 1\end{array}\right] \); במקרה השני \( \left[\begin{array}{cc}1 & 0\\1 & 1\end{array}\right] \) ניתנת לצמצום אל \( \left[\begin{array}{cc}1 & 0\\0 & 1\end{array}\right] \); במקרה השלישי \( \left[\begin{array}{cc}0 & 0\\1 & 0\end{array}\right] \) ניתנת לצמצום אל \( \left[\begin{array}{cc}1 & 0\\0 & 0\end{array}\right] \) ובמקרה הרביעי \( \left[\begin{array}{cc}0 & 1\\1 & 0\end{array}\right] \) ניתנת לצמצום אל \( \left[\begin{array}{cc}1 & 0\\0 & 1\end{array}\right] \).

כעת, איך מדרגים מטריצה באופן כללי? ובכן, קודם כל מוצאים בעמודה הראשונה את השורה הראשונה שבה לא מופיע 0 (אם בכולן מופיע 0 עוברים מייד לעמודה הבאה). מחליפים את סדר השורות (פעולה אלמנטרית 1) כך שהשורה הזו תופיע הראשונה במטריצה. כופלים את השורה הזו בקבוע מתאים (פעולה אלמנטרית 2) כך שבעמודה הראשונה יופיע בה כעת 1. לבסוף, מחסירים את השורה הזו מכל האחרות כשהיא מוכפלת בכל פעם בקבוע מתאים כדי לאפס את כל שאר הכניסות בעמודה הזו. בואו נראה את התהליך על מטריצה מסדר \( 3\times3 \):

\( \left[\begin{array}{ccc}0 & 2 & 1\\2 & 1 & 1\\1 & 3 & 1\end{array}\right]\overset{r_{1}\leftrightarrow r_{2}}{\to}\left[\begin{array}{ccc}2 & 1 & 1\\0 & 2 & 1\\1 & 3 & 1\end{array}\right]\overset{\frac{1}{2}r_{1}}{\to}\left[\begin{array}{ccc}1 & \frac{1}{2} & \frac{1}{2}\\0 & 2 & 1\\1 & 3 & 1\end{array}\right]\overset{r_{3}-r_{1}}{\to}\left[\begin{array}{ccc}1 & \frac{1}{2} & \frac{1}{2}\\0 & 2 & 1\\0 & \frac{5}{2} & \frac{1}{2}\end{array}\right] \)

בסופו של דבר קיבלתי בעמודה 1 מופע בודד של 1 וכל היתר 0. כעת נטפל בצורה דומה בעמודה 2, פרט לכך ששורה 1 היא כבר “מחוץ למשחק” במובן זה שלא מזיזים אותה יותר (אבל כן צריך לאפס בתוכה את עמודה 2 אם מגיעים לשלב הזה).

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

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