Vector spaces, linear mappings, and convexity

Jiří Lebl, Basic Analysis I–II, version 6.3. Free author edition of this section. Selection and attribution · Notation.

L8.1.13: Uniqueness of basis coordinates.

Proposition 8.1.13.

Suppose a vector space

X

has a basis

B = \{ x_1, x_2, \ldots, x_n \}\text{.}

Then every

y \in X

has a unique representation of the form

\begin{equation*} y = \sum_{k=1}^n a_k \, x_k \end{equation*}

for some scalars

a_1, a_2, \ldots, a_n\text{.}

Proof.

X

is the span of

B\text{,}

every

y \in X

is a linear combination of elements of

B\text{.}

Suppose

\begin{equation*} y = \sum_{k=1}^n a_k \, x_k = \sum_{k=1}^n b_k \, x_k . \end{equation*}

Then

\begin{equation*} \sum_{k=1}^n (a_k-b_k) x_k = 0 . \end{equation*}

By linear independence of the basis,

a_k = b_k

for all

k\text{,}

and so the representation is unique.

L8.1.14: All six finite-dimensional exchange, basis and subspace assertions.

Proposition 8.1.14.

Let

X

be a vector space and

d

a nonnegative integer.

If $X$ is spanned by $d$ vectors, then $\dim \, X \leq d\text{.}$
If $T$ is a linearly independent set and $v \in X \setminus \spn (T)\text{,}$ then $T \cup \{ v \}$ is linearly independent.
$\dim \, X = d$ if and only if $X$ has a basis of $d$ vectors. In particular, $\dim \, \R^n = n\text{.}$
If $Y \subset X$ is a vector subspace and $\dim \, X = d\text{,}$ then $\dim \, Y \leq d\text{.}$
If $\dim \, X = d$ and a set $T$ of $d$ vectors spans $X\text{,}$ then $T$ is linearly independent.
If $\dim \, X = d$ and a set $T$ of $m$ vectors is linearly independent, then there is a set $S$ of $d-m$ vectors such that $T \cup S$ is a basis of $X\text{.}$

Proof.

All statements hold trivially when

d=0\text{,}

so assume

d \geq 1\text{.}

We start with i. Suppose

S \coloneqq \{ x_1 , x_2, \ldots, x_d \}

spans

X\text{,}

and

T \coloneqq \{ y_1, y_2, \ldots, y_m \}

is a linearly independent subset of

X\text{.}

We wish to show that

m \leq d\text{.}

S

spans

X\text{,}

write

\begin{equation*} y_1 = \sum_{k=1}^d a_{k,1} x_k , \end{equation*}

for some numbers

a_{1,1},a_{2,1},\ldots,a_{d,1}\text{.}

One of the

a_{k,1}

is nonzero, otherwise

y_1

would be zero. Without loss of generality, suppose

a_{1,1} \neq 0\text{.}

Solve

\begin{equation*} x_1 = \frac{1}{a_{1,1}} y_1 - \sum_{k=2}^d \frac{a_{k,1}}{a_{1,1}} x_k . \end{equation*}

In particular,

\{ y_1 , x_2, \ldots, x_d \}

spans

X\text{,}

since

x_1

can be obtained from

\{ y_1 , x_2, \ldots, x_d \}\text{.}

Therefore, there are some numbers

a_{1,2},a_{2,2},\ldots,a_{d,2}\text{,}

such that

\begin{equation*} y_2 = a_{1,2} y_1 + \sum_{k=2}^d a_{k,2} x_k . \end{equation*}

T

is linearly independent—and so

\{ y_1, y_2 \}

is linearly independent—one of the

a_{k,2}

for

k \geq 2

must be nonzero. Without loss of generality suppose

a_{2,2} \neq 0\text{.}

Solve

\begin{equation*} x_2 = \frac{1}{a_{2,2}} y_2 - \frac{a_{1,2}}{a_{2,2}} y_1 - \sum_{k=3}^d \frac{a_{k,2}}{a_{2,2}} x_k . \end{equation*}

