88-112 לינארית 1 תיכוניסטים קיץ תשעא/מערך תרגול/6

חזרה למערכי התרגול

בסיס ומימד

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

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

• S פורשת את W. כלומר, spanS=W.
• S בת"ל. (כלומר, זרקנו ממנה את כל הוקטורים המיותרים.)

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

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

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

הגדרה: הבסיס של מרחב האפס הינו הקבוצה הריקה, ולכן המימד של מרחב האפס הינו אפס.

(חידה מטופשת: אם ניקח את המימד של צירוף לינארי נקבל מנה טעימה. מהי?)

תרגיל

הוכח כי כל קבוצה A המכילה את אפס הינה תלויה לינארית

הוכחה

יש למצוא קבוצה סופית של וקטורים ת"ל בתוך הקבוצה: $\{0\}\subseteq A$. וקטור האפס תמיד תלוי לינארית כי לכל סקלר שונה מאפס (ובפרט לאחד) מתקיים $1\cdot 0 = 0$.

לכן הקבוצה $\{0\}$ לעולם אינה מהווה בסיס כי היא ת"ל, בפרט היא לא בסיס למרחב האפס.

משפט השלישי חינם

יהיה V מ"ו ותהי S קבוצה המוכלת בV. אזי אם שניים מבין התנאים הבאים מתקיימים, השלישי מתקיים בהכרח (בחינם) ומתקיים שS היא בסיס לV:

