Some Concepts of Linear Algebra

## A linear combination of vectors

A vector w is called a linear combination of the vectors v1, v2, …, vr if w can be expressed in the form
w = k1 v1 + k2 v2 + … + kr vr
where k1, k2, …, kr are scalars.
Given, vectors u = [1, 2, −1]T and v = [6, 4, 2]T. Is w = [9, 2, 7]T a linear combination of u and v? What about w' = [4, −1, 8]T?

Tackling the question "Is w = [9, 2, 7]T a linear combination of u and v?"

From definition we know that if w is a linear combination of u and v then there must exist scalars k1 and k2 such that

w = k1 u + k2 v
Substituting the values for the vectors we get This system corresponds to
k1 + 6k2 = 9
2k1 + 4k2 = 2
k1 + 2k2 = 7
To solve the system let us add the top and bottom equations
k1 + 6k2 = 9
k1 + 2k2 = 7
0 + 8k2 = 16
⇒ k2 = 2
Substituting k2 = 2 into the middle equation returns
2k1 + 4⋅2 = 2
⇒ k1 = −3
Substituting k1 = −3 and k2 = 2 into the system returns
k1 + 6k2 = −3 + 6⋅2 = 9
2k1 + 4k2 = 2(−3) + 4⋅2 = 2
k1 + 2k2 = −(−3) + 2⋅2 = 7
The equations do not contradict the system equations. Thus the solution of the system are the scalars k1 = −3 and k2 = 2. That is, w can be expressed in the form
w = −3u + 2v
Hence, w is a linear combination of u and v.

Tackling the question "Is w' = [4, −1, 8]T a linear combination of u and v?"

For w' to be a linear combination of u and v there must exist (some other) scalars k1 and k2 such that

w' = k1 u + k2 v
or or
k1 + 6k2 = 4
2k1 + 4k2 = −1
k1 + 2k2 = 8
To solve the system let us add the top and bottom equations
k1 + 6k2 = 4
k1 + 2k2 = 8
0 + 8k2 = 12
⇒ k2 = 3/2
Substituting k2 = 3/2 into the middle equation returns
2k1 + 4⋅3/2 = −1
⇒ k1 = −7/2
Substituting k1 = −7/2 and k2 = 3/2 into the system returns
k1 + 6k2 = −7/2 + 6⋅3/2 = −7/2 + 9 ≠ 4
2k1 + 4k2 = 2(−7/2) + 4⋅3/2 = −7 +6 = −1
k1 + 2k2 = −(−7/2) + 2⋅3/2 = 7/2 + 3 ≠ 8
Because the equations contradict the system equations k1 = −7/2 and k2 = 3/2 are the scalars that solves the system. In other words, the system has no solution. Therefore w' cannot be expressed in the form
w' = k1 u + k2 v
Hence, w' is not a linear combination of u and v.

## Span for vector space V

For any vector space V containing the vectors v1, v2, …, vr if every vector in V can be expressed as a linear combination of v1, v2, …, vr, then the vectors v1, v2, …, vr are said to span V.
Given the vector space ℜ3 containing the vectors i = [1, 0, 0]T, j = [0, 1, 0]T and k = [0, 0, 1]T, do the vectors i, j and k span ℜ3?

From definition we know that for the vectors i, j and k to span the vector space any vector in the vector space should be expressible as their linear combination.

Let us consider an arbitrary vector [a, b, c]T in ℜ3. Picking one element of this vector and multiplying it to one of the span in question, say ai, and doing this for other elements we get

a i + b j + c k
Substituting the values for the vectors we get This is the same as
[a, b, c]T = a i + b j + c k
Therefore, the vectors i, j and k span ℜ3 because any arbitrary vector in the said vector space can be represented as a linear combination of i, j and k.

What if the arbitrary vector is specified to be one of the vectors that spans ℜ3, say [a, b, c]T = [1, 0, 0]T = i?

The linear combination 1 i + 0 j + 0 k returns Thus, vector i can be expressed as the lienar combination; i = 1 i + 0 j + 0 k.

What this tells us is that when the definition states "every vector in the vector space should be expressible as a linear combination" it includes vectors that are said to span the vector space.

## Linearly Dependent and Indenpendent Set (of vectors)

For any vector space V containing the finite set of vectors S = { v1, v2, …, vr } such that the vector equation
k1 v1 + k2 v2 + … + kr vr = 0
has at least one solution, namely
k1 = 0, k2 = 0, …, kr = 0
• If this is the only solution, S is called a linearly independent set.
• If there are other solutions, S is called a linearly dependent set.
Given the vector space ℜ3 containing the vectors i = [1, 0, 0]T, j = [0, 1, 0]T and k = [0, 0, 1]T, are the vectors i, j and k linearly independent?

