On Tue Nov 2 20:15:35 EDT 2010 ## This example shows how large powers of a diagonalizable matrix can be easily computed. > G := Matrix(4,4,{(1, 1) = 1203, (1, 2) = 798, (1, 3) = -624, (1, 4) = 1128, (2, 1) = -1106, (2, 2) = -732, (2, 3) = 588, (2, 4) = -1036, (3, 1) = 158, (3, 2) = 105, (3, 3) = -81, (3, 4) = 148, (4, 1) = -410, (4, 2) = -273, (4, 3) = 204, (4, 4) = -385}); [ 1203 798 -624 1128] G = [-1106 -732 588 -1036] [ 158 105 -81 148] [ -410 -273 204 -385] > Gofx := G - x*eye(4); fGx := Det(Gofx) = factor(fGx); [1203 - x 798 -624 1128 ] [ ] [ -1106 -732 - x 588 -1036 ] Gofx = [ ] [ 158 105 -81 - x 148 ] [ ] [ -410 -273 204 -385 - x] 2 3 4 2 fGx = 9 x + 3 x - 5 x + x = x (x + 1) (x - 3) > G0 := G - 0*eye(4); Gn1 := G - (-1)*eye(4); G3 := G - 3*eye(4); [ 1203 798 -624 1128] G0 = [-1106 -732 588 -1036] [ 158 105 -81 148] [ -410 -273 204 -385] [ 1204 798 -624 1128] Gn1 = [-1106 -731 588 -1036] [ 158 105 -80 148] [ -410 -273 204 -384] [ 1200 798 -624 1128] G3 = [-1106 -735 588 -1036] [ 158 105 -84 148] [ -410 -273 204 -388] > rrG0 := RREF(G0); rrGn1 := RREF(Gn1); rrG3 := RREF(G3); [1 0 0 38/13] rrG0 = [0 1 0 -35/13] [0 0 1 5/13] [0 0 0 0 ] [1 0 0 3 ] rrGn1 = [0 1 0 -14/5] [0 0 1 2/5] [0 0 0 0 ] [1 0 -18 -4 ] rrG3 = [0 1 184/7 52/7] [0 0 0 0 ] [0 0 0 0 ] ##Since Nullity(rrG0) is 1, our G-eigenspace for the 0-eigenvalue is 1-dim'al. We use back-substitution to solve for a 0-eigenvector v0. > v0 := <-38/13, 35/13, -5/13, 1>; v0 := 13 * v0; G . v0; [-38/13] [-38] [0] v0 = [ 35/13] , v0 = [ 35] , [0] [ -5/13] [ -5] [0] [ 1 ] [ 13] [0] ##Since Nullity(rrGn1) is 1, the G-eigenspace for the [-1]-eigenvalue is 1-dim'al. Back-substitution will give us a G-eigenvector vn1 for eigenvalue -1. > vn1 := 5 * <-3, 14/5, -2/5, 1>; G . vn1 ; [-15] [ 15] vn1 = [ 14] , [-14] [ -2] [ 2] [ 5] [ -5] ##Finally, as Nullity(rrG3) is 2, the G-eigenspace for eigenvalue 3 is 2-dim'al. Back-substitution gives us a basis {v3a, v3b} for this G-eigenspace. > v3a := 7 * <18, -184/7, 1,0>; v3b := 7 * < 4, -52/7,0,1>; [ 126] [ 28] v3a = [-184] , v3b = [-52] [ 7] [ 0] [ 0] [ 7] > GTimesv3a := G . v3a ; 3 * v3a ; [ 378] [ 378] GTimesv3a = [-552] , [-552] [ 21] [ 21] [ 0] [ 0] > GTimesv3b := G . v3b; 3 * v3b ; [ 84] [ 84] GTimesv3b = [-156] , [-156] [ 0] [ 0] [ 21] [ 21] ##With cvec the ordered-basis (v3a, v3b, v0, vn1), note that the below matrix C is the matrix-name of Id going from cvec to the standard-basis. > C := ; [ 126 28 -38 -15] C = [-184 -52 35 14] [ 7 0 -5 -2] [ 0 7 13 5] > Cinv := MI(C) ; [ 52/7 5 -15/7 52/7 ] Cinv = [-135/7 -13 38/7 -135/7 ] [ 10 7 4 12 ] [ 1 0 -18 -4 ] > D := Cinv . G . C ; [3 0 0 0] D = [0 3 0 0] [0 0 0 0] [0 0 0 -1] > C . D . Cinv ; G := G ; [ 1203 798 -624 1128] [-1106 -732 588 -1036] [ 158 105 -81 148] [ -410 -273 204 -385] [ 1203 798 -624 1128] G = [-1106 -732 588 -1036] [ 158 105 -81 148] [ -410 -273 204 -385] /--------------------------------------------------------\ ## Now look at G. Imagine computing G^k where, say, k=2000. Oy!, what a pain. But note that G^k = [C * D * Cinv]^k = C * D^k * Cinv [3^k 0 0 0 ] [0 3^k 0 0 ] = C * [0 0 0 0 ] * C^{-1} . [0 0 0 (-1)^k ] \________________________________________________________/ > Dk:=Matrix(1..4,1..4, Vector([Tk, Tk, 0, Nk]),shape=diagonal); [Tk 0 0 0 ] Dk = [0 Tk 0 0 ] [0 0 0 0 ] [0 0 0 Nk] > GtoPowerk := C . Dk . Cinv ; ##So GtoPowerk equals [ 396 Tk - 15 Nk 266 Tk -118 Tk + 270 Nk 396 Tk + 60 Nk] [-364 Tk + 14 Nk -244 Tk 112 Tk - 252 Nk -364 Tk - 56 Nk] [ 52 Tk - 2 Nk 35 Tk -15 Tk + 36 Nk 52 Tk + 8 Nk] [-135 Tk + 5 Nk -91 Tk 38 Tk - 90 Nk -135 Tk - 20 Nk] > subs( {Tk = 3, Nk = -1} , GtoPowerk) ; [ 1203 798 -624 1128] [-1106 -732 588 -1036] [ 158 105 -81 148] [ -410 -273 204 -385] > G ; [ 1203 798 -624 1128] [-1106 -732 588 -1036] [ 158 105 -81 148] [ -410 -273 204 -385] > subs( {Tk = 9, Nk = 1} , GtoPowerk) ; [ 3549 2394 -792 3624] [-3262 -2196 756 -3332] [ 466 315 -99 476] [-1210 -819 252 -1235] > G . G ; [ 3549 2394 -792 3624] [-3262 -2196 756 -3332] [ 466 315 -99 476] [-1210 -819 252 -1235] GtoPowerk = [ 396 Tk - 15 Nk 266 Tk -118 Tk + 270 Nk 396 Tk + 60 Nk] [-364 Tk + 14 Nk -244 Tk 112 Tk - 252 Nk -364 Tk - 56 Nk] [ 52 Tk - 2 Nk 35 Tk -15 Tk + 36 Nk 52 Tk + 8 Nk] [-135 Tk + 5 Nk -91 Tk 38 Tk - 90 Nk -135 Tk - 20 Nk] = [ 396 266 -118 396] [-15 0 270 60] k [-364 -244 112 -364] k [ 14 0 -252 -56] 3 * [ 52 35 -15 52] + (-1) * [ -2 0 36 8] [-135 -91 38 -135] [ 5 0 -90 -20] ##Let [ 396 266 -118 396] [-15 0 270 60] [-364 -244 112 -364] [ 14 0 -252 -56] M := [ 52 35 -15 52] , B := [ -2 0 36 8] . [-135 -91 38 -135] [ 5 0 -90 -20] For each posint k, then, we have that G^k = [3^k]*M + [(-1)^k]*B. So for each /even/ posint k, G^k = [3^k]*M + B. And for each /odd/ posint k, G^k = [3^k]*M - B. ## Application: Given an arbitrary 4x1 col-vec u, by computing Cinv * u we can tell trivially what the growth rate of k |-> [[G^k] * u] is. The lefthand action of G is isomorphic to the lefthand action of D. ================================================================