#import "/0366-[Math]/globals/template.typ": *

#show: project.with(
  title: "אלגברה לינארית 1א׳ - שיעור 4",
  authors: ("<NAME>",),
  date: "11 בינואר, 2024",
)

#set enum(numbering: "(1.א)")

= מערכות משוואות לינאריות
== הגדרה
מערכות משוואות לינאריות באותן נעלמים נקראות *שקולות* אם יש להן את אותו אוסף פתרונות. 
=== דוגמה
$ cases(x+y=1, x-y=1) $ 
אוסף הפתרונות $S = {(1,0)}$.

$ cases(x=1, y=0) $
גם פה, אוסף הפתרונות $S = {(1,0)}$.

כלומר, שתי המערכות *שקולות*.

== הגדרה
שלושת הפעולות הבאות המבוצעות על מע׳ משוואות נקראות *פעולות אלמנטריות*:
+ החלפת סדר המשוואות במערכת.
+ מכפלת משוואה בסקלר שאינו 0.
+ הוספת מכפלה בסקלר של משוואה אחת למשוואה אחרת.

== פעולות אלמנטריות מעבירות בין מע׳ משוואות שקולות

=== הוכחה
נתונה מערכת משוואות לינארית 
$
(M) = cases(a_11 x_1 + a_12 x_2 + dots + a_(1n) x_n = b_1,
  a_21 x_1 + a_22 x_2 + dots + a_(2n) x_n = b_2,
  dots.v,
  a_(m 1) x_1 + a_(m 2) x_2 + dots + a_(m n) x_n = b_m)
$

נסמן ב-$tilde(M)$ את המערכת המתקבלת מ-$M$ לאחר הפעלת פעולה אלמנטרית אחת. לכאורה עלינו להראות הכלה דו-כיוונית בין אוסף הפתרונות של $M$ לזה של $tilde(M)$. בפועל, אם נשים לב שלכל פעולה אלמנטרית יש פעולה אלמנטרית הופכית, נוכל להסיק שמספיק להראות שכל פתרון של $M$ הוא גם פתרון של $tilde(M)$. ואמנם:
+ הפעולה ההופכית להחלפת שתי משוואות היא החלפה נוספת של אותן שתי משוואות.
+ אם נכפול משוואה בסקלר $lambda !=0$ אחרי מכפלה של אותה משוואה ב-$lambda^(-1)$ נחזור למשוואה המקורית.
+ על מנת לחזור למשוואה המקורית לאחר שהוספנו לה מכפלה בסקלר של משוואה אחרת, עלינו להוסיף לה גם מכפלה של אותה משוואה אך בסקלר הנגדי.

#pagebreak()
יהי $(c_1, c_2, dots, c_n)$ פתרון של המערכת $M$: 
$
cases(
  a_11 c_1 + dots + a_(1n) c_n = b_1,
  dots.v,
  a_(i 1) c_1 + dots + a_(i n) c_n = b_i,
  dots.v,
  a_(j 1) c_1 + dots + a_(j n) c_n = b_j,
  dots.v,
  a_(m 1) c_1 + dots + a_(m n) c_n = b_m
)
$

+ ברור שהחלפת סדר המשוואות אינה משנה את נכונותן, ולכן $(c_1, c_2, dots, c_n)$ פתרון גם לאחריה.
+ אם נכפול את המשוואה ה-$i$-ית ב-$lambda !=0$, יתר המשוואות לא משתנות, קיומן לא משתנה והמשוואה החדשה מתקיימת.
+ אם נוסיף למשוואה ה-$i$-ית את מכפלת המשוואה ה-$j$-ית ב-$lambda$, כל יתר המשוואות יתקיימו כמקודם והמשוואה החדשה מתקיימת. 
#QED

= מטריצה
מטריצה מגודל $m xx n$ מעל השדה $FF$ היא טבלה שבה $m$ שורות ו-$n$ עמודות, וכל רכיביה סקלרים מ-$FF$:
$ mat(
  a_11, a_12, dots, a_(1 n);
  a_21, a_22, dots, a_(2 n);
  dots.v;
  a_(m 1), a_(m 2), dots, a_(m n);
) = mat(-, R_1, -; -, R_2, -;,dots.v,; -, R_m, -;) = mat(|, |, dots, |; C_1, C_2, dots, C_m; |, |, dots, |) $

