INTRO TO LINEAR ALG
INTRO TO LINEAR ALG MATH 307
Popular in Course
Popular in Applied Mathematics
This 58 page Class Notes was uploaded by Sadie Schroeder on Wednesday September 30, 2015. The Class Notes belongs to MATH 307 at Western Kentucky University taught by David Neal in Fall. Since its upload, it has received 74 views. For similar materials see /class/216739/math-307-western-kentucky-university in Applied Mathematics at Western Kentucky University.
Reviews for INTRO TO LINEAR ALG
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/30/15
Dr Neal Fall 2008 MATH 307 Characterization of n x n Matrices Part 2 Let A be an n X n matrix Let T A Rquot gt Rquot be the linear transformation defined by xl TAx AX where x x1 xnandX xn i The following statements are equivalent a detA 0 b A is invertible c A is nonisingular d Every system of equations AX B has exactly one solution given by X ATIB e The homogeneous system AX 0 has only the trivial solution of X 0 f A reduces to the n X n identity In by means of row operations rref A In g T A is oneitoione h T A is onto fl 1 TA is a bljeCUOn and TA TAil ii The following statements are equivalent a detA 0 b A is noniinvertible c A is singular d Every system AX B has either no solutions or infinitely many solutions e The homogeneous system AX 0 has infinitely many solutions f A does not reduce to In by means of row operations rref A i In g TA is not oneitoione h T A is not onto i T A is not a bijection Dr Neal Fall 2008 MATH 307 Characterization of n x n Matrices Part 3 Let A be an nxn matrix Let T A Rquot gt Rquot be the linear transformation defined by xl TAx AX where x x1 xnandX xn i The following statements are equivalent a detA 0 b A is invertible c A is nonisingular d Every system of equations AX B has exactly one solution given by X ATIB e The homogeneous system AX 0 has only the trivial solution of X 0 f A reduces to the n X n identity In by means of row operations rref A In g T A is oneitoione h T A is onto i TA is invertible and TA1 TAil j The columns of A span Rn k The columns of A form a linearly independent set in Rquot l The columns of A form a basis for Rquot m The rows of A span Rquot n The rows of A form a linearly independent set in Rquot o The rows of A form a basis for Rquot p RankA n q NullityA 0 Dr Neal Fall 2008 ii The following statements are equivalent a detA 0 b A is noniinvertible c A is singular d Every system AX B has either no solutions or infinitely many solutions e The homogeneous system AX 0 has infinitely many solutions f A does not reduce to In by means of row operations rrefA i In g TA is not oneitoione h T A is not onto i T A is not invertible j The columns of A do not span Rquot k The columns of A form a linearly dependent set in Rquot l The columns of A do not form a basis for Rquot m The rows of A do not span Rn n The rows of A form a linearly dependent set in Rquot o The rows of A do not form a basis for Rquot p RankA lt n q NullityA gt 0 Dr Neal Fall 2008 MATH 307 Change of Bases Suppose we have two different bases for Rquot U ul u2 un and V v1 v2 V where U and V are the matrix representations with the bases vectors stacked as columns Then any other vector b in Rquot can be written uniquely as a linear combination of the vectors in U but also can written uniquely as a linear combination of the vectors in V To find the coefficients of the linear combinations we find the unique solution to the systems U B and V B where B is the column form of b So suppose b cl u1 cn un and b d1 vl dn V In abbreviated notation we write b 6162 CnU and b d1d2 dnV Note If we are working with the standard basis then the subscript is not necessary For instance in R3 if b 761 00 80 10 150 0 1 then we may simply write b 76 8 15 To recover b cl c2 on U in terms of the standard basis simply multiply U X C where C is the column matrix of coefficients cl c2 on Transition Matrix from U to V Now suppose we have b qc2 onU but we wish to find b d1d2 dnV How do we do so We need the transition matrix W from U to V In other words we must write each of the vectors ul u2 un as linear combinations of the other basis v1 v2 vn We can do so with one calculation by computing rrefVU rrefV1 V2 Vn uil H2 un1n W The 139 th column in W will be the coefficients used to write ul as a linear combination ofv1v2vn Then the coefficients for writing b in terms of v1 v2 vn are found by Dr Neal Fall 2008 Example In R3 let ul 100 u2 l l 0 and 113 l l 1 be basis U and let v1 123 v232 land V3 0 10 be basis V Let b 810 12U a Find the transition matrix from U to V b Write b in terms of V c Use both U and V to write b in terms of the standard basis Solution a First find the transition matrix from U to V 13 011110 0 18 1814 rrefVlUrre 2 2101 1J 0 1 0 38 38 14J K310001K001 1212 0 18 18 14 gtWL38 38 14J 12 12 0 So 1 3 1 1 3 1 and 1 1 u v v u v v u v 1 8V1 8 2 3 2 8V1 8 2 2 3 3 4V1 4 2 2 8 275 b Since I 810 12U we have W X L10J L371 thus I 275 v1 375v2 9v3 12 9 275 375 9V c We can obtain b in terms of the standard basis in two ways 8 14 275 14 Ugtlt 10J 22J and Vgtlt 375J 22J Thus I 14 22 12 K12 K12 K 9 K12 Exercise ln R2 let H be the basis 11 1 2 12 2 71 and let J be the basis jl 72 Z 1392 l l Letv3 4J a Find the transition matrix W from J to H b Use W to write v in terms of H c Use both J and H to write v in terms of the standard basis in R2 Dr Neal Fall 2008 MATH 307 Proving that a Subset is a Subspace Let W be a subset of a vector space V Then W must have some defining property that distinguishes its elements from the other elements in V To show that W is actually a subspace we must verify three properties i W must be noneempty ii W must be closed under scalar multiplication and iii W must be closed under addition i The zero vector 6 must always be in any subspace So to show W is noneempty it is usually easiest to show that 6 is in W That is you must argue that the specific zero vector of the vector space V under consideration has the defining property of the set W Then conclude that W is noneempty ii To show W is closed under scalar multiplication a Let w e W b Then state what it means for w to be in W ie explain the defining property c Let c be any scalar ie real number d Argue that cw has the defining property of W e Conclude that W is closed under scalar multiplication iii To show W is closed under addition a Let WI and w2 be in W b Then state what it means for WI and w2 to be in W ie explain that they have the defining property c Argue that w1 w2 has the defining property of W e Conclude that W is closed under addition iv Conclude that W is a subspace of V Throughout you may use different symbols that are more appropriate to the context of the problem But throughout use complete sentences to explain what you are doing use correct mathematical logic do not skip steps and give conclusions Example 1 Let V be the set of all n X n matrices Let W be the subset of symmetric matrices that is W A e VIAT 14 Claim W is subspace of V Proof Let 0 be the ngtlt n zero matrix Then OT is also the ngtlt n zero matrix thus OT 0 Hence 0 e W and therefore W is noneempty Let A e W Then AT A If C is any scalar then cAT cATcA hence CA 6 W Thus W is closed under scalar multiplication Let AB e W Then AT A and ET 3 But then ABT AT BT AB hence AB e W and W is closed under addition Ergo W is a subspace of the vector space of all n X n matrices Dr Neal Fall 2008 Example 2 Let V Ca b be the set of continuous functions over 61 b where a lt b Let a lt dlt b and let D f e V f39d exists Then D is a subspace of V Proof Let f0 be the zero function ie f0x 0 for all x e 61 b Then f6x 0 for all x e a b thus f6d exists and equals 0 So f0 6 D and D is noneempty Let f e D so that f 39d exists For any scalar c cf is still a continuous function and cf 39d c f 39d still exists Thus cf 6 D and D is closed under scalar multiplication Let g 6 D so that f 39d and g39d exist Then f g is still a continuous function and f g39d f39dg39d still exists Thus fg e D and D is closed under addition Whence D is a subspace of Ca b Example 3 Let T Rm gt Rquot be a linear transformation Then kerT is a subspace of Rm Recall For T R quot gt R kerT x ele Tx 6 Proof Let 6m be the zero vector in Rm and let 6 be the zero vector in Rquot Then for any linear transformation TRm gtRn we have T6m6 Thus 6m ekerT Hence kerT is noneempty Let x ekerT Then Tx6 If C is any scalar then cx is still in Rm and TcxcTxc66 hence cxekerT Thus kerT is closed under scalar multiplication Let u v e kerT Then Tu 6 Tv Then Tu v Tu Tv 6 6 6 hence u v e ker T and ker T is closed under addition Ergo kerT is a subspace of Rm Example 4 Let S u1 u2 um be a collection of vectors in Rquot The set spanS is the collection of all linear combinations of the vectors in S Then span S is a subspace ofRn Dr Neal Fall 2008 Proof i First 3 0u1 0u2 0um is a linear combination of the vectors in S thus 3 e spanS and spanS is noniempty ii Next suppose u e spanS Then u can be written as u qul c2u2 cmum For any scalar c we then have cu Cc1u1 czuz cmumcclu1cczu2 ccmum which is still a linear combination of the vectors in S Thus cu e spanS and spanS is closed under scalar multiplication iii Now let u v espanS Then u and v can be written as u qul c2u2 cmum and V d1u1 dzuz Then uvclu102u2 cmumd1u1d2u2 dmum c1d1u1 cm almum which is still a linear combination of the vectors in S Thus u v e spanS and spanS is closed under addition Therefore spanS is a subspace of Rquot Dr Neal Fall 2008 MATH 307 Composition of Linear Transformations Let T Rquot gt Rm and S Rm gtRp be linear transformations Then the composition of functions SoT is a function from Rquot to RP defined by SoTxSTx for all n xeR i Note that T is applied first to a vector in x ERquot Then T x is in Rm Now apply S to Tx Then STx is in RP So SoT is applied to a vector x in Rquot and SoTx ends up in RP thus we may write S o T Rquot gt RP Theorem 1 Let T 1quot gtRm be a linear transformation with m X n matrix representation A and let S Rm gtRp be a linear transformation with p X m matrix representation B Then SoT is a linear transformation with matrix representation B X A Proof To show that So T is linear let x y e Rquot and let c be a scalar Then because T and S are linear we have 3 TX y STCx y SCTx T00 cSTxSTy CS Tx 3 Ty Hence S o T is linear Next Tx AX and Sw BW where X is the column matrix form of x and W is the column matrix form of w Then So Tx STx 3 X AX BAX So BA is the matrix representation of S o T Note Applying the composition to X in matrix form as BA X BAX means that we apply A first and then apply B which is the same as applying T first and then applying S Dr Neal Fall 2008 Example Let T R3 gt R2 and S R2 gt R4 be defined by Tx1x2x3x1 x2 2x3 2x1 x2 4x3 and Sxl x22x13x2 5x1 4x2 3x1 x2 Give the matrix representation and function form of S o T 1 2 Solution First T R3 gt R2 has a 2 X 3 matrix representation A 2 1 4J and 2 3 2 4 5 0 S R gt R has a 4 X 2 matrix representation B 0 4 Thus BA is defined as a 3 1 8 1 8 5 5 10 4 X 3 matrix and BA 8 4 16 Moreover BA is the matrix representation of 1 4 10 S o T R3 gt R4 which in function form is 3 T9 1962x3 8x1x2 8X3 5x1 5x2 lOX3 8x14x2 l6X3 x1 4x2 lOX3 Theorem 2 Let T Rquot gt Rm and S Rm gtRp be linear transformations If T and S are both oneetoeone then S o T is oneetoeone Proof Suppose So Tx S0 Ty for some x y e Rquot We must show that x y But we have STx STy Because S is oneetoeone we must have Tx Ty Then because T is oneetoeone we must have x y Theorem 3 Let T Rquot gt Rm and S Rm gtRp be linear transformations If T and S are both onto then S o T is onto Proof First So T Rquot gtRp has coedomain RP To show So T is onto we must show that every vector in RP has a preeimage in Bquot Let z eRp Because S is onto there exists y e Rm such that S y 2 Then because T is onto there exists x ERquot such that Tx y Then SoTx STx Sy 2 So x is the preeimage of z and thus S o T is onto Dr Neal Fall 2008 Theorem 4 Let T Rquot gt Rquot and S Rn gt Rquot be linear transformations both of which are oneitoione and onto having matrix representations A and B respectively Then SoT is also oneitoione and onto and SoT71 TiloSil Moreover the matrix representation of S o T71 is BA 71 ATIBT1 Proof By Theorems 2 and 3 SoTRn gtRn is both oneitoione and onto and by Theorem 1 has matrix representation BA Therefore So T is invertible and the matrix representation of its inverse is BA 71 ATIBTI which is the unique representation of the composition T71 oSTl Thus T71 0S71 So T71 So for T Rquot gt Rquot and S Rquot gt Rquot both oneitoione and onto then So T Rquot gt Rquot is also oneitoione and onto and thus has an inverse which is T71 o S71 In other words for S o T we apply T first and then apply S To undo this process we undo S first and then undo T which is precisely the action of T71 o S71 z S o Tx STx Apply T first and then apply S Now undo zSTx gt S71z Tx gt T 1S 1z x undo S first and then undo T So if 2 So Tx then xTT1 oS 1z Dr Neal Fall 2008 MATH 307 Inverses Let A be an n X n matrix We say that A is invertible or nonrsingular if there is another n X n matrix B such that AB In BA If no such matrix B has this property then A is called nonrinvertible or singular If a matrix B has this property then B is called A inverse and is then denoted by the symbol A71 Thus the defining property of A71 is AATI 1 A 1A 1 Theorem 4 Let A be invertible Then A71 is invertible and A71 A Proof Because AilA In AAil the matrix A has the inverse property when acting on 1 the matrix A71 So A is the inverse of A71 That is A71 is invertible and A A71 Inverse of a 2 x 2 Matrix l Let A all an be a 2 X 2 matrix with detA 0 Then A 1 6122 an 021 022 616104 021 011 Because detA 61116122 61126121 it can easily be shown that an 012 X 1 022 0121 0 1 022 012X011 012 021 022 16104 021 an 0 1 616104 021 an 021 022 thus A71 is as stated Example 1 Let A Then detA 4 6 23 18 Thus 1 l 6 2 13 l9 4 13 l9 l 0 A and X 18 3 4 16 29 3 16 29 0 l Your calculator can easily compute the inverse of an n X n matrix or tell you if the matrix is singular Simply enter the matrix say as A on a T178384 or as ma on a T189 Then TL8384 Enter A1 then MATH 1 T1789 Enter maA 1 Use your TI to compute A71 in the above example and to show A X A71 12 Dr Neal Fall 2008 Some More Theorems about Inverses and Determinants We shall assume the following basic facts 1 detIn 1 Because the n X n identity matrix In is diagonal its determinant is the product of the main diagonal which gives 1 ii Any two n X n matrices can be multiplied together to give another n X n matrix iii For n X n matrices A and B detA B detA gtlt detB iv Matrix multiplication is associative Theorem 5 Let A and B be n X n matrices a If A is invertible then A71 is unique b If A and B are invertible then AB is invertible and AB71 B7 c If A71 exists then detA 0 and detA71 1A 1 detA 39 Proof a Because A is invertible AT1 exists and AA 71 In ATIA We must show that A71 is the only matrix with this property So suppose there is another n X n matrix C such that AC In CA Then C CIn CAA 1CAA 1 In A 1 A71 Thus C A71 which means that A71 is unique b Assume both A71 and B71 exist We claim that BTIAT1 behaves as the inverse of AB To demonstrate this we multiply AB on both sides by B7 1A71 to get In ABX B71A71ABB71AT1 AInA 1 AA 1 1n and B lA lx AB B 1A 1AB 341 B 3 13 In Thus BTIAT1 is the inverse ofAB Therefore AB is invertible and AB71 B7 1A71 c We know that detA gtlt detA71 detAATl detIn 1 Thus neither detA nor detA71 can be 0 because their product is nonezero So detA 0 Also because detA gtlt detA71 1 we have detA71 1 detA Dr Neal Fall 2008 To find the inverse of an ngtlt n matrix by hand we actually have to solve n separate systems of n equations and n unknowns We will illustrate with a symbolic 3 X 3 matrix which requires that we solve 3 systems of 3 equations 3 unknowns For a 3gtlt 3 matrix A we need another 3gtlt 3 matrix B such that AB 13 Each column of B if it exists has 3 unknowns x1 y1 21 and we need 3 equations to solve for them We obtain the first system from the inner products of the three rows of A with the first column of B which yields the first column of 13 011 012 013 x1 1 0 0 011x1012y101321 1 021 022 023 X M 0 1 0 gt 021x1022y1023210 0 0 l 031 032 033 21 a31x1a32y1a33210 A X B 13 We obtain the second system from the inner products of the three rows of A with the second column of B which yields the second column of 13 011 012 013 x1 1 0 0 011x1012y101321 0 021 022 023 X yi 0 1 0 gt 021x1 022y1 02321 1 031 032 033 Zi 0 0 1 a31x1 a32y1 03321 0 A X B 13 We obtain the third system from the inner products of the three rows of A with the third column of B which yields the third column of 13 011 012 013 x1 1 0 0 011x1012y101321 0 021 022 023 X y1 0 1 0 gt 021x1 022y1 02321 0 031 032 033 21 0 0 1 a31x1 a32y1 03321 1 A X B 13 Each of these systems has a unique solution if and only if detA 0 o The process is the same for n X n matrices which allows us to state Lemma 1 Let A be an n X n matrix lf detA 0 then there exists another n X n matrix B such that AB In But is B actually the inverse of A 7 We still must show that BA In also Dr Neal Fall 2008 However suppose AB In Then 1 detn detAB detA gtlt detB thus detB 0 Applying Lemma 1 to matrix B there exists another n X n matrix C such that BC In Then B 31 BAB BAB Multiplying on the right by C we obtain In BC BA BC BAIn BA So if AB In then we must have BA In also We now can state Theorem 6 Let A be an n X n matrix If detA 0 then A71 exists h But we also proved in Theorem 5c that if A71 exists then detA 0 So we actually ave Theorem 7 Let A be an n X n matrix Then A71 exists if and only if detA 0 2 l 3 2 l 3 Example 2 Let A 3 1 6 and B 3 1 6 0 2 3 l 2 3 57 17 37 37 27 17 27 421 521 Use your calculator to show that detB 0 and trying to compute its inverse results in a singular matrix message Use your calculator to show that detA 21 and A71 Solving Matrix Equations with Inverses We can use inverses to solve matrix algebra equations and also to solve a system of n equations and n unknowns Example 3 a Suppose C is invertible and BC D Solve for B b Suppose PTIAP D Solve for A Solution a Multiply each side of BC D on the right by C71 BCCTI DC 1 gt B1 DC 1 gt B DC I b Multiply each side of PTIAP D on the left by P and on the right by P71 PP IAPP 1 PDP 1 gt InAIn PDP 1 gt A PDP 1 Dr Neal Fall 2008 Theorem 8 Let A be an invertible n X n matrix Every system of equations AX B has a unique solution given by X A7 B Proof Because AT1 exists we know that detA 0 So AX B has a unique solution for X To obtain the solution multiply on the left by A71 ATIAXA71B gt InXA71B gt XA71B 2x y 22 3 2 1 2 3 Example 4 Consider the system xy 22 6 Let A 1 1 2 and B 6 3x2y z3 3 2 1 3 3 a Enter these matrices into your calculator and show that A71 X B 7 2 b Adjust A to A B then compute rref A B to obtain the same solution Characterization of n x n Matrices Part 1 i The following statements about an n X n matrix A are equivalent a detA 0 b A is invertible ie AT1 exists c A is nonisingular d Every system of equations AX B has exactly one solution given by X ATIB e The homogeneous system AX 0 has only the trivial solution of X 0 f A reduces to the n X n identity In by means of row operations rref A In ii The following statements about an n X n matrix A are equivalent a detA 0 b A is noniinvertible ie A71 does not exist c A is singular d Every system AX B has either no solutions or infinitely many solutions e The homogeneous system AX 0 has infinitely many solutions f A does not reduce to In by means of row operations rrefA i In Dr Neal Fall 2008 MATH 307 Eigenvalues and Eigenvectors Let T Rquot gt Rquot be a linear transformation with matrix representation A A nonezero vector v ERquot is called an eigenvector of T if there exists a scalar c such that Tv cv The scalar c is then called an eigenvalue ln matrix form we say that a non zero X is an eigenvector if AX cX The eigenvectors are simply those vectors in Rquot that are expanded or contracted in the same or opposite direction by the transformation T 5 0 ExampIeI Let T R2 gtR2 be given by Txy 75x 3y ThenA 0 3 For nonezero vectors of the form v x0 we have Tv Tx 0 75x 0 75v Thus any nonezero vector of the form x0 is an eigenvector of T with associated eigenvalue c 75 Since Tv 75v such a vector v x0 is simply expanded by 5 in the opposite direction These eigenvectors form a oneedimensional eigenspace with basis 10 Signilgrly nonezero vectors of the form 0 y are eigenvectors of T with associated eigenvalue c 3 These vectors are expanded by a factor of 3 by the transformation T These eigenvectors form another oneedimensional eigenspace with basis 0 1 In this case the two eigenspace basis vectors 1 0 and 0 1 form a basis for all of R2 Finding the Eigenvalues To find all possible eigenvalues we must find the scalars c such that AX cX for some nonezero X This equation can be rewritten in the following ways AX cX0 gt AX cInX0 gtA c1x0 Thus the equation A clnX 0 must have a nontrivial solution X In other words detA of must equal 0 If the determinant were not equal to 0 then there would be only the trivial solution of X 0 To find the eigenvalues c we must solve the equation detA c In 0 5 0 Example 1 continued Because T has matrix representation A 0 3 then A of 5 J 6 0 f OJ 0 3 0 c 0 3 6 SodetA cn5C3 C Solving 5 c3 c 0 we obtain c 75 and c 3 as the only eigenvalues Dr Neal Fall 2008 Finding the Eigenvectors Once we have an eigenvalue c we must find all nonizero solutions to the homogeneous system A cInX 0 These solutions are called the eigenspace for the eigenvalue c The eigenspace is a subspace of Rquot thus we also can find a basis for each eigenspace 0 0 Example 1 continued When c 75 then A cln 0 8 The general solution to A clnX 0 is x1 t and x2 0 1e vectors of the form t 0 So a basis for this eigenspace is l 0 8 0 For c 3 then A cIn 0 OJ Now the general solution to the system A clnX 0 is x1 0 and x2 t ie vectors of the form 0 I So a basis for this eigenspace is the vector 0 1 Example 2 Let T R2 gtR2 be a counterclockwise rotation by 90 Then T1 0 0 1 01 and T01 10 SoA 1 0 Then A cIn and detA cn c l c2 1 Solving c2 1 0 we see that there are no real solutions Thus there are no eigenvalues or eigenvectors No vector in R2 is magnified along the same line by this transformation Every vector is rotated l 0 1 Example 3 Let T R3 gtR3 be defined by the matrix A 0 1 0 Find the l 0 l eigenvalues and bases for the associated eigenspaces Determine if the basis vectors form a basis for all of R3 1 c 0 1 Solution We look at the matrix A cIn 0 1 c 0 and we must compute l 0 l c detA c In To do so we will use the weave method for finding 3 X 3 determinants Dr Neal Fall 2008 l c 1 c1 c0gtlt0gtltl lgtlt0gtlt07l 1 cl1 cgtlt0gtlt00gtlt0gtlt1 c 101010 10 1 c1 c2 71 Sowemustsolve 1 c1 c271 0 gt c7lor 1 c2l gt l c il gt I lc gtc00rc2 So we have three eigenvalues c 71 c 0 and c Z 2 0 l l 0 0 lfc7lthenA c1n 0 0 0 rref gt 0 0 1 gtx10x2 tx30 The l 0 2 0 0 0 oneidimensional eigenspace for c 71 has basis 0 l 0 Any nonizero vector of the form t0 l 0 0 t 0 is an eigenvector for eigenvalue c 7 l 0 l l 0 l lfc 0thenA c1n 0 1 0 rref gt 0 1 0 gt x17tx2 0 x3 t The l 0 l 0 0 0 oneidimensional eigenspace for c 0 has basis 71 0 l l 0 l l 0 l lfc2thenA c1n 0 3 0 rref gt 0 1 0 gtx1tx20x3t The l 0 l 0 0 0 oneidimensional eigenspace for c 2 has basis 1 0 1 Consider the three eigenspace basis vectors S 0 l 0 71 0 l l 0 1 Do they form a basis for all of R 7 0 l 1 Let P 1 0 0 Then detP Z i 0 thus S does form a basis for R3 0 l l Diagonalizing the Matrix A Suppose the n X n matrix A has n eigenvectors which form a basis for all of Rquot Let P be the associated matrix representation of these eigenvectors detP 0 PT1 exists Then the matrix D P71 AP will become diagonal with the corresponding eigenvalues down the main diagonal In this case we also obtain the following results Dr Neal Fall 2008 detP 1 AP detA and MP 1 AP TrA These results actually hold for any invertible matrix P and are proven below 1 0 l 0 l l Examp1e3continued Here A 0 1 0 andP 1 0 0 We see that P71 AP 1 0 l 0 l l l 0 0 0 0 0 which shows the three eigenvalues c 71 c 0 and c 2 down the 0 0 2 main diagonal Finally we can check that detA 0 detPT1 AP and TrA l TrP 1 AP De nition Let A be an n X n matrix and let P be any invertible n X n matrix Then the matrix P71 AP is said to be similar to A Theorem 1 Similar matrices have the same determinant and the same trace Proof If A is n X n and P is an invertible n X n matrix then detP 1 A P detP 1 gtlt detA gtlt detP detP 1 gtlt detP gtlt detA detP 1Px detA det1n gtlt detA 1 X detA detA Thus similar matrices have the same determinant For the trace operator recall that TrAB TrBA thus TrP 1 AP TrAPP 1 TrA1 TrA This second proof also works for the determinant because detA B detBA Dr Neal Fall 2008 Theorem 2 Let A be invertible If c is an eigenvalue of A then 1 c is an eigenvalue of A71 Proof Suppose c is an eigenvalue of A Then AX cX for some nonizero eigenvector X Because A is invertible we have XA71cX 61471 X Because X is a nonzero vector then c cannot equal 0 or else CA71X X would be 0 So c i 0 Then because cA 71XX we have A71X X So lc is an eigenvalue of A71 with the same eigenvector X Exercises 0 l l 110 210 410 iA 1 0 1 iiA110 iiiA222 ivA020 l l 0 0 01 012 014 1 For each of the above matrices A a Find the eigenvalues of A b For each eigenvalue find the eigenspace and a basis for the eigenspace c Determine if there is a basis of eigenvectors If so show how to convert A into a diagonal matrix that is similar to A Then verify that the similar matrix has the same determinant and the same trace as A Z Successive generations of genotypes AA Aa aa are always bred with the same type of genotype AA always with AA Aa always with Aa and aa always with aa a Give the matrix of transition probabilities T b Find the eigenvalues of T For each eigenvalue find the eigenspace and a basis for the eigenspace c Compute Tquot and lim Tn ngt00 d Given an initial state of I p1 p2 p3 what is the limiting distribution Does it depend on the initial state Dr Neal Fall 2008 MATH 307 Bases in Rquot Linear Independence and Spanning Let S u1 u2 um be a collection of m distinct vectors in Bquot Each vector has n coordinates When we write the vectors in column form then they become n gtltl matrices Aligning them together into one matrix we obtain an nxm matrix representation A Example 1 ln R4 let ul 10 4 2 L12 3 72 0 6 and u3 171 14 Then A is the 4 X 3 matrix 1 2 3 1 3 1 A 0 2 1 4 0 1 2 6 4 This 4 X 3 matrix also defines a linear transformation T R3 gt R4 which we know cannot be onto but may or may not be oneetoeone Spanning Sets De nition Let S u1 u2 um be a collection of m distinct vectors in Rquot Then S n n is said to span R if every vector in R can be written as a linear combination of the vectors in S Theorem 1 Let S be a collection of m distinct vectors in Rquot with the n X m matrix representation A The set S spans Rquot if and only if AX B always has a solution for every n X 1 matrix B Recall In order to determine if a vector b is a linear combination of the vectors in S we simply let B be the column form of b and see if AX B has a solution Case 1 m n so that we have n vectors in Rquot Then S spans Rquot if and only if detA 0 which means that AX B always has a solution Case 2 m lt n so that we have fewer than n vectors in Rquot Now it is impossible for S to span Rquot The n X m matrix A defines a linear transformation from Rm to Rquot that cannot be onto because m lt n Thus AX B will not always have a solution and S cannot span Rn Case 3 m gt n so that we have more than n vectors in Rquot Then S spans Rquot if and only if the reduced row echelon form of A does not contain a row of all 039s meaning that there are never any inconsistencies for a system AX B Dr Neal Fall 2008 Note You need at least n vectors to span Rn Fewer than n vectors cannot cover all of Rquot which requires n dimensions Linear Independence De nition Let S u1 uz um be a collection of m distinct vectors in Rquot Then S is said to be linearly independent if the zero vector cannot be written as a nontrivial linear combination of the vectors in S In other words if 01 ul c2 u2 cm um 0 0 0 then each scalar coefficient 01 c2 cm mustbe0 If the zero vector can be written as a nontrivial linear combination of the vectors in S then S is called linearly dependent Theorem 2 Let S be a collection of m distinct vectors in Rquot with the n X m matrix representation A The set S is linearly independent if and only if the homogeneous system AX 0 has only the trivial solution of X 0 Case 1 m n so that we have n vectors in Rquot Then S is linearly independent if and only if detA 0 which means that AX 0 has only the trivial solution of X 0 Case 2 m gt n so that we have more than n vectors in Rquot Now it is impossible for S to be linearly independent The n X m matrix A defines a linear transformation from Rm to Rquot that cannot be oneitoione because m gt n Thus AX 0 will have infinite solutions and S will be linearly dependent Case 3 m lt n so that we have fewer than n vectors in Rquot Then S is linearly independent if and only if the reduced row echelon form of A reduces to the m X m identity with additional rows of 039s which means that AX 0 has only the trivial solution of X 0 Note Given n vectors in Rquot either they are linearly independent and they span when detA 0 or they have neither property when detA 0 One property holds if and only if the other property holds Note further A set of more than n vectors cannot be linearly independent in Rquot The extra vectors must be dependent on the others In fact they actually will be linear combinations of the others which makes them redundant The following theorem formalizes the result Dr Neal Fall 2008 Theorem 3 Let S u1 u2 um be linearly independent Then none of the vectors in S can be the zero vector Proof Suppose u 6 for some j with 1 S j S m Then we could write 1 X u 6 which expresses 6 as a nontrivial linear combination of the vectors in S Thus S would be linearly dependent which is a contradiction to the assumption Theorem 4 A set of vectors S u1 u2 um in Rquot is linearly dependent if and only if some vector in S is a linear combination of the preceding vectors in the list Proof Suppose uk1c1u1m ckuk ie suppose that a vector in S is a linear combination of the preceding vectors in the list Then 6 clul ckuk luk10uk1 0un hence 6 is a nontrivial linear combination of the vectors in S Therefore S is linearly dependent On the other hand suppose that S is linearly dependent Then there is a nontrivial linear combination such that 0 c1u1 cm um Choose the last such nonizero coefficient ckH then 6 01 ul ck1uk1 Hence ck1uk1 Cl ul ck uk and C uk1Lu1m k Ck CkH preceding vectors in the list uk Therefore a vector in S is a linear combination of the Basis De nition Let S u1 u2 un be a collection of n distinct vectors in Rquot If S is linearly independent and S spans Rn then S is called a basis Note Because fewer than n vectors cannot span Rquot and more than n vectors cannot be linearly independent in Rquot it requires exactly n vectors to form a basis for Rquot It is easy to check whether or not n vectors actually form a basis for Rquot Theorem 5 Let S be a collection of n distinct vectors in Rquot with the n X n matrix representation A Then S is a basis if and only if detA 0 Dimension De nition A vector space V is called n dimensional if it has a basis with n elements Dr Neal Fall 2008 Example 2 Let Pn be the set of real polynomials having degree S n Then Pn is n 17 dimensional lndeed consider the set of n1 vectors S 1 x x2 xn Every polynomial in Pn is a linear combination of those in S thus S spans Pn Also if cnxn qxc0 0 then each cl must be 0 So the zero polynomial cannot be written as a nontrivial linear combination of the vectors in S Thus S is linearly independent Therefore S is a basis for Pn having n1 elements Standard Basis In Rquot let e1 10 0 e2 01 0 en 0 01 The matrix representation A is the n X n identity In hence detA 1 0 Thus e1 e2 en is a basis for Rquot called the standard basis Every vector in Rquot is clearly a linear combination of e1 e2 en For instance in R4 8 710 12 16 810 0 0 7100 1 00 1200 1 0 160 0 0 1 The standard basis for Pn is S 1 x x2 xquot as explained in Example 2 There can be other bases as well For example in R3 let S 100 120 123 1 1 1 Then A 0 2 2 and detA 6 0 thus S is a basis for R3 We can write any 0 0 3 vector in R3 as a linear combination of the vectors in S How about 8 10 712 1 1 1 8 1 0 0 3 0 2 210 gtrref gt 0 1 0 9 gt 810712310091Z074123 0 0 3 12 0 0 1 4 Note The set of m X n matrices Mm is an mn7dimensional vector space What is the standard basis for M23 7 Theorem 6 Given a basis of vectors S u1 u2 un for an nedimensional vector space V every other vector in V can be written uniquely as a linear combination of the vectors in S Proof Because S is a basis for V we know that S spans V therefore every other vector can be written at least one way as a linear combination of the vectors in S Dr Neal Fall 2008 But suppose a vector v can be written two ways v clu1 cnun d1u1 dnun Then 6 d1 c1u1 dn onun Because S is linearly independent we must have 511 cl 0 for 1 Si S n That is 511 cl for all z39 and there cannot be two distinct ways to write the linear combination Theorem 7 Let S u1 u2 un be a basis for Rquot Let T Rn gtRn be a bijective linear transformation Then TS Tul Tuz Tun is also a basis for Rquot Proof Let v be a vector in Rquot We will show that v is a linear combination of the vectors in TS Because T is bijective it has an inverse T71 Because S is a basis we can write T7102 as a linear combination of the vectors in S T7102 c1u1 cnun Now apply T and use the properties of linearity v TT71v Tq u1 cnun 01Tu1 chun Thus TS spans Rn Because there are n vectors in TS they also must be linearly independent hence TS is a basis for Rquot n 1191 511 m MATH 307 1701mmin Rewion Gwenn dxmmlpmntsmthe xy planewe nd apalynarma ufdegee s quot71 um 1quoterth m1 pm Fax examph we can nd a but degree 11 um gm Lhmugh twapmnts w mm a quadraucmegreee 2111mm thraugh three nanrmlhnear paints Haw dawe mm 121 mm x y be thesepmnts Wemuxtfmd apalynurmal H H 1 p00 4X Hx ch thatgnesdqmughearhpamt There are n unlmawns an H and we can meat 71 equaumshy uhsmuurgeach x mm palynamlal and setungn equal in y H H 4 Mn Hz H H mm Wm mm H H WW Wm Hz x x x 1 x2 xi x 1 y x xxquot x 1 y Subkg m system Qwsusthe denied m umts m 1 m1 Fmd a mmefunmm39hatgaesthmugq 1 A A 11 s x and 11 1A m 1191 511sz z Sawemuxt SnluLmn Here we have n 4 pmms and the mhm 1s a1 degee n salve the system 5 x3 x l y 13 12 1 1 A 43 41 A 1 1n 53 51 5 1 2 1n3 12 1n 1 14 wmm1s a mhmpalynarmal Lhatgnesdqmwh Lhafaur palms Because there 1s m1y me samum m the system a1 equauans Lhm 1s the m1y mhm um gaes 111mm these nut palms 1s 139 s e u39z x e1 Ends 1 Fmd the umque quarucpalynamdthatgaesthrvugq the paint m 42 66 82 1H 1 Pravedqatdqe pamt5 511s arehuve mammum a1 mes palynama Dr Neal Fall 2008 MATH 307 Vectors in RI Matrices of dimension lgtlt n can be thought of as coordinates or vectors in n7 dimensional space Rquot We can perform special calculations on these vectors In particular we can find special geometric interpretations for vectors in R2 the x y plane and for vectors in R3 In fact most of the definitions and theorems for Rquot are generalizations of results that can be seen geometrically in R2 and R3 Throughout let u u1 un and v 21 vn be vectors in Rquot 0 SumDifference i u vu1v1 un vn ii v u vl u1 vn un which gives the directional vector from u to v I Norm The norm or length or magnitude of the vector u is defined by 1112 un2 This definition is an extension of the Pythagorean Theorem Consider the vector u 5 8 in R2 Then the length of the line segment from 0 0 to 5 8 is V52 82 J8 9 ln R3 the norm of the vector x y z is simply the length of the segment from the origin to the point xy z and is given by Ixz y2 z2 However for n 2 4 we lose the geometric interpretation of length So for u 4 73 5 6 in R4 the norm is simply Iu J42 732 52 62 Jig without the concept of length attached to it Some Properties of Norm i Z 0 ii 0 if and only if u is the zero vector 000 iii u12 un2 and iv Icu cgtltul foranyconstantc II Distance The distance duv between vectors u and v is given by the length of the vector from u to v 2 2 duvv uquotv1 u1 vn un This definition is an extension of the result in R2 If u 5 8 and v 10 76 then the distance between these points is found by the usual distance formula from algebra duv lx2 x12 y2 yl2 J52 142 J221 Although we do not really have a distance in Rquot for n 2 4 we still use the name distance for this measurement Some Properties ofDistance i duv Z 0 ii duu 0 and duv gt 0 if u i v and iii duv dvu m Neal knzum m Dot mam We de ne the an prnducl u v aka calhd m prndud between vevlaxs u and v w u v elm Hm Inteme a mamx muluphcauan u v really the mamx mam u v whmh I a 1x Imamx u u 44551dexAe2mmmu v3271271 5 7 ngemes 0r Dot mam man e u v v u a Faxanysnalar em v cgtltu v and u w eem v e Fmanmhzrvectm wuv w 01 mm w Bandage memes m R2 and 2 we mnemumee Wm u and V pmueWem Veum u 3 5 andv 414 Thelma agana afthepara elagramahwexsgwenbythevemax u e v m shun me a a The gnna Qvesthevectmfmmu m wwhmhxsgven by the du39fexenoe v e 11 444 h R2 and awe can ndthe Wm meme mmmuw me Lew Wm m we a hemememe em mgeheween u and V Then 2 2 2 IVWH IMH M ZHHHHVHcasn and 2 2 2 IHVH M M Zlquvlcaswn 2 2 M M 2quvlwsl Dr Neal Fall 2008 These formulas are never used directly to find the lengths of the diagonals For instance withu 35 and v 74 then u v 10 9 Thus uv J102 92 J181 However the first formula can be used to find the measure of the angle 6 Angle Between Vectors in R2 and R3 Because Iv uII2 v2 Ilvllcose we can solve for 0059 and simplify the expression u2l VIZl v uu2 2quot M II V II uuvv v uv u cos8 2IIHIIIVI uuvv vv uv vuuu 2uIV 2uv uv leullvl lullllvll39 uv 1 uv Thus 0056 and 0 cos uv uv Note It is always the case that 00 S 6 S 1800 The angle 6 between u 3 5 and v 7 4 is given by 6 cosil j m o 7 u v 2929 We can compute cos for any two vectors u and v in Rquot however u v only in R2 and R3 does the value give the geometric interpretation of the measure of the angle between the vectors Orthogonal Vectors In R2 and R3 two vectors u and v are perpendicular if and only if the angle 6 between them is 90 that is if and only if 0059 0 Because 056 then 0056 0 if and only if the dot product uv equals 0 u v Thus in R2 and R3 we can say that u and v are perpendicular if and only if u v 0 For Rquot in general we say that vectors u and v are orthogonal if and only if u v 0 For example if u 72 0 3 0 6 and v 3 5 Z 10 0 then uv 76 6 0 so u and v are orthogonal in R5 Dr Neal Fall 2008 Identities in Rquot Only in R2 and R3 do we have the geometric interpretation of angle between vectors However the parallelogram identities can be generalized to Rquot as follows 2 2 2 2 2 2 Ivull Iull V 2uv and uV Iull V 2uv We quickly obtain these results using the properties of dot product 2 2 2 Iv ull v uv uvv uv vuuu v 2uv 2 2 2 Iuv uvuvuuuvvuvvIuII Iv 2uv Alternately in R2 and R3 uv uv 2 2 2 2 2 2 2 Ivull u v 2uvcoseu v 2uv u v 2uv Cauchyischwarz Inequality Let u and v be vectors in Rquot Then Iuvl S lull Ivll Proof Let k be a scalar and consider the vector ku v Then 0 Sllku vl2 ku vku v k2uu kuvkvuvv u2 k2 2uvkv2 This expression defines a quadratic in k which is always noninegative so the i quadratic has zero roots or just one root Thus the discriminant b2 4ac must be less than or equal to 0 where au2 b 2uv and c v2 If the discriminant were positive then the quadratic would have two roots and therefore would have to be negative over some interval Thus 132 4616 4uv2 4Iu2Iv2 s 0 which implies that uv2SIuII2I VIZ Taking square roots we obtain v S Iu QED Triangle Inequality Let u and v be vectors in Rquot Then uV S lull IVII Proof We simply expand Iu v2 The first inequality below arises from the fact that the number uv is less than or equal to its absolute value The second inequality is from Cauchyischwarz Dr Neal Fall 2008 Iuv2 uvuvuI2IvI2 2uv 2 2 Slull v 2luvl Slullzv22uv Ilullvl2 By taking square roots we obtain Iu Vquot S Iu QED Note For vectors u and v in R2 the triangle inequality states that length of the diagonal u v can be no more than the sum of the lengths of the two sides u and v hence the name triangle inequality uV The result can be generalized to the distance V between vectors as shown next Shortest Distance Between Points Let u and v be vectors in Rquot For any other vector w we have duv duw dwv Proof We use the definition of distance and apply the triangle inequality duv v u v WWu Sllv WIHIIW ul dwv duw duwdwv QED The result states that the planar distance directly from u to v is less than or equal to the sum of the distances from u to w then from w to v We note that if u v and w are collinear with w between u and v then duv will equal duwdwv Some Applications of Determinants to Vectors R2 and E Area of a Triangle Three nonicollinear points x1 yl x2 y2 and x3 y3 form a triangle in the x yeplane The area of the triangle is given by 1 x1 yl 1 Area E det x2 y2 1 x3 3 1 The above determinant equals 0 if and only if the three points are on the same line m 1191 511sz W1Lh Lhepmnts 1n 9 1 A and 3 5 1n 9 1 than an 7 A 1 alumnae area a1 6 15 z 5 39hemanglexsZS nm P m Pmm nvmv 1 X2421 a UL 2 1sgvmhy ValmvveaszeAnhedlon Faur andIX Jovl4memaleuahedran1nlg Th e 1 12 1 13 1 o m to The have detnmmant equals 1 11 and unly 10112 aux mm are an the same plane Farthepmnts n n A n n n s and n n n WW7 1 31111 1 n 4111 than Emu D 6 12 thus the tetrahedral n n 111 vulumz 1 12 1 u m Bangle Letu 454 5 andv 11 5421 a 1111 meme m 1 and 1m mememe 1 e1er ehe 1 Fmd the vectm 1mm 1 m v the uent amine 1mm 1 m v and the argle m between 1 and v e Venl39y the oauehyesdewm lnequahty 2 3 Venl39y um duv duwdwv and the merge Inequath 111131 and v d Letw Dr Neal Fall 2008 Solution a Below are the points u 5 78 5 and v 74 6 712 and some other points in R3 Z 0785 5 5 78 74 4 6 8 Illll Illl I I I I I 6 y 540 5 X 7465712 712 0 6 712 Below are the vectors u 5 78 5 and v 74 6 712 5 78 5 Z 4 78 N y 5 X 74 6712 The length of u is u J52 82 52 J114 e 10677 and the length of v is IvII J42 62 122 J196 14 Dr Neal Fall 2008 u 5 78 5 and v 74 6 712 and w 1 2 3 b The vector from u to v is v u 9 14 717 The direct distance from u to v is 12 11 J92 142 172 J566 m 2379 As before Iu II J114 and I v 14 The dot product is u v 720 7 48 7 60 7128 1 128 J So the an le 1n between vectors u and v 1s 9 cos L m 1489 g Jll4 X 14 Z M 5 78 5 114 e 14 X J566 V 74 6 712 c IuVI 128 and lullxllvll 14J114 m 149479 thus luvl s lull Iv Also uvl 2 7 and uvJ1449 J54m 735 However Iu v J114 14 m 24677 thus uv S d From b duvv ulmm2379 Also duwIIw ull 42102 22 J120 dwvv wl5242152 J So duw dwv aim J z 27264 gt duv That is duv S duw dwv Dr Neal Fall 2008 MATH 307 Matrices An m X n matrix A al 1 is an array of mn numbers arranged into m rows and n columns where aij is the entry in the 139 th row jth column The values m X n are called the dimensions or size of the matrix If the dimensions are n X n then A is called a square matrix A2 1 4 1 4 2 0 4 2 a 0 3 6 B 2 0 1 3 G 5 1 6 L2 3 5 2f L S 5 2 A is a 2 X 3 matrix B is a 3 X 4 matrix G is a square matrix an 1 and 6123 6 b 32 3 and b24 3 with dimensions 3 X 3 Scalar Multiplication Let A ellj be an m X n matrix and let c be a real number Henceforth an individual real number will be called a scalar We define scalar multiplication to be the product of the scalar c with the matrix A given by cAcaZJ That is we simply multiply every entry in A by the value c For A as given above then 2 l 4 6 3 l2 3A3gtlt 0 3 6 0 9 18 Matrix Addition Let A ellj and B blj both be m X n matrices Then we define the sum A B by ABcZJ where cij alJ blJ or ABalJ blJ That is if A and B have the same dimensions then we can add A and B and we do so by adding their entries term by term 2 l 4 3 5 6 5 4 2 ExampIeI J 0 3 6 2 4 10 2 l 16 The operations of scalar multiplication and matrix addition make the set of all m X n matrices a vector space over the set of real numbers In this context an m X n matrix is called a vector and the real numbers are the scalars A special case is the set of IX n n matrices which are more often called the set of vectors in n edimen51onal space or R x1 x2 xn Dr Neal Fall 2008 Properties of Scalar Multiplication H Closure If A is m X n then cA is also m X n for every scalar c N Scalar Multiplicative Identity 1A A for all m X n matrices A w Associative cdA c dA for all scalars c and d and all m X n matrices A 3 Scalar Distribution cA B cA cB for all scalars c and all m X n matrices A B G1 Matrix Distribution c dA cA dA for all scalars c d and all m X n matrices A Properties of Matrix Addition H Closure lfA and B are m X n then AB is also m X n N Commutative A B BA for all m X n matrices A and B 9 Associative A B C A B C for all m X n matrices A B and C a Additive Identity A0A for all m X n matrices A where 0 is the m X n Zero matrix that has a 0 for each entry 5 Additive Inverse A is the scalar product 1A and A A0 for all m gtltn matrices A We define matrix subtraction by A B A B 01J bif which is done by subtracting entries term by term Matrix Multiplication Let A ellj be an m X n matrix and let BblJ be an n X p matrix Because the number of columns in A equals the number of rows in B we can define the matrix product AB in that order to be an m X p matrix given by n AB C c1Jwhere cij kzlcykbkj Example 2 3 1 1 4 2 0 2 4 A2 1 4 B 2 01 3 D s 2 0 3 6 2 3 5 2 1 6 2x3 3x4 4x2 AB BD DA 2X3 3gtlt4 3gtlt4 4gtlt2 4gtlt2 2X3 3 cols in A pair with 3 rows 4 cols in B pair with 4 rows 2 cols in D pair with 2 rows in B so AB is defined in D so BB is defined in A so DA is defined andist4 andis3gtlt2 andis4gtlt3 Note With these matrices BA DB and AD are not defined Dr Neal Fall 2008 Now how do we compute a matrix product Consider A and B as above and let C AB be its 2 X 4 product 611 612 613 614 CAB 621 622 623 624 To find CU use the inner product of the 139 th row of A with the jth column of B 1 4 2 01 2 1 41 AL J B 2 0 1 3 0 3 6 L2 3 5 2 2714 2714 2714 2714 1 4 2 0 2 0 1 73 72 3 5 2 611 012 013 014 21 12 42 24 10 43 22 11 45 20 13 42 8 20 23 11 0 3 6 0 3 6 0 3 6 0 3 6 1 4 2 0 2 0 1 73 72 3 5 2 621 622 623 624 01 32 6 2 04 30 63 02 31 65 00 3 3 62 6 18 33 3 8 20 23 11 C A3 6 18 33 3 Note To avoid this tedious manual labor you should learn how to enter matrices into your calculator On the T1789 go to APPS 6 3 to get a new matrix editor Set Type to Matrix then give the matrix a name and set its dimensions After one is defined you can use APPS 6 2 to bring it up and edit its dimensions or entries While editing a matrix use F6 6 to change the dimensions With A B and D defined as above use your calculator to verify that 21 21 6 0 18 BD 8 14 d DA 10 32 an 10 1 32 39 27 32 21740 Dr Neal Fall 2008 Identity Matrix The n X n identity matrix denoted In is the n X n matrix with all Is down the main diagonal and 0 s everywhere else In 6 where eil l and eij 0 for tat 1000 10 100l 12 0100 1201J 131010 4 0010 001 L0001J Theorem 1 Let A ellj be an m X n matrix Then ImA A and AI A Proof Because 1m has m columns which equals the number of rows in A the product ImA is defined Moreover ImA is m X n the number of rows in 1m by the number of columns in A 0 ImA has the same dimensions as A m Now let ImA C clj where cij Zeikakj kl If k i then eik 0 and e 1 hence cij simplifies to ciJe aiJaZJ Because their entries are equal for all z39 j we have C A Now consider AIn which is defined because A has n columns which equals the number of rows in In Moreover AI is m X n which is the same size as A n Now let AI D cgj where allJ Zaikekj kl If kart then ekj 0 and eJJ 1 hence dij s1mp11f1es to dij alJ eJJaZJ Because their entries are equal for all z39 j we have D A 2 l 4 Example 3 LetA0 3 6Jwhichis 2gtlt3 Then 12AAAI3 That is 10 0 10 2 1 4 2 1 4 2 1 4 x gtlt010 01 0 3 6 0 3 6 0 3 6 0 01 2gtlt2 2gtlt3 2gtlt3 2gtlt3 3gtlt3 Dr Neal Fall 2008 Other Properties of Matrix Multiplication 1 Associative ABC ABC whenever A is m X n B is n X p and C is p X q 2 Distributive ABCABAC whenever A is m X n and B C are n X p 3 Distributive A BC ACBC whenever A B are m X n and C is n X p 4 Scalar Associative cAB cAB AcB for all scalars c whenever A is m X n B is n X p Proofon Let A ellj B blj and CclJ Then BCbZJclJ and ABCDdZJwhere n n n n dij Elam bkj ij 31691 bkj aikckj Elam bkj k 16 k ij fun where JABAC De nition A square matrix A al 1 is called diagonal if aij 0 whenever z39 i j Theorem 2 Let A ellj and B b1 j both be diagonal n X n square matrices Then ABBAcZJ where oil61 xbli and cij 0 for tat That is ABBA and this product is a diagonal matrix with its diagonal entries being the product of the diagonal entries in A and B Proof Because A and B are both n X n the products AB and BA are both defined and are n X n Because A and B are diagonal then aij 0 and bi 0 whenever tat Now let n ABC c1Jwhere cij chykbkj 1 Whenever k i then aik0 hence cij simplifies to cij a bif Now if j i then bij 0 and so c if 0 If j 139 then c 1 a b An analogous argument shows the result as well for the product BA 2 0 0 3 0 0 6 0 0 Example 4 Let A 0 4 0 and B 0 2 0 ThenAB 0 8 0 BA L0 0 3 L0 0 4J L0 0 12J Note Whenver A and B are both nxn then the products AB and BA are both defined However it is generally the case that AB BA Create your own example with some 2 X 2 matrices So matrix multiplication is nonrcommutative Dr Neal Fall 2008 Transpose Let A ellj be an m X n matrix We define A transpose denoted by AT to be an n X m matrix defined by AT al j where 611 aJi That is we simply take rows of A and make them the columns of AT or take the columns of A and make them the rows of AT A square matrix A is called symmetric if AT A which means that aij aJZ for all z39 j 4 2 3 l 2 3 5 2 1 4 2 6 0 4 Examp1e5 LetAL0 3 6 GL5 1 6 H 3 0 8 9 8 5 2 4 9 2 2 01 Tf45 81 Then AT 1 3 G 2 1 5 andHTHsoHissymmetric L4 6 L 3 6 2 T Quick Facts i AT A The transpose of the transpose gives back the original A ii cAT CAT and A BT AT BT Fact ii means that transpose is a linear operator on the set of matrices ie constants factor out and transpose is additive You have seen other linear operators such as the integral operator on the set of continuous functions f With integration we have jcfxdxcjfxdx and jfxgxdxjfxdxjgxdx that is constants factor out and integration is additive Other linear operators include differentiation on the set of differentiable functions and summation on the set of infinite series Theorem 3 Let A be an m X n matrix Then AAT and ATA are both defined and are square matrices Proof Because A is m X n then AT is n X m So the number of columns in A equals the number of rows in AT thus AAT is defined and is m X m the number of rows in A by the number of columns in AT Because AT is n X m and A is m X n the number of columns in AT equals the number of rows in A So ATA is defined and is n X n the number of rows in AT by the number of columns in A Dr Neal Fall 2008 MATH 307 Linear Transformations from R1 to Rm Let T Rquot gt Rm be a function which maps vectors from Rquot to Rm Then T is called a linear transformation if the following two properties are satisfied i Tcu cTu for all scalars c and all vectors u in Rquot ii Tu v Tu Tv for all u v in R It is equivalent to say that Tcu v cTuv for all scalars c and all vectors u v ian In order to define such a transformation T we must describe its action on a point x1x2 xn in Rquot That is we must define Tx1x2 xn which must be a vector in m R hav1ng m coordinates In order for T to be linear each coordinate in Rm must be a linear combination of x1x2 xn That is T must have the functional form Tx1x2 991 a11x1a12x2 a1nxn a21x1 612 2x2 612 nxn am 1x1 am 2x2 61quot nxn Example 1 Let T R3 gt R4 be defined by Txl x x3 2x1 72x2 3x3 x1 x27 x3 x1 4x274xl 76x2 3x3 ls T linear What is T1 2 3 Each of the four coordinates in the range is a linear combination of the three variables x1 x x3 from the domain thus T is a linear transformation Also T1232 4912 3184 12970977 Example 2 Let T R3 gt R2 be defined by Tx x2 x3 sinx1cosx2 4x3 x1x2 x36 Neither coordinate in the range is a linear combination of the domain variables x1 x2 x3 thus T is not a linear transformation although T is still a function Dr Neal Fall 2008 The Matrix Representation Every linear transformation T Rquot gt Rm can be represented by a unique m X n matrix A The m rows are the coefficients from the linear combinations of the function form coordinates in Rm That is suppose T Rquot gt Rm is defined by Tx1x2 xn a11x1a12x2 a1nxn a21x1 612 2x2 612 nxn am1x1am2x2 amnxn all 012 aln If we let x x1x2xn e Rquot then we 6121 6122 612 x1 then A x2 can write X I as an n X 1 matrix aml amZ amn xn The function value Tx1x2 xn then can be computed by the matrix product AX which gives an m X 1 matrix that is the function value point in Rm We therefore interchangeably write Tx AX Example 3 Let T R3 gt R4 be defined by Txl x x3 2x1 72x2 3x3 x1 x27 x3 xl4x 74xl 76x2 3x3 2 2 3 l l The matrix representation is the 4 X 3 matrix A 1 4 0 How do we evaluate 4 6 3 1 2 2 3 1 7 l l l 0 T123 LetX 2 thenT123AgtltX 1 4 0 X 2 7 9 3 4 6 3 3 7 7 0 9 77 as coordinates in R4 What is the action of T on the standard basis in R3 Dr Neal Fall 2008 2 2 3 1 2 2 2 3 0 2 W h 1 1 1 0 1 d 1 1 1 1 1 d t t esee a 1 4 0 X 0 1 an 1 4 0 X 0 4 an 4 6 3 4 4 6 3 6 2 2 3 3 1 1 1 0 1 Thus the columns of A are simply the action of X 0 T on the standard basis elements 1 0 0 0 l 0 1 4 0 1 and 0 0 1 Therefore each of the columns of A are 4 6 3 3 actually elements in the range of T A Matrix De nes a Linear Transformation Reversing the process we see that any m X n matrix A defines a linear transformation T A Rquot gt Rm by xl x2 TAx AX where x x1x2xn and X xn 2 8 3 2 For example given the 2 X 3 matrix A 4 6 3 then TA R gt R is defined by 3 2 x Txlx x3 4 6 3 X x2 kx3 3x1 2x2 8X3 7 3 2846 3 4x1 6x2 3X3 XI x2 x3 x1 x2 x3 Defining Tby Action on the Standard Basis A linear transformation T Rquot gt Rm can also be defined by its action on the standard basis Let e1 1 0 0 e2 01 0 en 001 lfwe know what T does to each basis element then we can evaluate T at any point Because T is linear we have Tx1x2 991 Tltx1 1x2 2 xnen x1 Te1x2 TeZ xn Ten Also once we know the action on the standard basis then we also know the columns of the matrix representation A thus we can easily evaluate T at any point Dr Neal Fall 2008 Example 4 Evaluate T 2 3 8 10 for T R4 gt R3 defined by Tl 00 0 1 2 3 TO 10 0 2 1 4 TO 01 0 12 4 TO 00 1 2 06 Solution Because T is linear we have T2 38 10 2 T1000 3 TO 1 0 0 8 TO 0 1 0 10 TO 0 01 2 1 2 3 32 1 4 8 1 2 4 10 2 0 6 36 9 10 1 2 1 2 Or we can write A L 2 1 2 OJ where the columns of A are the action on 3 4 4 6 2 121 23l36 thestbasis Then T 238 10 2 1 2 OJx 8 J369 10 K 3 4 4 6 FIOJ K 10 Oneetonne Transformations Let T Rquot gt Rm be a linear transformation Then T is onertorone or injective if it is always the case that different values in the domain are assigned to different values in the range That is whenever u i v then Tu Tv By the contrapositive it is logically equivalent to say that whenever Tu Tv then u v To prove that a function is oneetoeone we often assume that Tu Tv and then argue that u must equal v With a linear transformation T from Rquot to Rm we can use the following results to check if T is oneetoeone Theorem 1 Let T Rquot gt Rm be a linear transformation with matrix representation A Then T is oneetoeone if and only if the homogeneous system AX 0 has only the trivial solution of X 0 Proof We note that Tx AX where X is then n X 1 column matrix form of the vector x e Rquot ForX0thenx000 First suppose T is oneetoeone We know that X 0 is always one solution to the homogeneous system AX 0 But suppose there is another solution Y such that AY 0 Then TO 0 0 A X 0 0 AY Ty Because T is oneetoeone then y 0 0 0 which implies that Y is the n X 1 zero matrix Thus 0 is the only solution to the homogeneous system AX 0 Dr Neal Fall 2008 Now suppose that 0 is the only solution to the homogeneous system AX 0 To prove that T is oneitoione assume that Ty Tz Then AY AZ which means that 0 AY AZ AY Z Thus Y Z is a solution to the homogeneous system But because 0 is the only solution then Y Z 0 Thus Y Z which is equivalent to y z in Rquot Hence T is oneitoione QED Theorem 2 Let T Rquot gt Rm be a linear transformation with matrix representation A If m lt n then T cannot be oneitoione Proof Note Because Rquot is a larger set than Rm when m lt n it should not be possible to map Rquot to Rm in a oneitoione fashion To prove the result observe that the matrix representation A will be an m X n matrix with fewer rows than columns Thus the last nonizero row of the reduced row echelon form of the homogeneous system A 0 will have independent or free variables Hence AX 0 will have infinite solutions not just the trivial solution By Theorem 1 T cannot be oneitoione 0 0 0 1 0 1 1 0 1 c 0 Theorem 3 Let T Rquot gt Rm be a linear transformation with matrix representation A Assume m gt n Then T is oneitoione if and only if the reduced row echelon form of A reduces to the n X n identity with additional rows that are all 0 Proof To determine if T is oneitoione we must see if the homogeneous system AX 0 has only the trivial solution We consider the reduced row echelon form of the m X n matrix A Because there are more rows than columns we have two cases 1 0 1 c1 1 l 1 1 on 1 0 0 0 l 0 0 0 0 the n X n identity with free variables remain in the additional rows that are all 0 last nonizero row In the first case AX 0 has only the trivial solution thus T is oneitoione In the second case AX 0 has infinite solutions thus T is not oneitoione Dr Neal Fall 2008 Theorem 4 Let T Rquot gt Rquot be a linear transformation with matrix representation A Then T is oneitoione if and only if detA 0 Proof Because A is now n X n we can say detA 0 if and only if the homogeneous system AX 0 has only the trivial solution if and only if T is oneitoione Example 5 Let T R3 gt R4 be defined by Txl x x3 2x1 72x2 3x3 x1 x27 x3 xl 4x 74xl 76x2 3x3 ls T oneitoione Solution We let A be the matrix representation and look at the reduced row echelon form of homogeneous system A 0 2 230 10 11 10 01 1400gtrrefgt0010 4 630 00 The only solution to AX 0 is X 0 thus T is oneitoione A reduces to the identity with an additional row of 039s Example 6 Let T R4 gt R5 be defined by T1 00 0 1 2 30 1 T0 10 0 2 1 41 0 T0 010 1 2 4 0 2 T0001 2 63 2 5 Is T is oneitoione Solution We look at the reduced row echelon form of homogeneous system A 0 12120 10030 2 1260 01020 34430 gtrref gt00110 01020 00000 10250 00000 We see that AX 0 has infinitely many solutions thus T is not oneitoione Matrix A does not reduce to the identity with additional rows of 0 Dr Neal Fall 2008 Example 7 Let T R2 gt R2 be the reflection about the xeaxis ls T oneetoeone l 0 Solution We define T by Tx y x y The matrix representation is A 0 J which are the coefficients from the linear combinations of the function form coordinates Because detA 71 0 we see that T is oneetoeone Onto Transformations Let T Rquot gt Rm be a linear transformation Then T is onto or surjective if every vector b e Rm has a preeimage in Rquot That is for every b e Rm there is a v e Rquot such that Tv b The vector v is a preeimage of b In other words the equation Tx b always has a solution for every b e Rm We can use the following results to determine if a linear transformation is onto Theorem 5 Let T Rquot gt Rm be a linear transformation with matrix representation A Then T is onto if and only if the matrix equation AX B always has a solution for every m X 1 matrix B Proof Because the equation Tx b is equivalent to the matrix equation AX B the theorem is simply a matrix form restatement of the definition of onto Theorem 6 Let T Rquot gt Rm be a linear transformation with matrix representation A If m gt n then T cannot be onto Proof Note Because Rm is a larger set than Bquot when m gt n it should not be possible for every element in Rm to have a preeimage by means of the function T To prove the result observe that the matrix representation A will be an m X n matrix with more rows than columns Thus the reduced row echelon form of any system A I B will have the additional rows in A become all 0 These rows will lead to inconsistencies for certain m gtltl matrices B Thus AX B will not always have a solution and T cannot be onto Dr Neal Fall 2008 Theorem 7 Let T Rquot gt Rm be a linear transformation with matrix representation A Assume m lt n Then T is onto if and only if the reduced row echelon form of A does not contain a row of all 039s Proof To determine if T is onto we must see if every possible system AX B has a solution We consider the reduced row echelon form of the m X n matrix A Because there are fewer rows than columns we have two cases 1 0 l 0 l 0 l l l l 0 l 0 0 0 no rows become all 0 a row becomes all 0 If no rows become all 0 then there will never be an inconsistency So AX B will always have a solution and T is onto If a row becomes all 0 then there will be inconsistencies for some B when trying to solve AX B Thus at times AX B will have no solution and T will not be onto Theorem 8 Let T Rquot gt Rquot be a linear transformation with matrix representation A Then T is onto if and only if detA 0 Proof Because A is now n X n we can say detA 0 if and only if any system AX B always has a solution if and only if T is onto Theorem 9 Let T Rquot gt Rquot be a linear transformation Then T is either both oneitoi one and onto ie a bijection or T is neither oneitoione nor onto Proof Let A be the matrix representation of T By Theorems 4 and 8 T is oneitoione if and only if detA 0 if and only if T is onto Thus T is oneitoione if and only if T is onto That is T is either both oneitoione and onto or T is neither Example 8 Let T A R4 gt R3 be defined by the matrix representation 1 0 2 4 A 1 2 1 3 2 1 0 2 where TAx AX ls TA oneitoione andor onto Is the point 4 72 6 in the range of TA If so find a preiimage Dr Neal Fall 2008 Solution Because R3 is a smaller set than R4 T A cannot be oneitoione Theorem 2 To determine if T A is onto we consider the reduced row echelon form of A 1 0 0 12 0 1 0 04 0 0 1 26 Because no rows became all 0 there will never be an inconsistency So every system AX B will have a solution therefore T A is onto Now we can say that for any vector b 6R3 there is a preiimage v 6R4 such that Tv b In fact we can see from rrefA that there will be infinite preiimages which also verifies that T A is not oneitoione In particular we can solve the equation T Ax 4 72 6 x1 4812t x2 36 041 x3 44 261 1 0 2 4 4 10 0 12 48 1 2 1 3 2J gtrref gt 0 1 0 04 36J gt K 2 1 0 2 6 K0 0 1 26 44 X4 I If t 0 then 48 736 744 0 is one particular preiimage of 4 72 6 That is T 48 36 44 0 4 42 6 Example 9 Let T R3 gtR4 be the embedding map which places a point from R3 into R4 by adding a 0 in the 4th coordinate ls T oneitoione andor onto Solution Here we can define T by Tx y 2 x y z 0 The matrix representation is l 0 l 0 the 4 X 3 matrix A 0 0 1 We see that A is already in rref form and has a row of 0 0 0 all 039s By Theorem 7 T is not onto In particular every element in R4 with a non zero 4th coordinate will cause an inconsistency thus these elements will not be in the range However the homogeneous system AX 0 has only the trivial solution of X 0 thus T is oneitoione Inverses of Transformations from i t Rquot When a linear transformation T Rn gt Rquot is both oneitoione and onto then we can find the inverse transformation T71 Rquot gt Rquot such that if T x1x2 xn fl ylay2quot39 yn then T ylay2939 yn xlax2quot39xn39 Dr Neal Fall 2008 If A is the matrix representation of the oneitoione and onto T then we know that detA 0 Therefore AT1 exists Because Tx1x2 xn yly2 yn is equivalent to AX Y we can apply the matrix inverse and say that X A71 Y Thus A71 must be the matrix representation of T71 because x1x2 xn T71yly2 yn Example 10 Let T R3 gt R3 be defined by T1 00 1 0 71 T010 2 12 T0 01 1 1 4 Verify that T is a bijection Find the function form of T71 K 1 2 1 Solution The matrix representation of T is A L 0 1 1J and detA l i 0 thus T is l 2 4 both oneitoione and onto ie a bijection The matrix representation of T71 is A71 K 2 6 1 L l 5 1J Thus 1 4 l T71xyz 2x 6yz x5y zx 4yz Note T 110 1 100 T 1212 0 10and T 11 1 4 0 0 1 Example 11 Let T R2 gt R2 be the reflection about the xiaxis Find T71 0 1 1 0 Then A also So 1 0 l T71x y x y Tx y In other words T is its own inverse If you reflect about the xiaxis then you undo the process by re ecting back about the xiaxis 1 Solution Here Txy x y and A 0 Dr Neal Fall 2008 Null Space and Nullity Let T Rn gt Rm be a linear transformation with m X n matrix representation A The null space or kernel of T is the set of all vectors x ERquot such that Tx 0 We know that T0 0 0 0 0 0 that is T0 0 or A X 0 0 If T is oneitoione then no other vector gets mapped to the origin that is AX 0 has only the trivial solution of X 0 and the null space is simply 0 But if T is not oneitoione then AX 0 will have infinitely many solutions The set of all solutions to AX 0 is the null space The nullity is the dimension of this null space and is given by the number of independent parameters r s t etc used in writing the form of all solutions to AX 0 And if T is oneitoione then the nullity is simply 0 Range and Rank The range of T is the set of all vectors y e Rm for which T x y for some x All of the columns in the matrix representation A are actually elements in the range of T The first column in A is the value T1 0 0 0 the second column in A is the value T0 1 0 0 etc But some of these columns may be linear combinations of the previous columns The columns in A that are independent of each other create the dimensions in the range of T The actual range of T will be the collection of all linear combinations of these independent vectors and the rank of T is the dimension of this range Example 12 Let T R5 gt R5 be defined by its action on the standard basis as Tel112 01 T92 1 1 11 Te30111 1 Te4l 12 00 Te5l0 l ll a Give the matrix representation and functional form of T b Is T oneitoione and or onto c Are 1 Z 3 4 5 and 4 Z 6 72 5 in the range of T If so find preiimages d Find the null space and nullity e Find the range and rank Solution a The columns of the matrix representation are the action on the standard basis elements Thus 1 0 0 1 1 1 1 1 1 0 A 2 1 1 2 1 0 1 1 0 1 1 1 1 0 1 Tx1 x x3 x4 965 x1 x4 x5 x1 7 x2 x3x4 Zxr x2x3 2x4x57x2 x37x5 x1x27x3x5 Dr Neal Fall 2008 b detA 0 thus A is neither oneetoeone nor onto 1 0 0 1 1 1 4 1 0 0 0 0 0 3 1 1 1 1 0 2 2 0 1 1 0 1 0 2 c AB 2 1 1 2 1 3 6 rref gt 0 0 0 1 1 0 1 0 1 1 0 1 4 2 0 0 0 0 0 10 1 1 1 0 1 5 5 0 0 0 0 0 0 0 For B l 2 3 4 5 we see that AX B has no solution so 1 Z 3 4 5 is not in the range of T However there are infinite solutions for B 4 7 5 One such solution is 3 20 10 That is 4 Z 6 72 5 is in the range of T and T3 Z 0 l 0 4 Z 6 72 5 l 0 0 0 0 0 0 1 1 0 1 0 The null space is d WefA0 0 0 0 1 1 0 x1x2x3x4x5 03 ts tt 0 0 0 0 0 0 0 0 0 0 0 0 which uses 2 variables Zedimensional So nullity 2 e From rref A we see that the original third column is a linear combination of the original first and second columns The original fifth column is a linear combination of the original first second and fourth columns So the original first second and fourth columns create three dimensions in the range of T Thus rankT 3 and the range of T is the collections of all linear combinations of the three Vectors Te1 1 1 2 01 Te2 0 1 1 11 and Te4 1 1 2 00 Description T R5 gt R5 Domain R5 Range 5 5 dimensions A Three Dimensional Subpace of R spane1 e2 e4 gt SPaHTei T92 T94 T U U a Twoedimensional Null Space 0 0 0 0 0 T is not oneetoeone Two dimensions of R5 all get mapped to 0 0 0 0 0 T is not onto The range is 37d only three dimensions of R5 have preeimages Dr Neal Fall 2008 MATH 307 Cryptography with Matrices Goals i To take a message and encrypt it into a string of numbers via matrix multiplication ii Then to take the string of numbers and decrypt it back to a written message As an initial example We shall use the following message quotHI THERE BUDDYquot AlphaiNumeric Substitution First we must assign each letter a numeric equivalent Here we shall reserve the number 0 to represent a space and use the numbers 1 7 26 to represent the 26 letters Rather than just making a direct substitution in order we can permute the digits in some way For example IAIBICIDIEIFIGIHIIIJIKILIMI Z1436587109121114 INIOIPIQIRISITIUIVIWIXIY Z 131615181720192221Z42326 25 Coding Matrix Next we choose an invertible n X n matrix A for some size n which will be used to encrypt the message Here we shall use 3 2 3 A L 6 5 4J 9 8 7 Encrypting The Message We first convert the message into the numeric script using the alphainumeric substitution above H 7 l 10 Blank 0 etc 7100197617601223326 Then we convert this script into a m X 3 matrix 3 columns because our A is 3 X 3 The number of rows m depends on the length of the message We fill out the last row with more 039s as necessary 7 10 0 I19 7 6 B17 6 0 1223J 3260 Dr Neal Fall 2008 Here B is 5 X 3 Now we multiply C BA 7 10 m 39 36 19 I19 7 6 3 2 3 I69 51 71 l 15 4 27 CBA 3917 6 0 xL 6 5 4J 1 22 3J 9 8 7 102 84 64J 3 26 0 l47 124 95 Finally we convert matrix C into a string that becomes the encrypted message 739 736 719 69 51 71 15 4 27 7102 784 764 7147 7124 795 H l T H E R E B U D D Y Notice that has been sent to two different values The first H has been encrypted as 739 and the second H has been encrypted as 51 Likewise the three blanks are assigned different values as are the two E s and the two D s Decrypting the message The second party receives only the encrypted message 739 736 719 69 51 71 15 4 27 7102 784 764 7147 7124 795 However the receiver knows the alphainumeric code and the coding matrix A Thus the encrypted script is converted back into an m X 3 matrix C and then multiplied by AT1 to undo the original matrix multiplication Because C BA we obtain the original matrix B by B CATI and then we convert the string back to the alphabet ToCharacterCode Command When using a software package to encode messages we can use the builtiin features that will automatically convert alphabetic symbols into numeric equivalents With Mathematica we can use the ToCharacterCode command For example consider the following message Dear colleague what is 4 of 120 We would need alphainumeric equivalents not only for the 26 letters but also for the symbols and 7 and for numbers Rather than trying to define our own alphai numeric substitution we can use the builtiin Mathematica command that is also case sensitive First type the message enclosed in quotes Here we define the message to be the term script Then apply the ToCharacterCode command Dr Neal Fall 2008 scriptquotDear colleague what is 4 of 120quot numericToCharacterCode script 68101971143299llllOBlOBlOl97103ll7lOl4432ll9 104971163210511532523732llllOZ3249504863 We observe that a blank is represented by 32 and that an 1 is assigned 108 Mathematica Codes Now we need a short program that will allow us to input our n X n coding matrix A convert numeric into an m X n matrix B and fill out the last row with Blanks multiply BA to get C and then convert the matrix C into just a string of numbers This string of numbers will be the encrypted message which is sent The following commands perform each of these tasks scriptquotDear colleague what is 4 of 120 quot A3236 5 4987sizen3Det A numericToCharacterCode script While Mod Length numeric n l0AppendTo numeric 32 Do Do b ij numeric nil j j ln i lCeiling Length numeric n BTable b i j i lCeiling Length numeric n j ln MatrixForm B ZB AMatrixFormZ encryptFlatten Z 47l407479lO4l86090765754665764854l636l4l81255 318301348 ll7 13051 87 lO979222l752329 32l49 279232283285222285 We see common letters are assigned to different numerical values One 1 has been assigned 546 and the other is given 657 Now the code cannot be broken by studying the frequency of numeric occurrences In addition different letters may be assigned the same numerical value The first 657 in encrypt came from the letter 0 while the second 657 came from Likewise one 285 is from and the other 285 is actually a blank Decryption The person receiving the encrypted message must also know the encoding matrix A The received string must first be reiconverted into a matrix Y that is then multiplied on the right by A l The resulting product is put back into a string and then converted into its character code giving the plaintext message We illustrate with the encrypted message encrypt created above Dr Neal Fall 2008 encrypt47l407479104l860 907657546657648541636l4l 8125531830l348 ll7 l3051 87 10979222l752329 32l49279232283285222285 A323 6 5 4987Sizen3 Do Do c ij encry39pt nil j jln ilLengthencrypt n YTable c i j i lLength encrypt n j ln VY Inverse A MatrixForm V decryptFlatten V FromCharacterCode decrypt Dear colleague what is 4 of 120 Assignment 1 Pick a partner Together decide on a square invertible coding matrix A Adjust the programs accordingly with this matrix A 2 Each student create an encrypted message to send to the other Print out the program and outputs used to create your encrypted message On it write quotMessage from 39your name39 to partners name39quot 3 Email your partner only your encrypted message Send the numbers enclosed in braces and separated by commas 4 Check your email to obtain the encrypted message from your partner Print out this email 5 Decrypt your received message Print out the codes and outputs used to decrypt On it write quotMessage from 39partner39s name39 decoded by 39your name 6 Turn in both printiouts along with the received email message Note If doing this in the lab you can first create your encrypted message with Mathematica Then highlight and copy the final encrypted message output Then use email on the same computer to send it by simply pasting into the body of the message Likewise you can check your email in the lab highlight and copy the received message then open your Mathematica le and paste it into the decryption codes Otherwise you will have to type out the numbers when you send the email and type them out again when you decrypt
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'