Chapter 7
Dimension and Subspaces
7.1 Properties of bases and dimensions
7.2 Basic spaces of matrix
7.3 Rank-Nullity theorem
7.4 Rank theorem
7.5 Projection theorem
*7.6 Least square solution, https://youtu.be/GwHh5lh5wEs
7.7 Gram-Schmidt orthonomalization process
7.8 QR-Decomposition; Householder transformations
7.9 Coordinate vectors
7.10 Exercises
(English Textbook) http://matrix.skku.ac.kr/2015-Album/Big-Book-LinearAlgebra-Eng-2015.pdf
(e-book : Korean) http://matrix.skku.ac.kr/2015-Album/BigBook-LinearAlgebra-2015.pdf
http://matrix.skku.ac.kr/LA-Sage/
선형대수학 http://matrix.skku.ac.kr/LinearAlgebra.htm
Credu http://matrix.skku.ac.kr/Credu-CLA/index.htm
OCW http://matrix.skku.ac.kr/OCW-MT/index.htm
행렬 계산기 http://matrix.skku.ac.kr/2014-Album/MC-2.html
그래프 이론 http://matrix.skku.ac.kr/2014-Album/Graph-Project.html
행렬론 http://matrix.skku.ac.kr/MT2010/MT2010.htm
JFC http://matrix.skku.ac.kr/JCF/index.htm
The vector space 
has a basis, and it is a key concept to understand the vector space.
In particular, a basis provides a tool to compare sizes of different vector spaces with infinitely many elements.
By understanding the size and structure of a vector space, one can visualize the space and efficiently use the data sitting contained within it.
In this chapter, we discuss bases and dimensions of vector spaces and then study their properties.
We also study fundamental vector spaces associated with a matrix such as row space, column space, and nullspace, along with their properties.
We then derive the Dimension Theorem describing the relationship between the dimensions of those spaces.
In addition, the orthogonal projection of vectors in 
will be generalized to vectors in 
,
and we will study a standard matrix associated with an orthogonal projection which is a linear transformation.
This matrix representation of an orthogonal projection will be used to study Gram-Schmidt Orthonomalization process and QR-Factorization.
It will be shown that there are many different bases for 
, but the number of elements in every basis for 
is always 
.
We also show that every nontrivial subspace of 
has a basis, and study how to compute an orthogonal basis from a given basis.
Furthermore, we show how to represent a vector as a coordinate vector relative to a given basis,
which is not necessarily a standard basis, and
find a matrix that maps a coordinate vector relative to a basis to a coordinator vector relative to another basis.
7.1 Properties of bases and dimensions
Lecture Movie : https://youtu.be/eePPvXLiffo http://youtu.be/or9c97J3Uk0 ,
Lab : http://matrix.skku.ac.kr/knou-knowls/cla-week-9-sec-7-1.html
Having learned about standard bases, we will now discuss the concept of dimension of a vector space.
Previously, we learned that an axis representing time can be added to the 3-dimensional physical space.
We will now study the mathematical meaning of dimension.
In this section, we define a basis and dimension of 
using the concept of linear independence and study their properties.
Basis of a vector space
|
Definition |
[Basis] |
||
|
|
|
|
|
|
|
If a subset
(1) (2) |
|
|
|
|
|
||
|
|
|||
of 
satisfies the following two conditions, then 
is called a 
:
is 
.
(1) If 
is the subset of 
consisting of all the points on a line going through the origin, then any nonzero vector in 
forms a basis for
.
(2) If a subset 
of 
represents a plane going through the origin,
then any two nonzero vectors in 
that are not a scalar multiple of the other form a basis for 
. ■
Let 
where 
. Since 
is linearly independent and spans 
, 
is a basis for 
. ■
In general 
is a basis for 
, and it is called the standard basis for 
.
How to show linear independence of vectors in 
?
Set of vectors 
in 
is linear independent if
Let 
where 
's are column vectors and 
.
If the homogeneous linear system 
has the unique solution 
,
then the columns of the matrix 
are linearly independent.
In particular, for 
, 
implies the linear independence of the columns of 
.
|
Theorem |
7.1.1 |
|
The following
are linearly independent if and only if
|
|
vectors in 
.
For 
,
.
This gives us the following linear system
.
This linear system always has the trivial solution 
.
Furthermore, 
if and only if 
.
Therefore 
are linearly independent if and only if 
. ■
By Theorem 7.1.1, the following three vectors in 
are linearly independent because 
. ■
● http://matrix.skku.ac.kr/RPG_English/7-TF-linearly-independent.html
with
is a basis for 
.
is a basis for 
, we need to show that 
is linearly independent and it spans 
. 
Since the computed determinant above is not zero, 
is 
. Let 
be a vector in 
.
in 
.
is spanned by 
and so 
)
.
,
,
(1)
spans 
.
of the linear system (1) is invertible,
is a basis for 
. 
be a basis for 
. For 
, any subset 
of 
is 
is linearly independent, then 
must be less than or equal to 
.
is a basis for 
, each vector in 
can be written as a linear combination of 
.
such that
, 
(2)
:
.
.
are linearly independent,
.
. (3)
unknowns, 
, and 
linear equations.
, the linear system (3) must have a nontrivial solution. 
is linearly dependent. 
and 
are bases for 
, then 
.
There are infinitely many bases for 
. However, all the bases have the same number of vectors.
is a basis for 
, then the number of vectors in 
is called the 
and is denoted by 
.
Note that 
. If its subspace 
is the trivial subspace, 
, then 
.
, the following holds:
is linearly independent, then 
is a 
.
spans 
(i.e., 
), then 
is a 
.
,
in 
as its column vectors is
.
is linearly independent.
is a basis for 
. 
is a basis for a subspace 
of 
, then every vector 
in 
can be written as a 
.
Since 
spans 
, a vector 
in 
can be written as a linear combination of the vectors in 
. Suppose
and 
.
.
is linearly independent, 
.
for each 
and 
can be written as a unique linear
. 
is defined to a set which satisfies conditions of Theorem 7.1.4 or Theorem 7.1.5.
. Then
.
can also be written as follows:
.
is not a basis for 
. 
Lecture Movie : 
Lab : 
matrix 
, there are
as its coefficient matrix.
and how to find a basis for the nullspace of 
.
of an 
matrix 
associated to an eigenvalue 
is a subspace of 
. The 
is also a subspace of 
. This is also called the 
Let 
be an 
matrix. For the given augmented matrix 
of a homogeneous linear system with 
,
.
has 
nonzero rows.
, then the only solution to 
is 
. Hence 
, then with permitting column exchanges, we can transform 
as
.
,
,
.
are 
free variables
,
,
vectors as follows:
.
are arbitrary,
vectors can be written as 
.
spans the solution space of 
.
is linearly independent.
is a basis for the null space 
of 
and 
.
matrix 
, the dimension of the solution space of 
is called the 
and denoted by 
)
)
nullity(
).
, find a basis for the null space of 
and the nullity of 
.
The RREF of the augmented matrix 
for 
is
.
.
is
, nullity(
)
2. 
:
and 
are free variables, letting 
for real numbers 
, the solution can be written
.
, nullity(
)
matrix 
, the vectors obtained from the rows of 
spanned by the row vectors 
, that is,
and denoted by 
. 
spanned by the column vectors 
, that is,
, and denoted by 
is called the 
is called the 
and 
respectively, that is, 
,
dim Col
.
are row equivalent
Note that the nonzero rows in the RREF of 
form a basis for the row space of 
.
.
, find a basis for 
which is a subspace of 
:
is equal to the row space of the following matrix
.
.
.
:
is equal to the row space of 
.
:
.
is a basis for the column space of 
.
, the column rank and the row rank of 
are 
The same number for the column rank and the row rank of 
is called the
, and denoted by
.
Col(
), Col(
)=Row(
,
)
Null(
), Null(
)
Row(
),
)
Null(
), Null(
)
Col(
).
, 
is a hyperplane of 
.
is a subspace of 
.
. Then
.
. Then
passing through the origin and perpendicular to the vector 
. 
Lecture Movie: 
Lab: 
.
and the dimensions of the associated vector spaces. 
is defined to be the column rank (or the row rank) and denoted by 
.
Let 
be an 
matrix. If 
, then 
can be written as the following:
)
and nullity(
)
.
, we have
)
nullity(
) 
) and the number of leading 1 in
U be r
. Then
.
0 is 
(n-r) which is the number of free variables in it.
0 and
0 are equivalent, the dimension of solution space of
0 is 
(n-r) which is the nullity(
). So
■
The Rank-Nullity Theorem can be written as follows in terms of a linear transformation:
is the standard matrix for a linear transformation 
, then
, 
.
.
is 
.
)
. Since 
,
is equal to nullity(
)
. 
, where
.
can be computed as follows
)
, and by Theorem 7.3.1,
.
has a solution if and only if
.
Let 
, 
, 
. Then the linear system 
can be written as
. (1)
has a solution.
There exist 
satisfying the linear system (1).
is a linear combination of the columns of 
.
Col
. 
has 
.
, Theorem 7.3.2 implies that the linear system has a solution. 
be a nonzero vector. Then
is called the 
. 
. 
.)
Note that 
nullity(
) 
has 
variables and one equation.
is a 
dimensional subspace of 
).
be a 
dimensional subspace of 
. Then 
for some nonzero vector 
.
Since 
, by the Rank-Nullity Theorem, 
. Thus
for a nonzero vector 
. Therefore
.
Lecture Movie : 
Lab : 
and the theorems
.
, dim Row(
)
dim Col(
).
matrix 
and an invertible 
matrix 
has the block form 
where 
is an 
identity matrix for some 
,
.
, rank(
) ≤ min {
}.
)≤
, dim Col(
)≤
, and
)=dim Row(
)
dim Col(
), it follows that rank(
)≤min {
}.
, the followings hold:
) 
dim Null(
) 
the number of columns of 
)
nullity(
)
).
) 
dim Null(
) 
the number of rows of 
)
nullity(
)
).
(1) follows from Theorem 7.3.1,
Col
and rank
rank 
along with replacing 
in (1) by 
.
of order 
, 
is invertible
) 
.
If 
is invertible, then 
has the trivial solution only and hence Null(
)
,
)
.
REF(
).
and the Rank-Nullity Theorem gives 
.
, 
with multiplication 
defined, the followings hold:
) 
Null(
).
) 
Null(
).
) 
Col(
).
) 
Row(
).
We prove only (1) here.
.
. 
) 
Null(
).
) ≤ min{rank(
), rank(
)}.
by an invertible matrix 
does not change the rank of 
. That is, if 
, then
)
rank(
)
rank(
).
has rank(
)
. Then
of 
satisfies rank(
)
.
must have at least one 
submatrix whose rank is equal to 
.
(1) 
is obtained by taking 
rows and 
columns of 
.
,
.
is 
, there are 
linearly independent rows of 
.
consisting of the 
linearly independent rows has the rank equal to 
.
by taking 
linearly independent columns of 
.
is an 
submatrix of 
whose rank is equal to 
.
matrix 
, the following are equivalent:
is invertible.
.
is 
.
is a product of elementary matrices.
has a unique 
-factorization.
such that 
where 
is a lower triangular matrix with all the diagonal entries equal to 1, 
is an invertible diagonal matrix, and 
is an upper triangular matrix whose main diagonal entries are all equal to 1.
vector 
, 
has a unique solution.
has the unique solution 
.
are linearly independent.
span 
.
has a left inverse.
of order 
such that 
.
.
are linearly independent.
span 
.
has a right inverse.
of order 
satisfying 
.
is one-to-one.
is onto.
is not an eigenvalue of 
.
.
We first prove the following equivalence:
(7) 
(8) 
(11) 
(10)
(7):
has a left inverse 
such that 
. If 
satisfies 
, then 
gives
.
has the unique solution 
.
(8):
has only the trivial solution.
denotes the 
th column vector of 
and 
, then
of the column vectors of 
is linearly independent.
(11): 
are linearly independent. Then 
,
, is equal to 
.
(10):
. Then the rows of 
are linearly independent.
be the 
th standard basis vector. Then the following linear systems
, 
, since rank(
)
rank
.
be a solution to the linear systems, 
is 
.
(6) 
(14) 
(2) 
(1)
(6):
is invertible. Then, for any 
vector 
,
.
has a solution 
.
is another solution. Then
.
has a unique solution.
(14):
, the linear system 
has a unique solution.
to be 
, the 
th standard basis vector, then the following linear system
, 
is the solution to the linear system,
is a right inverse of 
.
(2):
has a right inverse 
such that 
. Then
.
.
(1):
. If we let 
, then it can be shown that
.
is invertible. 
Lecture Movie :
Lab : 
where the vectors and their projections can be visualized.
.
in 
, every vector 
can be expressed as follows:
,
is a scalar multiple of 
and 
is perpendicular to 
. Furthermore, the vectors 
can be written as follows: 
, 
.
and 
.
In the above theorem, the vector 
is called the 
onto 
and
.
is called the 
.
]
defined below
onto 
)
It can be shown that the orthogonal projection 
is a linear transformation.
be a nonzero column vector in 
. Then the standard matrix of
.
is a symmetric matrix and 
.
of the orthogonal projection in 
passing through the origin.
in Chapter 6.)
onto the subspace spanned by a vector 
.
as a unit vector 
on the line 
.
, 
and 
.
. 
for the orthogonal projection 
in 
onto the subspace spanned by the vector 
.
, 
.
on subspace 
in 
be a subspace of 
. Then 
in 
can be uniquely expressed
where 
and 
.
is called 
onto 
.
, 
be a subspace of 
.
is a matrix whose columns are the vectors in a basis for 
, then for each vector 
.
onto the plane 
.
The general solution to 
is
(
).
is 
.
, the standard matrix is 
.
and
,
The standard matrix 
for an orthogonal projection is symmetric and 
Lecture Movie : 
Lab : 
when the linear system has a solution.
Lecture Movie: 
Lab: 
has 
elements, but all the bases are distinct. In this section,
has a basis and
and 
of 
are called
, but all the bases have 
elements and 
is called the dimension of 
in 
, let
.
is orthogonal, then 
is called an 
is a unit vector, then 
is called an 
The above definition can be summarized as follows:
is an orthogonal set. 
)
is an orthonormal set. 
(
Kronecker delta) 
for 
is orthonormal.
, let 
.
is orthogonal, but not orthonormal. 
, let
. 
is orthonormal. 
is an orthogonal set, then 
is an orthonormal set. 
be a set of nonzero vectors in 
. 
is orthogonal, then 
is linearly independent. 
For 
, suppose
.
(
, 
, 
, 
),
.
, 
, we have 
.
implies 
, we have
.
is linearly independent. 
be a basis for 
. If 
is orthogonal, then 
is called an 
is orthonormal, then 
is called an 
are orthonormal bases of 
and the set in (2) is an orthogonal basis of 
.
be a basis for 
. 
is orthonormal, then each vector 
in 
can be expressed as
,
.
is orthogonal, then 
.
We prove (1) only. Since 
is a basis for 
,
can be expressed as a linear combination of vectors in 
as follows:
.
, we have
.
is orthonormal, 
. Hence 
as a linear combination of the vectors in
in (3)
. Then, by Theorem
. Hence 
, 
, 
.
.
)
is an orthonormal basis for 
. Then, since 
, the orthogonal projection 
onto 
in 
.
is an orthogonal basis, but not an orthonormal basis for 
, then
can be written as
.
be a subspace of 
spanned by the two vectors 
in an orthonormal set
. Find the orthogonal projection of 
onto 
and 
perpendicular to 
.
.
perpendicular to 
is
. 
be a basis for 
. Then we can obtain an orthonormal basis for 
from 
.
for 
from the basis 
as follows:
.
be a subspace spanned by 
and let
.
be a subspace spanned by 
and 
and let
.
.
is orthogonal. By taking
,
for 
.
for 
from the two linearly independent vectors 
.
, 
as follows:
.
where
, 
. Use the Gram- Schmidt Orthonomalization to find an orthonormal basis 
for 
using the basis 
for 
.
:
.
, we get
,
,
.
.
is orthonormal as follows:
. Use the Gram-Schmidt Orthonomalization to find an orthonormal basis 
for a subspace of 
for which 
is a basis. 
Lecture Movie : 
Lab : 
matrix 
has 
linearly independent columns, then the Gram-Schmidt Orthogonalization can be used to decompose the matrix 
in the form of 
where the columns of 
are the orthonormal vectors obtained by applying the Gram-Schmidt Orthogonalization to the columns of 
and 
is an upper triangular matrix.
-decomposition is widely used to compute numerical solutions to linear systems, least-squares problems, and eigenvalue and eigenvector problems.
-decomposition.
Lecture Movie : 
Lab : 
.
If 
is an ordered basis for 
,
in 
is uniquely expressed as a linear combination of the vectors in 
as follows:
(1)
are called coordinates of the vector 
relative to the basis 
.
in (1) are called the coordinates of 
relative to the ordered basis 
. Furthermore, the column vector in 
relative to the ordered basis 
and denoted by 
.
in 
can be expressed as follows relative to the standard basis 
for 
:
.
. 
.
find the coordinate vector 
relative to the basis 
for 
.
,
.
.
.
As described above, finding the coordinate vector relative to a basis is equivalent to solving a linear system.
be a basis for 
. For vectors 
in 
and a scalar 
, the following holds:
.
.
In general we have
.
and 
be two different ordered bases for 
.
and 
.
Letting 
, the coordinate vector of 
relative to 
is
,
of 
relative to 
can be expressed as
.
be the coordinate vector of 
relative to 
and matrix 
be
.
,
. (2)
In the equation (2) matrix 
transforms the coordinate vector 
to another coordinate vector 
.
is called a transition matrix from ordered basis 
to ordered basis 
and denoted by 
. Therefore, 
.
This transformation is called 
be the standard basis for 
and 
.
, 
:
from basis 
to basis 
.
. Find the coordinate vector 
.
, show that equation (2) holds.
, we need to compute the coordinate vectors for 
relative to 
. Since
,
. Hence
.
and also 
,
.
.
and 
, 
, 
,
and 
, both of which are bases for 
. Find 
.
, we first find the coordinate vectors for 
relative to 
. Letting
,
as their coefficient matrix.
in its RREF,
, 
, 
at the same time:
.
to 
is
. 
and 
are two different ordered bases for 
and 
be the transition matrix from 
to 
.
is invertible and its inverse 
is the transition matrix from 
to 
, that is, 
.
for 
in 
, compute the following:
from basis 
to basis 
.
relative to basis 
for given 
.
to 
is 
, by Theorem 7.9.2, we have
.
