$SPAD/src/input chtheorem.input

Alaisdair McAndrew, Themos Tsikas, Timothy Daly

December 3, 2016

Abstract

The Cayley-Hamilton theorem states that every square matrix over the real or complex field satisfies its own characteristic equation.

Contents

1 Definition

The Cayley-Hamilton theorem states that every square matrix over the real or complex field satisfies its own characteristic equation.

If A is a given square matrix n x n and I_{n} is the n x n identity matrix, then the characteristic polynomial of A is defined at

p(λ) = det(λI_{n} − A)

where det is the determinant function. The Cayley-Hamilton theorem states that substituting the matrix A in the characteristic polynomial results in the zero matrix:

p(A) = 0

The Cayley-Hamilton theorem also holds for square matrices over commutative rings.

2 Example

Consider the matrix

A = [ \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix} ]

The characteristic polynomial is given by

p(λ) [ \begin{matrix}λ − 1 & −2 \\ −3 & λ − 4 \end{matrix} ]

= (λ − 1)(λ − 4) − 2 ∗ 3

= λ_{2} − 5λ − 2

The Cayley-Hamilton theorem states that

A^{2} − 5A − 2I_{2} = 0

3 Discussion

The Cayley-Hamilton theorem allows us to calculate powers of matrices more simply than by direct multiplication.

Taking the result above we can solve for A^{2}:

A^{2} = 5A + 2I_{2}

So to compute other powers of A:

A^{3} = (5A + 2I_{2})A = 5A^{2} + 2A = 5(5A + 2I_{2}) + 2A = 27A + 10I_{2}

A^{4} = A^{3}A = (27A + 10I_{2})A = 27A^{2} + 10A = 27(5A + 2I_{2}) + 10A

A^{4} = 145A + 54I_{2}

— * —

)set break resume
)spool chtheorem.output
)set message test on
)set message auto off
)clear all
--S 1 of 28
D:=FFP(PF 2,x^4+x+1)
--R
--R
--R   (1)  FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?+1)
--R                                                                 Type: Domain
--E 1
--S 2 of 28 random input -- failure ok
M:=matrix([[random()$D for i in 1..4] for j in 1..4])
--R
--R
--R        +      3     2                                           3     2+
--I        |    %A  + %A                0                1        %A  + %A |
--R        |                                                               |
--R        |  3     2                  2                             2     |
--I        |%A  + %A  + %A + 1       %A  + %A            1         %A  + 1 |
--R   (2)  |                                                               |
--R        |      3     2            3                                     |
--I        |    %A  + %A           %A  + %A + 1          0         %A + 1  |
--R        |                                                               |
--R        |                      3     2             2             3     2|
--I        +        0           %A  + %A  + %A + 1  %A  + %A + 1  %A  + %A +
--R        Type: Matrix(FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?+1))
--E 2
--S 3 of 28 random input -- failure ok
p:=characteristicPolynomial(M,y)
--R
--R
--R         4      2       3      2           2            3     2
--I   (3)  y  + (%A  + %A)y  + (%A  + %A + 1)y  + %A y + %A  + %A  + %A
--R    Type: Polynomial(FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?+1))
--E 3
--S 4 of 28
SM:=SquareMatrix(4,D)
--R

--R
--R   (4)
--R   SquareMatrix(4,FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?+1))
--R                                                                 Type: Domain
--E 4
--S 5 of 28 random input -- failure ok
sp:=map(z+->(squareMatrix$SM)diagonalMatrix([z,z,z,z]),p)
--R
--R
--R   (5)
--R          +  2                                   +
--I          |%A  + %A     0         0         0    |
--R          |                                      |
--R          |            2                         |
--I      4   |   0      %A  + %A     0         0    | 3
--R     y  + |                                      |y
--R          |                      2               |
--I          |   0         0      %A  + %A     0    |
--R          |                                      |
--R          |                                2     |
--I          +   0         0         0      %A  + %A+
--R   +
--R     +  2                                                   +
--I     |%A  + %A + 1       0             0             0      |
--R     |                                                      |
--R     |                2                                     |
--I     |     0        %A  + %A + 1       0             0      | 2
--R     |                                                      |y
--R     |                              2                       |
--I     |     0             0        %A  + %A + 1       0      |
--R     |                                                      |
--R     |                                            2         |
--I     +     0             0             0        %A  + %A + 1+
--R   +
--I     +%A  0   0   0 +
--R     |              |
--I     |0   %A  0   0 |
--R     |              |y
--I     |0   0   %A  0 |
--R     |              |
--I     +0   0   0   %A+
--R   +
--R     +  3     2                                                     +
--I     |%A  + %A  + %A        0               0               0       |
--R     |                                                              |
--R     |                  3     2                                     |
--I     |      0         %A  + %A  + %A        0               0       |
--R     |                                                              |
--R     |                                  3     2                     |

