[[88-112 לינארית 1 תיכוניסטים קיץ תשעא/מערך תרגול|חזרה למערכי התרגול]]
'''תרגיל.'''
האם הפולינומים <math>x^3-x+1,2x^2+x-1,x^3-1</math> תלויים לינארית?==משפט המימדים==[[משפט המימדים]]:
יהי <math>V</math> מ"ו ויהיו <math>U,W\leq V</math> תתי מרחבים. אזי
'''פתרון:'''<math>dim(U+W)=dim(U)+dim(W)-dim(U\cap W)</math>
====סקיצה של ההוכחה - לא מפחיד כמו שנהוג לחשוב====#ניקח בסיס לU חיתוך W. נסמן אותו ב<math>a\{v_1,...,v_k\}</math>#נשלים אותו לבסיס לU. נסמן <math>\{v_1,...,v_k,u_1,...,u_m\}</math>#נשלים את הבסיס לחיתוך גם לבסיס לW. נסמן <math>\{v_1,...,v_k,w_1,...,w_p\}</math>#'''נוכיח''' (x^3-xוזה עיקר העבודה) שהקבוצה <math>\{v_1,...,v_k,u_1,...,u_m,w_1,...,w_p\}</math> הינה בסיס לU+1W:##נראה כי כל וקטור מהצורה u+w ניתן להצגה כצירוף לינארי של איברים אלה (זה ברור)##נראה כי הקבוצה הזו בת"ל, אחרת וקטורים שהנחנו שאינם בחיתוך יהיו חייבים להיות בחיתוך בסתירה#המשל נובע בקלות מספירת הוקטורים בבסיסים שכן <math>dim(U+bW) = k+m+p=(2x^2k+x-1m)+c(x^3-1k+p)=0-k</math> אם"ם
===תרגיל 8.3===יהא V מ"ו ממימד 5, ויהיו U ממימד 3 ו-W ממימד 4 תתי מרחבים של V. מהן האפשרויות עבור <math>dim(a+cU\cap W)x^3+2bx^2+(b-a)x+(a-b-c)=0</math> אם"ם? הוכח!
====פתרון====ראשית, <math>U+W\subseteq V</math> ולכן <math>dim(a=-cU+W)\andleq dim(2b=0V)=5</math>. אבל לפי משפט המימדים מתקיים <math>5\andgeq dim(bU+W)=adim(U)\and+dim(aW)-dim(U\cap W)=b3+c4-dim(U\cap W)</math> אם"ם.
<math>a=b=c=d=0</math>
ביחד מקבלים ש <math>dim(U\cap W)\geq 2</math>. מצד שני, החיתוך מוכל גם בU וגם בW ולכן המימד שלו קטן שווה מהמימדים שלהם, ובפרט מהקטן מהם. לכן <math>dim(U\cap W)\leq 3</math>.
אם כן, הצירוף הלינארי היחיד שמתאפס הינו הטריוויאלי ולכן הפולינומים בת"ל.
==קואורדינטות==משפט: יהא V מסה"ו מעל שדה F, יהי <math>B=\{v_1כ האפשרויות למימד הן 2,3...,v_n\}</math> בסיס ל-V ויהי <math>v\in V</math> וקטור. אזי ל-v יש הצגה יחידה כצירוף לינארי לפי הבסיס B. כלומר, אם מתקיים <math>v=a_1v_1+...+a_nv_n=b_1v_1+...+b_nv_n</math> אזי בהכרח <math>\forall i:a_i=b_i</math>. (קל להוכיח את זה על ידי חיסור הצד הימני של המשוואה מהצד השמאלי, מקבלים צירוף לינארי שמתאפס עם מקדמים <math>a_i-b_i</math>למצוא דוגמאות המוכיחות שאפשרויות אלה אכן מתקבלות מתישהו.)
הגדרה: יהיו ===תרגיל 8.5===יהא <math>V</math> מ"ו ממימד <math>n</math>,B וv כמו במשפט. אזי '''וקטור הקואורדינטות''' של v לפי בסיס Bויהיו <math>U, מסומן W</math>[v]_B\in\mathbb{F}^תתי מרחבים כך ש <math>dimU=n-1</math> מוגדר להיות ו-<math>[v]_B=\begin{pmatrix}a_1 \\ a_2 \\ \vdots \\ a_n\end{pmatrix}W</math> כאשר אינו מוכל בU. הוכח כי <math>v=a_1v_1W+...+a_nv_nU=V</math> ההצגה הלינארית היחידה הקיימת לפי המשפט.
====הוכחה====
נוכיח בעזרת משפט המימדים ש <math>dim(U+W)=dimV</math> ואז המשל נובע (כי תת מרחב שמוכל בתת מרחב אחר מאותו מימד).
<math>dim(U+W)=dimU+dimW-dim(U\cap W)</math>. מכיוון שW אינו מוכל בU החיתוך בינהם שונה מW. ולכן <math>dim(U\cap W)<dimW </math> ולכן <math>dimW-dim(U\cap W)\geq 1</math>. ביחד מקבלים <math>dim(U+W)=n-1 + dimW -dim(U\cap W)\geq n-1+1=n=dimV</math>. משל.
===תרגיל===
יהיו W1,W2 ת"מ של מ"ו V כך ש <math>dim(W_1+W_2)=\dim (W_1\cap W_2) +1</math>. הוכיחו כי <math>\{W_1,W_2\}=\{W_1+W_2,W_1\cap W_2\}</math>
פתרון:
מתקיים לפי נתון כי<math>\dim (W_1\cap W_2)\leq \dim W_1, \dim W_2 \leq dim(W_1+W_2)=\dim (W_1\cap W_2) +1</math>
ולכן לכל i מתקיים כי <math>\dim W_i </math> שווה למימד הסכום או למימד החיתוך. כיוון שיש הכלה <math>W_1\cap W_2\subseteq W_1,W_2\subseteq W_1+W_2 </math> אז יתקיים שיוויון.
כעת לא ייתכן כי <math>W_1,W_2</math> שניהם שווים כי אז מימד הסכום היה שווה למימד החיתוך.
=== תרגיל ===
יהא <math>V</math> מ"ו מימד אי זוגי <math>\dim V=2n+1</math> ויהיו <math>W_{1},W_{2},U_{1},U_{2}</math> ת"מ המקיימים כי <math>W_{1}+W_{2}=V=U_{1}+U_{2}</math> הוכיחו <math>\left(W_{1}\cap U_{1}\right)+\left(W_{1}\cap U_{2}\right)+\left(W_{2}\cap U_{1}\right)+\left(W_{2}\cap U_{2}\right)\neq\left\{ 0\right\}</math>
==קואורדינטות==
משפט: יהא <math>V</math> מ"ו מעל שדה <math>\mathbb{F}</math>, יהי <math>B=\{v_1,...,v_n\}</math> בסיס ל-<math>V</math> ויהי <math>v\in V</math> וקטור.
ראינו ש-<math>v</math> ניתן להצגה יחידה כצ"ל של <math>B</math> וההצגה שלו לפי הבסיס הוא וקטור שמורכב מהמקדמים של הצ"ל.
באופן פורמאלי, ההצגה של <math>v</math> לפי בסיס <math>B</math> הוא '''וקטור הקואורדינטות''' המסומן <math>[v]_B\in\mathbb{F}^n</math> ומוגדר להיות <math>[v]_B=\begin{pmatrix}a_1 \\ a_2 \\ \vdots \\ a_n\end{pmatrix}</math> כאשר <math>v=a_1v_1+...+a_nv_n</math>.
'''חשוב לזכור''' <math>[v]_B=\begin{pmatrix}a_1 \\ a_2 \\ \vdots \\ a_n\end{pmatrix}</math> אם"ם <math>v=a_1v_1+...+a_nv_n</math>
תרגיל קל אבל חשוב הוא להראות שלכל : הוכח כי לכל בסיס <math>B </math> מתקיים ש <math>v=0</math> אם"ם <math>[v]_B=0</math>. הוכחה: ישירות מההגדרה. <math>B</math> בת"ל ולכן הצ"ל היחידי שמתאפס זהו הצ"ל הטריאלי. בהכללה: <math>[v_1]_B=[v_2]_B</math> אמ"מ <math>v_1=v_2</math>
אנו רואים שאין זה קל למצוא את הקואורדינטות לפי בסיס כלשהו שאינו הסטנדרטי.
'''=== תרגיל.'''===
יהא V מ"ו ויהי B בסיס לו. יהיו <math>u_1,...,u_k\in V</math> וקטורים כלשהם. הוכח:*מ"ו מעל <math>u_1,...,u_k\mathbb{F}</math> בת"ל אם"ם ויהי <math>[u_1]_BB=\{v_1,...\dots ,[u_k]_Bv_n\}</math> בת"ל*בסיס לו. יהיו <math>w\in span\{u_1,...,u_k\}in V</math> אם"ם וקטורים כלשהם וסקלארים <math>[w]_B\alpha_i,\dots ,\alpha_k \in span\mathbb{[u_1]_B,...,[u_k]_B\F}</math>. הוכח:
נוכיח תרגיל זה בהמשך, לאחר שנלמד על העתקות לינאריות. כעת נניח שהוא נכון ונתרכז בכלי החישובי המשמעותי שקיבלנו; כל בדיקה/חישוב של תלות לינארית או פרישה בכל מרחב וקטורי (מטריצות, פולינומים, פונקציות) יכול בעצם להעשות במרחב הוקטורי המוכר והנוח <math>\mathbbsum_{Fi=1}^nk\alpha_i[u_i]_B =[\sum_{i=1}^k\alpha_iu_i]_B</math>.
הוכחה:
מ"ל את הטענה <math>[u_1]_B+[u_2]_B =[u_1+u_2]_B</math> ואת הטענה <math>\alpha[u_1]_B=[\alpha u_1]_B</math> (ואז המעבר לצ"ל כללי נעשה ע"י אינדוקציה)
נסמן <math>u_1=a_1v_1+...+a_nv_n, u_2=b_1v_1+...+b_nv_n</math> אזי <math>u_1+u_2=(a_1+b_1)v_1+...+(a_n+b_n)v_n</math> ומתקיים
<math>[u_1]_B+[u_2]_B =\begin{pmatrix}a_1 \\ a_2 \\ \vdots \\ a_n\end{pmatrix} + \begin{pmatrix}b_1 \\ b_2 \\ \vdots \\ b_n\end{pmatrix} =
\begin{pmatrix}a_1+b_1 \\ a_2+b_2 \\ \vdots \\ a_n+b_n\end{pmatrix}
[u_1+u_2]_B</math>
בנוסף <math>\alpha u_1=\alpha a_1v_1+...+\alpha a_nv_n</math> ומתקיים
<math>\alpha[u_1]_B= \alpha \begin{pmatrix}a_1 \\ a_2 \\ \vdots \\ a_n\end{pmatrix}=
\begin{pmatrix} \alpha_1 \\ \alpha a_2 \\ \vdots \\\alpha a_n\end{pmatrix} =
[\alpha u_1]_B</math>
מש"ל
'''מסקנה:'''
2. <math>u_1,...,u_k</math> בת"ל אם"ם <math>[u_1]_B,...,[u_k]_B</math> בת"ל
3. <math>w\in span\{u_1,...,u_k\}</math> אם"ם <math>[w]_B\in span\{[u_1]_B,...,[u_k]_B\}</math>
הוכחה:
2. <math>u_1,...,u_k</math> בת"ל
אמ"מ
<math>\sum_{i=1}^k\alpha_iu_i=0 \Rightarrow \forall i \; \alpha_i =0</math>
אמ"מ
<math>[\sum_{i=1}^k\alpha_iu_i]_B=[0]_B=0 \Rightarrow \forall i \; \alpha_i =0</math>
אמ"מ
<math>\sum_{i=1}^k\alpha_i[u_i]_B=0 \Rightarrow \forall i \; \alpha_i =0</math>
אמ"מ
<math>[u_1]_B,...,[u_k]_B</math> בת"ל
3. ברעיון דומה
מה בעצם המסקנה אומרת? שכל בדיקה/חישוב של תלות לינארית או פרישה '''בכל''' מרחב וקטורי (מטריצות, פולינומים, פונקציות) יכול בעצם להעשות במרחב הוקטורי המוכר והנוח <math>\mathbb{F}^n</math>.
ועוד הגדרה לפני ההמשך, עד כה דיברנו "רק" על ייצוג של וקטורים לפי בסיס. אפשר להכליל בפשטות לכל המרחב הוקטורי. הנה ההגדרה:
'''הגדרה''' :
יהא <math>V</math> מ"ו (או תת מרחב) ויהי <math>B</math> בסיס לו. אזי מרחב הקורדיאנטות (של <math>V</math> לפי בסיס <math>B</math>) הוא
<math>[V]_B = \{[v]_B \; | \; v\in V\}</math>
'''הערה :''' יהא <math>V</math> מ"ו, <math>W_1,W_2\leq V</math> תתי מרחבים ו <math>B</math> בסיס. אזי
#<math>[W_1 \cap W_2]_B = [W_1]_B \cap [W_2]_B</math>
#<math>[W_1 + W_2]_B = [W_1]_B + [W_2]_B</math>
== דוגמאות ואלגוריתמים==
=== חיתוך תת מרחבים ===
===='''תרגיל 7.31''' ====
נגדיר שני תתי מרחבים של <math>\mathbb{R}_3[x]</math>:
<math>V=\{p(x)|p(2)=0\}</math>, ו <math>U=\{p(x)|p(1)=0\}</math>
מצא את המימד של חיתוך המרחבים.
'''פתרון.'''
בתרגיל זה נשתמש בשיטה נפוצה ביותר. אנו מעוניינים לתאר את המרחבים הוקטוריים באופן קל יותר לעבודה מאשר התיאור לעיל; לכן ננסה לתאר את תתי המרחבים הללו כמרחבי פתרון של מערכת הומוגנית (אחת מהדרכים להצגת תת מרחב מתירגול קודם). המשתנים שלנו במערכת המשוואות יהיו '''המקדמים''' של הפולינומים.
נביט ב <math>V</math>. זהו אוסף כל הפולינומים ש2 הוא שורש שלהם. יהי פולינום כללי <math>p(x)=a+bx+cx^2+dx^3</math>, הוא שייך ל<math>V</math> אם"ם מקדמיו מקיימים את המשוואה הלינארית: <math>a+2b+4c+8d=0</math>. לכן <math>V=\{a+bx+cx^2+dx^3|a+2b+4c+8d=0\}</math> אם נעבוד עם הבסיס הסטנדרטי <math>S</math> נקבל כי
<math>[V]_S=\{\begin{pmatrix}a\\ b\\ c\\ d \end{pmatrix}\in \mathbb{R}^4 |a+2b+4c+8d=0\}</math>
באופן דומה הפולינום שייך ל<math>U</math> אם"ם מקדמיו מקיימים את המשוואה הלינארית <math>0=a+b+c+d</math>. ומרחב הקורדינאטות הוא
<math>[U]_S=\{\begin{pmatrix}a\\ b\\ c\\ d \end{pmatrix}\in \mathbb{R}^4 |a+b+c+d=0\}</math>
את החיתוך <math>[V]_S\cap[U]_S</math> קל למצוא! ראינו איך עושים זאת זה פשוט שווה ל
<math>\{\begin{pmatrix}a\\ b\\ c\\ d \end{pmatrix}\in \mathbb{R}^4 |
\begin{pmatrix} 1 & 2 & 4 & 8 \\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix}a\\ b\\ c\\ d \end{pmatrix} = 0 \}</math>
נדרג את המטריצה ונמצא את הפתרון:
<math>\begin{pmatrix} 1 & 2 & 4 & 8 \\ 1 & 1 & 1 & 1 \end{pmatrix} \to \begin{pmatrix} 1 & 2 & 4 & 8 \\ 0 & -1 & -3 & -7 \end{pmatrix} \to
\\
\begin{pmatrix} 1 & 0 & -2 & -6 \\ 0 & -1 & -3 & -7 \end{pmatrix} \to \begin{pmatrix} 1 & 0 & -2 & -6 \\ 0 & 1 & 3 & 7 \end{pmatrix}
</math>
ולכן הפתרון הכללי הוא מהצורה <math>(2t+6s,-3t-7s,t,s)</math>, ולכן הבסיס הינו <math>(2,-3,1,0),(6,-7,0,1)</math>.
נחזור לצורה הפולינומית לקבל את התשובה הסופית:
<math>U\cap V = sapn \{v_1, v_2 \; | \; [v_1]_s = (2,-3,1,0), [v_2]_s = (6,-7,0,1) \} = span\{2-3x+x^2,6-7x+x^3\}</math>
====אלגוריתם למציאת חיתוך בין שני תתי מרחבים U,W====
ישנן שתי שיטות לחשב את החיתוך, נתחיל בראשונה (שביצענו הרגע, למעשה):
# החלף את <math>U,W</math> במרחב הקורדינאטות שלהם.
#מצא מערכת משוואות המתארת את <math>U</math> ומערכת משוואות המתארת את <math>W</math>
#פתור מערכת אחת המכילה את כל המשוואות משתי המערכות וקבל את החיתוך
# חזור ל <math>U,W</math> המקוריים.
שיטה שנייה:
# החלף את <math>U,W</math> במרחב הקורדינאטות שלהם.
# הצג את המרחבים כ <math>span(?)</math>
#כתוב צירוף לינארי כללי ב<math>U</math> וצירוף לינארי כללי ב<math>W</math>
#השווה את הצירופים ופתור מערכת משוואות על '''הסקלרים'''
#הצב את הסקלרים שקיבלת בצירוף הלינארי וקבל את החיתוך
# חזור ל <math>U,W</math> המקוריים.
=====תרגיל ======
מצא את החיתוך בין תתי המרחבים הבאים בשיטה השנייה לעיל.
<math>B=\operatorname{span}\left (\Big\{\begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix},\begin{pmatrix}0 & 1 \\ 0 & 0 \end{pmatrix},\begin{pmatrix}0 & 0 \\ 1 & 0\end{pmatrix}\Big\}\right ),
C=\operatorname{span}\left ( \Big\{\begin{pmatrix} 3 & 2 \\ 4 & -3\end{pmatrix},\begin{pmatrix}1 & 4 \\ -1 & 4 \end{pmatrix},\begin{pmatrix}1 & 1 \\ 1 & -2\end{pmatrix}\Big\}\right )</math>
'''פתרון.'''
(קחו נשימה עמוקה) יהיו סקלרים a,b,c,x,y,z, וקטור הוא בחיתוך אם"ם הוא צירוף לינארי של שתי הקבוצות הפורשות:
<math>a\begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix}+b\begin{pmatrix}0 & 1 \\ 0 & 0 \end{pmatrix}+c\begin{pmatrix}0 & 0 \\ 1 & 0\end{pmatrix}=x\begin{pmatrix} 3 & 2 \\ 4 & -3\end{pmatrix}+y\begin{pmatrix}1 & 4 \\ -1 & 4 \end{pmatrix}+z\begin{pmatrix}1 & 1 \\ 1 & -2\end{pmatrix}</math>
במרחב הקורדינאטות (עם הבסיס הסטדנדרטי <math>S</math>, נקבל את השיוון
<math>a\begin{pmatrix} 1 \\ 0 \\ 0 \\ -1\end{pmatrix}+b\begin{pmatrix}0 \\ 1 \\ 0 \\ 0 \end{pmatrix}+c\begin{pmatrix}0 \\0 \\ 1 \\ 0\end{pmatrix}=x\begin{pmatrix} 3 \\ 2 \\ 4 \\ -3\end{pmatrix}+y\begin{pmatrix}1 \\ 4 \\ -1 \\ 4 \end{pmatrix}+z\begin{pmatrix}1\\ 1 \\ 1 \\ -2\end{pmatrix}</math>
לכן מערכת המשוואות '''על הסקלרים''' הינה:
<math>\begin{pmatrix}
1 & 0 & 0 & -3 & -1 & -1 & | & 0 \\
0 & 1 & 0 & -2 & -4 & -1 & | & 0 \\
0 & 0 & 1 & -4 & 1 & -1 & | & 0 \\
-1 & 0 & 0 & 3 & -4 & 2 & | & 0 \\
\end{pmatrix}</math>
נדרג ונמצא את הפתרונות (שימו לב: מספיק למצוא רק את x,y,z או רק את a,b,c מכיוון שבהנתן צירוף לינארי של איברי C שנותן את החיתוך אין צורך להמשיך (כמו כן לגבי B).)
<math>\begin{pmatrix}
1 & 0 & 0 & -3 & -1 & -1 & | & 0 \\
0 & 1 & 0 & -2 & -4 & -1 & | & 0 \\
0 & 0 & 1 & -4 & 1 & -1 & | & 0 \\
0 & 0 & 0 & 0 & -5 & 1 & | & 0 \\
\end{pmatrix}</math>
במקרה זה קל יותר למצוא את x,y,z; המשתנים החופשיים הינם x,z ומתקיים z=5y. ולכן הצ"ל הכללי בחיתוך הינו:
<math>[B]_S \cap [C]_S=
\Big\{x\begin{pmatrix} 3 \\ 2 \\ 4 \\ -3\end{pmatrix}+y\begin{pmatrix}1 \\ 4 \\ -1 \\ 4 \end{pmatrix}+5y\begin{pmatrix}1 \\ 1 \\ 1 \\ -2\end{pmatrix}\Big\}= \\
\Big\{x\begin{pmatrix} 3 \\ 2 \\ 4 \\ -3\end{pmatrix}+y\begin{pmatrix}6 \\ 9 \\ 4 \\ -6 \end{pmatrix}\Big\}=
span\Big\{\begin{pmatrix} 3 \\ 2 \\ 4 \\-3\end{pmatrix},\begin{pmatrix}6 \\ 9 \\ 4 \\ -6 \end{pmatrix}\Big\}
</math>
אם נחזור למרחבים המקוריים נקבל כי
<math>B\cap C=span\Big\{\begin{pmatrix} 3 & 2 \\ 4 & -3\end{pmatrix},\begin{pmatrix}6 & 9 \\ 4 & -6 \end{pmatrix}\Big\}</math>
=== תלות לינארית ===
'''דוגמא.'''
האם הפולינומים <math>v_1=1+x^2,v_2=1-x,v_3=x+x^2</math> תלויים לינארית?
דבר ראשון, נעבור למרחב הקואורדינטות. מכיוון שבחירת הבסיס היא לשיקולנו, נבחר את הבסיס הסטנדרטי S של הפולינומים איתו קל לעבוד. מתקיים ש <math>[v_1]_S=(1,0,1),[v_2]_S=(1,-1,0),[v_3]_S=(0,1,1)</math>
הוכחנו בשיעור שעבר שוקטורים "רגילים" ת"ל אם"ם המטריצה שהם השורות שלה אינה הפיכה אם"ם הצורה המדורגת של המטריצה מכילה שורת אפסים. לכן, נשים את וקטורי הקואורדינטות בשורות מטריצה ונדרג.
<math>\begin{pmatrix}1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 1 & 1\end{pmatrix}\xrightarrow[]{R_3-R_1,R_3+R_2}\begin{pmatrix}1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 0 & 0\end{pmatrix}</math>
<math>R_3-R_1,R_3+R_2</math>
<math>\begin{pmatrix}1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 0 & 0\end{pmatrix}</math>לכן וקטורי הקואורדינטות תלויים לינארית ולכן הפולינומים עצמם תלויים לינארית.
לכן וקטורי הקואורדינטות תלויים לינארית ולכן הפולינומים עצמם תלויים לינארית. נסכם את התהליךדרך נוספת:נשים את הוקטורים בעמודה של מטריצה <math>A</math>. צ"ל של עמודות <math>A</math> זה פשוט <math>Ax</math>. ולכן הוקטורים בת"ל אמ"מ הפתרון היחידי למערכת <math>Ax=0</math> (צ"ל שמתאפס) הוא הפתרון הטריאלי (הצ"ל הטריאלי)
<math>\begin{pmatrix}1 & 1 & 0 \\ 0 & -1 & 1 \\ 1 & 0 & 1\end{pmatrix} \to \begin{pmatrix}1 & 1 & 0 \\ 0 & -1 & 1 \\ 0 & -1 & 1\end{pmatrix} \to \begin{pmatrix}1 & 1 & 0 \\ 0 & -1 & 1 \\ 0 & 0 & 0\end{pmatrix} \</math> קיבלנו שיש משתנים חופשיים ולכן יש פתרון לא טרויאלי ולכן הוקטורים תלויים לינארית! נסכם את התהליך: ====אלגוריתם לבדיקת תלות לינארית בין וקטורים====
#הפוך את הוקטורים לוקטורי קואורדינטות לפי הבסיס הסטנדרטי המתאים
#שים את וקטורי הקואורדינטות ב'''שורות''' מטריצה A
#אם הגעת לצורה מדורגת ללא שורת אפסים סימן שהוקטורים בלתי תלויים לינארית
ובדרך הנוספת
#הפוך את הוקטורים לוקטורי קואורדינטות לפי הבסיס הסטנדרטי המתאים
#שים את וקטורי הקואורדינטות ב'''עמודות''' מטריצה A
# בדוק אם יש פתרון לא טריאלי למערכת <math>Ax=0</math>
# אם יש אז הם תלויים ואם אין אז הם בת"ל
=== צירופים לינאריים ===
'''דוגמא.'''
האם המטריצה <math>v=\begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}</math> נפרשת על ידי היא צ"ל של המטריצות
<math>
v_1=\begin{pmatrix}1 & 1 \\ 0 & 0\end{pmatrix},
v_2=\begin{pmatrix}1 & 0 \\ 2 & 1\end{pmatrix},
v_3=\begin{pmatrix}2 & 2 \\ 10 & 10\end{pmatrix}
</math>? אם כן, הצג אותה כצירוף לינארי שלהן.
פתרון: נעבור דבר ראשון למרחב הקואורדינטות לפי הבסיס הסטנדרטי <math>S=\Big\{\begin{pmatrix}1 & 0 \\ 0 & 0\end{pmatrix},\begin{pmatrix}0 & 1 \\ 0 & 0\end{pmatrix},\begin{pmatrix}0 & 0 \\ 1 & 0\end{pmatrix},\begin{pmatrix}0 & 0 \\ 0 & 1\end{pmatrix}\Big\}</math>
למדנו בשיעור שעבר שוקטור b נפרש על ידי וקטורים מסויימים אם"ם קיים פתרון למערכת Ax=b כאשר A היא המטריצה שעמודותיה הם אותם וקטורים. הפתרון x הוא וקטורים וקטור הסקלרים מהצירוף הלינארי. לכן, אנו רוצים לדעת האם קיים פתרון למערכת ואם כן מהו:
<math>\begin{pmatrix}1 & 1 & 2\\ 1 & 0 & 2\\ 0 & 2 & 10\\ 0 & 1 & 10\end{pmatrix} x = \begin{pmatrix}1 \\ 2 \\ 3 \\4 \end{pmatrix}</math>
נסכם:
====אלגוריתם לחישוב צירוף לינארי====
#נתון וקטור b וקבוצת וקטורים. העבר את כולם לוקטורי קואורדינטות לפי הבסיס הסטנדרטי המתאים
#פתור את המערכת Ax=b כאשר '''עמודות''' A הינן וקטורי הקואורדינטות של קבוצת הוקטורים הפורשים
#אם קיים פתרון x אזי הוא מכיל את הסקלרים של הצירוף הלינארי בהתאם לסדר העמודות בA
==מרחבי המטריצותמטריצות מעבר בין בסיסים==תהי מטריצה <math>A\in\mathbb{F}^{m\times n}</math>. מגדירים שלושה מרחבים עיקריים:*'''מרחב השורות''' של A. זהו המרחב הנפרש על ידי שורות המטריצה A. נסמן <math>R(A)=span\{R_1(A)ראינו שקל מאד למצוא קואורדינטות לפי הבסיס הסטנדרטי,נשתמש בהנחה הזו בהמשך...אנו מעוניינים לדעת כיצד לחשב קואורדינטות לפי בסיס כלשהו,R_m(A)\}\subseteq\mathbb{F}^n</math>*'''מרחב העמודות''' של Aלאו דווקא סטנדרטי. זהו המרחב הנפרש על ידי עמודות המטריצה A. נסמן <math>C(A)=span\{C_1(A),...,C_n(A)\}\subseteq\mathbb{F}^m</math>*'''מרחב השורות''' של A. זהו מרחב הפתרונות של המערכת ההומוגנית Ax=0. נסמן <math>N(A)=\{x\in\mathbb{F}^n|Ax=0\}\subseteq\mathbb{F}^n</math>
'''משפט:''' לכל מטריצה יהא <math>A\in\mathbb{F}^{m\times n}V</math> מתקיים מ"ו ויהיו <math>\mathbb{E,F}</math> בסיסים לו. אזי '''קיימת''' מטריצה '''יחידה''' המסומנת <math>[I]^n=R(A)\oplus N(A)E_F</math>המקיימת את הפסוק הבא:
<math>\forall v\in V: [I]^E_F[v]_E=[v]_F</math>
הגדרה: '''דרגת''' המטריצה A שווה למספר השורות בצורה המדורגת שלה השונות מאפס. מסומן rankA
משפט: נסמן <math>rankAE=dimR(A)=dimC(A)=n-dimN(A)\{v_1,...,v_n\}</math>ו <math>F=\{w_1,... אלה שווים למספר המשתנים התלויים, ומימד מרחב האפס שווה למספר המשתנים החופשייםw_n\}</math>.אזי מתקיים ש<math>[I]^E_F</math> הינה המטריצה שעמודותיה הן <math>[v_i]_F</math>
'''דוגמא.'''
מצא בסיס למרחב האפס של המטריצה יהא <math>V=\mathbb{R}^2</math> ושני בסיסים <math>E=\{v_1=\begin{pmatrix}1 & 0 & 1 & 1 3\\ -2 & \end{pmatrix} , v_2 = \begin{pmatrix} 0\\ 1 & 1 & 2\end{pmatrix} \ }</math>ו<math>F=\{w_1= \begin{pmatrix} 1 & 1 & \\ 0 & \end{pmatrix},w_2 = \begin{pmatrix} 1\\ 1\end{pmatrix}\}</math>
דבר ראשון, נדרג קנונית נמצא את המטריצה לקבל <math>[I]^E_F</math>.
מתקיים כי <math>v_1 = \beginmathbf{pmatrix5}1 & 0 & 1 & 1w_1-\mathbf{2}w_2 \ 0 & 1 & \v_2 = -\mathbf{1 & 0 }w_1+\\ 0 & 0 & 0 & 0\endmathbf{pmatrix1}w_2 </math>
לפיכך המשתנה השלישי והרביעי הם חופשיים, נציב במקומם פרמטרים t,s והפתרון הכללי הוא מהצורה <math>(-t-s,t,t,s)</math>. תמיד ניתן לפרק את הפתרון הכללי לסכום של וקטורים קבועים כפול הסקלרים שהם הפרמטרים: <math>t(-1,1,1,0) +s(-1,0,0,1)</math>. וקטורים קבועים אלה תמיד מהווים בסיס למרחב הפתרונות: *אנו רואים שכל פתרון הוא צירוף לינארי של הוקטורים הללו עם הסקלרים שהם הפרמטרים (במקרה זה - t,s)*וקטורים אלה תמיד בת"ל, שכן אם יש צירוף לינארי שלהם שמתאפס, מכיוון שהפרמטרים תמיד מופיעים לבדם בעמודה של המשתנה שלהם, הם חייבים להיות אפסלכן
לכן הבסיס למרחב האפס הינו <math>[I]^E_F=\begin{(pmatrix} 5& -1,0,0,1),(\\ -2 & 1,1,1,0)\end{pmatrix}</math>
===אלגוריתם למציאת בסיס למרחב האפס===
#דרג את המטריצה קנונית
#הצב פרמטרים במקום המשתנים החופשיים
#מצא את הפתרון הכללי
#פרק את הפתרון הכללי לצירוף לינארי של וקטורים קבועים כפול הפרמטרים
#הוקטורים הקבועים מהווים בסיס למרחב האפס
'''תרגיל:'''
'''תרגיל 7הוכח ש <math>[I]^S_B[I]^A_S=[I]^A_B</math>.31'''מכיוון שאנו יודעים שמטריצה המעבר הינה יחידה, מספיק להראות שהכפל מקיים את הפסוק מההגדרה:
נגדיר שני תתי מרחבים של <math>\mathbb{R}_3[x]</math>:
<math>V=\{p(x)|p(2)=0forall v\}</math>, ו <math>Uin V: [I]^S_B[I]^A_S[v]_A=\{p(x)|p(1)[I]^S_B[v]_S=0\}[v]_B</math>
מצא את המימד של חיתוך המרחבים.
'''משפט:''' לכל שני בסיסים E,F מטריצת המעבר הינה מטריצה הפיכה ומתקיים <math>([I]^E_F)^{-1}=[I]^F_E</math>
'''פתרון.'''
בתרגיל זה נשתמש בשיטה נפוצה ביותר. אנו מעוניינים לתאר את המרחבים הוקטוריים באופן קל יותר לעבודה מאשר התיאור לעיל; לכן ננסה לתאר את תתי המרחבים הללו כ'''מרחבי אפס''' של מטריצות מתאימות. כמובן שכחלק מתהליך זה נעבור לוקטורי הקואורדינטות, הרי פולינום לא יכול להיות פתרון למערכת הומוגנית של מטריצות.מסקנה:
נביט בV. זהו אוסף ===אלגוריתם למציאת מטריצת מעבר בין '''כל הפולינומים ש2 הוא שורש שלהם. יהי פולינום כללי ''' שני בסיסים E,F===#בחר בסיס סטנדרטי S מתאים למרחב שלך#מצא את מטריצת המעבר <math>p(x)=a+bx+cx^2+dx[I]^3E_S</math>, הוא שייך לV אם"ם מקדמיו מקיימים . זה קל מאד שכן יש למצוא את המשוואה הלינארית: הקואורדינטות של איברי הבסיס E לפי הבסיס הסטנדרטי S#מצא את מטריצת המעבר <math>a+2b+4c+8d=0[I]^F_S</math>. באופן דומה הפולינום שייך לU אם"ם מקדמיו מקיימים #הפוך את המשוואה הלינארית המטריצה האחרונה לקבל <math>0([I]^F_S)^{-1}=a+b+c+d[I]^S_F</math>. לכן פולינום נמצא בחיתוך אם"ם מקדמיו (הקואורדינטות) מקיימים #כפול את מערכת המשוואות המכיל המטריצות על מנת לקבל את שתי המשוואות הללו, כלומר מקדמיו הם מרחב האפס של המערכת.התוצאה הסופית <math>[I]^S_F[I]^E_S=[I]^E_F</math>
נמצא בסיס למרחב האפס <math>\begin{pmatrix}1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 8\end{pmatrix}</math>. נדרג קנונית לקבל
====דוגמא:====
<math>V=\beginmathbb{pmatrix}1 & 0 & -2 & -6 \\ 0 & 1 & 3 & 7\end{pmatrixR}_2[x]</math> מצא את <math>[I]^E_F</math>כאשר
ולכן הפתרון הכללי הוא מהצורה <math>(2tE=\{1+6sx,-3t-7sx+x^2,t,s)</math>, ולכן בסיס למרחב האפס הינו <math>(x^2\},-3F=\{x,1,0),(6,-7,0+x,1)+2x^2\}</math>. נחזור מהקואורדינטות לצורה הפולינומית לקבל את התשובה הסופית:
פתרון:
נסמן <math>S</math> הבסיס הסטנדרטי ואז
<math>
[I]^E_S=
\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix},
<math>[I]^F_S=\begin{pmatrix} 0 & 1 & 1 \\1 & 1 & 0 \\0 & 0 & 2-3x+x^2,6-7x+x^3\end{pmatrix}</math> מהווים בסיס לחיתוך בין V לU.
אחרי חישובים מקבלים כי
<math>[I]^S_F=
\begin{pmatrix}
0 & 1 & 1 \\
1 & 1 & 0 \\
0 & 0 & 2
\end{pmatrix}^{-1} =
ראינו בהרצאה שפעולות שורה אינן משנות את המרחב הנפרש על ידי השורות. מכאן נובע האלגוריתם הבא:
===אלגוריתם למציאת בסיס למרחב השורות (ומציאת בסיס לקבוצה כלשהי של וקטורים)===\begin{pmatrix} #שים את הקואורדינטות של הוקטורים לפי בסיס סטנדרטי מתאים בשורות מטריצה-1 & 1 & 0.5 \\#דרג את המטריצה1 & 0 & -0.5 \\#השורות שאינן שורות אפסים בצורה המדורגת מהוות יחדיו בסיס למרחב השורות (או למרחב הקואורדינטות של הוקטורים שלנו)0 & 0 & 0.5 \end{pmatrix}</math>
==מטריצות מעבר בין בסיסים==ראינו שקל מאד למצוא קואורדינטות לפי הבסיס הסטנדרטי, נשתמש בהנחה הזו בהמשך. אנו מעוניינים לדעת כיצד לחשב קואורדינטות לפי בסיס כלשהו, לאו דווקא סטנדרטי.ולכן
'''משפט:''' יהא V מ"ו ויהיו E,F בסיסים לו. אזי '''קיימת''' מטריצה '''יחידה''' המסומנת <math>[I]^E_F</math> המקיימת את הפסוק הבא: =[I]^S_F[I]^E_S=
<math>\forall vbegin{pmatrix} -1 & 1 & 0.5 \in V: [I]^E_F[v]_E=[v]_F</math>\1 & 0 & -0.5 \\0 & 0 & 0.5 \end{pmatrix}
\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix}
=
נסמן <math>E=\begin{v_1,pmatrix} 0 & 1.5 & 0..,v_n5 \}</math> ו <math>F=\{w_1,1 & -0.5 & -0.5 \\0 & 0.,w_n5 & 0.5 \end{pmatrix}</math>. אזי מתקיים ש<math>[I]^E_F</math> הינה המטריצה שעמודותיה הן <math>[v_i]_F</math>
</math>
'''דוגמא.'''====תרגיל====
הוכח ש תהא <math>[I]^S_B[I]^A_SA =[I]^A_B\begin{pmatrix}1 & 2 & 3 \\4 & 5 & 6 \\1 & 1 & 0 \\\end{pmatrix}</math>. מכיוון שאנו יודעים שמטריצה המעבר הינה יחידה, מספיק להראות שהכפל מקיים את הפסוק מההגדרה:
ובסיס
<math>E =\forall v{\in V: [I]^S_B[I]^A_S[v]_A=[I]^S_B[v]_S=[v]_Bbegin{pmatrix}1 \\1 \\0 \\\end{pmatrix},\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix},\begin{pmatrix}0 \\0 \\1 \\\end{pmatrix}\}</math>
מצאו בסיס <math>F</math> כך ש <math>A=[I]^E_F</math>
'''משפטפתרון:''' לכל שני בסיסים E,F מטריצת המעבר הינה מטריצה הפיכה ומתקיים <math>([I]^E_F)^{-1}=[I]^F_E</math>
נסמן <math>F=\{v_1,v_2,v_3\}</math>
מסקנה:נחשב ונמצא כי
===אלגוריתם למציאת מטריצת מעבר בין '''כל''' שני בסיסים E,F===#בחר בסיס סטנדרטי S מתאים למרחב שלך#מצא את מטריצת המעבר <math>[I]^E_SF_E= A^{-1} = \begin{pmatrix}-4/3 & 1/3 & 1 \\2/3 & 1/3 & -2 \\1/3 & -1/3 & 1 \\\end{pmatrix}</math>. זה קל מאד שכן יש למצוא את הקואורדינטות של איברי הבסיס E לפי הבסיס הסטנדרטי S#מצא את מטריצת המעבר מהגדרה נקבל כי <math>[I]^F_S<v_1 = -4/math>.3#הפוך את המטריצה האחרונה לקבל \begin{pmatrix}1 <math>([I]^F_S)^\\1 \\0 \\\end{pmatrix}+2/3\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}+1/3\begin{pmatrix}0 \\0 \\1 \\\end{pmatrix} =\begin{pmatrix}-2/3 \\-4/3 \\1 \\\end{pmatrix}, \\v_2 =[I]^S_F<1/math>3#כפול את המטריצות על מנת לקבל את התוצאה הסופית <math>[I]^S_F[I]^E_S\begin{pmatrix}1 \\1 \\0 \\\end{pmatrix}+1/3\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}+-1/3\begin{pmatrix}0 \\0 \\1 \\\end{pmatrix} =[I]^E_F\begin{pmatrix}2/3 \\1/3 \\0 \\\end{pmatrix},\\v_3 = 1\begin{pmatrix}1 \\1 \\0 \\\end{pmatrix}+-2\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}+1\begin{pmatrix}0 \\0 \\1 \\\end{pmatrix} =\begin{pmatrix}-1 \\1 \\-1 \\\end{pmatrix} </math>