Linearly independence

Definition: Consider a set of n-vectors, {(Subscript[K, 1]^□),(Subscript[K, 2]^□),...,(Subscript[K, n]^□)}. 

If there exist a set of coefficient {(Subscript[x, 1]^□),(Subscript[x, 2]^□),...,(Subscript[x, n]^□)}≠ {0,0,...,0} such that  (Subscript[x, 1]^□)(Subscript[K, 1]^□)+(Subscript[x, 2]^□)(Subscript[K, 2]^□)+...+(Subscript[x, n]^□)(Subscript[K, n]^□)=0, the set of vector {(Subscript[K, 1]^□),(Subscript[K, 2]^□),...,(Subscript[K, n]^□)} is not linearly independent.

In other words, if the only solution for (Subscript[x, 1]^□)(Subscript[K, 1]^□)+(Subscript[x, 2]^□)(Subscript[K, 2]^□)+...+(Subscript[x, n]^□)(Subscript[K, n]^□)=0 is {(Subscript[x, 1]^□),(Subscript[x, 2]^□),...,(Subscript[x, n]^□)}={0,0,...,0}, then the set of vector {(Subscript[K, 1]^□),(Subscript[K, 2]^□),...,(Subscript[K, n]^□)} is linearly independent. 

Example:
Consider the 3-vectors pair, (Subscript[X, 1]^T)=[1,2,3], (Subscript[X, 2]^T)=[-1,-2,-3].
Find any possible values of (Subscript[k, 1]^□) and (Subscript[k, 2]^□), with {(Subscript[k, 1]^□),(Subscript[k, 2]^□)}≠{0,0}, such that 
(Subscript[k, 1]^□)(Subscript[X, 1]^T)+ (Subscript[k, 2]^□)(Subscript[X, 2]^T)=0. (ii) Are the vectors linearly dependent or linearly-independent ?

Ans: (i) Any arbitrary value of (Subscript[k, 1]^□)= (Subscript[k, 2]^□)  ≠ 0 will do. (ii).
They are linearly dependent, since there exist values of  {(Subscript[k, 1]^□),(Subscript[k, 2]^□)}≠{0,0} such that (Subscript[X, 1]^T)= -((Subscript[k, 2]^□)/(Subscript[k, 1]^□))(Subscript[X, 2]^T). Any pairs of vectors that are parallel or antiparallel is not linearly independent. 

Note that when, say for example, the set of 3 vectors {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)} are not lienarly independent, any of the vector in the set can be expressed as linear combination of the rest, e.g., 
(Subscript[x, 1]^□)(Subscript[K, 1]^□)+(Subscript[x, 2]^□)(Subscript[K, 2]^□)+(Subscript[x, 3]^□)(Subscript[K, 3]^□)=0
⇒(Subscript[K, 3]^□)=-((Subscript[x, 1]^□)(Subscript[K, 1]^□)+(Subscript[x, 2]^□)(Subscript[K, 2]^□))/(Subscript[x, 3]^□).
In other words, (Subscript[K, 3]^□) is not a vector independent from the rest, (Subscript[K, 2]^□)and (Subscript[K, 1]^□) (because (Subscript[K, 3]^□) can be expressed in terms of (Subscript[K, 1]^□) and (Subscript[K, 2]^□)) 

Example of linearly independent set of vectors
(Subscript[X, 1]^T)=[1,2,3], (Subscript[X, 2]^T)=[4,5,6]. 
The set of two vectors {(Subscript[X, 1]^□),(Subscript[X, 2]^□)} is linearly independent. 

For (Subscript[k, 1]^□)(Subscript[X, 1]^□)+(Subscript[k, 2]^□)(Subscript[X, 2]^□)=(Subscript[[0,0,0], □]^T), we need (Subscript[k, 1]^□) + 4(Subscript[k, 2]^□) = 0, 2(Subscript[k, 1]^□) + 5(Subscript[k, 2]^□) = 0, 3(Subscript[k, 1]^□)+6(Subscript[k, 2]^□)= 0. The only possible solution is (Subscript[k, 1]^□), (Subscript[k, 2]^□) both being zero. This means that for (Subscript[k, 1]^□)(Subscript[X, 1]^□)+(Subscript[k, 2]^□)(Subscript[X, 2]^□)=(Subscript[[0,0,0], □]^T), the coefficients {(Subscript[k, 1]^□), (Subscript[k, 2]^□)} must be all zero. This proves the linearly independence of (Subscript[X, 1]^□) and (Subscript[X, 1]^□).


