5. Vector spaces and linear combinations

Part 1.: problems, solutions.
Part 2.: problems, solutions.

Vector spaces

Generally speaking a vector space over a field K is a ,,space” consisting of vectors, which can be:

  • added and addition is associative ((u+v)+w=u+(v+w)) and commutative (u+v=v+u)
  • multiplied by a number from K and multiplication is distributive with respect to the addition(a(v+w)=av+aw), and with respect to the addition of numbers ((a+b)v=av+bv) and compatible with multiplication of numbers (a(bv)=(ab)v, and 1v=v)

in which there exists a zero vector 0 such that v+0=v, for any vector v and for each vector v there exists a vector w (inverse to v) such that v+w=0.

The plane is a classic example of a vector space over reals. Vectors have a form of a pair of numbers (x,y), and can be added one to another (x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2) and multiplied by a number a\cdot(x,y)=(ax,ay). There exists a zero vector (0,0) and for each vector (x,y) there is an inverse vector, (-x,-y).

But obviously a space consisting of vectors of the form of sequence of larger number of numbers over a given field K, e.g. 4, (x,y,z,t) is also a vector space, called K^n. Although it is not easy to imagine this space geometrically, addition and multiplication works in the same way as in the two-dimensional case.

But vector spaces can also be constructed in other different ways. It is easy to check that M_{n\times m}(K) — the set of all matrices n\times m with coefficients in field K, K^\infty — the set of infinite sequences with values in K, K[x] — the set of all polynomials over K and F(X,K) — the set of all functions from a set X into field K are all vector spaces over K. Indeed, for every of these sets operations of addition and multiplication by an element of the field can be easily defined in a natural way.

Vector subspaces

A vector subspace is a subset X of a vector space closed under the operations on vectors, meaning that if vectors u,v are in X, then u+v is also in X and for any number a, also au is in X.

To prove that a subset is a vector subspace we have to prove that for any two vectors in this subset their sum is also in this subset and that for any vector in the subset and any number, their multiplication is in the subset. To prove that a subset is not a vector subspace it suffices to find two vectors in the subset with the sum outside it or a vector in the subset and a number such that their multiplication does not belong to the subset.

For example, the line y=0 is a vector subspace of the plane, since if u,v belong to this line, then they are of form (x_1,0) i (x_2,0) and their sum is (x_1+x_2,0) and also belongs to the line. Similarly for every number a, a(x_1,0)=(ax_1,0) belongs to this line.

On the other hand the set \{(x,y)\colon x\geq0\} is not a vector subspace, because vector (1,0), which is in the set, multiplied by -1 gives (-1,0), which is not in the set.

The smallest subspace in any vector space is the zero subspace consisting only of the zero vector.

K[x]_n — the set of all polynomials over K of degree less or equal to n is an interesting example of a subspace of K[x]. Indeed, after adding two polynomials from this subset we get a polynomial still in the subset. The same happens with multiplication by an element of K.

Linear combinations

Given a finite set of vectors v_1,v_2,\ldots v_n, any vector of form a_1v_1+a_2v_2+\ldots a_nv_n, where a_1,a_2,\ldots a_n are some numbers is called their linear combination. For example vector (-2,1) is a linear combination of vectors (1,1) and (2,1) because (-2,1)=4(1,1)-3(2,1). How to calculate those coefficients without simply guessing them? Notice that we look for numbers a,b, such that a(1,1)+b(2,1)=(-2,1). This is actually a system of two linear equations:

    \[\begin{cases}a+2b=-2\\a+b=1\end{cases}\]

it suffices to solve it:

    \[\left[\begin{array}{cc|c}1&2&-2\\1&1&1\end{array}\right]\underrightarrow{w_2-w_1} \left[\begin{array}{cc|c}1&2&-2\\0&-1&3\end{array}\right] \underrightarrow{(-1)\cdot w_2}\]

    \[\left[\begin{array}{cc|c}1&2&-2\\0&1&-3\end{array}\right]\underrightarrow{w_1-2w_2}\left[\begin{array}{cc|c}1&0&4\\0&1&-3\end{array}\right]\]

so a=4,b=-3. If this system were contradictory, it would mean that our vector is not a linear combination of those two vectors.

The set of all linear combinations of vectors v_1,\ldots, v_n is denoted as \text{lin}(v_1,\ldots,v_n).

Linear independence

A set of vectors will be called linearly independent, if none of them is a linear combination of others. It is quite an impractical definition, because to check whether a set of four vectors is linearly independent directly from this definition we have to check that four systems of equations are contradictory. We need a different but equivalent definition.

Notice that if a vector is a linear combination of others, e.g. v_5=a_1 v_1+a_2 v_3+a_3 v_3+a_4 v_4, then the zero vector can be written as a_1 v_1+a_2 v_3+a_3 v_3+a_4 v_4 + (-1)v_5, so the zero vector is a linear combination of vectors from our set in which at least one coefficient is non-zero. It seems that we are close to the another definition of linear independence: a set of vectors is linearly independent, if in every their combination giving the zero vector all the coefficients are zeros. In other words the only way to get the zero vector is the trivial way: multiplying them all by zero.

How to check that a given set of vectors is linearly independent? Obviously we have to calculate the coefficients of their linear combination giving the zero vector (if the only solution is that all the coefficients are zero, then the set is linearly independent). So we need to check whether a system of linear equations has only one solution.

For example, let us check whether (1,1), (2,1) are linearly independent. We solve a system of equations:

    \[\left[\begin{array}{cc|c}1&2&0\\1&1&0\end{array}\right]\underrightarrow{w_2-w_1} \left[\begin{array}{cc|c}1&2&-2\\0&-1&3\end{array}\right]\]

We already know that the system has only one solution because we have a stair in every row. Therefore this set of vectors is linearly independent.

There is also a second method of checking whether a set of vector is linearly independent. Notice that the operations on rows of a matrix are just creating linear combinations of the vectors written in the rows of the matrix. If we manage to get a row of zeros, it means we have a non-trivial linear combination of rows giving the zero vector, and so the set of vectors written in the rows is not linearly independent. Let us check whether (1,2,1),(-2,0,-2),(1,3,1) are linearly independent.

    \[\left[\begin{array}{ccc}1&2&1\\-2&0&-2\\1&3&1\end{array}\right]\underrightarrow{w_2+2w_1, w_3-w_1}\left[\begin{array}{ccc}1&2&1\\0&4&0\\0&1&0\end{array}\right]\underrightarrow{w_2\leftrightarrow w_3}\]

    \[\left[\begin{array}{ccc}1&2&1\\0&1&0\\0&4&0\end{array}\right]\underrightarrow{w_3-4 w_2}\left[\begin{array}{ccc}1&2&1\\0&1&0\\0&0&0\end{array}\right]\]

we get a row of zeros, so (1,2,1),(-2,0,-2),(1,3,1) are not linearly independent.

Steinitz Theorem

An important property of linearly independent systems of vectors is described by Steinitz Theorem. If a system of vectors v_1,\ldots, v_k is linearly independent and V=\text{lin}(w_1,\ldots,w_m), then k\leq m, and moreover we can choose i_1,\ldots, i_{m-k}\in\{1,\ldots, m\} such that

    \[\text{lin}(w_1,\ldots, w_m)=\text{lin}(v_1,\ldots, v_k, w_{i_1},\ldots, w_{i_{m-k}}).\]