From definition we know that for the vectors i, j and k to be independent its vector equation

k1 i + k2 j + k3 k = 0
must have just one solution; k1 = 0, k2 = 0, k3 = 0.

Substituting the values for the vectors in the vector equation we get Thus k1 = 0, k2 = 0, k3 = 0 is the only solution to the equation; the set S = { i, j, k } is linearly independent.

Given the vector space V containing the set S = { v1, v2, v3 } such that vectors v1 = [2, −1, 0, 3]T, v2 = [1, 2, 5, −1]T and v3 = [7, −1, 5, 8]T. Are v1, v2 and v3 linearly dependent?

From definition we have the vector equation

k1 v1 + k2 v2 + k3 v3 = 0
Substituting the values for the vectors in the vector equation we get This system corresponds to
2k1 + k2 + 7k3 = 0
k1 + 2k2k3 = 0
5k2 + 5k3 = 0
3k1k2 + 8k3 = 0
The third equation says k2 = −k3. So if we let k2 = 1 then k3 = −1. Substituting these values to any of the remaining three equations yields k3 = 3. Below shows the result for subsitution done on the first equation.
2k1 + 1 − 7k3 = 0
⇒    2k1 − 6 = 0
or   k1 = 6/2 = 3
Substituting k1 = 3, k2 = 1 and k3 = −1 into the system
2k1 + k2 + 7k3 = 2⋅3 + 1 + 7(−1) = 6 − 6 = 0
k1 + 2k2k3 = −3 + 2 − (−1)= −3 + 3 = 0
5k2 + 5k3 = 5 + 5(−1) = 5 − 5 = 0
3k1k2 + 8k3 = 3⋅3 − 1 + 8(−1) = 9 − 9 = 0
we observer that the equations do not contradict each other. Therefore, in addition to the solution
k1 = 0, k2 = 0, k3 = 0
another solution is
k1 = 3, k2 = 1, k3 = −1
Therefore, the set S = { v1, v2, v3 } is linearly dependent.

## Linearly Dependent Set and Linear combination of vectors

The term linearly dependent suggests that vectors in the set in some way depend on each other. This statement can be illustrated with an example.

Let the set S = { v1, v2, …, vr } be a linearly dependent set. Then by definition the vector equation

k1 v1 + k2 v2 + … + kr vr = 0
will have a solution other that k1 = k2 = … = kr = 0.

Furthermore, assume k1 ≠ 0. Multiplying both sides by 1/k1 and solving for v1 yields

v1 = (−k2/k1) v2 + (−k3/k1) v3 + … + (−kr/k1) vr
Therefore, v1 can be expressed as a linear combination of the remaining vectors.

A set with two or more vectors is linearly dependent if and only if at least one of the vectors is a linear combination of the remaining vectors.
Two vectors v1 and v2, form a linearly dependent set if and only if one of them is a scalar multiple of the other.

For a linearly dependent set S = { v1, v2 } and the vector expression k1 v1 + k2 v2 = 0, if k1 ≠ 0 then v1 = (−k2/k1) v2. That is v1 is a scalar multiple of v2. Therefore, if S = { v1, v2 } is linearly independent then geometrically the vectors v1 and v2 do not lie along the same line.

If a vector space ℜ2 has a set that contains more than two vectors then the set is linearly dependent.

Let S = { v1, v2, …, vr } be a set of vectors in ℜn. If r > n, then S is linearly dependent.

Assume
v1 = [v11, v12, …, v1n]
v2 = [v21, v22, …, v2n]

vr = [vr1, vr2, …, vrn]
For the vector equation
k1 v1 + k2 v2 + … + kr vr = 0
Substituting the values for the vectors we get This system corresponds to
v11 k1 + v21 k2 + … + vr1 kr = 0
v12 k1 + v22 k2 + … + vr2 kr = 0

v1n k1 + v2n k2 + … + vrn kr = 0
That is, a homogeneous system of n equations with r unknowns k1, k2, …, kr.

Invoking the fundamental theorem of homogeneous system of linear equations

A homogeneous system of linear equations with more unknowns than equations always has infinitely many solutions.
We can conclude that since the above vector equation for the set S = { v1, v2, …, vr } in the vector space ℜn is a homogeneous system with r > n the system has nontrivial solutions, i.e. many solutions.

Therefore, for r > n the set S = { v1, v2, …, vr } in ℜn is a linearly dependent set.∎

