#import "/template.typ": *
#import "@preview/colorful-boxes:1.2.0": *

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

// #include "/utils/toc.typ"
// #pagebreak()

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

= בסיסים - המשך

== תזכורת

יהי $V$ מ״ו מעל השדה $F$ ותהי $A subset V$ קבוצה.

- נאמר ש-$A$ *פורשת* את $V$ אם $span_F (A)=V$, כלומר כל וקטור ב-$V$ ניתן להבעה כצ״ל של איברי $A$.
- נאמר ש-$A$ *בת״ל* אם הצירוף הלינארי #underline[היחידי] של איברי $A$ שמתאפס הוא הטריוויאלי.
- נאמר ש-$A$ *בסיס* של $V$ אם כל וקטור ניתן להבעה כצ״ל של איברי $A$ בצורה #underline[יחידה].
- נאמר ש-$V$ *נוצר סופית* אם קיימת קבוצה סופית שפורשת את $V$.

== טענות, משפטים ומסקנות

=== (טענה) אם במ״ו $V$ ישנה קבוצה פורשת בת $m$ וקטורים, כל קבוצה שבה יותר מ-$m$ וקטורים תהיה ת״ל

=== (משפט) יהי $V$ מ״ו מעל $F$ ותהי $B subset V$ קבוצה. אזי, $B$ בסיס של $V$ אם״ם $B$ פורשת ובת״ל
==== הוכחה
- $arrow.double.l$: נניח ש-$B$ בסיס של $V$. נסיק ש-$B$ פורשת את $V$ שהרי כל וקטור ב-$V$ ניתן להביע כצ״ל של איברי $B$. כמו-כן, כל וקטור ב-$V$ ניתן להביע בצורה יחידה כצ״ל של איברי $B$, ובפרט גם את וקטור האפס נוכל להביע רק כצירוף הטריוויאלי. כלומר, $B$ בת״ל.
- $arrow.double.r$: נניח ש-$B$ פורשת ובת״ל. $B$ פורשת ולכן כל וקטור ב-$V$ ניתן להביע כצ״ל של איברי $B$. בכדי להוכיח את היחידות נתבונן בזוג צ״ל ששווים זה לזה:
  $
    sum_(k=1)^n alpha_k b_k = sum_(k=1)^n beta_k b_k \
    alpha_1, dots, alpha_n, beta_1, dots, beta_n in F and b_1, dots, b_n in B
  $

  נעביר אגפים:
  $
    sum_(k=1)^n (alpha_k - beta_k) b_k = 0
  $
  קיבלנו צ״ל של איברי $B$ שמתאפס, $B$ בת״ל ולכן נסיק: $alpha_1 - beta_1 = alpha_2 - beta_2 = dots.h.c = alpha_n - beta_n $, כלומר $cases(alpha_1=beta_1, dots.v, alpha_n = beta_n)$. #QED

=== (מסקנה) אם $V$ מ״ו נוצר סופית ו-$B_1, B_2$ זוג בסיסים אז ב-$B_1, B_2$ מספר איברים זהה

==== הוכחה
$B_1$ בסיס ולכן פורש את $V$. $B_2$ בסיס ולכן בת״ל. נראה כי מספר האיברים ב-$<= B1$ מספר האיברים ב-$B_2$. מצד שני, $B_2$ בסיס ולכן פורש את $V$, $B_1$ בסיס ולכן בת״ל. נראה כי מספר האיברים ב-$<= B_2$ מספר האיברים ב-$B_1$. לכן מספר האיברים ב-$B_1$ וב-$B_2$ זהה. #QED

=== (טענה) אם $V$ מ״ו מעל השדה $F$ ו-$A={u_1, u_2, dots, u_n}$ קב׳ ת״ל אז אחד מאיברי $A$ הוא צ״ל של האחרים <s1>
==== הוכחה
הקב׳ ת״ל ולכן קיים צ״ל לא טריוויאלי שמתאפס $sum_(k=1)^n lambda_k u_k = 0$. בה״כ נניח $lambda_n !=0$ ונציג:
$sum_(k=1)^(n-1) lambda_k u_k = -lambda_n u_n$.

כלומר, $u_n = sum_(k=1)^(n-1) = (-lambda_n)^(-1) lambda_k u_k$, ונסיק: $u_n in span_F {u_1, dots, u_(n-1)}$. #QED

=== (טענה) יהי $V$ מ״ו מעל $F$ ותהי $A={u_1, u_2, dots, u_n}$ קבוצה בת״ל, ויהי גם $w in V$. אזי $A uu {w}$ בת״ל אם״ם $w in.not span_F (A)$

==== הוכחה
- $arrow.double.l$: נניח $A uu {w}$ בת״ל. אם $w in span_F (A)$ אז $w=sum_(k=1)^n lambda_k u_k$ ונקבל $sum_(k=1)^n lambda_k u_k + (-1) dot w = 0$. נסיק ש-$A uu {w}$ ת״ל בסתירה להנחה.
- $arrow.double.r$: נניח $w in.not span_F (A)$. נתבונן בצ״ל שמתאפס: $sum_(k=1)^n lambda_k u_k + alpha w = 0$.

  אם $alpha != 0$ נציג: $w = sum_(k=1)^n (-alpha)^(-1) lambda_k u_k$ בסתירה לכך ש-$w in.not span_F (A)$. כלומר $alpha=0$ ונקבל $sum_(k=1)^n lambda_k u_k$ צ״ל לא טריוויאלי שמתאפס בסתירה לכך ש-$A$ בת״ל.