--I     |      0               0         %A  + %A  + %A        0       |
--R     |                                                              |
--R     |                                                  3     2     |
--I     +      0               0               0         %A  + %A  + %A+
--RType: Polynomial(SquareMatrix(4,FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?+1)))
--E 5
--S 6 of 28 random input -- failure ok
sm:=squareMatrix(M)$SM
--R
--R
--R        +      3     2                                           3     2+
--I        |    %A  + %A                0                1        %A  + %A |
--R        |                                                               |
--R        |  3     2                  2                             2     |
--I        |%A  + %A  + %A + 1       %A  + %A            1         %A  + 1 |
--R   (6)  |                                                               |
--R        |      3     2            3                                     |
--I        |    %A  + %A           %A  + %A + 1          0         %A + 1  |
--R        |                                                               |
--R        |                      3     2             2             3     2|
--I        +        0           %A  + %A  + %A + 1  %A  + %A + 1  %A  + %A +
--RType: SquareMatrix(4,FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?+1))
--E 6
--S 7 of 28
eval(sp,y=sm)
--R
--R
--R        +0  0  0  0+
--R        |          |
--R        |0  0  0  0|
--R   (7)  |          |
--R        |0  0  0  0|
--R        |          |
--R        +0  0  0  0+
--RType: Polynomial(SquareMatrix(4,FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?+1)))
--E 7
)clear all
--S 8 of 28
D:=INT
--R
--R
--R   (1)  Integer
--R                                                                 Type: Domain
--E 8
--S 9 of 28 random input -- failure ok

M:=matrix([[random()$D for i in 1..4] for j in 1..4])
--R
--R
--R        +23884875  62211449  24992607  36817117+
--R        |                                      |
--R        |11791443  2792865   1578023   13067461|
--R   (2)  |                                      |
--R        |24115163  48682825  18166895  38340141|
--R        |                                      |
--R        +63446755  11508337  5309495   33821973+
--R                                                        Type: Matrix(Integer)
--E 9
--S 10 of 28 random input -- failure ok
p:=characteristicPolynomial(M,y)
--R
--R
--R   (3)
--R      4            3                    2
--R     y  - 78666608y  - 2034871330953280y  - 37379714246895929917440y
--R   +
--R     - 43330011013671754134127116288
--R                                                    Type: Polynomial(Integer)
--E 10
--S 11 of 28
SM:=SquareMatrix(4,D)
--R
--R
--R   (4)  SquareMatrix(4,Integer)
--R                                                                 Type: Domain
--E 11
--S 12 of 28 random input -- failure ok
sp:=map(z+->(squareMatrix$SM)diagonalMatrix([z,z,z,z]),p)
--R
--R
--R   (5)
--R          +- 78666608      0           0           0     +
--R          |                                              |
--R      4   |    0       - 78666608      0           0     | 3
--R     y  + |                                              |y
--R          |    0           0       - 78666608      0     |
--R          |                                              |
--R          +    0           0           0       - 78666608+
--R   +
--R   [[- 2034871330953280,0,0,0], [0,- 2034871330953280,0,0],
--R    [0,0,- 2034871330953280,0], [0,0,0,- 2034871330953280]]
--R    *
--R        2