In particular,

\{ y_1 , y_2, x_3, \ldots, x_d \}

spans

X\text{.}

We continue this procedure. If

m < d\text{,}

we are done. Suppose

m \geq d\text{.}

After

d

steps, we obtain that

\{ y_1 , y_2, \ldots, y_d \}

spans

X\text{.}

Any other vector

v

X

is a linear combination of

\{ y_1 , y_2, \ldots, y_d \}

and hence cannot be in

T

T

is linearly independent. So

m = d\text{.}

We continue with ii. Suppose

T = \{x_1,x_2,\ldots,x_m\}

is linearly independent, does not span

X\text{,}

and

v \in X \setminus \spn (T)\text{.}

Suppose

a_1 x_1 + a_2 x_2 + \cdots + a_m x_m + a_{m+1} v = 0

for some scalars

a_1,a_2,\ldots,a_{m+1}\text{.}

a_{m+1} \neq 0\text{,}

then

v

would be a linear combination of

T\text{,}

a_{m+1} = 0\text{.}

Then, as

T

is linearly independent,

a_1=a_2=\cdots=a_m = 0\text{.}

T \cup \{ v \}

is linearly independent.

We move to iii. If

\dim \, X = d\text{,}

then there must exist some linearly independent set

T

d

vectors, and

T

must span

X\text{,}

otherwise we could choose a larger set of linearly independent vectors via ii. So we have a basis of

d

vectors. On the other hand, if we have a basis of

d

vectors, the dimension is at least

d

as a basis is linearly independent. A basis also spans

X\text{,}

and so by i we know that dimension is at most

d\text{.}

Hence the dimension of

X

must equal

d\text{.}

The “in particular” follows by noting that

\{ e_1, e_2, \ldots, e_n \}

is a basis of

\R^n\text{.}

To see iv, suppose

Y \subset X

is a vector subspace, where

\dim \, X = d\text{.}

X

cannot contain

d+1

linearly independent vectors, neither can

Y\text{.}

For v, suppose

T

is a set of

m

vectors that is linearly dependent and spans

X\text{.}

We will show that

m > d\text{.}

One of the vectors is a linear combination of the others. If we remove it from

T\text{,}

we obtain a set of

m-1

vectors that still span

X\text{.}

Hence

d = \dim \, X \leq m-1

by i.

For vi suppose

T = \{ x_1, x_2, \ldots, x_m \}

is a linearly independent set. First,

m \leq d

by definition of dimension. If

m=d\text{,}

the set

T

must span

X

as in the proof of iii, otherwise we could add another vector to

T\text{.}

m < d\text{,}

T

cannot span

X

by iii. So find

v

not in the span of

T\text{.}

Via ii, the set

T \cup \{ v \}

is a linearly independent set of

m+1

elements. Therefore, we repeat this procedure

d-m

times to find a set of

d

linearly independent vectors. Again, they must span

X\text{,}

otherwise we could add yet another vector.

L8.1.16: Inverse linearity, with the other four parts completed locally.

Proposition 8.1.16.

Let

X\text{,}

Y\text{,}

and

Z

be vector spaces.

If $A \in L(X,Y)\text{,}$ then $A0 = 0\text{.}$
If $A,B \in L(X,Y)\text{,}$ then $A+B \in L(X,Y)\text{.}$
If $A \in L(X,Y)$ and $a \in \R\text{,}$ then $aA \in L(X,Y)\text{.}$
If $A \in L(Y,Z)$ and $B \in L(X,Y)\text{,}$ then $AB \in L(X,Z)\text{.}$
If $A \in L(X,Y)$ is invertible, then $A^{-1} \in L(Y,X)\text{.}$

Proof.

We leave the first four items as a quick exercise, Exercise 8.1.20. Let us prove the last item. Let

a \in \R

and

y \in Y\text{.}

A

is onto, there is an

x \in X

such that

y = Ax\text{.}

As it is also one-to-one,

A^{-1}(Az) = z

for all

z \in X\text{.}

