05. Dimension

04 - Steinitz Exchange Lemma

Steinitz Exchange Lemma

Let $V$ be a vector space over a field $\mathbf{F}$
Let $X=\{v_1,v_2,\cdots ,v_n\}\subseteq V$
Suppose that $u\in ⟨X⟩$ but $u\notin ⟨X\setminus \{v_i\}⟩$ for some $i$

Let $Y=(X\setminus \{v_i\})\cup \{u\}$
Then

$$⟨Y⟩=⟨X⟩$$

In other words you exchange $u$ for $v_i$

Proof

Since $u\in ⟨X⟩$ then there are ${\alpha }_1,\cdots ,{\alpha }_n\in \mathbf{F}$ such that

$$u={\alpha }_1{v}_1+\cdots +{\alpha }_n{v}_n$$

There is $v_i\in X$ such that $u\notin \{X\setminus \{v_i\}\}$.
Without loss of generality, it is safe to assume that $i=n$
Since $u\notin ⟨X\setminus \{v_n\}⟩$, we see that $a_n\ne 0$
So by dividing by ${\alpha }_n$ and rearranging we get

$$v_n=\frac{1}{{\alpha }_n}(u-{\alpha }_1{v}_1-\cdots -{\alpha }_{n-1}{v}_{n-1})$$

Suppose for $w\in ⟨Y⟩$ then $w$ is a linear combination of the elements of $Y$
As we can replace $u$ by ${\alpha }_1{v}_1+\cdots +{\alpha }_n{v}_n$ so that $w$ is now a linear combination of the elements of $X$
Hence

$$⟨Y⟩\subseteq ⟨X⟩$$

Similarly if $w\in ⟨X⟩$ then $w$ is a linear combination of the elements of $X$
Substituting $v_n$ using the above then $w$ is now a linear combination of $Y$
Hence

$$⟨Y⟩\supseteq ⟨X⟩$$

Therefore

$$⟨X⟩=⟨Y⟩$$

Link to original

05 - Size Inequality for Independent vs Spanning Sets

Size Inequality for Independent vs Spanning Sets

Let $V$ be a vector space
Let $S,T$ be finite subsets of $V$

Suppose $S$ is linearly independent and $T$ spans $V$ then

$$|S|\le |T|$$

Proof

Assume that $S$ is linearly independent and $T$ spans $V$
Let the elements of $S$ be $u_1,u_2,\cdots ,u_m$
Let the elements of $T$ be $v_1,v_2,\cdots ,v_n$

Then we use Steinitz Exchange Lemma to swap the elements of $T$ with those of $S$, exhausting $S$ as follows

Let $T_0=\{v_1,\cdots ,v_n\}$
Since $⟨T_0⟩=V$, then $u_1\in ⟨v_1,\cdots ,v_i⟩$ for some $1\le i\le n$ and choose $i$ to be minimal
Note that then $u_1\notin ⟨v_1,\cdots ,v_{i-1}⟩$
Using the Steinitz Exchange Lemma then

$$⟨v_1,\cdots ,v_i⟩=⟨u_1,v_1,\cdots ,v_{i-1}⟩$$

Hence

$$\begin{array}{rl}V& =⟨v_1,\cdots v_n⟩\\ & =⟨v_1,\cdots ,v_i⟩+⟨v_{i+1},\cdots ,v_n⟩\\ & =⟨u_1,v_1,\cdots ,v_{i-1}⟩+⟨v_{i+1},\cdots ,v_n⟩\\ & =⟨u_1,v_1,\cdots ,v_{i-1},v_{i+1},\cdots ,v_n⟩\end{array}$$

By relabelling the elements of $T$ we can assume without loss of generality assume that

$$u_1\text{ has been exchange for }{v}_1$$

Then set

$$T_1=\{u_1,v_2,\cdots ,v_n\}\text{noting that }⟨T_1⟩=V$$

This can be inductively repeated creating sets