Refer (9.5) in page 69, Ayres. Given a set of m  vectors, we want to know whether they are linearly independent or otherwise. What is the easiest way (or one of the easier ways) to determine the linear independence of such a set of vectors? 

Ans: Use row elementary operations to reduce the matrix A formed by these vectors to RREF. The number of non-zero row in the RREF of A is the rank of the matrix A, r. The rank, r, also tells us how many linearly independent vectors are there in the set of m vectors. 

If r = m, then the set of this m vectors is linearly independent. If r < m, then the set of m vectors is linearly dependent. See theorem V, page 69, Ayers.

Example 2.3, Prof. Rosy Teh’s note on Linear Algebra, page 33.
Consider the set S containing the following 4 3-vectors: (Subscript[K, 1]^□)=(([1,1,1])^T), (Subscript[K, 2]^□)=(([1,3,5])^T), (Subscript[K, 3]^□)=(([1,5,3])^T),(Subscript[K, 4]^□)=(([5,3,1])^T);
S={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)}. (i) Form the matrix K whose rows are made up of the vectors (Subscript[K, i]^□), i=1, 2, 3, 4. (ii) Reduce K into RREF. (iii) What is the rank of K? (iv) How many linearly independent vectors are there in the set S? (v) Are the vectors in set S linearly independent?

Answer:
K=((Subscript[K, 1]^□) (Subscript[K, 2]^□) (Subscript[K, 3]^□) (Subscript[K, 4]^□))=(({{1, 1, 1, 5}, {1, 3, 5, 3}, {1, 5, 3, 1}})). 
RREF(K)=(({{1, 0, 0, 6}, {0, 1, 0, -1}, {0, 0, 1, 0}})). Obviously, the rank of matrix K is r=3. 
Since the number of vectors in S, m = 4 is larger than the number of linearly independent vectors, r = 3, the set of vectors in S is  NOT linearly independent by the virtue of theorem V, page 69, Ayers.

In the above example, the set of vectors S={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} is proven to be not linearly independent. Now we ask another different question:  is the set of vector R={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)} linearly independent? To answer the question, we perform the following calculation: 

"K1="(({{1}, {1}, {1}}))", K2="(({{1}, {3}, {5}}))", K3="(({{1}, {5}, {3}}))
"K = (K1 K2 K3)="(({{1, 1, 1}, {1, 3, 5}, {1, 5, 3}}))
"m = number of vectors forming the matrix K = "3

"RREF[K] = "(({{1, 0, 0}, {0, 1, 0}, {0, 0, 1}})).

"Hence Rank [K] is r = "3
"Since r = m = "3" the set of vectors {K1,K2,K3} is linearly independent", by the virtue of theorem V, page 69, Ayers.

Is the set of vector R={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 4]^□)} linearly independent? To answer the question:  

"K1="(({{1}, {1}, {1}}))", K2="(({{1}, {3}, {5}}))", K4="(({{5}, {3}, {1}}))
"K = (K1 K2 K4)="(({{1, 1, 5}, {1, 3, 3}, {1, 5, 1}}))
"m = number of vectors forming the matrix K = "3
"RREF[K] = "(({{1, 0, 6}, {0, 1, -1}, {0, 0, 0}}))
"Rank [K] is r = "2" ≠ m = "3
"Hence the set of vector K is not linearly independent".

Is the set of vector R={(Subscript[K, 1]^□),(Subscript[K, 2]^□)} linearly independent?

"K1="(({{1}, {1}, {1}}))", K2="(({{1}, {3}, {5}}))
"K = (K1 K2 )="(({{1, 1}, {1, 3}, {1, 5}}))
"m = number of vectors forming the matrix K = 2"
"RREF[K] = "(({{1, 0}, {0, 1}, {0, 0}}))
"Hence Rank [K] is r = "2

Since r = m = 2, the set of vectors in K is linearly independent

The span of the vector space (Subscript[V, 3])(R) by a set of 4 3-vectors (Refer to example 2.2, page 33, Prof. Rosy Teh’s lecture note on Linear Algebra)

