Linear Independence

Covector

$\mathbf{v}=\left(\begin{array}{c}1\\ 2\end{array}\right)$, then ${\mathbf{v}}^{\top }=\left(\begin{array}{cc}1& 2\end{array}\right)$.

$${\mathbf{v}}^{\top }\mathbf{w}=\sum _{i=1}^m{v}_i{w}_i=\mathbf{v}\cdot \mathbf{w};\in \mathbb{R}$$

Definition 1.21

Linear Algebra ETH, p.36

Vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n\in {\mathbb{R}}^m$ are linearly dependent if at least one of them is a linear combination of the others, i.e. there is an index $k\in [n]$ and scalars ${\lambda }_j$ such that ${\mathbf{v}}_k={\sum }_{j=1,j\ne k}^n{\lambda }_j{\mathbf{v}}_j$ . Otherwise, ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ are linearly independent

Drei Vektoren im ${\mathbb{R}}^2$ sind immer linear abhängig: entweder sind zwei bereits kollinear, oder der dritte ist eine Linearkombination der beiden ersten

Special

linear abhängig:

• $\mathbf{v}=0$
• $\dots ,0,\dots$
• $\dots ,\mathbf{v}\dots ,\mathbf{v}\dots$

linear unabhängig:

• $\mathbf{v}\ne 0$
• empty sequence: $()$ Es gibt kein $k\in [n]$, deswegen linear independent according to the definition above

Equivalent Statements to linear dependence

1. At least one of the vectors is a linear combination of the other ones. (see Definition 1.21)
2. There are scalars ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ besides $0,0,...,0$ such that ${\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j=0$. We also say that $0$ is a nontrivial linear combination of the vectors.
3. At least one of the vectors is a linear combination of the previous ones.

Proof idea to proof: $S_1⟹S_2⟹S_3⟹S_1$

$S_1⟹S_2$ Sei ${\mathbf{v}}_k={\sum }_{j=1,j\ne k}^n{\lambda }_j{\mathbf{v}}_j$, setze ${\lambda }_k=-1$. Dann ${\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j=0$ und ${\lambda }_k\ne 0$, also gilt $S_2$

$S_2⟹S_3$ Sei $k$ der größte Index mit ${\lambda }_k\ne 0$ : Dann ${\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j=0$ $⟹{\mathbf{v}}_k={\sum }_{j=0}^{k-1}\left(-\frac{{\lambda }_j}{{\lambda }_k}\right){\mathbf{v}}_{\mathbf{j}}⟹S_3$

$S_3⟹S_1$ Eine Linearkombination der vorherigen ist auch eine Linearkombination der anderen.

Equivalent Statements to linear independence

1. None of the vectors is a linear combination of the other ones. (see Definition 1.21)
2. There are no scalars ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ besides $0,0,...,0$ such that ${\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j=0$. We also say that $0$ can only be written as a trivial linear combination of the vectors.
   1. $A\mathbf{x}=0$ has only the trivial solution $\mathbf{x}=0$
3. None of the vectors is a linear combination of the previous ones.

Note that: a linear combination of linearly independent vectors can be written as a linear combination in only one way

Span of vectors

Spann von Vektoren: Menge aller Linearkombinationen

Definition of Span 1.25

Let ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n\in {\mathbb{R}}^m$. Their span is the set of all linear combinations.

Example

$\mathbf{Span}({\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n):=\left\{{\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j:{\lambda }_j\in \mathbb{R},\forall j\in [n]\right\}$

Lemma 1.26

Let ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{\mathbf{n}}\in {\mathbb{R}}^m$, and let $\mathbf{v}\in {\mathbb{R}}^m$be a linear combination of ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_{\mathbf{n}}$ Then

$$\underset{S}{\underbrace{Span({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n)}}=\underset{T}{\underbrace{Span({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n,\mathbf{v})}}$$

Beweisidee:

• Jedes Element von $S$ ist auch in $T$ ($S$ ist Teilmenge von $T$)
• Jedes Element von $T$ ist auch in $S$ ($T$ ist Teilmenge von $S$) $⟹$ Dann haben wir $S=T$ Proof $S\subseteq T$: Jedes $\mathbf{w}\in S$ ist Linearkombination von ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ und deshalb auch eine Linearkombination von ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n,\mathbf{v}$ (plus $0\mathbf{v}$), also $\mathbf{w}\in T$

$T\subseteq S$ Jedes $\mathbf{w}\in T$ ist Linearkombination von ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n,\mathbf{v}$ d.h. $\mathbf{w}={\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j\lambda \mathbf{v}$ wir wissen $\mathbf{v}$ ist Linearkombination von ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ zusammen $\mathbf{w}={\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j\lambda \mathbf{v}+\lambda {\sum }_{j=1}^n{u}_j{v}_j$ $=\underset{\text{Linearkombination von }{\mathbf{v}}_1,\dots ,{\mathbf{v}}_{\mathbf{n}}}{\underbrace{\sum _{j=1}^n({\lambda }_j+\lambda u_j)v_j}}$

Lemma 1.28

See [LinArg assignment 1#6. Challenge 1.6]

Another Proof through Steinitz exchange lemma

Steinitz exchange lemma

(ii) means: one can enlarge $F$ by some elements from $G$ such that the result has at most the size of $G$ and also spans $V$

All bases have the same size

Link to original

• Proof