׸Դϴ.
 ׸ ̸: Bigbook-Linearalgebra-cover.jpg
 ׸ ũ:  587pixel,  798pixel    ׸Դϴ.
 ׸ ̸: sglee-4.GIF
 ׸ ũ:  292pixel,  423pixel

 

 



Chaper 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

7.7 Gram-Schmidt orthonomalization process

7.8 QR-Decomposition; Householder transformations

7.9 Coordinate vectors

7.10 Exercises


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 of satisfies the following two conditions, then is called a basis for :

 

(1) is linearly independent; and

(2) .

 

 

 

 

   

(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 vectors in

 

              

 

are linearly independent if and only if

 

                        .



 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 

                                                                     

x1=vector([1, 2, 3])

x2=vector([-1, 0, 2])

x3=vector([3, 1, 1])

A=column_matrix([x1, x2, x3])       # Generating the matrix with    

                                                     # x1, x2, x3 as its columns in that order

print A.det()    

                                                                   

 9                                                               


We can also use an inbuilt function of Sage to check whether sets of vectors are linearly independent or not.

                                                                     

V=RR^3;x1=vector([1, 2, 3]); x2=vector([-1, 0, 2]); x3=vector([3, 1, 1])

S=[x1, x2, x3]

V.linear_dependence(S)

                                                                   

 []            




Show that with

  is a basis for .


To show that is a basis for , we need to show that is linearly independent and it spans .     


http://sage.skku.edu or http://mathlab.knou.ac.kr:8080/

                                                                     

A=matrix(QQ, 3, 3, [1, 1, 1, 0, 1, 1, 0, 0, 1])

print A.det()

                                                                  

1                                                                



 Since the computed determinant above is not zero, is linearly independent.

We now show that spans . Let be a vector in .

Consider a linear system in .

Note that if this linear system has a solution, then we can say is spanned by and so span()=.

The linear system can be written as

 

            

                         ,

   more explicitly, we have a linear system in ,

                                                             (1)


    Hence we need to show that the linear system (1) has a solution to show that spans .

   Indeed, the coefficient matrix of the linear system (1) is invertible,

     so the linear system (1) has a solution. Therefore is a basis for         


   

Theorem 

 7.1.2

Let be a basis for . For , any subset of is linearly dependent. Therefore, if is linearly independent, then  must be less than or equal to .

 

 http://matrix.skku.ac.kr/CLAMC/chap7/Page6.htm

Since is a basis for , each vector in can be written as a linear combination of .

  That is, there are such that

     ,         (2)

We now consider a formal equation with :


                .


Then, from (2), we get


               .


Since are linearly independent,


               .


Hence we get the following linear system


                     .                         (3)


 The homogeneous linear system (3) has unknowns, , and linear equations.

 Since , the linear system (3) must have a nontrivial solution. Therefore, is linearly dependent.   


Theorem 

 7.1.3

If and are bases for , then .


The proof of this theorem follows the theorem 7.1.2.


 There are infinitely many bases for . However, all the bases have the same number of vectors.


   

Definition

 [Dimension]

 

 

 

 

If is a basis for , then the number of vectors in is called the dimension of and is denoted by .

 

 

 

 


 Note that . If its subspace is the trivial subspace, , then .


   

Theorem

 7.1.4

For , the following holds:

 

 (1) If is linearly independent, then is a basis for .

 (2) If spans (i.e., ), then is a basis for .




The determinant of the matrix having the vectors ,

  in as its column vectors is


                       .


Hence is linearly independent.

By Theorem 7.1.4, is a basis for .                         


   

Theorem 

 7.1.5

If is a basis for a subspace of , then every vector in can be written as a unique linear combination of the vectors in .


 Since spans , a vector in can be written as a linear combination of the vectors in . Suppose


               and  .


       By subtracting the second equation from the first one, we get

              .


        Since is linearly independent, .

       Therefore for each and can be written as a unique linear

       combination of the vectors in .                                  


[Remark] Many a times a basis of is defined to a set which satisfies conditions of Theorem 7.1.4 or Theorem 7.1.5.



Let . Then

 

                   .


However, the vector can also be written as follows:


and

.


This is possible because is not a basis for .               



7.2 Basic spaces of matrix

 

  Lecture Movie : https://youtu.be/BL9Bhj2ufHg http://youtu.be/KDM0-kBjRoM

  Lab : http://matrix.skku.ac.kr/knou-knowls/cla-week-9-sec-7-2.html

   

Associated with an matrix , there are four important vector spaces: row space, column space, nullspace, and eigenspace. These vector spaces are crucial to study the algebraic and geometric properties of the matrix as well as the solution space of a linear system having as its coefficient matrix. In this section, we study the relationship between the column space and the row space of and how to find a basis for the nullspace of .

 


Eigenspace and null space

   

 Definition

 [Solution space, Null space]

 

 

 

 

The eigenspace of an matrix associated to an eigenvalue is a subspace of . The solution space of the homogeneous linear system is also a subspace of . This is also called the null space of and denoted by Null.

 

 

 

 

 

                        ׸Դϴ.

 

Basis and dimension of a solution space


 Let be an matrix. For the given augmented matrix of a homogeneous linear system with ,

    by the Gauss-Jordan Elimination, we can get its RREF, .

 

 Suppose that matrix has nonzero rows.

 

  (1) If , then the only solution to is . Hence the dimension of the solution space is zero.

  (2) If , then with permitting column exchanges, we can transform as


             .


  Then the linear system is equivalent to


                  ,

                  ,

                                      

                 .


  Here, are free variables. Hence, for any real numbers ,

    setting ,

 any solution can be written as a linear combination of vectors as follows:


             .

  

  Since are arbitrary,

             


  are also solutions to the linear system. Hence, the previous linear combination of the vectors can be written as 


                        .


  This implies that spans the solution space of .

  In addition, it can be shown that is linearly independent.

  Therefore is a basis for the null space of and the dimension of the null space is .


   

 Definition

 [Dimension of Null space]

 

 

 

 

For an matrix , the dimension of the solution space of is called the nullity of and denoted by nullity(). That is, dim Null()nullity().

 

 

 

 


For the following matrix , find a basis for the null space of and the nullity of .

                      


 The RREF of the augmented matrix for is


                         .


Hence the general solution is

   

            .


Therefore a basis and the dimension of the null space of is


   ,  nullity() 2.          



Find a basis for the solution space of the following homogeneous linear system and its dimension.

                      


Using Sage we can find the RREF of the coefficient matrix :

                                                                      

A=matrix(ZZ, 3, 4, [4, 12, -7, 6, 1, 3, -2, 1, 3, 9, -2, 11])

print A.echelon_form()

                                                                    

[1 3 0 5]

[0 0 1 2]

[0 0 0 0]


Hence the linear system is equivalent to


                          


Since and are free variables, letting for real numbers , the solution can be written


              .


Hence we get the following basis and nullity:


        , nullity()          


 


Finding a basis for a null space

                                                                      

A=matrix(ZZ, 3, 4, [4, 12, -7, 6, 1, 3, -2, 1, 3, 9, -2, 11])

A.right_kernel()

                                                                    

Free module of degree 4 and rank 2 over Integer Ring

Echelon basis matrix:

[ 1  3  4 -2]

[ 0  5  6 –3]


Computation of nullity

                                                                      

A.right_nullity()

                                                                     

2                                                                 





Column space and row space

   

 Definition

 

 

 

 

 

For a given matrix , the vectors obtained from the rows of  

 

            

 

are called row vectors and the vectors obtained from the columns of

 

           

 

are called column vectors. The subspace of spanned by the row vectors , that is,

 

                           

 

is called the row space of and denoted by Row. The subspace of spanned by the column vectors , that is,

 

                           

 

is called the column space of , and denoted by Col. The dimension of the row space of is called the row rank of , and the dimension of the column space of is called the column rank of . The dimensions are denoted by  and respectively, that is,            

                  dim Row,dim Col .

 

 

 

 

      


   

Theorem

 7.2.1

If two matrices and are row equivalent, then they have the same row space. 

   


     

 http://www.millersville.edu/~bikenaga/linear-algebra/matrix-subspaces/matrix-subspaces.html


 Note that the nonzero rows in the RREF of form a basis for the row space of . The same result can be applied to the column space of .



For the following set , find a basis for which is a subspace of :


           


Note that the subspace is equal to the row space of the following matrix


                           .


 By Theorem 7.2.1, it is also equal to the row space of the RREF of


                          .


Therefore the collection of nonzero row vectors of


                 


is a basis for .


                                                                     

A=matrix(4, 5, [1, 2, 1, 3, 2, 3, 4, 9, 0, 7, 2, 3, 5, 1, 8, 2, 2, 8, -3, 5])

A.row_space()

                                                                    

Free module of degree 5 and rank 3 over Integer Ring

Echelon basis matrix:

[  1   0   7   0 -39]

[  0   1  -3   0  31]

[  0   0   0   1  -7]                                            



Find a basis for the column space of :


                      


The column space of is equal to the row space of .

   By Theorem 7.2.1, it is also equal to the row space of the RREF of :

                             .


Therefore is a basis for the column space of .

 

                                                                     

A=matrix(4, 5, [1, 2, 1, 3, 2, 3, 4, 9, 0, 7, 2, 3, 5, 1, 8, 2, 2, 8, -3, 5])

A.column_space()

                                                                    

Free module of degree 4 and rank 3 over Integer Ring

Echelon basis matrix:

[ 1  0  0 -1]

[ 0  1  0  1]

[ 0  0  1  0]                                                    




   

Theorem 

 7.2.2

For , the column rank and the row rank of are equal.


For the proof of Theorem 7.2.2, see http://mtts.org.in//expository-articles


 The same number for the column rank and the row rank of is called the rank of , and denoted by


                        .

 

[Remark]

Relationship between vector spaces associated with a matrix

 

 

 

 

Col(), Col()=Row(,

Row()Null(), Null()Row(),

Col()Null( ), Null( )Col().

  http://linear.ups.edu/html/section-CRS.html

 

 

 

 

 


For , is a hyperplane of .

   It is easy to see that is a subspace of .




(1) If . Then

                    

is a line in the plane passing through the origin perpendicular to the vector .

(2) Let . Then

                    

is the plane in passing through the origin and perpendicular to the vector .                         




7.3 Dimension theorem (Rank-Nullity Theorem)

 

 Lecture Movie: https://youtu.be/H1mFmDT5pUY http://youtu.be/ez7_JYRGsb4

 Lab: http://matrix.skku.ac.kr/knou-knowls/cla-week-9-sec-7-3.html

In Section 7.2, we have studied the vector spaces associated to a matrix .

  In this section, we study the relationship between the size of matrix and the dimensions of the associated vector spaces.  




Rank


 Definition

 [Rank]

 

 

 

 

The rank of a matrix 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:


                    


Hence rank()  and  nullity().


   

Theorem 

 7.3.1 [Rank-Nullity theorem]

For any , we have

                                           rank() nullity()

Let )  and the number of leading 1 in    U be   r.  Then.

 But the dimension of solution space of   0   is   (n-r)  which is the number of free variables in it.

  Since   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:

    If is the standard matrix for a linear transformation , then


              ,     .


Hence

                 .



The RREF of is .

Hence rank().  Since ,

  the dimension of the solution space for is equal to nullity().                        





Compute the rank and nullity of the matrix , where


                    .


The RREF of can be computed as follows

                                                                    

A = matrix(ZZ, 4, 5, [1, -2, 1, 1, 2, -1, 3, 0, 2, -1, 0, 1, 1, 3, 4, 1, 2, 5, 13, 5])

A.echelon_form()

                                                                 

[1 0 3 7 0]

[0 1 1 3 0]

[0 0 0 0 1]

[0 0 0 0 0]


Hence rank(), and by Theorem 7.3.1,

  .                           


http://matrix.skku.ac.kr/RPG_English/7-B2-rank-nullity.html 


 

                                                                   

print A.rank()                   # rank computation

print A.right_nullity()           # nullity computation

                                                                  

3

2                                                              



   

Theorem 

 7.3.2

A linear system has a solution if and only if

 

                        .


 Let , , . Then the linear system can be written as


                 .                   (1)


       Hence we have the following:


       has a solution.

                  There exist satisfying the linear system (1).

                   is a linear combination of the columns of .

                  Col

                  .                             


The linear system has its matrix form as following.                         .

                                                                     

A = matrix(ZZ, 3, 3, [1, -2, 2, 1, 4, 3, 2, 2, 5])

b = vector([1, 2, 3])

print A.rank()                               # rank(A)

print A.augment(b).rank()            # rank[A : b]

                                                                   

2

2

Since , Theorem 7.3.2 implies that the linear system has a solution.                                   


   

Definition 

 [Hyperplane]

 

 

 

 

Let be a nonzero vector. Then

    is called the orthogonal complement of .
This can be understood as the solution space of . (that is .)

 

 

 

 


Note that nullity() since has variables and one equation.

     The orthogonal complement of is a hyperplane of ( dimensional subspace of ).


   

Theorem 

 7.3.3

Let be a dimensional subspace of . Then for some nonzero vector .


 Since , by the Rank-Nullity Theorem, . Thus

        for a nonzero vector . Therefore

                       .                    


Note: The Four Fundamental Subspaces

        http://www.itshared.org/2015/06/the-four-fundamental-subspaces.html



7.4  Rank theorem

 

 Lecture Movie :  https://youtu.be/eYVZiWwB89A http://youtu.be/8P7cd-Eh328

  Lab : http://matrix.skku.ac.kr/knou-knowls/cla-week-9-sec-7-4.html

In this section, we study the relationship between the rank of a matrix and the theorems that is related to the dimension of subspaces associated to .

   

Theorem 

 7.4.1 [Rank theorem]

For any , dim Row()dim Col().


We have seen that there exist an invertible matrix and an invertible matrix such that has the block form where is an identity matrix for some , and the rest of the matrix is zero. For this matrix, it is obvious that row rank = column rank = . The strategy is to reduce an arbitrary matrix to this form. see the detail in the following.

http://ocw.mit.edu/courses/mathematics/18-701-algebra-i-fall-2010/study-materials/MIT18_701F10_rrk_crk.pdf                                                           

   

Theorem 

 7.4.2

  For any ,    rank() min {}.


Since dim Row(), dim Col(), and rank()=dim Row()dim Col(), it follows that rank()min {}.                 



Theorem 

 7.4.3 [Rank theorem]

Given , the followings hold:

 

(1) dim Row() dim Null() the number of columns of

                                (that is, rank()nullity()).

 

(2) dim Col() dim Null() the number of rows of

                                 (that is, rank()nullity()).


 (1) follows from Theorem 7.3.1,

       (2) follows from the fact that RowCol and rankrank  

             along with replacing in (1) by .                 


   

Theorem 

 7.4.4

For a square matrix of order , is invertible if and only if

                        rank() .


 If is invertible, then has the trivial solution only and hence Null(), giving nullity().

       By the Rank-Nullity Theorem, we have . This can be reversed.            


Find the rank and nullity of the following matrix:


                     


Using Gaussian Elimination,

    
                        

                           
                       REF().


 Hence and the Rank-Nullity Theorem gives .

 http://sage.skku.edu

                                                                     

A=matrix(3, 4, [1, 3, 1, 7, 2, 3, -1, 9, -1, -2, 0, -5])

print A.rank()                   # rank computation

print A.right_nullity()           # nullity computation

                                                                   

3

1                                                               


   

Theorem 

 7.4.5

For matrices , with multiplication defined, the followings hold:

 

(1) Null(Null().

(2) Null() Null().

(3) Col(Col().

(4) Row() Row().


We prove only (1) here.

           .

       .     This implies Null(Null().

     Others can be shown similarly.                                       


   

Theorem 

 7.4.6

                   rank() min{rank(), rank()}.


Follows from theorem 7.4.5.

   

Theorem 

 7.4.7

Multiplying a matrix by an invertible matrix does not change the rank of  . That is, if , then

 

                     rank()rank()rank().

 

Follows from theorem 7.4.6.


   

Theorem 

 7.4.8

Suppose has rank(). Then

 

(1) Every submatrix of satisfies rank().

(2) must have at least one submatrix whose rank is equal to .


(1) Suppose the submatrix is obtained by taking rows and columns of . Since ,

               .

      (2) Since the rank of is , there are linearly independent rows of .

     Then the matrix consisting of the linearly independent rows has the rank equal to .

      We now form a matrix by taking linearly independent columns of .

      Then is an submatrix of whose rank is equal to .                                 



Main Theorem of Inverse Matrices


   

Theorem 

 7.4.9 [Invertible Matrix Theorem]

For an matrix , the following are equivalent:

 (1) is invertible.

 (2) .

 (3) is (row) equivalent to .

 (4) is a product of elementary matrices.

*(5) has a unique -factorization. That is, there exists a permutation matrix 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.

 (6) For any vector , has a unique solution.

 (7) has the unique solution .

 (8) The column vectors of are linearly independent.

 (9) The column vectors of span .

*(10) has a left inverse. That is, there exists a matrix of order such that .

 (11) .

 (12) The row vectors of are linearly independent.

 (13) The row vectors of span .

*(14) has a right inverse. That is, there exists a matrix of order satisfying .

 (15) is one-to-one.

 (16) is onto.

 (17) is not an eigenvalue of .

 (18) .


 We first prove the following equivalence:

 


(10) (7) (8) (11) (10)


(10) (7): Suppose has a left inverse such that . If satisfies , then gives


                       .


Hence has the unique solution .


(7) (8): Suppose has only the trivial solution. If denotes the th column vector of and , then


               


Hence the set of the column vectors of is linearly independent.


(8) (11): Suppose the column vectors of are linearly independent. Then , which is equal to the maximum number of linearly independent columns of , is equal to .


(11) (10): Suppose . Then the rows of are linearly independent. Let be the th standard basis vector. Then the following linear systems


                             

      are consistent for all , since rank()rank.

     Letting be a solution to the linear systems, is (a left) inverse of .


(1) (6) (14) (2) (1)


(1) (6): Suppose is invertible. Then, for any vector ,


                       .


Hence has a solution .

  For the uniqueness of the solution, suppose is another solution. Then


                   .


Therefore has a unique solution.


(6) (14): Suppose that for each , the linear system has a unique solution.

   If we take to be , the th standard basis vector, then the following linear system


                          


also has a unique solution. If is the solution to the linear system,

         then the matrix is a right inverse of .


(14) (2): Suppose has a right inverse such that . Then


                     .


Hence .


(2) (1): Suppose . If we let , then it can be shown that

                                        .

Hence is invertible.                                                     





7.5 Projection Theorem

 

 Lecture Movie : http://youtu.be/GlcA4l8SmlM, http://youtu.be/Rv1rd3u-oYg 

 Lab : http://matrix.skku.ac.kr/knou-knowls/cla-week-10-sec-7-5.html

In Chapter 1, we have studied the orthogonal project in where the vectors and their projections can be visualized.

    In this section, we generalize the concept of projection in .

     We also show that the projection is a linear transformation and find its standard matrix,

    which will be crucial to study the Gram-Schmidt Orthogonalization and the QR-Decomposition*.



Orthogonal Projection in


                 


                    

                     



Projection (in 1-Dimensional subspace) on  

   

Theorem

7.5.1 [Projection]

For any nonzero vector in , every vector can be expressed as follows:

                  ,

 

where is a scalar multiple of and is perpendicular to . Furthermore, the vectors can be written as follows: 

                  .

The proof of the above theorem is similar to that in case of orthogonal projection in the and .


 In the above theorem, the vector is called the orthogonal projection of onto and

      denoted by .

      The vector is called the orthogonal complement of the vector .


   

Definition

 [Orthogonal projection on ]

 

 

 

 

The transformation defined below

 

                     

 

is called the orthogonal projection of onto (=span).

 

 

 

 


 It can be shown that the orthogonal projection is a linear transformation.

           (http://www.math.lsa.umich.edu/~speyer/417/OrthoProj.pdf)

  

Theorem

 7.5.2

Let be a nonzero column vector in . Then the standard matrix of

 

                       

 

is

 

                        .

Note that is a symmetric matrix and .

For the proof of this theorem, see the website:

http://ocw.mit.edu/courses/mathematics/18-06sc-linear-algebra-fall-2011/least-squares-determinants-and-eigenvalues/projections-onto-subspaces/MIT18_06SCF11_Ses2.2sum.pdf 



Using the above theorem, find the standard matrix of the orthogonal projection in

                onto the line passing through the origin.

 

  (Compare this with in Chapter 6.)

This is a problem of finding the orthogonal projection of a vector onto the subspace spanned by a vector .

     Hence we take as a unit vector on the line .

     Since the slope of the line is , and .

 

Therefore, by the previous theorem,


          

            .                                           


Find the standard matrix for the orthogonal projection in onto the subspace spanned by the vector .


                 ,

Hence, .                              



Projection of on subspace   in

   

Theorem

 7.5.3

Let be a subspace of . Then every vector in can be uniquely expressed as follows:

 

                  where   and .

 

In this case is called the orthogonal projection of onto and is denoted by .

                         


                ,


http://www.math.lsa.umich.edu/~speyer/417/OrthoProj.pdf

   

Theorem

 7.5.4

Let be a subspace of .

  If is a matrix whose columns are the vectors in a basis for , then for each vector

 

                    .


A rigorous proof uses facts from Sec 7.7 and *Sec 7.8.

               http://www.math.lsa.umich.edu/~speyer/417/OrthoProj.pdf 



Find the standard matrix for the orthogonal projection in   onto the plane .


 The general solution to is


             ().


Thus is a basis for the solution space of the plane .


Hence, by taking , the standard matrix is  

                   .

Since and

                 ,


         

                                                                    

M=matrix(3, 2, [4, -2, 1, 0, 0, 1])

print M*(M.transpose()*M).inverse()*M.transpose()

                                                                   

[20/21  4/21 -2/21]

[ 4/21  5/21  8/21]

[-2/21  8/21 17/21]                                             


 The standard matrix for an orthogonal projection is symmetric and idempotent ().

    

 

[Remark]  Simulation of the projection of two vectors

 

 

 

 

http://www.geogebratube.org/student/m9503

 

    

 

 

 

 

 



7.6 * Least square solutions

 

 Lecture Movie : https://youtu.be/BC9qeR0JWis

 Lab : http://matrix.skku.ac.kr/knou-knowls/cla-week-10-sec-7-6.html

     Previously, we have studied how to find solve the linear system when the linear system has a solution.

   In this section, we study how to find an optimal solution using projection when the linear system does not have any solution.


Details can be found in the following websites:

        http://www.seas.ucla.edu/~vandenbe/103/lectures/ls.pdf




Least square solutions with GeoGebra

<Simulations> http://www.geogebratube.org/student/m12933


     



Least square solutions with Sage

<Simulations> http://matrix.skku.ac.kr/2012-album/11.html


     




7.7 Gram-Schmidt Orthonomalization process

 

 Lecture Movie: http://youtu.be/gt4-EuXvx1Y , http://youtu.be/EBCi1nR7EuE

 Lab: http://matrix.skku.ac.kr/knou-knowls/cla-week-10-sec-7-7.html


Every basis of has elements, but all the bases are distinct.

  In this section, we show that every nontrivial subspace of has a basis and how to find an orthonormal basis from a given basis.



[Remark]

 

 

 

 

 

The subspaces and of are called trivial subspaces.

There are many different bases for , but all the bases have elements and the number is called the dimension of .

 

 

 

 

 




Orthogonal set and orthonormal set

   

Definition 

 

 

 

 

 

For vectors in , let

 

                             .

 

If every pair of vectors in is orthogonal, then is called an orthogonal set. Furthermore, if every vector in the orthogonal set is a unit vector, then is called an orthonormal set.

 

 

 

 


 The above definition can be summarized as follows:


  is an orthogonal set.           ()

  is an orthonormal set.      ( Kronecker delta) 


(1) The standard basis for is orthonormal.


(2) In , let . Then is orthogonal, but not orthonormal.


(3) In , let

      .

Then the set is orthonormal.  

                                

(4) If is an orthogonal set, then is an orthonormal set.                                                           





Orthogonality and Linear independence


   

Theorem

 7.7.1

Let be a set of nonzero vectors in . If is orthogonal, then is linearly independent.


 For , suppose


                       .

       

        Then, for each (, , , ),


                       .


       That is,


               


       Since, for , we have


                 .


       Since implies ,  we have


                        .


       Therefore, is linearly independent.                             



Orthogonal Basis and Orthonormal Basis


   

Definition

 [Orthonormal basis]

 

 

 

 

Let be a basis for . If is orthogonal, then is called an orthogonal basis. If is orthonormal, then is called an orthonormal basis.

 

 

 

 



Sets in (1) and (3) of are orthonormal bases of and the set in (2) is an orthogonal basis of .

  

Theorem

 7.7.2

Let be a basis for .

 

(1) If is orthonormal, then each vector in can be expressed as

 

                       ,

 

   where .

 

(2) If is orthogonal, then .


 We prove (1) only. Since is a basis for ,

    each vector can be expressed as a linear combination of vectors in as follows:


                    .


       For each , we have


          

                  .


       Since is orthonormal, . Hence


                       .                        


Write as a linear combination of the vectors in

    

 that is the orthonormal basis for in (3)


Let . Then, by Theorem 7.7.2,

 . Hence

       , , .


.            


Theorem

 7.7.3  (General form of Theorem 1.3.1 in )

(1) Suppose is an orthonormal basis for .

   Then, since , the orthogonal projection onto the subspace

     in is

 

           .

 

(2) If is an orthogonal basis, but not an orthonormal basis for ,

    then can be written as

          .


Let be a subspace of spanned by the two vectors  in an orthonormal set

 . Find the orthogonal projection of onto and the orthogonal component of perpendicular to .

         

            .


The orthogonal component of perpendicular to is

.    



Gram-Schmidt orthonormalization process


   

Theorem 

 7.7.4

Let be a basis for . Then we can obtain an orthonormal basis  for from .


[Gram-Schmidt Orthonomalization]

We first derive an orthogonal basis for from the basis as follows:



[Step 1] Take .


[Step 2] Let be a subspace spanned by and let

         .


[Step 3] Let be a subspace spanned by and and let

        .


[Step 4] Repeat the same procedure to get

    

        where      .


It is clear that is orthogonal. By taking

                        ,

we get an orthonormal basis for .                         



The above process of producing and orthonormal basis from a given basis is called the Gram-Schmidt Orthonormalization process.

[Remark]

Simulation for Gram-Schmidt Orthonomalization

 

 

 

 

http://www.geogebratube.org/student/m58812

 

    

 

 

 

 

 


Use the Gram-Schmidt Orthonomalization to find an orthonormal basis for from the two linearly independent vectors and .


We first find orthogonal vectors , as follows:


[Step 1]

[Step 2]

            .

Finally where

       

   is an orthonormal basis.                                       


Let . Use the Gram- Schmidt Orthonomalization to find an orthonormal basis for using the basis for .


We first find orthogonal vectors :

[Step 1] Take .

[Step 2]

           

[Step 3]

           


By normalizing , we get

         ,

         ,

         .

Therefore,

        



Computation for an orthogonal basis

                                                                     

x1=vector([1,1,0])

x2=vector([0,1,2])

x3=vector([1,2,1])

A=matrix([x1,x2,x3])         # generate a matrix with x1, x2, x3

[G,mu]=A.gram_schmidt()   # find an orthogonal basis. A==mu*G

print G

                                                                   

[   1    1    0]

[-1/2  1/2    2]

[-2/9  2/9 –1/9]


Normalization

                                                                    

B=matrix([G.row(i) / G.row(i).norm() for i in range(0, 3)]); B

# The rows of matrix B are orthonormal

                                                                   

[   1/2*sqrt(2)     1/2*sqrt(2)              0]

[-1/3*sqrt(1/2)   1/3*sqrt(1/2)  4/3*sqrt(1/2)]

[          -2/3            2/3           -1/3]


Therefore, we get an orthonormal basis

     .

We can verify if is orthonormal as follows:


Checking for orthonormality

                                                                     

print B*B.transpose()     # Checking if B is an orthogonal matrix.

print

print B.transpose()*B

                                                                   

[1 0 0]         [1 0 0]

[0 1 0]         [0 1 0]

[0 0 1]         [0 0 1]                                           


Let . Use the Gram-Schmidt Orthonomalization to find an orthonormal basis for a subspace of for which is a basis. 


 

   





7.8 * QR-Decomposition; Householder Transformations

 

 Lecture Movie : http://www.youtube.com/watch?v=crMXPi2lgGs 

 Lab : http://matrix.skku.ac.kr/knou-knowls/cla-week-10-sec-7-8.html

If an 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.

 

  The -decomposition is widely used to compute numerical solutions to linear systems, least-squares problems, and eigenvalue and eigenvector problems.

 In this section, we briefly introduce the -decomposition.



Details can be found in the following websites:

http://www.math.ucla.edu/~yanovsky/Teaching/Math151B/handouts/GramSchmidt.pdf 

https://inst.eecs.berkeley.edu/~ee127a/book/login/l_mats_qr.html 

http://www.ugcs.caltech.edu/~chandran/cs20/qr.html

 

        ׸Դϴ.
 ׸ ̸: qr.gif
 ׸ ũ:  720pixel,  540pixel




7.9 Coordinate vectors

 Lecture Movie : http://youtu.be/M4peLF7Xur0,  http://youtu.be/tdd7gbtCCRg

 Lab : http://matrix.skku.ac.kr/knou-knowls/cla-week-10-sec-7-9.html

In a finite-dimensional vector space, a basis is closely related to a coordinate system.

  We have so far used the coordinate system associated to the standard basis of .

  In this section, we introduce coordinate systems based on non-standard bases.

  We also study the relationship between coordinate systems associated to different bases. 


 If is an ordered basis for ,

     then any vector in is uniquely expressed as a linear combination of the vectors in as follows:

 

                            (1)

 

  Then are called coordinates of the vector relative to the     basis .


  

Definition

 [Coordinate vectors]

 

 

 

 

The scalars in (1) are called the coordinates of relative to the ordered basis . Furthermore, the column vector in

 

                               

 

is called the coordinate vector of relative to the ordered basis and denoted by .

 

 

 

 



The vector in can be expressed as follows relative to the standard basis for :


                     .


Therefore 

                          .                          



Let .

   For find the coordinate vector relative to the basis for .


From

          ,


we get the linear system .


By solving this linear system, we get .


                     .                             



 As described above, finding the coordinate vector relative to a basis is equivalent to solving a linear system.


Theorem

 7.9.1

Let be a basis for . For vectors in and a scalar , the following holds:

 

(1) .

(2) .


 In general we have

           .



Change of Basis


Let and be two different ordered bases for .

   In the following, we consider a relationship between and .

   

                      ׸Դϴ.


 Letting , the coordinate vector of relative to is

                              ,

  and  the coordinate vector of relative to can be expressed as


        .


  Let  be the coordinate vector of relative to and matrix be

                .

  Then we have



               

                      ,


  that is, .                                                (2)


 In the equation (2) matrix transforms the coordinate vector to another coordinate vector .

   Hence the matrix is called a transition matrix from ordered basis to ordered basis and denoted by . Therefore, .


 This transformation is called change of basis.

      Note that the change of basis does not modify the nature of a vector,

    but it changes coordinate vectors. The following example illustrates this.




Let be the standard basis for and .

    For the two different ordered bases , :


(1) Find the transition matrix from basis to basis .

(2) Suppose . Find the coordinate vector .

(3) For , show that equation (2) holds.

(1) Since , we need to compute the coordinate vectors for relative to . Since

                                 ,

 . Hence

                                .


(2)


(3) Since and also ,

                .

   It can be easily checked that .



For and , , ,

     let and , both of which are bases for . Find .


Since , we first find the coordinate vectors for relative to . Letting

,

we get the following three linear systems:

                


Note that all of the above linear systems have as their coefficient matrix.

     Hence we can solve the linear systems simultaneously using the RREF of the coefficient matrix.

   That is, by converting the augmented matrix in its RREF,

    we can find the values of , , at the same time:

 

       

has the RREF

      .

Therefore, the transition matrix from to is


                       .          

http://matrix.skku.ac.kr/RPG_English/7-MA-transition-matrix.html 

                                                                     

x1=vector([1,2,0]);x2=vector([1,1,1]);x3=vector([2,0,1])

A=column_matrix([x1, x2, x3])

y1=vector([4, -1, 3]);y2=vector([5, 5, 2]);y3=vector([6, 3, 3])

B=column_matrix([y1, y2, y3]) # Creating the matrix with columns y1, y2, y3

aug=A.augment(B, subdivide=True)

aug.rref()      

                                                                   

[ 1  0  0|-1  2  1]

[ 0  1  0| 1  1  1]

[ 0  0  1| 2  1  2]                                              


  

Theorem

 7.9.2

Suppose and are two different ordered bases for and be the transition matrix from to .

 Then is invertible and its inverse is the transition matrix from to , that is, .


For the two bases for in , compute the following:


(1) The transition matrix from basis to basis .


(2) The coordinate vector relative to basis for given .


(1) Since the transition matrix from to is , by Theorem 7.9.2, we have

               .


(2) .                 

 

                                                                     

x1=vector([1,2,0]);x2=vector([1,1,1]);x3=vector([2,0,1])

x0=vector([1,5,2])

A=column_matrix([x1, x2, x3])

y1=vector([4, -1, 3]);y2=vector([5, 5, 2]);y3=vector([6, 3, 3])

B=column_matrix([y1, y2, y3])

aug=B.augment(A, subdivide=True)

Q=aug.rref()

print Q    

                                                                   

[   1    0    0|-1/2  3/2 -1/2]

[   0    1    0|   0    2   -1]

[   0    0    1| 1/2 -5/2  3/2]