כאן, $R_1, dots, R_m in FF^n$ (השורות) ו-$C_1, dots, C_n in FF^m$ (העמודות).

נסמן ב-$M_(m xx n) (FF)$ את אוסף כל המטריצות מגודל $m xx n$ מעל $FF$ ואם $m = n$ נסמן $M_n (FF)$ ונאמר שהמטריצה ריבועית.
אם $A in M_(m xx n) (FF)$ נסמן ב-$A_(i j)$ את האיבר שבשורה ה-$i$ ובעמודה ה-$j$-ית במטריצה $A$.

== דוגמאות למטריצות
$ mat(2,3,1;2,9,8) in M_(2 xx 3) (RR) \
  mat(1,8; 0,1; 2,0; 0,1) in M_(4 xx 2) (QQ) \
  mat(1;7;1;2) in M_(4 xx 1) (ZZ slash 11 ZZ) \
  mat(1,7,1,2) in M_(1 xx 4) (ZZ slash 11 ZZ) 
$

#pagebreak()
== הגדרה
בהינתן מע׳ משוואות לינאריות מעל השדה $FF$: 
$
cases(a_11 x_1 + a_12 x_2 + dots + a_(1n) x_n = b_1,
  dots.v,
  a_(m 1) x_1 + a_(m 2) x_2 + dots + a_(m n) x_n = b_m)
$
נבנה מטריצה מגודל $m xx (n+1)$ מעל השדה $FF$ שבה כל שורה מייצגת משוואה כל עמודה מייצגת נעלם, והמקדמים החופשיים מיוצגים בעמודה נוספת:
$
  mat(
    a_11, a_12, dots, a_(1 n), b_1;
    a_21, a_22, dots, a_(2 n), b_2;
    dots.v,,,,dots.v;
    a_(m 1), a_(m 2), dots, a_(m n), b_m
    ; augment: #4
  ) in M_(m xx (n+1)) (FF)
$

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

=== הגדרה
נוכל לבצע *פעולות שורה אלמנטריות* על מטריצה. פעולות אלה הן:
+ החלפה בין שתי שורות $R_i <-> R_j$.
+ מכפלת שורה בסקלר שונה מאפס $R_i-> lambda dot R_i, lambda !=0$
+ הוספת מכפלה בסקלר של שורה אחרת לאחרת $R_i -> R_i+ lambda dot R_j$

זוג מטריצות נקראות *שקולות שורה* אם ניתן לעבור מאחת לשניה על ידי מספר סופי של פעולות שורה אלמנטריות, ונסמן $A tilde B$.

== שקילות שורה של מטריצות היא יחס שקילות
=== הוכחה
- *רפלקסיביות*: אם נבצע 0 פעולות שורה אלמנטריות, נקבל שכל מטריצה שקולת שורה לעצמה.
- *סימטריות*: אם ניתן להגיע מ-$A$ ל-$B$ על ידי סדרה סופית של פעולות שורה אלמנטריות, נבצע את אותן פעולות אך הופכיות ובסדר הפוך כדי להגיע מ-$B$ ל-$A$. 
- *טרנזיטיביות*: אם אפשר להגיע מ-$A$ ל-$B$ על ידי סדרה סופית של פעולות שורה אלמנטריות, וכך גם מ-$B$ ל-$C$, אז אם נבצע את שתי סדרות הפעולות ברצף נגיע מ-$A$ ל-$C$ כנדרש.
#QED

=== מסקנה: מטריצות שקולות שורה מייצגות מערכות משוואות שקולות.

== הגדרה
- שורה במטריצה שבה יש רק אפסים נקראת *שורת אפסים*.
- האיבר הראשון שאינו אפס בשורה שאינה שורת אפסים נקרא *איבר פותח (מוביל)*.
- מטריצה נקראת *מדורגת* אם:
  + כל איבר פותח נמצא מימין לאיברים הפותחים בשורות שמעליו.
  + שורות אפסים (אם קיימות) בתחתית המטריצה.
