Linear Algebra I MT22, Steinitz Exchange Lemma
Flashcards
What is the technical statement of the Steinitz exchange lemma, in terms of $V$, $X$, $Y$, $u$ and $v _ i$?
Let $V$ be a vector space and let $X = \{v _ 1, v _ 2, \ldots, v _ n\} \subseteq V$. Suppose that $u \in \langle X \rangle$ but that $u \notin \langle X \backslash \{v _ i\} \rangle$ for some $i$. Let $Y = (X \backslash \{v _ i\}) \cup \{u\}$. Then $\langle Y \rangle = \langle X \rangle$.
When proving the Steinitz exchange lemma, what common proof technique do you use to show that the two sets $\langle X \rangle$ and $\langle Y \rangle$ are the same?
Double inclusion.
When proving the Steinitz exchange lemma
Let $V$ be a vector space and let $X = \{v _ 1, v _ 2, \ldots, v _ n\} \subseteq V$. Suppose that $u \in \langle X \rangle$ but that $u \notin \langle X \backslash \{v _ i\} \rangle$ for some $i$. Let $Y = (X \backslash \{v _ i\}) \cup \{u\}$. Then $\langle Y \rangle = \langle X \rangle$.
What’s the basic idea?
Let $V$ be a vector space and let $X = \{v _ 1, v _ 2, \ldots, v _ n\} \subseteq V$. Suppose that $u \in \langle X \rangle$ but that $u \notin \langle X \backslash \{v _ i\} \rangle$ for some $i$. Let $Y = (X \backslash \{v _ i\}) \cup \{u\}$. Then $\langle Y \rangle = \langle X \rangle$.
Rewriting $v _ i$ in terms of $u$ and other vectors in $X$.
Let $V$ be a vector space. Let $S, T$ be finite subsets of $V$. If $S$ is linearly independent and $T$ spans $V$, then what must be true?
When proving that a linearly independent set $S$ is always smaller than or equal to a spanning set $T$, what’s the main idea?
Use the Steinitz exchange lemma to swap vectors from $S$ and $T$ until $S$ is exhausted.
When proving that a linearly independent set $S$ is always smaller than or equal to a spanning set $T$, you work with a series of sets $T _ 0, T _ 1, \ldots T _ m$. Why?
You end up showing
\[\begin{aligned} |T| &= |T_0| \\\\ &= |T_1| \\\\ &= \ldots \\\\ &= |T_m| \\\\ &\ge |S| \end{aligned}\]What result (in full) do you quote to prove that all bases of a finite-dimensional vector space $V$ are of the same size?
Let $V$ be a finite-dimensional vector space and $S, T$ finite subsets of $V$. If $S$ is linearly independent, and $\langle T \rangle = V$, then $ \vert S \vert \le \vert T \vert $.