i.

Suppose \(T\) is linearly independent, and \(S\) is a subset of \(T\). For pairwise distinct vectors \(\Vect{a}_1,\dots ,\Vect{a}_r\) in \(S\) consider the vector equation

\(t_1 \Vect{a}_1+ \cdots + t_r \Vect{a}_r\)

\(=\)

\(\Vect{0}\)

It follows that \(t_1=\cdots =t_r=0\) because \(\Vect{a}_1,\dots ,\Vect{a}_r\) also belong to the linearly independent set \(T\).

ii.

Let \(T\DefEq S\cup \Set{ \Vect{b} }\). We show first that linear independence of \(T\) implies that \(\Vect{b}\) is not in \(\span(S)\). We argue by contradiction: Suppose \(\Vect{b}\)is in \(\span(S)\). Then

\(\Vect{b}\)

\(=\)

\(t_1 \Vect{a}_1 + \cdots + t_r \Vect{a}_r\)

for pairwise distinct vectors \(\Vect{a}_1,\dots ,\Vect{a}_r\) in \(S\) and suitable numbers \(t_1,\dots ,t_m\). But then

\((-1)\Vect{b}\ +\ t_1 \Vect{a}_1 + \cdots + t_r \Vect{a}_r\)

\(=\)

\(\Vect{0}\)

implying that \(\Vect{0}\) is a linear combination of vectors in \(T\) for which not all coefficients are 0; a contradiction to the assumption that \(T\) is linearly independent. Therefore \(\Vect{b}\) cannot be in \(\span(S)\).

Consider now the case where \(\Vect{b}\) is not in \(\span(S)\). We need to show that \(T\) is linearly independent. Suppose the desired conclusion is not true; i.e. \(T\) is linearly dependent. Then there exists a linear combination

\(t_1 \Vect{a}_1 + \cdots + t_r \Vect{a}_r\ +\ u \Vect{b}\)

\(=\)

\(\Vect{0}\)

in which the vectors on the left are pairwise distinct and at least one coefficient is not 0. If \(u\neq 0\), we find

\(\Vect{b}\)

\(=\)

\((-1/u)\cdot (t_1 \Vect{a}_r + \cdots + t_r \Vect{a}_r)\)

implying that \(\Vect{b}\) is a linear combination of vectors from \(S\); a contradiction to the assumption that \(\Vect{b}\) is not in \(\span(S)\). The case ‘\(u=0\)’ is impossible. For, if \(u=0\), we would have \(t_1 \Vect{a}_r+\cdots + t_r \Vect{a}_r=\Vect{0}\), with at least one nonzero coefficient; a contradiction to the assumption that \(S\) is linearly independent.

In either case, the assumption ‘\(T\) is linearly dependent’ leads to a contradiction. Therefore \(T\) must be linearly independent. The proof of the proposition is complete.

iii.

We know that each of the vectors \(\Vect{b}_i\) can be expressed in some way as a linear combination of the vectors \(\Vect{a}_1,\dots ,\Vect{a}_m\):

\(\Vect{b}_i\)

\(=\)

\(t_{1i}\Vect{a}_i + \cdots + t_{mi}\Vect{a}_m\)

In addition, we know that the vector equation

\(s_1 \Vect{b}_1 + \cdots s_n \Vect{b}_n\)

\(=\)

\(0\)

has exactly one solution , namely \(s_1=\dots = s_n = 0\). This implies

\(s_1(t_{11} \Vect{a}_1+ \cdots + t_{m1} \Vect{a}_m) + \cdots + s_n( t_{1n}\Vect{a}_1 + \cdots + t_{mn}\Vect{a}_m)\)	\(=\)	\(\Vect{0}\)
\((s_1 t_{11} +\cdots + s_n t_{1n}) \Vect{a}_1 + \cdots + (s_1 t_{m1}+\cdots + s_n t_{mn}) \Vect{a}_m\)	\(=\)	\(\Vect{0}\)

The number \(s_1,\dots ,s_n\) satisfy this latter vector equation if and only if they solve the homogeneous system of linear equations below.

\[ \begin{array}{rcl} \left[ \begin{array}{ccc} t_{11} & \cdots & t_{1n} \\ \vdots & \ddots & \vdots \\ t_{m1} & \cdots & t_{mn} \end{array} \right] \left[ \begin{array}{c} s_1 \\ \vdots \\ s_n \end{array} \right] & = & \left[ \begin{array}{c} 0 \\ \vdots \\ 0 \end{array} \right] \\ \Mtrx{T} \Vect{s} & = & \Vect{0} \end{array} \]

Given that \(s_1=\cdots = s_n=0\) is the only solution of this system, we have

\[0 = \text{number of free variables} = n - \Rnk{T} \geq n-m\]

This gives \(n\leq m\) as claimed.