## Basis for vector space V

For any vector space V the finite set of vectors in V, S = { v1, v2, …, vr } is called a basis for V if
• S spans V;
• S is linearly independent.
Given the vector space ℜ3 and its set of vectors S = { i, j, k } such that i = [1, 0, 0]T, j = [0, 1, 0]T and k = [0, 0, 1]T, is S a basis for ℜ3?

Does S span ℜ3?

We showed in the above example that for an arbitrary vector [a, b, c]T in ℜ3 the vector equation

a i + b j + c k
becomes which is
[a, b, c]T = a i + b j + c k
Therefore, the vectors i, j and k span ℜ3 because any arbitrary vector in the said vector space can be represented as a linear combination of i, j and k.

Is S a linearly independent set?

We showed in another example that for some scalars k1, k2 and k3 which form the coefficients of the vector equation

k1 i + k2 j + k3 k = 0
or We see that k1 = 0, k2 = 0, k3 = 0 is the only solution to the equation; the set S = { i, j, k } is linearly independent.

Thus, the set of vectors S spans its vector space and is a linearly independent set. Thus S is a basis for the vector space ℜ3.

Notice that any vector v = [v1, v2, v3]T in ℜ3 can be written as a linear combination of all the vectors in the set S. That is
v = v1 i + v2 j + v3 k
S is a special kind of basis called the standard basis for ℜ3.

If the set of vectors S = { v1, v2, …, vr } spans the vector space V and any vector v = [v1, v2, …, vr] in V can be expressed as v = v1 v1 + v2 v2 + … + vr vr, then S is called the standard basis for V.

## Dimension of vector space V

Given a finite vector space V, the number of vectors in a basis for V is called the dimension of V. Furthermore, the zero vector is defined to have dimension zero.
Given the homogeneous system
2x1 + 2x2x3            + x5 = 0
x1x2 + 2x3 − 3x4 + x5 = 0
x1 + x2 − 2x3            − x5 = 0
x3  +  x4  +  x5 = 0
What is the dimension of its solution space?

We must first find the set of vectors that span the solution space. But to this we need to know the solutions for the homogeneous system.

The augmented matrix of the homogeneous system is whose reduced-echelon form is The corresponding system of equation is
x1 + x2 +               x5 = 0
x3       + x5 = 0
x4          = 0
Solving for the leading variables we get
x1 = −x2x5
x3 = −x5
x4 = 0
Setting x2 and x5 to some arbitrary constants, say, x2 = s and x5 = t, then the solution space (or solution set) for the homogeneous system is
x1 = −st,      x2 = s,      x3 = −t,      x4 = 0,      x5 = t
The solution space can be written as the vector [x1, x2, x3, x4, x5]T = [−st, s, −t, 0, t]T. Taking out the unknown terms s and t in the vector we get If we define v1 = [−1, 1, 0, 0, 0]T and v2 = [−1, 0, −1, 0, 1]T then the solution space can be expressed as the solution vector
[x1, x2, x3, x4, x5]T = s v1 + t v2
which as we can see is a linear combination of vectors in the set S = { v1, v2 } where s and t are scalars. Furthermore we know that the vector equation is consistent for any arbitrary s and t values; that is, the vectors of the set span the solution space.

To check if the set S = { v1, v2 } is linearly independent or dependent we need to solve the vector equation

s v1 + t v2 = 0
Substituting the values for the vectors we get showing that s = 0 and t = 0 is the only solution. Thus, the set is independent and because it also span the solution space we can conclude that the set S = { v1, v2 } is a basis for the solution space.

The number of vectors in the basis S = { v1, v2 } is two so the solution space is two dimensional.

Finding the dimension of a vector space V requires first finding its basis which by definition requires determining if the set in question spans V and is linearly independent. But, for a vector space V known to be n-dimensional finding if some set of n vectors is a basis for V requires determining if it is either spanning or linearly independent (theorem below).

If S = { v1, v2, …, vn } is a set of n linearly independent vectors in a n-dimensional space V, then S is a basis for V.

If S = { v1, v2, …, vn } is a set of n vectors that spans an n-dimensional space V, then S is a basis for V.

If S = { v1, v2, …, vn } is a set of n linearly independent vectors in a n-dimensional space V and r < n, then S can be enlarged to a basis for V; that is, there are vectors vr+1, …, vn such that { v1, v2, …, vr, vr+1, …, vn } is a basis for V.

## Row space and column space

Given the m × n such that vectors
r1 = [a11, a12, …, a1n]
r2 = [a21, a22, …, a2n]