--R       y
--R   +
--R   [[- 37379714246895929917440,0,0,0], [0,- 37379714246895929917440,0,0],
--R    [0,0,- 37379714246895929917440,0], [0,0,0,- 37379714246895929917440]]
--R    *
--R       y
--R   +
--R   [[- 43330011013671754134127116288,0,0,0],
--R    [0,- 43330011013671754134127116288,0,0],
--R    [0,0,- 43330011013671754134127116288,0],
--R    [0,0,0,- 43330011013671754134127116288]]
--R                                    Type: Polynomial(SquareMatrix(4,Integer))
--E 12
--S 13 of 28 random input -- failure ok
sm:=squareMatrix(M)$SM
--R
--R
--R        +23884875  62211449  24992607  36817117+
--R        |                                      |
--R        |11791443  2792865   1578023   13067461|
--R   (6)  |                                      |
--R        |24115163  48682825  18166895  38340141|
--R        |                                      |
--R        +63446755  11508337  5309495   33821973+
--R                                                Type: SquareMatrix(4,Integer)
--E 13
--S 14 of 28
eval(sp,y=sm)
--R
--R
--R        +0  0  0  0+
--R        |          |
--R        |0  0  0  0|
--R   (7)  |          |
--R        |0  0  0  0|
--R        |          |
--R        +0  0  0  0+
--R                                    Type: Polynomial(SquareMatrix(4,Integer))
--E 14
)clear all
--S 15 of 28
D:=PF 7
--R
--R
--R   (1)  PrimeField(7)
--R                                                                 Type: Domain

--E 15
--S 16 of 28 random input -- failure ok
M:=matrix([[random()$D for i in 1..4] for j in 1..4])
--R
--R
--R        +0  0  4  6+
--R        |          |
--R        |4  1  2  6|
--R   (2)  |          |
--R        |1  5  4  1|
--R        |          |
--R        +1  1  2  0+
--R                                                  Type: Matrix(PrimeField(7))
--E 16
--S 17 of 28 random input -- failure ok
p:=characteristicPolynomial(M,y)
--R
--R
--R         4     3     2
--R   (3)  y  + 2y  + 4y  + 4y + 1
--R                                              Type: Polynomial(PrimeField(7))
--E 17
--S 18 of 28
SM:=SquareMatrix(4,D)
--R
--R
--R   (4)  SquareMatrix(4,PrimeField(7))
--R                                                                 Type: Domain
--E 18
--S 19 of 28 random input -- failure ok
sp:=map(z+->(squareMatrix$SM)diagonalMatrix([z,z,z,z]),p)
--R
--R
--R             +2  0  0  0+     +4  0  0  0+     +4  0  0  0+    +1  0  0  0+
--R             |          |     |          |     |          |    |          |
--R         4   |0  2  0  0| 3   |0  4  0  0| 2   |0  4  0  0|    |0  1  0  0|
--R   (5)  y  + |          |y  + |          |y  + |          |y + |          |
--R             |0  0  2  0|     |0  0  4  0|     |0  0  4  0|    |0  0  1  0|
--R             |          |     |          |     |          |    |          |
--R             +0  0  0  2+     +0  0  0  4+     +0  0  0  4+    +0  0  0  1+
--R                              Type: Polynomial(SquareMatrix(4,PrimeField(7)))
--E 19
--S 20 of 28 random input -- failure ok
sm:=squareMatrix(M)$SM
--R

--R
--R        +0  0  4  6+
--R        |          |
--R        |4  1  2  6|
--R   (6)  |          |
--R        |1  5  4  1|
--R        |          |
--R        +1  1  2  0+
--R                                          Type: SquareMatrix(4,PrimeField(7))
--E 20
--S 21 of 28
eval(sp,y=sm)
--R
--R
--R        +0  0  0  0+
--R        |          |
--R        |0  0  0  0|
--R   (7)  |          |
--R        |0  0  0  0|
--R        |          |
--R        +0  0  0  0+
--R                              Type: Polynomial(SquareMatrix(4,PrimeField(7)))
--E 21
)clear all
--S 22 of 28
D:=FF(2,4)
--R
--R
--R   (1)  FiniteField(2,4)
--R                                                                 Type: Domain
--E 22
--S 23 of 28 random input -- failure ok
M:=matrix([[random()$D for i in 1..4] for j in 1..4])
--R
--R
--R        +                      2            2       3     2         +
--I        |        %A          %A  + %A     %A      %A  + %A  + %A + 1|
--R        |                                                           |
--R        |  3     2             3     2    3              3          |
--I        |%A  + %A  + %A + 1  %A  + %A   %A  + %A       %A  + %A     |
--R   (2)  |                                                           |
--R        |  3     2             3          3                         |
--I        |%A  + %A  + %A + 1  %A  + %A   %A  + %A          %A        |
--R        |                                                           |
--R        |     3                 2           2         3     2       |
--I        +   %A  + %A + 1      %A  + 1     %A        %A  + %A  + %A  +