Consider the same set containing 4 3-vectors: (Subscript[K, 1]^□)=(([1,1,1])^T), (Subscript[K, 2]^□)=(([1,3,5])^T), (Subscript[K, 3]^□)=(([1,5,3])^T),(Subscript[K, 4]^□)=(([5,3,1])^T). Does the vectors {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} span the vector space (Subscript[V, 3])(R)?  

In other words, can any arbitray vector living in (Subscript[V, 3])(R) be expressed as a linear combination of {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)}?  If yes, {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} is said to span (Subscript[V, 3])(R), else, it does not. 

Let an arbitrary vectors in (Subscript[V, 3])(R) is denoted by a column vector with components a, b, c  which are not all zero, H=(([a,b,c])^T). Then we form a linear combination of {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} and equate them to H, 

	(Subscript[x, 1])(Subscript[K, 1]^□)+(Subscript[x, 2])(Subscript[K, 2]^□)+(Subscript[x, 3])(Subscript[K, 3]^□)+(Subscript[x, 4])(Subscript[K, 4]^□)=H. 
	
If putting the column vectors (Subscript[K, i]^□) into a matrix K, 

		K=((Subscript[K, 1]^□) (Subscript[K, 2]^□) (Subscript[K, 3]^□) (Subscript[K, 4]^□))=(({{1, 1, 1, 5}, {1, 3, 5, 3}, {1, 5, 3, 1}})),

then (Subscript[x, 1])(Subscript[K, 1]^□)+(Subscript[x, 2])(Subscript[K, 2]^□)+(Subscript[x, 3])(Subscript[K, 3]^□)+(Subscript[x, 4])(Subscript[K, 4])=H can be compactly expressed as a non- homogeneous equation in matrix form, 

		KX=H

where "X is "(({{x1}, {x2}, {x3}, {x4}})). 
The rank of the matrix K can be deduced from it RREF, 
	
	"RREF[K] ="(({{1, 0, 0, 6}, {0, 1, 0, -1}, {0, 0, 1, 0}})), which tells us that Rank[K]=3.
So is the rank of the augmented matrix [K | H ] can be deduced from it RREF [K | H ],

	RREF [K | H ]=(({{1, 0, 0, 6, ((4 a)/3)-(b/6)-(c/6)}, {0, 1, 0, -1, -(a/6)-(b/6)+(c/3)}, {0, 0, 1, 0, (1/6) (-a+2 b-c)}})), which tells us that Rank[K|H]=3.

Hence the non-homogeneous equation KX=H is consitent (i.e., non-trivial solutions X exist). This means the set of vectors spans (Subscript[V, 3])(R). In other words, given any arbitrary vector H=(([a,b,c])^T), it can always be expressed as a linear combanation based on the vectors {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)}. 

Note: The exact values of (Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3]),(Subscript[x, 4]) are not important here. What is important is that the non-trivial solution, X, exist.

Note: In the discussion of whether the set of vector {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} span (Subscript[V, 3]^□)(R) we do not care whether the vectors {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} are linearly independent. This is a different question at all, and has to be considered separately.

In the example above, the set of vectors S={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} is proven to span (Subscript[V, 3]^□)(R). We ask another different question:  does the set of vector R={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)} span (Subscript[V, 3]^□)(R)? To answer the question:  

"K1="(({{1}, {1}, {1}}))", K2="(({{1}, {3}, {5}}))", K3="(({{1}, {5}, {3}}))
"K = (K1 K2 K3)="(({{1, 1, 1}, {1, 3, 5}, {1, 5, 3}}))
"H is "(({{a}, {b}, {c}})), "X is "(({{x1}, {x2}, {x3}})).

"KX="H = (({{1, 1, 5}, {1, 3, 3}, {1, 5, 1}}))(({{x1}, {x2}, {x3}}))"="(({{x1+x2+5 x3}, {x1+3 x2+3 x3}, {x1+5 x2+x3}}))"="□(({{a}, {b}, {c}})).

"RREF[K]="(({{1, 0, 0}, {0, 1, 0}, {0, 0, 1}})) ⇒Rank[K]=3.

"RREF[K|H]="(({{1, 0, 0, ((4 a)/3)-(b/6)-(c/6)}, {0, 1, 0, -(a/6)-(b/6)+(c/3)}, {0, 0, 1, (1/6) (-a+2 b-c)}})) ⇒Rank[K|H]=3.