rm = [ar1, ar2, …, amn]
from rows of A are called row vectors of A and the vectors
c1 = [a11, a21, …, am1]T
c2 = [a12, a22, …, am2]T

cn = [a1n, a2n, …, amn]T
formed from columns of A are called column vectors of A.
The subspace (set of vectors) of ℜn spanned by the row vectors of the m × n matrix A is called the row space of A.

The subspace (set of vectors) of ℜn spanned by the column vectors of the m × n matrix A is called the column space of A.

If the row space or column space is taken as a vector space how can its basis be found? To help us find the basis below are some theorems.
Elementary row operations do not change the row space of a matrix A.
Let
r1, r2, …, rm
represent the row vectors of a m × n matrix A. Also, suppose matrix B is the result of performing elmentary row operations on A.

Then to show A and B have the same row space we need to show that

• 1. every row vector in B is also in row space of A
• 2. every row vector in A is in the row space of B
Consider the following possible elementary row operations
• • row interchange
B and A will have the same row vectors and hence the same row space.
• • scalar multiplication of row or addition of a multiple of one row to another
The row vectors r1', r2', …, rm' of B are linear combinations of r1, r2, …, rm. Therefore, row vectors of B lie in the row space of A.
What about the linear combinations of r1', r2', …, rm', do they lie in the row space of A?
Because of the theorem that says that a vector space is closed under addition and scalar multiplication
If W is a set of one or more vectors from a vector space V, then W is a subspace of V if and only if the following conditions hold.
• W is closed under addition; If u and v are any vectors in W, then u + v is in W.
• W is closed under scalar multiplication; If k is any scalar and u is any vectors in W, then ku is in W.
and since the row vectors of B lie in the row space of A (consequence of the row vectors of B being linear combinations of row vectors of A) we can conclude that all linear combinations of r1', r2', …, rm' will also lie in the row space of A.
Thus, every vector in the row space of B is in the row space of A.∎1
Since matrix B was obtained from A by performing row operations we can obtain A by doing the inverse operations on B Therefore, using the above argument we can show that vectors r1, r2, …, rm lie in the row space of B and all linear combinations of r1, r2, …, rm lie in the row space of B.

Hence, every vector in the row space of A is in the row space of B.∎2

Nonzero row vectors in a row-echelon form of a matrix A form a basis for the row space of A.
Let
r1, r2, …, rm
represent the row vectors of a m × n matrix A whose row-echelon form is B containing the row vectors
r1', r2', …, rm'
Let us also denote the zero row vectors ri' = 0 of B as
01, 02, …, 0p
and the nonzero row vectors ri' ≠ 0 of B as
01, 02, …, 0q
Hence, we need to show that
• 1. the set { 01, 02, …, 0p } is not a basis for the row space of A
• 2. the set { 01, 02, …, 0q } is a basis for the row space of A
By definition a basis S of space V must span V and S is linearly independent.

Because of the theorem