--R                                               Type: Matrix(FiniteField(2,4))
--E 23
--S 24 of 28 random input -- failure ok
p:=characteristicPolynomial(M,y)
--R
--R
--R         4      3       3      3       2         3
--I   (3)  y  + (%A  + %A)y  + (%A  + %A)y  + y + %A  + 1
--R                                           Type: Polynomial(FiniteField(2,4))
--E 24
--S 25 of 28
SM:=SquareMatrix(4,D)
--R
--R
--R   (4)  SquareMatrix(4,FiniteField(2,4))
--R                                                                 Type: Domain
--E 25
--S 26 of 28 random input -- failure ok
sp:=map(z+->(squareMatrix$SM)diagonalMatrix([z,z,z,z]),p)
--R
--R
--R   (5)
--R          +  3                                   +
--I          |%A  + %A     0         0         0    |
--R          |                                      |
--R          |            3                         |
--I      4   |   0      %A  + %A     0         0    | 3
--R     y  + |                                      |y
--R          |                      3               |
--I          |   0         0      %A  + %A     0    |
--R          |                                      |
--R          |                                3     |
--I          +   0         0         0      %A  + %A+
--R   +
--R     +  3                                   +
--I     |%A  + %A     0         0         0    |
--R     |                                      |
--R     |            3                         |
--I     |   0      %A  + %A     0         0    | 2
--R     |                                      |y  + y
--R     |                      3               |
--I     |   0         0      %A  + %A     0    |
--R     |                                      |
--R     |                                3     |
--I     +   0         0         0      %A  + %A+
--R   +
--R     +  3                               +

--I     |%A  + 1     0        0        0   |
--R     |                                  |
--R     |           3                      |
--I     |   0     %A  + 1     0        0   |
--R     |                                  |
--R     |                    3             |
--I     |   0        0     %A  + 1     0   |
--R     |                                  |
--R     |                             3    |
--I     +   0        0        0     %A  + 1+
--R                           Type: Polynomial(SquareMatrix(4,FiniteField(2,4)))
--E 26
--S 27 of 28 random input -- failure ok
sm:=squareMatrix(M)$SM
--R
--R
--R        +                      2            2       3     2         +
--I        |        %A          %A  + %A     %A      %A  + %A  + %A + 1|
--R        |                                                           |
--R        |  3     2             3     2    3              3          |
--I        |%A  + %A  + %A + 1  %A  + %A   %A  + %A       %A  + %A     |
--R   (6)  |                                                           |
--R        |  3     2             3          3                         |
--I        |%A  + %A  + %A + 1  %A  + %A   %A  + %A          %A        |
--R        |                                                           |
--R        |     3                 2           2         3     2       |
--I        +   %A  + %A + 1      %A  + 1     %A        %A  + %A  + %A  +
--R                                       Type: SquareMatrix(4,FiniteField(2,4))
--E 27
--S 28 of 28
eval(sp,y=sm)
--R
--R
--R        +0  0  0  0+
--R        |          |
--R        |0  0  0  0|
--R   (7)  |          |
--R        |0  0  0  0|
--R        |          |
--R        +0  0  0  0+
--R                           Type: Polynomial(SquareMatrix(4,FiniteField(2,4)))
--E 28
)spool
)lisp (bye)

———-

References

[1] http://en.wikipedia.org/wiki/Cayley-Hamilton theorem