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

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

טענה 1: יהי $V$ מ"ו מעל $\mathbb {F}$, ו$\left(v_{1},..,v_{n}\right)$ בסיס סדור של $V$. אז לכל $v\in V$ קיים ${\begin{bmatrix}c_{1}\\\vdots \\c_{n}\end{bmatrix}}\in \mathbb {F} ^{n}$ יחידה כך ש $v=c_{1}v_{1}+..+c_{n}v_{n}$ קיום מכך ש $span\left(v_{1},..,v_{n}\right)=V$. יחידות נניח כי ${\begin{bmatrix}c_{1}\\\vdots \\c_{n}\end{bmatrix}},{\begin{bmatrix}d_{1}\\\vdots \\d_{n}\end{bmatrix}}\in \mathbb {F} ^{n}$ הם וקטורים כך ש: ${\begin{bmatrix}d_{1}v_{1}+...+d_{n}v_{n}=v=c_{1}v_{1}+..+c_{n}v_{n}\\d_{1}v_{1}+...+d_{n}v_{n}-\left(c_{1}v_{1}+..+c_{n}v_{n}\right)=0\\\left(c_{1}-d_{1}\right)v_{1}+...+\left(c_{n}-d_{n}\right)v_{n}=0\end{bmatrix}}$ מאחר ש $\left(v_{1},..,v_{n}\right)$ בת"ל, צירוף ליניארי זה הנו טריוויאלי. מכאן: $c_{1}-d_{1}=...=c_{n}-d_{n}=0$ $c_{1}=d_{1},....c_{n}=d_{n}$ ומכאן היחידות, כלומר ${\begin{bmatrix}c_{1}\\\vdots \\c_{n}\end{bmatrix}}={\begin{bmatrix}d_{1}\\\vdots \\d_{n}\end{bmatrix}}$.

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

טענה 3: $V$ מ"ו נוצר סופית, ו-$U$ תת מרחב של $V$. $S$ תת קבוצה של $U$ בת"ל. אז קיימת תת קבוצה $S'$ של $U$ שמכילה את $S$ כך ש $S'$ היא בסיס של $U$. $spanS$ הוא תת מרחב של $U$. אם $spanS=U$ אז $S$ היא בסיס של $U$. אם $spanS\neq U$ אז קיים $w_{1}\in U\backslash spanS$ אז נגדיר $S_{1}=S\cup \left\{w_{1}\right\}$ . לפי הטענה אז $S_{1}$ בת"ל, ואם $spanS_{1}=U$ אז סיימנו, כלומר $S_{1}$ היא בסיס של $U$. אחרת, אם $spanS_{1}\neq U$ אז קיים $w_{2}\in U\backslash spanS_{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\leq \dim V$ יהי $S=\emptyset$, אז קיים בסיס $S'$ של $U$. מאחר ש -$S'$ בת"ל, מספר האיברים ב$S'$ קטן או שווה ל$\dim V$.

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

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