Elementary row operations do not change the row space of a matrix A.
we know that the set { r1', r2', …, rm' } span the row space of A, consequently both { 01, 02, …, 0p } and { 01, 02, …, 0q } wil span the row space of A.

Expressing set { 01, 02, …, 0p } as the vector equation

k1 01 + k2 02 + … + kp 0p = 0
we see that it has infinite solution since any arbitray values of k1, k2, …, kr is the solution. Hence, the set of zero row vectors are linearly dependent. Therefore, the set is not a basis for the row space of A.∎1

For the set { 01, 02, …, 0q } with the vector equation

k1 01 + k2 02 + … + kq 0q = 0
the only solution is
k1 = 0, k2 = 0, …, kr = 0
The set { 01, 02, …, 0q } is linearly independent. Therefore, the set is a basis for the row space of A.∎2

If the space is spanned by the vectors
v1 = [1, −2, 0, 0, 3]
v2 = [2, −5, −3, −2, 6]
v3 = [0, 5, 15, 10, 0]
v4 = [2, 6, 18, 8, 6]
then by definition the set S = { v1, v2, v3, v4 } span the vector space. The set can be viewed as a row space whose row-echelon form returns From this matrix the nonzero row vectors are
w1 = [1, −2, 0, 0, 3]
w2 = [0, 1, 3, 2, 0]
w3 = [0, 0, 1, 1, 0]
The above theorem tells us that the set { w1, w2, w3 } span the row space. And since the set of row vectors S span the vector space, the set { w1, w2, w3 } span the same vector space.

Therefore, { w1, w2, w3 } is the basis for the vector space.

If A is any matrix, then the row space and column space of A have the same dimension.
Given the m × n matrix with row vectors denoted by r1, r2, …, rm, suppose its row space has k dimension with basis of the row space S = { b1, b2, …, bk }, where bi = [bi1, bi2, …, bin].

Since S is a basis for the row space, each row vector can be expressed as a linear combination of the basis vectors b1, b2, …, bk.

r1 = c11b1 + c12b2 + … + c1kbk
r2 = c21b1 + c22b2 + … + c2kbk

rm = cm1b1 + cm2b2 + … + cmkbk
Because two vectors in a vector space ℜn are equal if and only if corresponding components are equal, equating the jth component in ri with the corresponding components of the vectors b1, b2, …, bk on the right hand side of the above expression we get
a1j = c11b1j + c12b2j + … + c1kbkj
a2j = c21b1j + c22b2j + … + c2kbkj

amj = cm1b1j + cm2b2j + … + cmkbkj
This is equivalent to with the left hand side of the equation representing the jth column vector of A for j = 1, 2, …, n and the right hand side showing that each column vector of A lies in the vector space spanned by the k vectors; [c11, c21, …, cm1]T, [c12, c22, …, cm2]T, …, [c1k, c2k, …, cmk]T.

Therefore, the set { [c11, c21, …, cm1]T, [c12, c22, …, cm2]T, …, [c1k, c2k, …, cmk]T } spans the column space of A. Hence, the column space has dimension ≤ k.

Since we assumed k to be the dimension of the row space

k = dim(row space of A)
thus
dim(column space of A) ≤ dim(row space of A)
Also, because matrix A is arbitrary, the same conclusion applies to AT
dim(column space of AT) ≤ dim(row space of AT)
Transposing a matrix converts rows to columns and columns to rows row space of A = column space of AT
column space of A = row space of AT
Thus,
dim(row space of A) ≤ dim(column space of A)
But,
dim(column space of A) ≤ dim(row space of A)
therefore
dim(column space of A) = dim(row space of A)∎

Given the matrix A its row-echelon form is Since there are two nonzero row vectors in the row-echelon form that span the row space of A, the row space is two dimensional.

The transpose of matrix A, AT is whose row-echelon form is There are two nonzero row vectors therefore, the row space of AT is two dimensional.

Since the column vectors of A are the row vectors of AT the basis for the row space of AT

{ [1, 3, 0]T, [0, 1, 2]T }
is the basis for the column space of A. Thus, the column space of A is two dimensional; the row space and column space of A are two dimensional.

If A is a matrix that is not square, then either the row vectors of A or the column vectors of A are linearly dependent.
Consider the consistent linear system Ax = b such that A is a m × n matrix, x a n × 1 vector and b a m × 1 column vector. [A b] is the augmented matrix.

From the theorem(ibid. 5)

Nonzero row vectors in a row-echelon form of a matrix A form a basis for the row space of A.
we know that the number of the resulting nonzero vectors gives us the dimension of the column or row space of A and consequently the rank of matrix A.

The preceeding theorem states that Ax = b is consistent if and only if b is in the column space of A. Thus, for a consistent system since the only unique column vector, b between matrices A and [A b] must be in the column space of A, the number of nonzero vectors following row operations on the A and [A b] will be equal.

Therefore, for a consistent system Ax = b, matrices A and [A b] will have equal ranks.

## Rank of a matrix

The dimension of the row and column space of a matrix A is called the rank of A.
Given the matrix A its row-echelon form is Since there are two nonzero row vectors in the row-echelon form that span the row space of A, the row space is two dimensional.

From theorem

If A is any matrix, then the row space and column space of A have the same dimension.
we know that column space of A is two dimensional.

The rank of A is 2.

If Am × n is a matrix and mn, then the largest possible rank is
m if m < n
n if m > n
From the lemma
The dimension of the row space and column space for any Am × n matrix is the same.
and the lemma
The nonzero row vectors in a row-echelon form of any Am × n matrix is a basis for the the row space.
Thus,
if m < n, then
dimension of row space = dimension of column space ≤ m
if m > n, then
dimension of row space = dimension of column space ≤ n
Then from the definition of rank it follows
if m < n, then
the largest possible rank ≤ m
if m > n, then
the largest possible rank ≤ n

Since the definition of rank refers to the number of vectors in a set that form a basis and since a basis must span (row/column space) and be linearly independent, then
If Am × n is a matrix and mn, then
if m < n, then
the column vectors of A are linearly dependent
if m > n, then
the row vectors of A are linearly dependent∎
From the preceeding theorem it follows
If A is a matrix that is not square, then either the row vectors of A or the column vectors of A are linearly dependent.

## Summary 