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

הגדרה 1: בסיס סדור

מ"ו, סופית של נקראת בסיס סדור כאשר היא פורשת ובת"ל.

קיום הסדר מאפשר להגדיר קואורדינטות של וקטור ביחס לבסיס (ראה טענה 1).


טענה 1: יהי מ"ו מעל , ו בסיס סדור של . אז לכל קיים יחידה כך ש

קיום

מכך ש .

יחידות

נניח כי הם וקטורים כך ש:

מאחר ש בת"ל, צירוף ליניארי זה הנו טריוויאלי. מכאן:

ומכאן היחידות, כלומר .

טענה 2: יהי מ"ו ו-, תת קבוצה של בת"ל בת איברים אז היא בסיס.

נניח בשלילה כי אז קיים . לפי טענה 1 למשפטי תלות, בת"ל. סתירה לכך ש- ולכן היא תלויה ליניארית .

טענה 3: מ"ו נוצר סופית, ו- תת מרחב של . תת קבוצה של בת"ל. אז קיימת תת קבוצה של שמכילה את כך ש היא בסיס של .

הוא תת מרחב של . אם אז היא בסיס של .

אם אז קיים אז נגדיר .

לפי הטענה אז בת"ל, ואם אז סיימנו, כלומר היא בסיס של .

אחרת, אם אז קיים ונגדיר .

נסמן , אם ב- השלבים הראשונים של התהליך לא מצאנו בסיס של , אז נקבל היא קבוצה בת"ל בת לפחות איברים, וזה לא ייתכן.

לכן האלגוריתם יעצור ב שלבים הראשונים.


טענה 4: מ"ו נוצר סופית, ו- תת מרחב של אז נוצר סופית, וגם

יהי , אז קיים בסיס של . מאחר ש - בת"ל, מספר האיברים ב קטן או שווה ל.

טענה 5: יהי מ"ו נוצר סופית, ו- תת קבוצה בת"ל של , אז קיימת תת קבוצה של שמהווה בסיס של ו- מוכלת

נצב בטענה 4

טענה 6: מ"ו נוצר סופית, תת-מרחב של כך ש- אז .

נסמן ו-.

קיים .

יהי בסיס של .

אז . ולכן בת"ל.

מכאן נובע כי . כנדרש.