• S בת"ל
• spanS=V
• מספר האיברים בS שווה למימד של V. (מסומן: $\#S=dimV$.)

תרגיל חשוב (חלק מ7.7)

יהיה V מרחב וקטורי, ויהי W תת מרחב. הוכח/הפרך: אם dimV=dimW מתקיים שV=W בהכרח

פתרון

נתון שdimV=dimW. נניח בשלילה ש$V\neq W$ ונראה אם אנחנו מקבלים סתירה או האם מוצאים דוגמא נגדית. מכיוון שנתון $W\subseteq V$ העובדה ש$V\neq W$גוררת בהכרח שקיים וקטור $v\in V$ כך ש $v\notin W$ (זה תרגיל לוגי פשוט). נסמן dimW=dimV=n וניקח בסיס כלשהו לW (אנחנו יודעים שקיים כזה) $S=\{v_1,...,v_n\}$.

כעת, נוכיח ש$S\cup \{v\}$ בהכרח בת"ל. נניח בשלילה שהיא כן תלוייה, לכן יש צירוף לינארי לא טריוויאלי של $v_1,v_2,..,v_n,v$ שמתאפס. נניח והמקדם של v שונה מאפס, לכן קל להראות שהוא צירוף לינארי של האחרים בסתירה לכך ש-v אינו שייך לW (הרי יש סגירות בW לצירופים לינאריים) לכן המקדם של v הינו אפס. כעת נשארנו עם צירוף לינארי לא טריוויאלי שמתאפס של $v_1,...,v_n$ וזו סתירה לכך שהם בת"ל מתוקף הגדרתם כבסיס.

על כן, מצאנו קבוצה בת"ל המכילה n+1 וקטורים, בסתירה לכך שהמימד של W הוא n.

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

תרגיל 7.17

יהא V מ"ו, ותהא B קבוצה המוכלת בV. הוכח שהתנאים הבאים שקולים:

• B בסיס עבור V
• וקטור האפס אינו שייך לB ולכל קבוצה $A\subseteq B$ מתקיים $V=spanA\oplus span(B/A)$

הוכחה

ראשית נוכיח שהתנאי הראשון גורר את השני:

נניח B בסיס לV, ברור מכך שB בת"ל שהוא אינו מכיל את אפס. תהי A קבוצה המוכלת בB נסמן ב.ה.כ $B=\{v_1,...,v_n\}$ ו $A=\{v_1,...,v_j\}$. יש להוכיח בעצם שמתקיים $V=span\{v_1,...,v_j\}\oplus span\{v_{j+1},...,v_n\}$. לצורך זה יש להוכיח שני דברים:

• $span\{v_1,...,v_j\}\cap span\{v_{j+1},...,v_n\}=\{0\}$
• $V=span\{v_1,...,v_j\}+ span\{v_{j+1},...,v_n\}$

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

נניח בשלילה שהתנאי הראשון אינו נכון, לכן קיים בחיתוך וקטור שונה מאפס. כלומר קיימים סקלרים כך ש$a_1v_1+...+a_jv_j=b_{j+1}v_{j+1}+...+b_nv_n$. מכיוון שמשני צידי המשוואה יש וקטור שונה מאפס, לפחות אחד מהסקלרים שונה מאפס. נעביר אגף ונקבל סתירה לכך שB בת"ל.

כעת, ברור שהמרחב כולו שווה לסכום הזה מכיוון שהמרחב מורכב מצירופים לינאריים של B והסכום הזה שווה בדיוק לכל הצירופים הלינאריים של B. (למעשה זה נובע מהתכונה הבאה: לכל שתי קבוצות A,B מתקיים: $spanA+spanB=span(A \cup B)$)

נוכיח שהתנאי השני גורר את הראשון:

מכיוון שזה נכון לכל קבוצה A המוכלת בB, בפרט זה נכון לקבוצה הריקה. לכן יוצא ש $V=span\phi\oplus span (B/\phi)=spanB$ כלומר B פורש את V. נותר להראות שB בת"ל.

נניח בשלילה שB אינה בת"ל, לכן וקטור אחד ממנה u הוא צירוף לינארי של האחרים. נסמן בA את הנקודון שמכיל את u כלומר $A=\{u\}$ ומכייון שבהכרח $u \neq 0$ נקבל סתירה לתכונת הסכום הישר (חיתוך שכולל רק את ווקטור האפס)

צירופים לינאריים - דוגמאות נוספות

תרגיל 7.31

נגדיר שני תתי מרחבים של $\mathbb{R}_3[x]$:

$V=\{p(x)|p(2)=0\}$, ו $U=\{p(x)|p(1)=0\}$

מצא את המימד של חיתוך המרחבים.

פתרון.

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

נביט בV. זהו אוסף כל הפולינומים ש2 הוא שורש שלהם. יהי פולינום כללי $p(x)=a+bx+cx^2+dx^3$, הוא שייך לV אם"ם מקדמיו מקיימים את המשוואה הלינארית: $a+2b+4c+8d=0$. באופן דומה הפולינום שייך לU אם"ם מקדמיו מקיימים את המשוואה הלינארית $0=a+b+c+d$. לכן פולינום נמצא בחיתוך אם"ם מקדמיו (הקואורדינטות) מקיימים את מערכת המשוואות המכילה את שתי המשוואות הללו. נמצא בסיס למרחב זה:

$\begin{pmatrix}1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 8\end{pmatrix}$. נדרג קנונית לקבל

$\begin{pmatrix}1 & 0 & -2 & -6 \\ 0 & 1 & 3 & 7\end{pmatrix}$

ולכן הפתרון הכללי הוא מהצורה $(2t+6s,-3t-7s,t,s)$, ולכן הבסיס הינו $(2,-3,1,0),(6,-7,0,1)$. נחזור לצורה הפולינומית לקבל את התשובה הסופית:

$\{2-3x+x^2,6-7x+x^3\}$ מהווים בסיס לחיתוך בין V לU.

אלגוריתם למציאת חיתוך בין שני תתי מרחבים U,W

ישנן שתי שיטות לחשב את החיתוך, נתחיל בראשונה (שביצענו הרגע, למעשה):

1. מצא מערכת משוואות המתארת את U ומערכת משוואות המתארת את W (כמו בהצגה השנייה מבין הצגות המרחב)
2. פתור מערכת אחת המכילה את כל המשוואות משתי המערכות וקבל את החיתוך

שיטה שנייה:

1. כתוב צירוף לינארי כללי בU וצירוף לינארי כללי בW
2. השווה את הצירופים ופתור מערכת משוואות על הסקלרים
3. הצב את הסקלרים שקיבלת בצירוף הלינארי וקבל את החיתוך

תרגיל.

מצא את החיתוך בין תתי המרחבים הבאים בשיטה השנייה לעיל.

$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 )$

פתרון.

(קחו נשימה עמוקה) יהיו סקלרים a,b,c,x,y,z, וקטור הוא בחיתוך אם"ם הוא צירוף לינארי של שתי הקבוצות הפורשות:

$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}$

לכן מערכת המשוואות על הסקלרים הינה:

$\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}$

נדרג ונמצא את הפתרונות (שימו לב: מספיק למצוא רק את x,y,z או רק את a,b,c מכיוון שבהנתן צירוף לינארי של איברי C שנותן את החיתוך אין צורך להמשיך (כמו כן לגבי B).)

$\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}$

במקרה זה קל יותר למצוא את x,y,z; המשתנים החופשיים הינם x,z ומתקיים z=5y. ולכן הצ"ל הכללי בחיתוך הינו:

$B\cap C=\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\}$

קואורדינטות

