Fundamental Concepts in Linear Algebra

Theorem.

If a vector space has an \(\,n\)-element basis, then every set consisting of more than \(\,n\,\) vectors is linearly dependent.

Proof.

Let \(\ \mathcal{B}\,=\,(v_1,v_2,\ldots,v_n)\ \) be a basis of the space \(\,V(K).\ \)

We have to show that every set \(\ \mathcal{C}=(w_1,w_2,\ldots,w_p)\ \) with \(\ p>n\ \) is linearly dependent.

This condition means that there exists a non-trivial linear combination of vectors \(\ w_1,w_2,\ldots,w_p\ \) which is equal to a zero vector \(\,\theta,\ \) that is, the equation

(1)\[c_1\ w_1\ +\ c_2\ w_2\ +\ \ldots\ +\ c_p\ w_p\ =\ \theta\]

with coefficients \(\ c_1,\,c_2,\,\ldots,\,c_p\in K\ \,\) has a non-zero solution.

Each of the vectors \(\ w_j\ \) may be written as a linear combination of the basis vectors:

(2)\[w_j\ =\ \sum_{i\,=\,1}^n\ a_{ij}\,v_i\,,\qquad j=1,2,\ldots,p.\]

Here \(\ a_{1j},\,a_{2j},\,\ldots,\,a_{nj}\ \) are coefficients of a vector \(\ w_j\ \) in basis \(\ \mathcal{B},\quad j=1,2,\ldots,p.\)

We substitute (8) into (7) and write the left hand side of the equation (7) as a linear combination of the basis vectors:

\[ \begin{align}\begin{aligned}\sum_{j\,=\,1}^p\ c_j\,w_j\ \ =\ \ \sum_{j\,=\,1}^p\ c_j\;\left(\ \sum_{i\,=\,1}^n\ a_{ij}\,v_i\right)\ \ =\ \ \sum_{i\,=\,1}^n\ \left(\ \sum_{j\,=\,1}^p\ a_{ij}\,c_j\right)\ v_i\ \ =\\\ \ =\ \ \left(\ \sum_{j\,=\,1}^p\,a_{1j}\,c_j\right)\ v_1\ \ +\ \ \left(\ \sum_{j\,=\,1}^p\,a_{2j}\,c_j\right)\ v_2\ \ +\ \ \dots\ \ +\ \ \left(\ \sum_{j\,=\,1}^p\,a_{nj}\,c_j\right)\ v_n\ \ =\ \ \theta\,.\end{aligned}\end{align} \]

The basis vectors \(\ v_1,\,v_2,\,\ldots,\,v_n\ \) are linearly independent. Hence, if their linear combination gives a zero vector \(\,\theta ,\,\) then the coefficients must be equal to zero:

\[\sum_{j\,=\,1}^p\ a_{ij}\ c_j\ \,=\ \,0\,,\qquad i=1,2,\ldots,n.\]

Unfolding these equalities we obtain

\[\begin{split}\begin{array}{l} a_{11}\ c_1\ +\ \,a_{12}\ c_2\ +\ \,\dots\ \,+\ \,a_{1p}\ c_p\ \,=\ \ 0 \\ a_{21}\ c_1\ +\ \,a_{22}\ c_2\ +\ \,\dots\ \,+\ \,a_{2p}\ c_p\ \,=\ \ 0 \\ \ \ \dots\qquad\quad\dots\qquad\,\dots\qquad\ \dots\qquad\ \dots\quad \\ a_{n1}\ c_1\ +\ \,a_{n2}\ c_2\ +\ \,\dots\ \,+\ \,a_{np}\ c_p\ \,=\ \ 0 \end{array}\end{split}\]

a homogeneous system of \(\,n\,\) linear equations with \(\,p\,\) unknowns \(\ c_1,\,c_2,\,\ldots,\,c_p\,,\ \) where the number of equations is smaller than the number of unknowns.

Such a system has non-zero solutions. Indeed, if we solve this system by the Gauss elimination method, we perform elementary operations on rows of the coefficient matrix in order to bring it to the reduced row echelon form. Then the unknowns corresponding to the columns without leading unities are taken as parameters on which the other (i.e. corresponding to the columns with leading unities) unknowns depend.

The number of parameters is equal to a difference between the number of unknowns and the number of leading unities, and the second number (equal to the rank of the coefficient matrix) is not greater than the number of equations. If there are more unknowns than the number of equations, then the number of parameters is positive, and that is equivalent to the existence of non-zero solutions.

Corollary 1.

If a vector space has an \(\,n\)-element basis, then each basis of this space has \(\,n\ \) elements.

Suppose the space \(\,V(K)\,\) has two bases: basis \(\ \mathcal{B}\ \) with \(\,n\,\) elements and basis \(\ \mathcal{C}\ \) with \(\,m\,\) elements.

If \(\,n>m,\ \) then the set \(\ \mathcal{B}\ \) is linearly dependent (contradiction). \(\,\) Hence \(\ \,n\le m.\)

If \(\,m>n,\ \) then the set \(\ \mathcal{C}\ \) is linearly dependent (contradiction). \(\,\) Hence \(\ \,m\le n.\)

In this way \(\ \,n\le m\ \) and \(\ m\le n,\ \,\) and thus \(\ \,m=n.\)

Corollary 1. allows to introduce a notion of dimension for a vector space as the number of elements of any finite basis of this space (if such a finite basis exists). \(\\\)

Corollary 2.

In an \(\,n\)-dimensional vector space each set containing more than \(\,n\,\) vectors is linearly dependent.

Corollary 3.

In an \(\,n\)-dimensional vector space each linarly independent set \(\,n\,\) of vectors comprises a basis.

Indeed, Corollary 2. implies that such a linearly independent set of \(\,n\,\) vectors is a maximal linearly independent set, and thus a basis.