- מטריצה מדורגת נקראת *מדורגת קנונית* אם:
  + כל איבר פותח הוא $.1$
  + בעמודה שבה מופיע איבר פותח, יתר הרכיבים הם אפסים.
- משתנה שמיוצג בעמודה שבה איבר פותח במטריצה מדורגת נקרא *משתנה תלוי (קשור)*. אחרת, נאמר שהמשתנה *חופשי*.

#pagebreak()

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

=== דוגמה
$ cases(x+2y+3z=4, 5x+6y+7z=8, 9x+10y+a z = b), a,b in RR $
נבנה את מטריצת המקדמים המורחבת של המערכת, ונבצע פעולות שורה אלמנטריות עד שנגיע למטריצה מדורגת קנונית:

$ mat(1, 2, 3, 4; 5,6,7,8; 9,10,a,b; augment: #3) $

+ בעזרת החלפת שורות נוודא שהאיבר בעמודה והשורה הראשונות אינו אפס. אם כל העמודה הראשונה היא אפסים, נתעלם ממנה.
+ בעזרת מכפלה מתאימה של השורה הראשונה נוודא שהאיבר הפותח בה הוא $1$.
+ נאפס את יתר רכיבי העמודה בעזרת הוספה של מכפלות מתאימות של השורה הראשונה באחרות (לאפס את כל העמודה, לא רק כלפי מטה).

$ mat(1, 2, 3, 4; 5,6,7,8; 9,10,a,b; augment: #3) 
arrow.long.r^(R_2->R_2 -5 R_1)_(R_3 -> R_3 - 9 R_1) 
mat(1, 2, 3, 4; 0,-4,-8,-12; 0,-8,a-27,b-36; augment: #3) $

4. נתעלם מהשורה והעמודה הראשונות ונחזור על פעולות (1) - (4).

$ mat(1, 2, 3, 4; 0,-4,-8,-12; 0,-8,a-27,b-36; augment: #3) arrow.long.r^(R_2->-1/4 R_2) mat(1, 2, 3, 4; 0,1,2,3; 0,-8,a-27,b-36; augment: #3) -> $

$ -> mat(1, 2, 3, 4; 0,1,2,3; 0,-8,a-27,b-36; augment: #3) arrow.long.r^(R_1->R_1 - 2 R_2)_(R_3 -> R_3 + 8R_2) mat(1, 0, -1, -2; 0,1,2,3; 0,0,a-11,b-12; augment: #3) $

אם $a=11$ המטריצה המצומצמת מדורגת קנונית במקרה הזה, והיא מייצגת את המערכת השקולה:
$ cases(x-z=-2, y+2z=3, 0 = b-12) $
כעת עבור $b!=12$, המשוואה האחרונה תהיה $0=b-12 != 0$ וקיבלנו סתירה, ולמערכת אין אף פתרון במקרה הזה.

ואם $b=12$ נבודד את המשתנים התלויים $x,y$ לפי המשתנה החופשי שהוא $z$, ונקבל: $ cases(x=z-2, y=3-2z) => S = {mat(z-2;3-2z;z) | z in RR} $

אם $a!=11$, נמשיך:
$ 
  arrow.long.r^(R_3->(a-11)^(-1)dot R_3) mat(1,0,-1,-2;0,1,2,3;0,0,1,frac(b-12, a-11); augment: #3) arrow.long.r^(R_1->R_1 + R_3)_(R_2->R_2-2R_3) mat(1,0,0,-2+frac(b-12, a-11); 0,1,0,3-2 dot frac(b-12, a-11); 0,0,1, frac(b-12, a-11); augment: #3)
$

המטריצה המצומצמת מדורגת קנונית ומייצגת את המע׳ השקולה:
$ cases(x=-2+frac(b-12, a-11), y=3-2 dot frac(b-12, a-11), z=frac(b-12, a-11)) $
למערכת פתרון *יחיד* כי כל המשתנים *תלויים*.

== תוספת למשפט: כל מטריצה שקולת שורה למטריצה מדורגת קנונית *יחידה*