משפט: יהא V מ"ו מעל שדה F, יהי $B=\{v_1,...,v_n\}$ בסיס ל-V ויהי $v\in V$ וקטור. אזי ל-v יש הצגה יחידה כצירוף לינארי לפי הבסיס B. כלומר, אם מתקיים $v=a_1v_1+...+a_nv_n=b_1v_1+...+b_nv_n$ אזי בהכרח $\forall i:a_i=b_i$. (קל להוכיח את זה על ידי חיסור הצד הימני של המשוואה מהצד השמאלי, מקבלים צירוף לינארי שמתאפס עם מקדמים $a_i-b_i$.)

הגדרה: יהיו V,B וv כמו במשפט. אזי וקטור הקואורדינטות של v לפי בסיס B, מסומן $[v]_B\in\mathbb{F}^n$ מוגדר להיות $[v]_B=\begin{pmatrix}a_1 \\ a_2 \\ \vdots \\ a_n\end{pmatrix}$ כאשר $v=a_1v_1+...+a_nv_n$ ההצגה הלינארית היחידה הקיימת לפי המשפט.

חשוב לזכור $[v]_B=\begin{pmatrix}a_1 \\ a_2 \\ \vdots \\ a_n\end{pmatrix}$ אם"ם $v=a_1v_1+...+a_nv_n$

תרגיל קל אבל חשוב הוא להראות שלכל בסיס B מתקיים ש $v=0$ אם"ם $[v]_B=0$.

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

מרחב וקטורי	בסיס סטנדרטי
$\mathbb{F}^n$	$(1,0,...,0),(0,1,0,...,0),...,(0,...,0,1)$
$\mathbb{F}^{m\times n}$	$\begin{pmatrix}1 & 0 & \cdots & 0 \\ 0 & \cdots & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & \cdots & 0\end{pmatrix}, \begin{pmatrix}0 & 1 & \cdots & 0 \\ 0 & \cdots & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & \cdots & 0\end{pmatrix},..., \begin{pmatrix}0 & \cdots & \cdots & 0 \\ 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & \cdots & 0\end{pmatrix},..., \begin{pmatrix}0 & \cdots & \cdots & 0 \\ 0 & \cdots & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & 1 \end{pmatrix}$
$\mathbb{F}_n[x]$	$1,x,x^2,...,x^n$

דוגמא. חשב את הקואורדינטות של הוקטור $v=1+2x-x^2$ לפי הבסיס הסטנדרטי S של $\mathbb{R}_3[x]$. למעשה הפולינום כמעט מוצג כצירוף לינארי של איברי הבסיס:

$v=a_1v_1+a_2v_2+a_3v_3+a_4v_4 = 1\cdot 1 + 2\cdot x + (-1)\cdot x^2 + 0\cdot x^3$.

לפיכך $[v]_S=(1,2,-1,0)$.

דוגמא. חשב את הקואורדינטות של הוקטור $(a,b,c)$ לפי הבסיס הסטנדרטי S של $\mathbb{F}^n$. קל לראות ש $[v]_S = (a,b,c)$.

דוגמא. $V=\mathbb{R}^2,B=\{(1,1),(1,-1)\}$ מצא את הקואורדינטות של הוקטור $v=(a,b)$ לפי הבסיס B. במקרה הכינותי מראש-

$v=\frac{a+b}{2}\cdot (1,1)+\frac{a-b}{2}\cdot (1,-1)$

ולכן לפי ההגדרה $[v]_B=(\frac{a+b}{2},\frac{a-b}{2})$

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

טענה.

יהא V מ"ו ויהי B בסיס לו. יהיו $u_1,...,u_k\in V$ וקטורים כלשהם. הוכח:

• $u_1,...,u_k$ בת"ל אם"ם $[u_1]_B,...,[u_k]_B$ בת"ל
• $w\in span\{u_1,...,u_k\}$ אם"ם $[w]_B\in span\{[u_1]_B,...,[u_k]_B\}$

נוכיח טענה זו בהמשך, לאחר שנלמד על העתקות לינאריות. כעת נניח שהיא נכונה ונתרכז בכלי החישובי המשמעותי שקיבלנו; כל בדיקה/חישוב של תלות לינארית או פרישה בכל מרחב וקטורי (מטריצות, פולינומים, פונקציות) יכול בעצם להעשות במרחב הוקטורי המוכר והנוח $\mathbb{F}^n$.

דוגמא.

האם הפולינומים $v_1=1+x^2,v_2=1-x,v_3=x+x^2$ תלויים לינארית?

