אלגברה לינארית/בסיס סדור

הגדרה 1: בסיס סדור $V$ מ"ו, סופית של $(v_1,\mathrm{..},v_n)$ נקראת בסיס סדור כאשר $(v_1,\mathrm{..},v_n)$ היא פורשת ובת"ל. קיום הסדר מאפשר להגדיר קואורדינטות של וקטור ביחס לבסיס (ראה טענה 1).

טענה 1: יהי $V$ מ"ו מעל $𝔽$, ו$(v_1,\mathrm{..},v_n)$ בסיס סדור של $V$. אז לכל $v\in V$ קיים $\left[\begin{array}{c}{c}_1\\ ⋮\\ c_n\end{array}\right]\in {𝔽}^n$ יחידה כך ש $v=c_1{v}_1+\mathrm{..}+c_n{v}_n$ קיום מכך ש $span(v_1,\mathrm{..},v_n)=V$. יחידות נניח כי $\left[\begin{array}{c}{c}_1\\ ⋮\\ c_n\end{array}\right],\left[\begin{array}{c}{d}_1\\ ⋮\\ d_n\end{array}\right]\in {𝔽}^n$ הם וקטורים כך ש: $\left[\begin{array}{c}{d}_1{v}_1+\mathrm{...}+d_n{v}_n=v=c_1{v}_1+\mathrm{..}+c_n{v}_n\\ d_1{v}_1+\mathrm{...}+d_n{v}_n-(c_1{v}_1+\mathrm{..}+c_n{v}_n)=0\\ (c_1-d_1)v_1+\mathrm{...}+(c_n-d_n)v_n=0\end{array}\right]$ מאחר ש $(v_1,\mathrm{..},v_n)$ בת"ל, צירוף ליניארי זה הנו טריוויאלי. מכאן: $c_1-d_1=\mathrm{...}=c_n-d_n=0$ $c_1=d_1,\mathrm{....}{c}_n=d_n$ ומכאן היחידות, כלומר $\left[\begin{array}{c}{c}_1\\ ⋮\\ c_n\end{array}\right]=\left[\begin{array}{c}{d}_1\\ ⋮\\ d_n\end{array}\right]$.

טענה 2: יהי $V$ מ"ו ו-$\dim V=n$, $S$ תת קבוצה של $V$ בת"ל בת $n$ איברים אז $S$ היא בסיס. נניח בשלילה כי $spanS\ne V$ אז קיים $w\in V\mathrm{\setminus }spanS$. לפי טענה 1 למשפטי תלות, $S\cup \left\{w\right\}$ בת"ל. סתירה לכך ש- $|S\cup \left\{w\right\}|=n+1>n$ ולכן היא תלויה ליניארית $\dim V=n$.

טענה 3: $V$ מ"ו נוצר סופית, ו-$U$ תת מרחב של $V$. $S$ תת קבוצה של $U$ בת"ל. אז קיימת תת קבוצה $S^{\prime }$ של $U$ שמכילה את $S$ כך ש $S^{\prime }$ היא בסיס של $U$. $spanS$ הוא תת מרחב של $U$. אם $spanS=U$ אז $S$ היא בסיס של $U$. אם $spanS\ne U$ אז קיים $w_1\in U\mathrm{\setminus }spanS$ אז נגדיר $S_1=S\cup \left\{w_1\right\}$ . לפי הטענה אז $S_1$ בת"ל, ואם $span{S}_1=U$ אז סיימנו, כלומר $S_1$ היא בסיס של $U$. אחרת, אם $span{S}_1\ne U$ אז קיים $w_2\in U\mathrm{\setminus }span{S}_2$ ונגדיר $S_2=S_1\cup \left\{w_2\right\}$ . נסמן $n=\dim V$, אם ב-$n$ השלבים הראשונים של התהליך לא מצאנו בסיס של $U$, אז נקבל $S_{n+1}$ היא קבוצה בת"ל בת לפחות $n+1$ איברים, וזה לא ייתכן. לכן האלגוריתם יעצור ב $n$ שלבים הראשונים.

טענה 4: $V$ מ"ו נוצר סופית, ו-$U$ תת מרחב של $V$ אז $U$ נוצר סופית, וגם $\dim U\le \dim V$ יהי $S=\mathrm{\varnothing }$, אז קיים בסיס $S^{\prime }$ של $U$. מאחר ש -$S^{\prime }$ בת"ל, מספר האיברים ב$S^{\prime }$ קטן או שווה ל$\dim V$.

טענה 5: יהי $V$ מ"ו נוצר סופית, ו-$S$ תת קבוצה בת"ל של $V$, אז קיימת תת קבוצה $S^{\prime }$ של $V$ שמהווה בסיס של $V$ ו-$S$ מוכלת $S^{\prime }$ נצב בטענה 4 $U=V$

טענה 6: $V$ מ"ו נוצר סופית, $U$ תת-מרחב של $V$ כך ש-$U\ne V$ אז $\dim U<\dim V$. נסמן $n=\dim V$ ו-$m=\dim U$. קיים $w\in V\mathrm{\setminus }W$. יהי $\{u_1,\mathrm{..},u_m\}$ בסיס של $U$. אז $w\notin U=span\{u_1,\mathrm{..},u_m\}$ . ולכן $\{u_1,\mathrm{..},u_m,w\}$ בת"ל. מכאן נובע כי $m<m+1\le n$. כנדרש.