Linear Algebra PDF Notes

# 4.5 The dimension of a vector space ## Theorem 10 If a vector space *V* has a basis *B = {b₁,..., b_n} (with *n* vectors), then any set in *V* containing more than *n* vectors is linearly dependent. (We already know this for *Rⁿ*, but now we are talking about a ge...

# 4.5 The dimension of a vector space ## Theorem 10 If a vector space *V* has a basis *B = {b₁,..., b_n} (with *n* vectors), then any set in *V* containing more than *n* vectors is linearly dependent. (We already know this for *Rⁿ*, but now we are talking about a general vector space) ## Proof Let us reduce the problem to a problem in *Rⁿ*, where we know the answer. Suppose *(u₁,..., u_m)* is the set of "Vectors" in question, with *m > n*. Each vector *u_i* has coordinates *(u_i)*_B in basis *B*. The number of coordinates is *n*, so *u_i*_B = (u_i¹, u_i²,..., u_iⁿ) are all in *Rⁿ*. But in *Rⁿ* any set of *m* vectors (with *m > n*) is linearly dependent. So, there exists a set of scalars *c₁,..., c_m*, not all zero, such that: *c₁*(u₁)_B + *c₂*(u₂)_B +... + *c_m*(u_m)_B = 0 Use linearity of coordinate transformation: (*c₁u₁ + c₂u₂ +... + c_mu_m)*_B = 0. This means the vector in parentheses is zero: *c₁u₁ + c₂u₂ +... + c_mu_m = 0* and *c₁,..., c_m* are not all zero *⇒* {u₁,..., u_m} is *lin. dependent*. ## Theorem 11 If a vector space *V* has a basis consisting of *n* "vectors", every other basis of *V* must have exactly *n* "vectors". ## Proof Suppose *B₁* is a basis with *n* "vectors", and *B₂* is any other basis. Then, *B₂* cannot have more than *n* "vectors". On the other hand, if *B₂* had less than *n* "vectors" and still be a basis, then *B₁* only could have the same number of vectors. So, *B₂* has exactly the same number of "vectors" - *n*. ## Def If a vector space *V* is spanned by a finite number of "vectors", then *V* is called *finite-dimensional*. In this case *dim V* (i.e. dimension of *V*) is the number of vectors in some basis (the basis can be obtained by reducing, if necessary, the spanning set). ## Def If a vector space *V* cannot be spanned by a finite number of vectors, such a space is called *infinite-dimensional*. ## Example 1 * Space *Rⁿ* is spanned by the standard basis *e₁, e₂,..., e_n*, where *e₁ = (1, 0,..., 0)*, *e₂ = (0, 1,..., 0)*, etc. There is *n* vectors in this basis, so *dim Rⁿ = n*. ## ⑥ * The space *P₂* of polynomials of *deg ≤* 2 is spanned by the basis {1, *t*, *t²*. Therefore, *dim P₂ = 3*. ## Similarly * *dim P_n* = *n* +1. ## The space * *P* of polynomials of arbitrary degree is infinite-dimensional. ## Example 2 Let *H = span{v₁, v₂}* with *v₁ = (1, 3)^T*, *v₂ = (-1, 1)^T*. Since *v₁, v₂* is a *lin. independent set*, and it spans *H*, this set is a basis for *H*. Therefore *dim H = 2*. ## Example Suppose *H = span{v₁, v₂, v₃}* where *v₁ = (1, 0)^T*, *v₂ = (0, 1)^T* and *v₃ = (1, -1)^T*. What’s *dim H*? Is the set *v₁, v₂, v₃* *linearly independent*? Note that *v₃ = v₁ - v₂*, so *v₃* is a combination of *v₁* and *v₂* and can be removed from the spanning set, but *H = span{v₁, v₂}* nevertheless. Set *{v₁, v₂}* is an independent spanning set → basis → *dim H = 2*. ## Example 4 Subspaces of *R³* * *dim = 0*: {0} * *dim = 1*: All lines through 0 * *dim = 2*: All planes through 0 * *dim = 3*: *R³* itself ## Theorem 12 Let *H* be a subspace of a finite-dimensional vector space *V*. Then, any linearly independent set of "vectors" in *H* can be expanded (if it is not a basis yet) to a basis of *H*. Also, *dim H ≤ dim V*. ## Proof Let *S* be a linearly independent set in *H*, *S = {u₁,..., u_k}*. If *S* spans *H*, *S* is a basis for *H*. If *S* does not span *H*, there is a vector *u_k+1* in *H* such that *u_k+1* cannot be expressed through *u₁,..., u_k*. Then, set *S₁ = {u₁,..., u_k, u_k+1}* is linearly independent. If *S₁* spans *H*, then stop. *S₁* is a basis. Otherwise, find vector *u_k+2* that is not in *S₁*, and add it, making *S₂ = {u₁,..., u_k, u_k+1, u_k+2}*. And, so on. This process will have to stop, since the number of vectors in a linearly independent set cannot exceed *dim V*. So, one of the sets *S_k* will have to span *H*, and the number of vectors in *S_k* will not exceed *dim V*. Thus, *dim H ≤ dim V*. ## Theorem 13 The basis theorem Let *V* be an *n*-dimensional vector space. Then, any independent set of *n* "vectors" is a basis of *V*. And, any set of *n* "vectors" that spans *V* is automatically linearly independent. ## Proof * **a)** Suppose *S* is a linearly independent set of *n* "vectors". By Theorem 12, it can be extended to a basis of *V*. But, it cannot have any more "vectors" without becoming dependent; therefore, *S* is already a basis of *V*. * **b)** Suppose *S* has *n* "vectors", and spans *V*. Assume *S* is dependent. Then, a vector can be removed from *S*, and the new set will still span *V*, with (*n* - 1) vectors. One can continue until the new *S* is independent and still spans *V*. But then it would be a basis of *V* with less than *n* vectors. This cannot be since *dim V = n*. Therefore (this assumption is false. The set *S* is independent and it spans *V*, *S* is a basis for *V*. ## Def The *rank* of (*m x n*) matrix *A* is the dimension of the column space *Col A*, and the *nullity* of *A* is the dimension of the null space *Nul A*. ## Theorem 14 The rank theorem The dimension of the column space and the dim. of the null space of a matrix *A* satisfy the equation *rank A + nullity A = number of columns in A*. ## Proof *number of pivot columns + number of non-pivot columns = number of columns* *rank A + nullity A = number of columns* *dim Col A + dim Nul A = number of columns* ## Example 6 * **a)** If *A* is (*x x g*) and *nullity = 2*, what is the *rank A*? * **b)** Can a (*6 x 9*) matrix have *nullity* equal to 2? ## Solutions * **a)** *rank A + nullity A = number of columns* * * * * * * rank A + 2 = 9 * ⇒ *rank A = 7*. * **b)** *rank A + nullity A = number of columns* * * * * * rank A + 2 = 9 But, there can be no more than 6 linearly independent columns, so *rank A ≤ 6*. *nullity A = 9 - rank A ≥ 9 - 6 = 3* ## Theorem (Addition to theorem 8, section 2.3) * **a)** (*n x n*) matrix *A* is invertible * **b)** The columns of *A* form a basis for *Rⁿ* * **c)** *Col A = Rⁿ* * **d)** *rank A = n* * **e)** *Nullity A = 0* (i.e. there is only a trivial solution to *Ax = 0*) * **f)** *Nul A = {0_y}* (This is really the same as *e*) ## Chapter 3 ### 3.1 Introduction to Determinants We have already defined a determinant of a (*2 x 2*) matrix. Suppose *A = ( a b c d )* Then, if the quantity *(ad - bc)* ≠ 0, the inverse exists – this is called *det(A)*. *A^-1 = ( d -b -c a )* / *det(A)* If *det(A) = ad - bc = 0*, the matrix is not invertible. Let us start with geometrical meaning of *det(A)*. Suppose Vector *x* = (a)^T, y = (d)^T *←* there are *columns* spanned by the *columns* of matrix *A*. What’s the area of a parallelogram spanned by *x* and *y*? [Insert image of the parallelogram] Area? Let’s put some angles in the figure. Also, I would like to have vector *x̃* perpendicular to *x*, and the same length, so *|x̃| = |x|*. *x̃* is easy to find, *x̃* = (c)^T. *Area of a parallelogram = H|x|*. But *H = |y|sin θ*. So *Area = |x||y|sin θ*. We would like to use *dot product* of two vectors, for example *b · c = |b||c|cos ψ* where *ψ* is the angle between *b* and *c*. But in our formula we have *sin θ*. In *dot product*, there is *cosine*. Note that *θ + α = 90° = π/2*. But then *sin(θ) = sin(π/2 - α) = cos α*. *α* is the angle between *x̃* and *ỹ*. So that *x̃ · y = |x̃||y|cos α = |x||y|sin θ = Area*. So, *Area = x̃ · y = (-c) · (d)^T = ad - bc = det(A)*. So, in our example, *det(A)* represents the area of the parallelogram. One can notice, though, that if we interchange the vectors *(a)^T* *(c)^T*, the *Area = bc - ad = - det(A)*. In fact: ## Theorem If *A* is a (*2 x 2*) matrix, then the absolute value of *det(A)* represents the area of the parallelogram spanned by the columns of *A*. In particular, if the columns are parallel, the parallelogram collapses into a line segment, the area = 0, the columns are linearly dependent, and the matrix is not invertible. We would like to introduce a determinant of a (*3 x 3*) matrix. The derivation is too complicated. So, here is the definition. Suppose *A = ( a₁₁ a₁₂ a₁₃ a₂₁ a₂₂ a₂₃ a₃₁ a₃₂ a₃₃ )* ## Define (*2 x 2*) matrices * *A₁₁ = ( a₂₂ a₂₃ a₃₂ a₃₃ )* ← obtained by removing column #1 and row #1 from *A*. * *A₁₂ = ( a₂₁ a₂₃ a₃₁ a₃₃ )* ← obtained by removing column #2 and row #1 from *A*. * *A₁₃ = ( a₂₁ a₂₂ a₃₁ a₃₂ )* ← obtained by removing column #3 and row #1 from *A*. ## Define * *det(A) = a₁₁det(A₁₁) - a₁₂det(A₁₂) + a₁₃det(A₁₃)* ## Example: *A = ( 1 2 3 4 5 6 7 8 9 )* Calculate *det(A)*. *det(A) = 1 * det ( 5 6 8 9 )* - 2 * det ( 4 6 7 9 )* + 3 * det ( 4 5 7 8 )* = 1(5 * 9 - 6 * 8) - 2(4 * 9 - 7 * 6) + 3(4 * 8 - 5 * 7) = 1(45 - 48) - 2(36 - 42) + 3(32 - 35) = -3 - 2(-6) + 3(-3) = -3 + 12 - 9 = 0* ## Theorem The absolute value of the determinant of a (*3 x 3*) matrix *A* represents the volume of a parallelepiped built on columns of *A*. [Insert an image of the parallelepiped] ## Determinant of an (*n x n*) matrix Suppose *A₁₁* is matrix *A* without first column and first row, *A₁₂* is matrix *A* without second column and first row, *A₁₃* is matrix *A* without third column and first row, ## Definition then: * *det(A) = a₁₁det(A₁₁) - a₁₂det(A₁₂) + ... + a_1ndet(A_1n) - ... + (-1)^{n + 1}a_n1det(A_n1)* Note that this definition is *recursive*. We define the determinant of a (*3 x 3*) matrix through determinants of (*2 x 2*) matrix. Then, we define the determinant of a (*4 x 4*) matrix through determinants of a (*3 x 3*) matrix. Then, we can define a determinant of a (*5 x 5*) matrix, and so on ... ## Example: Calculate *det(A)* for *A = ( 1 2 3 4 5 6 7 8 0 )*, using expansion w.r. to first row. *det(A) = 1 * det( 5 6 8 0 ) - 2 * det( 4 6 7 0 ) + 3 * det( 4 5 7 8 ) = 1(-48) - 2(-42) + 3(32 - 35) = -48 + 84 - 9 = 27* ## Example: Calculate *det(A)* for the same matrix using expansion w.r. to the second column. *det(A) = (-2) * det( 4 6 7 0 ) + 5 * det( 1 3 7 0 ) - 8 * det( 1 3 4 6 ) = -2(-42) + 5 (-21) - 8(6 - 12) = 84 - 105 + 48 = 132 - 105 = 32 - 5 = 27* [Same result as it should be]