Econ 205 - Slides from Lecture 7Joel SobelAugust 31, 2010Econ 205 SobelLinear Algebra: Main TheoryA linear combination of a collection of vectors {x1, . . . , xk} is avector of the formPki=1λixifor some scalars λ1, . . . , λk.Rnhas the property that sums and scalar multiples of elements ofRnremain in the set. Hence if we are given some elements of theset, all linear combinations will also be in the set. Some subsetsare special because they contain no redundancies:DefinitionA collection of vectors {x1, . . . , xk} is linearly independent ifPki=1λixi= 0 if and only if λi= 0 for all i.Econ 205 SobelDefinitionThe span of a collection of vectors {x1, . . . , xk}, S(X ), is the setof all linear combinations of {x1, . . . , xk}.S(X ) is the smallest vector space containing all of the vectors in X .TheoremIf X = {x1, . . . , xk} is a linearly independent collection of vectorsand z ∈ S(X ), then there are unique λ1, . . . , λksuch thatz =Pki=1λixi.Econ 205 SobelProof.Existence follows from the definition of span. Suppose that thereare two linear combinations that of the elements of X that yield zso thatz =kXi=1λixiandz =kXi=1λ0ixi.Subtract the equations to obtain:0 =kXi=1λ0i− λixi.By linear independence, λi= λ0ifor all i, the desired result.Econ 205 SobelDefinitionThe dimension of a vector space is N, where N is the smallestnumber of vectors needed to span the space.Rnhas dimension n.DefinitionA basis for a vector span V is any collection of linearlyindependent vectors than span V .Econ 205 SobelTheoremIf X = {x1, . . . , xk} is a set of linearly independent vectors thatdoes not span V , then there exists v ∈ V such that X ∪ {v} islinearly independent.Proof.Take v ∈ V such that v 6= 0 and v 6∈ S(X ). X ∪ {v} is a linearlyindependent set. To see this, suppose that there exists λii = 0, . . . , k such that at least one λi6= 0 andλ0v +kXi=1λixi. (1)If λ0= 0, then X are not linearly independent. If λ06= 0, thenequation (1) can be rewrittenv =kXi=1λiλ0xi.In either case, we have a contradiction.Econ 205 SobelDefinitionThe standard basis for Rnconsists of the set of N vectors ei,i = 1, . . . , N, where eiis the vector with component 1 in the ithposition and zero in all other positions.1. Standard basis is a linearly independent set that spans Rn.2. Elements of the standard basis are mutually orthogonal.When this happens, we say that the basis is orthogonal.3. Each basis element has unit length. When this also happens,we say that the basis is orthonormal.Econ 205 SobelOrthonormal Bases1. We know an orthonormal basis for Rn.2. It is always possible to find an orthonormal basis for a vectorspace.3. If {v1, . . . , vk} is an orthonormal basis for V then for allx ∈ V ,x =kXi=1vix · vi(To prove this, multiple both sides by vi.)Econ 205 SobelBasis PropertiesIt is not hard (but a bit tedious) to prove that all bases have thesame number of elements. (This follows from the observation thatany system of n homogeneous equations and m > n unknowns hasa non-trivial solution, which in turn follows from “row-reduction”arguments.)Econ 205 SobelEigenvectors and EigenvaluesDefinitionAn eigenvalue of the square matrix A is a number λ with theproperty A − λI is singular. If λ is an eigenvalue of A, then anyx 6= 0 such that (A − λI)x = 0 is called an eigenvector of Aassociated with the eigenvalue λ.IEigenvalues are those values for which the equationAx = λxhas a non-zero solution.IEigenvalues solve the equation det(A − λI) = 0.Econ 205 SobelCharacteristic PolynomialIf A is an n × n matrix, then this characteristic equation is apolynomial equation of degree n. By the Fundamental Theorem ofAlgebra, it will have n (not necessarily distinct and not necessarilyreal) roots. That is, the characteristic polynomial can be writtenP(λ) = (λ − r1)m1· · · (λ − rk)mk,where r1, r2. . . , rkare the distinct roots (ri6= rjwhen i 6= j) andmiare positive integers summing to n. We call mithe multiplicityof root ri. Eigenvalues and their corresponding eigenvectors areimportant because they enable one to relate complicated matricesto simple ones.Econ 205 SobelDiagonalizationTheoremIf A is an n × n matrix that has n distinct eigen-values or issymmetric, then there exists an invertible n × n matrix P and adiagonal matrix D such that A = PDP−1. Moveover, the diagonalentries of D are the eigenvalues of A and the columns of P are thecorresponding eigenvectors.1. Certain square matrices are “similar to” a diagonal matrix.2. The diagonal matrix has eigenvalues down the diagonal.3. Similarity relationship:A = PDP−1Econ 205 SobelSketch of ProofSuppose that λ is an eigenvalue of A and x is an eigenvector. Thismeans that Ax = λx. If P is a matrix with column j equal to aneigenvector associated with λi, it follows that AP = PD. Thetheorem would follow if we could guarantee that P is invertible.When A is symmetric, one can prove that A has only realeigenvalues and that one can find n linearly independenteigenvectors even if the eigenvalues are not distinct. This result iselementary (but uses some basic facts about complex numbers).Econ 205 SobelThe eigenvectors of distinct eigenvalues are distinct.To see this, suppose that λ1, . . . , λkare distinct eigenvalues andx1, . . . , xkare associated eigenvectors. In order to reach acontradiction, suppose that the vectors are linearly dependent.Econ 205 SobelWithout loss of generality, we may assume that {x1, . . . , xk−1} arelinearly independent, but that xkcan be written as a linearcombination of the first k − 1 vectors. This means that thereexists αii = 1, . . . , k − 1 not all zero such that:k−1Xi=1αixi= xk. (2)Multiply both sides of equation (2) by A and use the eigenvalueproperty to obtain:k−1Xi=1αiλixi= λkxk. (3)Multiply equation (2) by λkand subtract it from equation (3) toobtain:k−1Xi=1αi(λi− λk)xi= 0. (4)Since the eigenvalues are distinct, equation (4) gives a non-triviallinear combination of the first k − 1 xithat is equal to 0, whichcontradicts linear independence.Econ 205