=== (מסקנה) יהי $V$ מ״ו נוצר סופית מעל $F$. אזי, בסיס של $V$  הוא קב׳ בת״ל מקסימלית (1) וקב׳ פורשת מינימלית (2)

==== הוכחה
+ יהי $B$ בסיס של $V$. אזי $B$ בת״ל ו-$span_F (B) = V$ ולכל $v in V$ מתקיים $v in span_F (B)$. כלומר $B uu {v}$ ת״ל.
+ יהי $B$ בסיס של $V$. אזי $B$ פורש את $V$ ובת״ל. אם $b in B$ ונתבונן בקב׳ $B without {b}$. קב׳ זו כבר אינה פורשת את $V$, הרי ש-$b in.not span (B without {b})$, שהרי אם $b in span(B without {b})$ בהכרח $B=(B without {b}) uu {b}$ ת״ל, בסתירה. #QED

=== (מסקנה) יהי $V$ מ״ו נוצר סופית מעל $F$. אזי, (1) כל קב׳ בת״ל מקסימלית היא בסיס, (2) כל קב׳ פורשת מינימלית היא בסיס

==== הוכחה
+ קב׳ בת״ל מקסימלית היא בפרט בת״ל. ואם $B$ קב׳ כזו שאינה פורשת, אז קיים $v in.not span(B)$ אז $B uu {v}$ בת״ל בסתירה למקסימליות.
+ אם $B$ פורשת מינימלית אז בפרט $B$ פורשת את $V$. אם $B$ אינה בת״ל אז לפי טענה @s1 קיים $b in B$ כך ש-$b in span(B without {b})$ ונקבל $span(B without {b})=span(B)=V$ בסתירה למינימליות של $B$.

== מימד
נזכור שהגדרנו את המימד של מ״ו $V$ כעוצמת הבסיס שלו: $dim(V) = abs(B)$ ($B$ בסיס של $V$).

=== (טענה) יהי $V$ מ״ו נוצר סופית מעל $F$ עם $dim(V)=n$. (1) כל קב׳ בת״ל בת $n$ איברים היא בסיס. (2) כל קב׳ פורשת בת $n$ איברים היא בסיס.
==== הוכחה
+ בקבוצה בת״ל מס׳ האיברים $>=$ ממס׳ האיברים בקבוצה פורשת. ולכן קב׳ בת״ל שבה $dim(V)$ איברים היא קב׳ בת״ל מקסימלית, לכן בסיס.
+ בקבוצה פורשת מס׳ האיברים $<=$ ממס׳ האיברים בקבוצה בת״ל. ולכן קב׳ פורשת שבה $dim(V)$ איברים היא פורשת מינימלית, לכן בסיס.
#QED

=== (טענה) יהי $V$ מ״ו נוצר סופית ותהי $H=(u_1, dots, u_m)$ קב׳ בת״ל. אזי ניתן להרחיב את $H$ לבסיס של $V$, כלומר קיים בסיס $B$ של $V$ כך ש-$H seq B$ <s2>
==== הוכחה
באינדוקציה על $dim(V) - m$. נשים לב שהיות ו-$H$ בת״ל בהכרח מס׳ האיברים ב-$H$ $>=$ מס׳ האיברים בקב׳ פורשת.

- *בסיס האינדוקציה* - $dim(V)-m=0$

  במקרה הזה, ישנה קב׳ בת״ל מקסימלית (בת $dim(V)$ איברים) והיא בהכרח בסיס.

- *צעד האינדוקציה* - $dim(V)-m>=1$

  $H$ בהכרח אינה פורשת את $V$ הרי שאז היינו מקבלים קב׳ פורשת שבה פחות מ-$dim(V)$ איברים. כלומר קיים $v in.not span(H)$ ואז $H uu {v}$ בת״ל בת $m+1$ איברים. נפעיל עליה את הנחת האינדוקציה כאשר $dim(V)-(m+1)$ ונקבל שניתן להרחיב את $H uu {v}$ לבסיס.

#QED

=== (טענה) יהי $V$ מ״ו נוצר סופית מעל $F$, ותהי $H=(u_1, dots, u_m)$ קב׳ פורשת. אזי ניתן לצמצם את $H$ לבסיס של $V$, כלומר קיים ל-$V$ בסיס $B$ כך ש-$B seq H$
==== הוכחה
באינדוקציה על $m-dim(V)$.

- *בסיס האינדוקציה* - $m-dim(V)=0$

  כאן $H$ קב׳ פורשת מינימלית שבה $dim(V)$ איברים, ולכן היא בהכרח בסיס.

- *צעד האינדוקציה*

  כאשר $H$ קב׳ שבה יותר מ-$dim(V)$ איברים, היא בהכרח ת״ל כי היא מכילה יותר איברים מקב׳ פורשת. מ-@s2 קיים איבר ב-$H$ שהוא צ״ל של האחרים, בה״כ נניח שזהו $u_m$. נקבל $V= span{u_1, dots, u_m} = span {u_1, dots, u_m}$ כאשר $u_m = sum_(k=1)^(m-1) lambda_k u_k$. קיבלנו קב׳ בת $m-1$ איברים ומהנחת האינדוקציה ניתן לצמצם אותה לבסיס של $V$. #QED