"Hence the non-homegeneous system K X = H is consistent". 
"There is non-trivial solution X=[x1,x2,x3]^T such that any arbitray vector H can be expressed as a linear combination of K1,K2 and K3, H = K.X. By definition, the set of vectors {K1, K2, K3} spans S=V_3(R)."

In the example above, the set of vectors S={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)} is proven to span (Subscript[V, 3]^□)(R). We ask another different question:  does the set of vector R={(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 4]^□)} spans (Subscript[V, 3]^□)(R)? To answer the question:  

"K = (K1 K2 K4)="(({{1, 1, 5}, {1, 3, 3}, {1, 5, 1}}))

"H is "(({{a}, {b}, {c}})), "X is "(({{x1}, {x2}, {x3}}))

"K X = H =  ""KX = "(({{x1+x2+5 x3}, {x1+3 x2+3 x3}, {x1+5 x2+x3}}))=(({{a}, {b}, {c}}))

"[K|H] = "(({{1, 1, 5, a}, {1, 3, 3, b}, {1, 5, 1, c}})), 


"RREF[K]="(({{1, 0, 6}, {0, 1, -1}, {0, 0, 0}})),  Rank[K] = 2.

"RREF[K|H]="(({{1, 0, 6, 0}, {0, 1, -1, 0}, {0, 0, 0, 1}})), "Rank [K|H]="3

"Hence the non-homegeneous system K X = H is NOT consistent because Rank[K|H] is not equal to Rank [K]. 

"There is NO solution X=[x1,x2,x3]^T such that any arbitray vector H can be expressed as linear combination of K1,K2 and K3, H = K.X. By definition, the set of vectors {K1, K2, K4} does not spans S=V_3(R).""

Does the set of vector R={(Subscript[K, 1]^□),(Subscript[K, 2]^□)} span (Subscript[V, 3]^□)(R)? To answer this question:

"K = "(({{1, 1}, {1, 3}, {1, 5}})), "X = "(({{x1}, {x2}})), "H = "(({{a}, {b}, {c}}))

"[K|H] = "(({{1, 1, a}, {1, 3, b}, {1, 5, c}}))

"RREF[K]="(({{1, 0}, {0, 1}, {0, 0}})), "Rank [K]="2

"RREF[K|H]="(({{1, 0, 0}, {0, 1, 0}, {0, 0, 1}})), "Rank [K|H]="3.

"Hence the non-homegeneous system K X = H is NOT consistent because Rank[K|H] is not equal to Rank [K]. \\nThere are no non-trivial solution for K X = H "

"It is not possible to expressed H in terms of linear combination of K1, K2 in S=V_3(R). By definition, the set of vector {K1, K2} does not span V_3(R)."

Conclusion: 

{(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)} span (Subscript[V, 3]^□)(R), and is not linearly independent.
{(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)} span (Subscript[V, 3]^□)(R), and is linearly independent.
{(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 4]^□)} does not span (Subscript[V, 3]^□)(R), and is not linearly independent.
{(Subscript[K, 1]^□),(Subscript[K, 2]^□)} does not span (Subscript[V, 3]^□)(R), and is linearly independent.

Definition: The minimum number of linearly independent vector to span a space is the dimension of the vector space. In the above example, the vector space (Subscript[V, 3]^□)(R) has a dimension of 3, because that is the minimum of linearly independent vectors that is required to span it.  

Definition: Consider a vector space V  with dimension r. A set of r linearly independent vectors in V is called the basis (or basis set) of the vector space. It happens that given any set of r vectors, which are linearly independent, they (i) will form a basis set for V, and (ii) any vector in V can be expressed as a unique linear combination in this set of r vectors. 

{(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)} are basis vectors in (Subscript[V, 3]^□)(R), as any abitrary vector H  in (Subscript[V, 3]^□)(R) can be expressed as a linear combination of {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)}.  There are many other sets of basis vector in  (Subscript[V, 3]^□)(R), other than {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□)}, as long as the set of vectors is linearly independent and spans (Subscript[V, 3]^□)(R). For example, the set of vectors {(([1,0,0])^T), (([0,1,0])^T), (([0,0,1])^T)} is a good example of basis vectors. {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 4]^□)}, {(Subscript[K, 1]^□),(Subscript[K, 2]^□)}, {(Subscript[K, 1]^□),(Subscript[K, 2]^□),(Subscript[K, 3]^□),(Subscript[K, 4]^□)}, according to the definition, are not basis vectors in (Subscript[V, 3]^□)(R).