Raising the bar

Correctness of the space dimension definition

This proof has been taken from I. M. Gelfand, Lectures in Linear Algebra, 4th edition, 1970 (in Russian).

Lemma. Let $latex f_1,...,f_k$ be some vectors. Suppose that vectors $latex g_1,...,g_l$ are linearly independent and belong to the span $latex \text{span}(f_{1},...,f_{k}).$ Then $latex l\leq k.$

Proof. We prove the lemma by induction. Let $latex k=1.$ Then $latex l=1$ (linear dependence for an empty set of vectors is not defined) and the inequality $latex l\leq k$ is trivial.

Suppose the statement holds for $latex k-1$ and let us prove it for $latex k.$ Since $latex g_{1},...,g_{l}\in \text{span}(f_{1},...,f_{k}),$ we have

(1) $latex g_{1}=a_{11}f_{1}+...+a_{1k}f_{k} \\... \\
g_{l}=a_{l1}f_{1}+...+a_{lk}f_{k}.$

If all of $latex a_{1k},...,a_{lk}$ are zero, we have $latex g_{1},...,g_{l}\in \text{span}(f_{1},...,f_{k-1})$ and then by the induction assumption $latex l\leq k-1$ and, trivially, $latex l\leq k.$

Thus, we can assume that not all of $latex a_{1k},...,a_{lk}$ are zero. Suppose $latex a_{lk}\neq 0.$ Then we can solve the last equation in (1) for $latex f_{k}:$

(2) $latex f_{k}=\frac{1}{a_{lk}}g_{l}-\frac{1}{a_{lk}}\sum_{j=1}^{k-1}a_{l,j}f_{j}.$

Plugging this equation in the first equation in (1) we get

$latex g_{1}=a_{11}f_{1}+...+a_{1,k-1}f_{k-1}+a_{1k}\left( \frac{1}{a_{lk}}g_{l}-\frac{1}{a_{lk}}\sum_{j=1}^{k-1}a_{l,j}f_{j}\right) .$

Send $latex g_{l}$ to the left side; the remaining expression on the right side is a linear combination of $latex f_{1},...,f_{k-1}$; exact expressions of the coefficients $latex b_{1,j}$ of this linear combination don't matter. The result will be $latex g_{1}-\frac{a_{1k}}{a_{lk}}g_{l}=\sum_{j=1}^{k-1}b_{1,j}f_{j}.$ After doing the same with the first $latex l-1$ equations of (1) we get the system

$latex g_{1}-\frac{a_{1k}}{a_{lk}}g_{l}=\sum_{j=1}^{k-1}b_{1,j}f_{j},...,\ \
g_{l-1}-\frac{a_{l-1,k}}{a_{lk}}g_{l}=\sum_{j=1}^{k-1}b_{l-1,j}f_{j}.$

This shows that the vectors

$latex g_{1}^{\prime }=g_{1}-\frac{a_{1k}}{a_{lk}}g_{l},...,g_{l-1}^{\prime }=\
g_{l-1}-\frac{a_{l-1,k}}{a_{lk}}g_{l}$

belong to $latex \text{span}(f_{1},...,f_{k-1}).$ If they are linearly independent, we can use the induction assumption to conclude that $latex l-1\leq k-1,$ which will prove $latex l\leq k.$

Suppose with some $latex c_{i}$

$latex \sum_{i=1}^{l-1}c_{i}g_{i}^{\prime}=\sum_{i=1}^{l-1}c_{i}g_{i}-\sum_{i=1}^{l-1}c_{i}\frac{a_{i,k}}{a_{lk}}g_{l}=0.$

By the assumed linear independence of $latex g_{1},...,g_{l}$ this implies $latex c_{1}=...=c_{l-1}=0,$ so the system $latex g_{1}^{\prime },...,g_{l-1}^{\prime }$ is linearly independent.

Theorem. The definition of the space dimension is correct.

Proof. We write $latex \dim (L)=n$ if a) $latex L$ contains $latex n$ linearly independent vectors $latex x_{1},...,x_{n}$ and b) $latex L=\text{span}(x_{1},...,x_{n}).$ We need to prove that any system with properties a) and b) has the same number of vectors. Suppose $latex y_{1},...,y_{m}$ is another such system. Since $latex y_{1},...,y_{m}$ belong to $latex \text{span}(x_{1},...,x_{n}),$ by the lemma $latex m\leq n.$ Similarly, $latex n\leq m.$ So $latex n=m.$

← Previous: Basis and dimension | Next: Rank of a matrix and the rank-nullity theorem →

Get the PDF book “Matrix Algebra” on Lulu