דבר ראשון, נעבור למרחב הקואורדינטות. מכיוון שבחירת הבסיס היא לשיקולנו, נבחר את הבסיס הסטנדרטי S של הפולינומים איתו קל לעבוד. מתקיים ש $[v_1]_S=(1,0,1),[v_2]_S=(1,-1,0),[v_3]=(0,1,1)$

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

$\begin{pmatrix}1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 1 & 1\end{pmatrix}$

$R_3-R_1,R_3+R_2$

$\begin{pmatrix}1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 0 & 0\end{pmatrix}$

לכן וקטורי הקואורדינטות תלויים לינארית ולכן הפולינומים עצמם תלויים לינארית. נסכם את התהליך:

אלגוריתם לבדיקת תלות לינארית בין וקטורים

1. הפוך את הוקטורים לוקטורי קואורדינטות לפי הבסיס הסטנדרטי המתאים
2. שים את וקטורי הקואורדינטות בשורות מטריצה A
3. הבא את המטריצה לצורה מדורגת
4. אם באיזה שלב קיבלת שורת אפסים סימן שהוקטורים תלויים לינארית
5. אם הגעת לצורה מדורגת ללא שורת אפסים סימן שהוקטורים בלתי תלויים לינארית

דוגמא. האם המטריצה $v=\begin{pmatrix}1 & 2 \\ 3 & 4\end{pmatrix}$ נפרשת על ידי המטריצות $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}$ ? אם כן, הצג אותה כצירוף לינארי שלהן.

פתרון: נעבור דבר ראשון למרחב הקואורדינטות לפי הבסיס הסטנדרטי $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\}$

נקבל $[v]_S=(1,2,3,4),[v_1]_S=(1,1,0,0),[v_2]_S=(1,0,2,1),[v_3]_S=(2,2,10,10)$.

למדנו בשיעור שעבר שוקטור b נפרש על ידי וקטורים מסויימים אם"ם קיים פתרון למערכת Ax=b כאשר A היא המטריצה שעמודותיה הם אותם וקטורים. הפתרון x הוא וקטור הסקלרים מהצירוף הלינארי. לכן, אנו רוצים לדעת האם קיים פתרון למערכת ואם כן מהו:

$\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}$

קל לפתור ולגלות ש $x=(1,-1,\frac{1}{2})$ מקיים את המערכת ולכן מתקיים $v=v_1-v_2+\frac{1}{2}v_3$

נסכם:

אלגוריתם לחישוב צירוף לינארי

1. נתון וקטור b וקבוצת וקטורים. העבר את כולם לוקטורי קואורדינטות לפי הבסיס הסטנדרטי המתאים
2. פתור את המערכת Ax=b כאשר עמודות A הינן וקטורי הקואורדינטות של קבוצת הוקטורים הפורשים
3. אם אין פתרון, b לא נפרש על ידי האחרים
4. אם קיים פתרון x אזי הוא מכיל את הסקלרים של הצירוף הלינארי בהתאם לסדר העמודות בA

מטריצות מעבר בין בסיסים

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

משפט: יהא V מ"ו ויהיו E,F בסיסים לו. אזי קיימת מטריצה יחידה המסומנת $[I]^E_F$ המקיימת את הפסוק הבא:

$\forall v\in V: [I]^E_F[v]_E=[v]_F$

נסמן $E=\{v_1,...,v_n\}$ ו $F=\{w_1,...,w_n\}$. אזי מתקיים ש$[I]^E_F$ הינה המטריצה שעמודותיה הן $[v_i]_F$

דוגמא.

הוכח ש $[I]^S_B[I]^A_S=[I]^A_B$. מכיוון שאנו יודעים שמטריצה המעבר הינה יחידה, מספיק להראות שהכפל מקיים את הפסוק מההגדרה:

$\forall v\in V: [I]^S_B[I]^A_S[v]_A=[I]^S_B[v]_S=[v]_B$

משפט: לכל שני בסיסים E,F מטריצת המעבר הינה מטריצה הפיכה ומתקיים $([I]^E_F)^{-1}=[I]^F_E$

מסקנה:

אלגוריתם למציאת מטריצת מעבר בין כל שני בסיסים E,F

1. בחר בסיס סטנדרטי S מתאים למרחב שלך
2. מצא את מטריצת המעבר $[I]^E_S$. זה קל מאד שכן יש למצוא את הקואורדינטות של איברי הבסיס E לפי הבסיס הסטנדרטי S
3. מצא את מטריצת המעבר $[I]^F_S$.
4. הפוך את המטריצה האחרונה לקבל $([I]^F_S)^{-1}=[I]^S_F$
5. כפול את המטריצות על מנת לקבל את התוצאה הסופית $[I]^S_F[I]^E_S=[I]^E_F$