אלגברה לינארית/משפט ההחלפה של שטייניץ

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

תהי $A\subseteq V$ בת"ל, תהי $B$ קבוצה פורשת סופית ל־$V$, ויהי $\overrightarrow{a}\in A$.

אזי קיים $\overrightarrow{b}\in B\setminus (A\setminus \{\overrightarrow{a}\})$ עבורו $(A\setminus \{\overrightarrow{a}\})\cup \{\overrightarrow{b}\}$ בת"ל.

הוכחה

נסדר את אברי $A$ כך ש־$\overrightarrow{a}$ יהיה האחרון. נסמן $A=\{{\overrightarrow{a}}_1,\dots ,{\overrightarrow{a}}_m,\overrightarrow{a}\},B=\{{\overrightarrow{b}}_1,\dots ,{\overrightarrow{b}}_n\}$.

מכיון ש־$B$ פורשת, קיימים מקדמים שעבורם $\overrightarrow{a}=\sum _{i=1}^n{\beta }_i{\overrightarrow{b}}_i$.

אם כל אברי $B$ הם צירופים לינאריים של אברי $A\setminus \{\overrightarrow{a}\}$ אזי קיימים מקדמים שעבורם ${\overrightarrow{b}}_i=\sum _{j=1}^m{\alpha }_{ij}{\overrightarrow{a}}_j$

ולכן $\overrightarrow{a}=\sum _{i=1}^n\left(\sum _{j=1}^m{\alpha }_{ij}\right){\beta }_i{\overrightarrow{a}}_j$, בסתירה לכך ש־$A$ בת"ל.

לכן קיים $\overrightarrow{b}\in B$ שאינו צ"ל של $A\setminus \{\overrightarrow{a}\}$. לכן ברור כי $\overrightarrow{b}\notin A\setminus \{\overrightarrow{a}\}$, כלומר $\overrightarrow{b}\in B\setminus (A\setminus \{\overrightarrow{a}\})$.

מהיות $A$ בת"ל כל אחד מאברי $A\setminus \{\overrightarrow{a}\}$ אינו צ"ל של קודמיו.

$\overrightarrow{b}$ אינו צ"ל של $A\setminus \{\overrightarrow{a}\}$, כל אחד מאברי $A\setminus \{\overrightarrow{a}\}$ אינו צ"ל של קודמיו, ולכן $(A\setminus \{\overrightarrow{a}\})\cup \{\overrightarrow{b}\}$ בת"ל.

הקשר בין הגדלים

משפט 1: יהי $A\subseteq V$ בת"ל ו־$B\subseteq V$ פורשת סופית. אזי $|B|\ge |A|$. נסמן את $|B|=n$. נניח בשלילה שקיימת $C=\{u_1,\dots ,u_{n+1}\}\subseteq A$, אזי $C$ בת"ל. לפי משפט ההחלפה (אם נפעיל אותו על כל אברי C) נקבל שקיימת $D=\{w_1,\dots ,w_{n+1}\}\subseteq B$ בת"ל כאשר $w_i\ne w_j$. אבל לא קיימים $n+1$ אברים ב־$B$, ולכן לא קיימת $D\subseteq B$ שעבורה $|D|=n+1$, בסתירה.