$$T_k=\{u_1,\cdots ,u_k,v_{k+1},\cdots ,v_n\}\text{ such that }⟨T_K⟩=V$$

(Note that $u_{k+1}\in ⟨T_k⟩$ but $u_{k+1}\notin ⟨u_1,\cdots ,u_k⟩$ as $S$ is independent)
This repeats until $S$ is exhausted (as you replace elements of $T$ with elements of $S$)

Hence

$$m\le n$$

Link to original

![[20 - Bases#^949f6f|^949f6f]]

Row Rank (using Dimension)

Row Rank of a matrix is the dimension of the row space
Also the number of non-zero rows of RREF of the matrix

Link to original

Basis of Row Space

The non-zero rows of a matrix in RRE form

Link to original

---

5.1 Subspaces and Dimension

Spanning Sets contain a basis

Let $V$ be a vector space over $\mathbf{F}$ and $S$ be a finite spanning set then

$$S\text{ contains a basis }$$

Proof

Let $S$ be a finite spanning set for $V$
Take $T\subseteq S$ such that $T$ is linearly independent (and hence $T$ is the largest such set)

Suppose for contradiction that $⟨T⟩\ne V$
Since $⟨S⟩=V$ then there exists $v\in S\setminus ⟨T⟩$

By Expansion of Linearly Independent Sets,

$$T\cap \{v\}\text{ is linearly independent }\text{ and }T\cap \{v\}\subseteq S$$

With

$$|T\cap \{v\}|>|T|$$

Which is a contradiction of the maximality of $T$, so $T$ spans $V$ and hence linearly independent and thus a basis.

Link to original

Dimension of Subspaces

Let $U$ be a subspace of a finite-dimensional vector space $V$
Then $U$ is finite-dimensional and

$$\dim U=\dim U$$

However if $\dim U=\dim V$ then

$$U=V$$

Proof

Let $n=\dim V$
By 05 - Size Inequality for Independent vs Spanning Sets then each linearly independent subset of $V$ has size at most $n$
Let $S$ be a largest linearly independent set contained in $U$ ($S\subseteq U\subseteq V$) hence

$$|S|\le n$$

Suppose for a contradiction that $⟨S⟩\ne U$ then there exists $u\in U\setminus ⟨S⟩$
By Extension of a Linearly Independent Set then $S\cup \{u\}$ is linearly independent and

$$|S\cup \{u\}|>|S|$$

This is a contradiction for the definition of $S$ so $U=⟨S⟩$
As $S$ is linearly independent then $S$ is a basis of $U$ so

$$|S|\le n$$

---

Suppose $\dim U=\dim V$ and $U\ne V$
Then there exists $v\in V\setminus U$
Hence $v$ may be added to the basis of $U$ to create a linearly independent subset of $V$

$$\dim U+1=\dim V+1$$

Which is a contradiction so $\dim U=\dim V$ implies $U=V$

Link to original

Linearly Independent Sets are a subset of a Basis

Let $V$ be a finite-dimensional vector space over $\mathbf{F}$
Let $S$ be a linearly independent set
Then

$$\text{there exists basis }B\text{ such that }S\subseteq B$$

Proof

If $⟨S⟩=V$ then done as $S$ is linearly independent and spanning so a basis with $S\subseteq S$

If $⟨S⟩\ne V$ then extend $S$ to $S_1=S\cup \{u_1\}$ where $u_1\in V\setminus ⟨S⟩$ (a larger linearly independent set)

• If $⟨S_1⟩=V$ then $S_1$ is a basis with $S\subseteq S_1$
• If not then we repeat this until $⟨S_k⟩=V$ (so that $S_k$ is a basis)
• This cannot continue infinitely as the maximum linearly independent subset of $V$ contains at most $\dim V$ elements so $k\le \dim V$

Link to original

Alternate Definition of a Basis (using Linearly Independency)

Maximal Linearly Independent Subset of a finite-dimensional vector space

Proof

Let $S$ be a maximal linearly independent subset of a finite-dimensional vector space $V$
If $⟨S⟩\ne V$ then by Extending a linearly independent set with

$$S_1=S\cup \{u_1\}\text{ where }{u}_1\in V\setminus ⟨S⟩$$

which is still linearly independent

This contradicts the maximality of $S$ so $⟨S⟩=V$

Link to original

Alternate Definition of a Basis (using Span)

Minimal Spanning subset of a finite-dimensional vector space

Proof

Let $S$ be a minimal spanning set of a finite-dimensional vector space $V$

If $S$ is not linearly independent then there exists

$$v\in S\text{ that is a linear combination of }S\setminus \{v\}$$

However $S\setminus \{v\}$ is linearly independent
As shown in Extension of a linearly independent set then $S\setminus \{v\}$ is still spanning
This contradicts the minimality of $S$ hence $S$ is a basis

Link to original

Finding a basis for a finite set of vectors in ${\mathbb{R}}^n$

Suppose the set of vectors $S=\{v_1,v_2,\cdots ,v_m\}$
Define

$$A=\left(\begin{array}{cccc}\uparrow & \uparrow & & \uparrow \\ v_1& v_2& \cdots & v_m\\ \downarrow & \downarrow & & \downarrow \end{array}\right)$$

So $⟨S⟩=\mathrm{Row}(A)$
As applying EROs does not change row space then

$$\mathrm{Row}(A)=\mathrm{Row}(\mathrm{RRE}(A))$$

Hence the basis of $⟨S⟩$ is the

$$\text{non-zero rows of }\mathrm{RRE}(A)$$

Link to original

---

5.2 The Dimension Formula

06 - Dimension Formula

Dimension Formula

Let $U,W$ be subspaces of a finite-dimensional vector space $V$ over $\mathbf{F}$ then

$$\dim (U+W)+\dim (U\cap W)=\dim U+\dim W$$

Proof

Take a basis $v_1,v_2,\cdots ,v_m$ of $U\cap W$
As $U\cap W\le U$ and $U\cap W\le W$ then by Spanning Sets containing a Basis
We can separately extend this set to a basis

$$v_1,\cdots ,v_m,u_1,\cdots ,u_p\text{ of }U$$ $$v_1,\cdots ,v_m,w_1,\cdots ,w_q\text{ of }W$$

Hence we can see that

$$\dim (U\cap W)=m,\dim U=m+p,\dim W=m+q$$

(Now we need to show that $S=v_1,\cdots ,v_m,u_1,\cdots ,u_p,w_1,\cdots ,w_q$ is a basis of $U+W$)
Looking at the number of elements in $S$ we know that

$$\begin{array}{rl}m+p+q& =(m+p)+(m+q)-m\\ & \\ & =\dim U+\dim W-\dim (U\cap W)\end{array}$$

$S$ is spanning:
For $x\in U+W$ with $x=u+w$ for some $u\in U,w\in W$ then

$$\begin{array}{rl}u& ={\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m+{\alpha }_1^{\prime }{u}_1+\cdots +{\alpha }_p^{\prime }{u}_p\\ w& ={\beta }_1{v}_1+\cdots +{\beta }_m{v}_m+{\beta }_1^{\prime }{w}_1+\cdots +{\beta }_q^{\prime }{w}_q\end{array}$$

for some scalars ${\alpha }_i,{\alpha }_i^{\prime },{\beta }_i,{\beta }_i^{\prime }\in \mathbf{F}$ then

$$x=u+w=({\alpha }_1+{\beta }_1)v_1+\cdots +({\alpha }_m+{\beta }_m)v_m+{\alpha }_1^{\prime }{u}_1+\cdots +{\alpha }_p^{\prime }{u}_p+{\beta }_1^{\prime }{w}_1+\cdots +{\beta }_q^{\prime }{w}_q\in ⟨S⟩$$

hence showing that $⟨S⟩=U+W$

$S$ is linearly independent
Take ${\alpha }_1,\cdots ,{\alpha }_m,{\beta }_1,\cdots ,{\beta }_p,{\gamma }_1,\cdots ,{\gamma }_q\in \mathbf{F}$ such that

$${\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m+{\beta }_1{u}_1+\cdots +{\beta }_p{u}_p+{\gamma }_1{w}_1+\cdots +{\gamma }_q{w}_q=0$$

Then

$${\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m+{\beta }_1{u}_1+\cdots +{\beta }_p{u}_p=-({\gamma }_1{w}_1+\cdots +{\gamma }_q{w}_q)$$

The LHS vector is in $U$ , and RHS vector is in $W$, hence they are both in $U\cap W$

As $v_1,\cdots ,v_m$ form a basis of $U\cap W$, there are ${\lambda }_1,\cdots ,{\lambda }_m\in \mathbf{F}$ such that

$$-({\gamma }_1{w}_1+\cdots +{\gamma }_q{w}_q)={\lambda }_1{v}_1+\cdots +{\lambda }_m{v}_m$$

which rearranges to

$${\gamma }_1{w}_1+\cdots +{\gamma }_q{w}_q+{\lambda }_1{v}_1+\cdots +{\lambda }_m{v}_m=0$$

But $\{v_1,\cdots ,v_m,w_1,\cdots ,w_q\}$ is linearly independent (basis for $W$) so each ${\gamma }_i=0$
Hence

$${\alpha }_1{v}_1+\cdots +{\alpha }_m{v}_m+{\beta }_1{u}_1+\cdots +{\beta }_p{u}_p=0$$

But $\{v_1,\cdots ,v_m,u_1,\cdots ,u_p\}$ is linearly independent (basis for $U$) so that ${\alpha }_i=0,{\beta }_i=0$

Hence $S$ is linearly independent and so $S$ is a basis for $U+W$

Link to original

Direct Sum

Let $U,W$ be subspaces of a vector space $V$

If $U\cap W=\{0_V\}$ and $U+W=V$
Then

$$V\text{ is the direct sum of }U\text{ and }W⟹V=U\oplus W$$

Link to original

Equivalent Statement for Direct Sums

Let $U,W$ be subspaces of a finite-dimensional vector space $V$

1. $V=U\oplus W$
2. Every $v\in V$ has a unique expression as $u+w$ for $u\in U$ and $w\in W$
3. $\dim V=\dim U+\dim W$ and ${} V = U + W
4. $\dim V=\dim U+\dim W$ and $U\cap W=\{0_V\}$
5. If $u_1,\cdots ,u_m$ is a basis for $U$ and $w_1,\cdots ,w_n$ is a basis for $W$ then

$$u_1,\cdots ,u_m,w_1,\cdots ,w_n\text{ is a basis for }V$$

Proof

TODO

Link to original

Direct Sums on multiple Subspaces / Vector Spaces

1. Internal Direct Sum
   Vector space $V$ is a direct sum of sum of subspaces $X_1,\cdots ,X_k\le V$
   If every $v\in V$ can be uniquely written

$$v=x_1+x_2+\cdots +x_k\text{ where }{x}_i\in X_i\text{ for all }i$$

The general expression is the general form of (2) from the above

2. External Direct Sum
   Given vector spaces $V_1,\cdots ,V_k$ then the external direct sum

$$V_1\oplus V_2\oplus \cdots \oplus V_k$$

has the Cartesian product $V_1\times V_2\times \cdots \times V_k$ as the underlying set with
Addition and Scalar Multiplication defined component wise with

$$\begin{array}{rl}(v_1,\cdots ,v_k)+(w_1,\cdots ,w_k)& =(v_1+w_1,\cdots ,v_k+w_k)\\ \alpha \cdot (v_1,\cdots ,v_k)& =(\alpha \cdot v_1,\cdots ,\alpha \cdot v_k)\end{array}$$

Link to original