A subspace \(U\) has many different spanning sets. We use the concept of linear independence to determine when sets of spanning vectors are the ‘most efficient’. In data terms, independence asks whether one feature direction is already built from the others.
A set of vectors \(\{ \mathbf{x}_1, \dots, \mathbf{x}_k \}\) in \(\R^n\) is said to be linearly independent, or simply independent if the only solution to the equation \(t_1 \mathbf{x}_1 + \dots + t_k \mathbf{x}_k = 0\) is trivial, i.e., \(t_1 = \cdots = t_k = 0\text{.}\)
A set of vectors \(\{ \mathbf{x}_1, \dots, \mathbf{x}_k \}\) in \(\R^n\) is linearly dependent if it is not linearly independent, i.e., if there exists scalars \(t_1,\dots,t_k\text{,}\) not all zero, such that \(t_1 \mathbf{x}_1 + \cdots + t_k \mathbf{x}_k = 0\text{.}\)
We need to determine the solutions to the equation \(t_1 \mathbf{v}_1 + t_2 \mathbf{v}_2 + t_3 \mathbf{v}_3 = \mathbf{0}\text{.}\) Expanding out this equation gives the system
There is one free variable corresponding to this matrix, which implies that there is one basic solution to the equation, and thus the system has a nontrivial solution. Thus the vectors are not linearly independent.
In matrix form: put the vectors \(\mathbf{x}_1,\dots,\mathbf{x}_k\) as the columns of a matrix \(M\text{.}\) Then \(\{ \mathbf{x}_1,\dots,\mathbf{x}_k \}\) is independent exactly when \(M\mathbf{c}=\mathbf{0}\) has only the trivial solution, equivalently when every column of \(M\) is a pivot column.
If \(\{ \mathbf{x}_1, \dots, \mathbf{x}_k \}\) is a linearly independent set of vectors in \(\R^n\text{,}\) then every vector in their span \(\spans \{ \mathbf{x}_1, \dots, \mathbf{x}_k \}\) has a unique representation as a linear combination of the \(\mathbf{x}_i\text{.}\)
But the vectors \(\mathbf{x}_1,\dots,\mathbf{x}_k\) are linearly independent, and so this equation has only a trivial solution. Thus \(a_1 - b_1, \dots, a_k - b_k = 0\text{,}\) i.e., \(a_1 = b_1, \dots, a_k = b_k\text{,}\) proving that the representation of \(\mathbf{x}\) as a linear combination is unique.
We could use row-reduction here, though in this case a more ad-hoc approach is more efficient. The third equation gives \(t_3 = 0\text{,}\) and once this is deduced the fourth equation gives \(t_1 = 0\text{.}\) Then the first equation gives \(t_2 = 0\text{.}\) Thus the only solution to the equation is the trivial solution, and so the vectors are linearly independent.
In geometry, we often describe lines as being ‘\(1\)-dimensional’, and planes as being ‘\(2\)-dimensional’. We can describe the notion of dimension more precisely using linear algebra.
Let \(U\) be a subspace of \(\R^n\text{.}\) If \(U\) is spanned by \(m\) vectors, and if \(U\) contains \(k\) linearly independent vectors, then \(k \leq m\text{.}\)
It is not possible. \(\R^3\) is spanned by \(3\) vectors (for example, the standard basis vectors), so by Theorem 2.4.5, any linearly independent subset of \(\R^3\) must contain at most \(3\) vectors.
If \(U\) is a subspace of \(\R^n\text{,}\) a set of vectors \(\{ \mathbf{x}_1, \dots, \mathbf{x}_m \}\) in \(U\) is called a basis of \(U\) if it satisfies the following two conditions:
\(\{ \mathbf{x}_1, \dots, \mathbf{x}_m \}\) is linearly independent.
If \(\{ \mathbf{v}_1, \dots, \mathbf{v}_m \}\) and \(\{ \mathbf{w}_1, \dots, \mathbf{w}_k \}\) are both bases for a subspace \(U\) of \(\R^n\text{,}\) then \(m = k\text{.}\)
The dimension of a non-zero subspace \(U\) of \(\R^n\) is the number of vectors in a basis for \(U\text{.}\) We often write \(\dimens(U)\) for the dimension of \(U\text{,}\) and if \(\dimens(U) = d\text{,}\) we say \(U\) is \(d\)-dimensional. By convention, the dimension of the trivial subspace \(\{ \mathbf{0} \}\) is zero.
The standard basis for \(\R^3\) is a basis, i.e., the set of three vectors \(\{ \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3 \}\) defined in Definition 1.3.8 is linearly independent and spans \(\R^3\text{.}\) Thus \(\R^3\) has dimension \(3\text{.}\)
is a basis for \(W\) since \(S\) is linearly independent (neither vector in \(S\) is the scalar multiple of the other). In the solution to Activity 2.3.6, we showed that these vectors span \(W\text{,}\) so \(S\) is a basis for \(W\text{.}\) Since \(S\) contains two vectors, \(\dimens(W) = 2\text{.}\)
Let \(U\) be a subspace of \(\R^n\) where \(\dimens(U) = m\) and let \(B = \{ \mathbf{x}_1, \dots, \mathbf{x}_m \}\) be a set of \(m\) vectors in \(U\text{.}\) Then \(B\) is linearly independent if and only if \(B\) spans \(U\text{.}\)
Suppose \(B\) is linearly independent and \(|B| = m = \dimens(U)\text{.}\) By Theorem 2.4.5, one cannot add any new vectors to the set \(B\) and remain linearly independent. But Fact 2.4.10 says that if \(B\) is not already a spanning set for \(U\text{,}\) one can add new vectors to \(B\) from \(U\text{,}\) and remain linearly independent. Thus \(B\) must be a basis.
Conversely, if \(B\) spans \(U\text{,}\) then by Fact 2.4.10 we can choose a subset of \(B\) which is a basis for \(U\text{.}\) But any proper subset of \(B\) contains fewer than \(m\) vectors, and thus by Theorem 2.4.7, cannot be a basis for \(U\text{.}\) Thus \(B\) is the only subset of itself that can be a basis, and because \(B\) must contain a basis, the set \(B\) must itself be a basis.
If \(\mathbf{v}\) and \(\mathbf{w}\) are nonzero vectors in \(\R^3\text{,}\) show that \(\{ \mathbf{v}, \mathbf{w} \}\) is dependent if and only if \(\mathbf{v}\) and \(\mathbf{w}\) are parallel, i.e., if one vector is a scalar multiple of the other.
If \(\mathbf{v}\) and \(\mathbf{w}\) are parallel, then one is a scalar multiple of the other, say \(\mathbf{v} = a \mathbf{w}\) for some scalar \(a\text{.}\) Then \(1 \mathbf{v} - a \mathbf{w} = 0\text{,}\) which is a nontrivial linear combination of \(\mathbf{v}\) and \(\mathbf{w}\text{,}\) so \(\{ \mathbf{v}, \mathbf{w} \}\) is dependent.
Conversely, if \(\{ \mathbf{v}, \mathbf{w} \}\) is dependent, then \(s \mathbf{v} + t \mathbf{w} = 0\) for some scalars \(s\) and \(t\text{,}\) where \(s \neq 0\) or \(t \neq 0\text{.}\) If, say, \(s \neq 0\text{,}\) then \(\mathbf{v} = -t/s \mathbf{w}\text{,}\) so \(\mathbf{v}\) and \(\mathbf{w}\) are parallel. A similar argument works if \(t \neq 0\text{.}\)
Let \(\mathbf{u},\mathbf{v}\text{,}\) and \(\mathbf{w}\) are non-zero vectors in \(\R^n\text{,}\) where \(\{ \mathbf{v}, \mathbf{w} \}\) is independent. Show that \(\{ \mathbf{u}, \mathbf{v}, \mathbf{w} \}\) is independent if and only if \(\mathbf{u}\) is not in the subspace \(M = \spans \{ \mathbf{v}, \mathbf{w}\}\text{.}\) See Figure 2.4.13 and Figure 2.4.14.
A pale blue parallelogram labeled \(M\) represents the plane spanned by \(\mathbf{v}\) and \(\mathbf{w}\text{,}\) both drawn from the origin and lying in the plane. A red vector \(\mathbf{u}\) starts at the origin and points upward outside the plane. The label \(\mathbf{u}\notin M\) emphasizes that \(\mathbf{u}\) is not in the span of the other two vectors.
A pale blue parallelogram labeled \(M\) represents the plane spanned by \(\mathbf{v}\) and \(\mathbf{w}\text{.}\) The red vector \(\mathbf{u}\) also lies inside the same plane and starts at the origin with the other two vectors. The label \(\mathbf{u}\in M\) indicates that \(\mathbf{u}\) belongs to the span of \(\mathbf{v}\) and \(\mathbf{w}\text{.}\)
If \(\{ \mathbf{u}, \mathbf{v}, \mathbf{w} \}\) is independent, suppose that \(\mathbf{u}\) is in \(M = \spans \{ \mathbf{v}, \mathbf{w} \}\text{,}\) say, that \(\mathbf{u} = a \mathbf{v} + b \mathbf{w}\) for some scalars \(a\) and \(b\text{.}\) Then \(1 \mathbf{u} - a \mathbf{v} - b \mathbf{w} = 0\text{.}\) Thus a nontrivial linear combination of \(\mathbf{u}, \mathbf{v}\text{,}\) and \(\mathbf{w}\) is equal to zero, contradicting the independent of \(\{ \mathbf{u}, \mathbf{v}, \mathbf{w} \}\text{.}\)
On the other hand, suppose \(\mathbf{u}\) is not in \(M\text{.}\) We need to show that \(\{ \mathbf{u}, \mathbf{v}, \mathbf{w} \}\) is independent. If \(r \mathbf{u} + s \mathbf{v} + t \mathbf{w} = 0\text{,}\) where \(r\text{,}\)\(s\text{,}\) and \(t\) are not all zero, then \(r \neq 0\text{,}\) for otherwise \(s \mathbf{v} + t \mathbf{w} = 0\text{,}\) which contradicts the independence of \(\{ \mathbf{v}, \mathbf{w} \}\text{.}\) But then \(\mathbf{u} = -s/r \mathbf{v} - t/r \mathbf{w}\text{,}\) which contradicts that \(\mathbf{u}\) is not in \(M\text{.}\)
More generally, if \(\{ \mathbf{x}_1, \dots, \mathbf{x}_k \}\) are a linearly independent set of vectors in \(\R^n\text{,}\) and \(\mathbf{x}_{k+1}\) is another vector in \(\R^n\text{,}\) then \(\{ \mathbf{x}_1, \dots, \mathbf{x}_{k+1} \}\) is a linearly independent set if and only if \(\mathbf{x}_{k+1}\) is not contained in the span of the set \(\{ \mathbf{x}_1, \dots, \mathbf{x}_k \}\text{.}\)
Since \(\R^4\) is four dimensional, we must find two vectors \(\mathbf{w}_1\) and \(\mathbf{w}_2\) such that the vectors \(\{ \mathbf{v}_1, \mathbf{v}_2, \mathbf{w}_1,\mathbf{w}_2 \}\) is linearly independent. Fact 2.4.10 states that we can choose these vectors from any basis, so we might as well choose them from the standard basis \(\{ \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3, \mathbf{e}_4 \}\text{.}\)
One strategy is to choose one vector \(\mathbf{e}_i\) not contained in the span of the set \(\{ \mathbf{v}_1, \mathbf{v}_2 \}\text{,}\) and then choose a vector \(\mathbf{e}_j\) not contained in the span of the set \(\{ \mathbf{e}_i, \mathbf{v}_1, \mathbf{v}_2 \}\text{.}\) By Note 2.4.15, the set \(\{ \mathbf{e}_j, \mathbf{e}_i, \mathbf{v}_1, \mathbf{v}_2 \}\) is then linearly independent.
The vector \(\mathbf{e}_2\) is not contained in the span of the set \(\{ \mathbf{v}_1, \mathbf{v}_2 \}\text{,}\) since the second entry in any linear combination of the vectors \(\mathbf{v}_1\) and \(\mathbf{v}_2\) is equal to zero, and thus the vector cannot be equal to \(\mathbf{e}_2\text{.}\)
One way to think of a basis is as providing a coordinate system for a subspace. The uniquely determined coefficients in the linear combination of a vector in the subspace are the coordinates.
Let \(S = \{ \mathbf{b}_1, \dots, \mathbf{b}_n \}\) be a basis of the subspace \(U\text{.}\) We call the tuple \(B = (\mathbf{b}_1, \dots, \mathbf{b}_n)\) an ordered basis of \(U\text{.}\)
As an example, \((\mathbf{e}_1, \mathbf{e}_2)\) and \((\mathbf{e}_2, \mathbf{e}_1)\) are two different ordered bases of \(\R^2\text{.}\) The two sets \(\{ \mathbf{e}_1, \mathbf{e}_2 \}\) and \(\{ \mathbf{e}_2, \mathbf{e}_1 \}\text{,}\) and so describe the same bases of \(\R^2\text{.}\)
Many Linear Algebra textbooks, including Linear Algebra With Applications, Nicholson write ordered bases using set notation \(\{ \cdots \}\text{,}\) despite the order in which the basis elements appear being important. We use tuple notation \(( \cdots )\) to emphasize the importance of the order.
Given an ordered basis \(B\) for an \(m\)-dimensional subspace \(U\) of \(\R^n\text{,}\) and any vector \(\mathbf{v} \in U\text{,}\) we can describe its ‘coordinates’ with respect to the basis \(B\text{,}\) identifying \(\mathbf{v}\) with a vector in \(\R^m\text{.}\)
Definition2.4.18.Coordinate Vectors With Respect to a Basis.
Let \(U\) be an \(m\)-dimensional subspace of \(\R^n\text{,}\) and let \(B = (\mathbf{b}_1,\dots,\mathbf{b}_m)\) be an ordered basis for \(U\text{.}\) Given any vector \(\mathbf{v} \in U\text{,}\) there exists unique scalars \(t_1,\dots,t_m\) such that
If \(B = (\mathbf{b}_1,\dots,\mathbf{b}_m)\) is an ordered basis for a subspace \(U\text{,}\) then \(C_B(\mathbf{b}_i) = \mathbf{e}_i\text{,}\) where \(\mathbf{e_i}\) is the \(i\)th standard basis vector in \(\R^m\text{.}\)
A blue oblique grid fills the plane, with one family of lines parallel to \(\mathbf{v}_1\) and the other parallel to \(\mathbf{v}_2\text{.}\) Black arrows from the origin label the basis vectors \(\mathbf{v}_1\) and \(\mathbf{v}_2\text{.}\) A black point at a grid intersection is labeled \(2\mathbf{v}_1-\mathbf{v}_2\text{,}\) showing how integer coordinates in the basis land on grid points.
Figure2.4.20.A parallelogram grid constructed from a basis \(B = (\mathbf{v}_1, \mathbf{v}_2)\) for \(\R^2\text{.}\) The points lying at the intersection of lines on the grid are precisely those vectors \(\mathbf{v} \in \R^2\) where the entries of the vector \(C_B(\mathbf{v})\) are integers.
We are now going to connect the concept of dimension with the notion of rank. In this section, we will often realize vectors in \(\R^n\) as rows rather than columns. The notion of span, linear independence, and basis are defined analogously as how they are defined for column vectors.
The columns of \(A\text{,}\) considered as vectors in \(\R^m\) span a subspace of \(\R^m\) called the column space of \(A\text{,}\) denoted \(\col(A)\text{.}\)
The rows of \(A\text{,}\) considered as vectors in \(\R^n\text{,}\) span a subspace of \(\R^n\) called the row space of \(A\text{,}\) denoted \(\row(A)\text{.}\)
The notation \(\operatorname{im}(A)\) emphasizes outputs of the map \(\mathbf{x}\mapsto A\mathbf{x}\text{.}\) The notation \(\operatorname{col}(A)\) emphasizes the columns that span those outputs.
Each time we apply a row operation to a matrix, we replace one or more of its rows with a linear combination of other rows. Thus the row space of a matrix \(A'\) obtained by applying a row operation to a matrix \(A\) must be contained in the row space of \(A\text{.}\) But applying the argument in reverse (since every row operation is reversible), the row space of \(A\) must be contained in the row space of \(A'\text{.}\) Thus the two row spaces are equal. But if the row space is not changed after applying a single row operation, it is not changed after applying an arbitrary number of row operations, and so the result follows.
The nonzero rows of \(R\) are linearly independent by Fact 2.4.4, and span \(\row(R)\) by definition. They thus by definition form a basis for \(\row(R)\text{.}\)
In Definition 2.2.28, we defined the rank of a matrix as the number of leading 1s (i.e., the number of pivots) of any matrix \(R\) in row echelon form which is row-equivalent to \(A\text{.}\) By Lemma 2.4.24, \(\rank(A) = \dimens(\row(A))\text{,}\) which justifies that the rank of \(A\) is independent of the choice of matrix \(R\text{.}\)
If the pivots of \(R\) lie in columns \(j_1, j_2, \dots, j_r\text{,}\) then the columns \(j_1,j_2,\dots,j_r\) of \(A\) are a basis for \(\col(A)\text{.}\)
Warning2.4.27.Pivot columns come from the original matrix.
Row reduction identifies pivot positions, but row operations do not preserve the original columns of \(A\text{.}\) When finding a basis for \(\operatorname{col}(A)\text{,}\) use the pivot columns of the original matrix \(A\text{,}\) not the columns of the row-reduced matrix.
The dimension of the row space of \(A\) is equal to the rank of \(A\text{,}\) which is \(2\) (the number of non-zero rows in the row echelon form for \(A\text{,}\) as computed in the solution to Activity 2.4.12).
The leading 1s in the row echelon form for \(A\) computed in Activity 2.4.12 occur in the 1st and 2nd columns, so the 1st and 2nd columns of \(A\) form a basis for the column space, i.e.,
The dimension of the column space of \(A\) is two, since we constructed a basis with two elements in the previous task. Alternatively, the dimension of the column space is equal to the rank of \(A\text{,}\) which we also computed to be two.
To find a basis for the solutions to the equation \(A \mathbf{x} = \mathbf{0}\text{,}\) we use the row-echelon form computed in Activity 2.4.12 and find basic solutions as in Definition 2.2.36. The row-echelon form gives the equations \(x_1 + \frac{1}{2}x_2 = 0\) and \(x_2 - 2x_3 = 0\text{.}\) Setting the free variable \(x_3 = 1\text{,}\) we obtain \(x_2 = 2\) and \(x_1 = -1\text{,}\) so the basic solution is
Rank counts independent directions transmitted by a matrix. Nullity counts independent input directions forgotten by a matrix. The row-reduction definition of rank now connects to dimension.
Let \(A\) denote an \(m \times n\) matrix of rank \(r\text{.}\) Then
The \(n - r\) basic solutions to the equation \(A \mathbf{x} = \mathbf{0}\) provided by the Gaussian algorithm are a basis for \(\nulls(A)\text{,}\) so \(\dimens(\nulls(A)) = n-r\text{.}\)
Activity2.4.14.Same output from a null-space direction.
Suppose \(A\mathbf{x}=\mathbf{y}\) and \(A\mathbf{z}=\mathbf{0}\text{.}\) Compute \(A(\mathbf{x}+t\mathbf{z})\text{,}\) where \(t\in\mathbb R\text{.}\) What does this say about uniqueness?
So every vector \(\mathbf{x}+t\mathbf{z}\) gives the same output. A nonzero vector in the null space creates a whole line of inputs with the same output.
We use the fact that \(\im(B) = \col(B)\text{.}\) Using Theorem 2.4.26, since the RREF in (2.4.1) has pivots in the 1st and 3rd columns, the column space of \(B\text{,}\) and thus the image of \(B\text{,}\) has a basis given by the 1st and 3rd columns of \(B\text{,}\) i.e., we have a basis
The 2nd and 4th columns of the matrix in (2.4.1) do not contain pivots, so \(x_2\) and \(x_4\) correspond to free variables in the equation, and solutions to \(A\mathbf{x} = \mathbf{0}\) are specified by the two equations \(x_1 = x_2/3 + 2x_4\) and \(x_3 = -3x_4\text{.}\) The two basis solutions give a basis for the nullspace, and thus we have a basis of the form
The predictions are the same, but the coefficient interpretations are different. One coefficient vector puts weight on first-level and second-level area separately. The other puts weight on first-level area and total area. With redundant features, individual coefficient importance is not uniquely determined by the data matrix.
These are linear redundancies. Not every relationship between features is linear. For example, rectangle area is width times height, not a linear combination of width and height.
The zero output means that \(\mathbf{z}\) is a null-space direction. The rank is \(2\text{,}\) so the three feature columns contain only two independent directions.
The vectors \(\mathbf{c}\) and \(\mathbf{c}'\) differ by \(\mathbf{z}\text{,}\) and \(X\mathbf{z}=\mathbf{0}\text{.}\) Therefore they give the same prediction vector.
When features are redundant, different coefficient vectors can make the same predictions. Individual coefficients may not have a unique interpretation.
The matrix records consecutive differences. Adding the same constant to every entry does not change the differences, so the constant direction \((1,1,1,1)\) is forgotten.
for every scalar \(t\text{.}\) Thus many coefficient vectors can produce the same prediction vector. Rank counts how many independent feature directions remain; nullity counts how many independent coefficient changes are invisible to the data matrix.