\begin{equation*} A^{-1}(ay) = A^{-1}(aAx) = A^{-1}\bigl(A(ax)\bigr) = ax = aA^{-1}(y). \end{equation*}

Similarly, let

y_1,y_2 \in Y

and

x_1, x_2 \in X

be such that

Ax_1 = y_1

and

Ax_2 = y_2\text{,}

then

\begin{equation*} A^{-1}(y_1+y_2) = A^{-1}(Ax_1+Ax_2) = A^{-1}\bigl(A(x_1+x_2)\bigr) = x_1+x_2 = A^{-1}(y_1) + A^{-1}(y_2). \qedhere \end{equation*}

L8.1.17: Determination and extension from basis values, including the omitted linearity check.

Proposition 8.1.17.

A \in L(X,Y)

is linear, then it is completely determined by its values on a basis of

X\text{.}

Furthermore, if

B

is a basis of

X\text{,}

then every function

\widetilde{A} \colon B \to Y

extends to a linear function

A

X\text{.}

Proof.

Let

\{ x_1, x_2, \ldots, x_n \}

be a basis of

X\text{,}

and let

y_k \coloneqq A x_k\text{.}

Every

x \in X

has a unique representation

\begin{equation*} x = \sum_{k=1}^n b_k \, x_k \end{equation*}

for some numbers

b_1,b_2,\ldots,b_n\text{.}

By linearity,

\begin{equation*} Ax = A\sum_{k=1}^n b_k x_k = \sum_{k=1}^n b_k \, Ax_k = \sum_{k=1}^n b_k \, y_k . \end{equation*}

The “furthermore” follows by setting

y_k \coloneqq \widetilde{A}(x_k)\text{,}

and then for

x = \sum_{k=1}^n b_k \, x_k\text{,}

defining the extension as

A(x) \coloneqq \sum_{k=1}^n b_k \, y_k\text{.}

The function is well-defined by uniqueness of the representation of

x\text{.}

We leave it to the reader to check that

A

is linear.

L8.1.18: Injectivity iff surjectivity for finite-dimensional endomorphisms.

Proposition 8.1.18.

X

is a finite-dimensional vector space and

A \in L(X)\text{,}

then

A

is one-to-one if and only if it is onto.

Proof.

Let

\{ x_1,x_2,\ldots,x_n \}

be a basis for

X\text{.}

First suppose

A

is one-to-one. Let

c_1,c_2,\ldots,c_n

be scalars such that

\begin{equation*} 0 = \sum_{k=1}^n c_k \, Ax_k = A\sum_{k=1}^n c_k \, x_k . \end{equation*}

A

is one-to-one, the only vector that is taken to 0 is 0 itself. Hence,

\begin{equation*} 0 = \sum_{k=1}^n c_k \, x_k, \end{equation*}

and so

c_k = 0

for all

k

\{ x_1,x_2,\ldots,x_n \}

is a basis. So

\{ Ax_1, Ax_2, \ldots, Ax_n \}

is linearly independent. By Proposition 8.1.14 and the fact that the dimension is

n\text{,}

we conclude

\{ Ax_1, Ax_2, \ldots, Ax_n \}

spans

X\text{.}

Consequently,

A

is onto, as any

y \in X

can be written as

\begin{equation*} y = \sum_{k=1}^n a_k \, Ax_k = A\sum_{k=1}^n a_k \, x_k . \end{equation*}

For the other direction, suppose

A

is onto. Suppose that for some

c_1,c_2,\ldots,c_n\text{,}

\begin{equation*} 0 = A\sum_{k=1}^n c_k \, x_k = \sum_{k=1}^n c_k \, Ax_k . \end{equation*}

A

is determined by the action on the basis,

\{ Ax_1, Ax_2, \ldots, Ax_n \}

spans

X\text{.}

So by Proposition 8.1.14, the set is linearly independent, and

c_k = 0

for all

k\text{.}

In other words, if

Ax = 0\text{,}

then

x=0\text{.}

Thus,

A

is one-to-one.