Cyclic Subspace Decomposition

The purpose of these examples is to illustrate the concept of minimal annihilating polynomials (with respect to a given map defined by a matrix) and the main theorem that guarantees the decomposition of a given space into the direct sum of cyclic invariant subspaces

Am0 = {{2,0,0,0},{0,2,0,0},{0,0,2,0},{0,0,0,2}}; Am0//MatrixForm

the MAP of whole space (w.r.t Am0) is (-2 + lam)

Am0-2 IdentityMatrix[4]

Am1 = {{2,0,0,0},{0,2,0,0},{0,0,2,1},{0,0,0,2}}; Am1//MatrixForm

the MAP of whole space (w.r.t. Am1) is (-2 + lam)^2

Am1.Am1 - 4 Am1 + 4 IdentityMatrix[4]

Am2 = {{2,0,0,0},{0,2,1,1},{0,0,2,1},{0,0,0,2}}; Am2//MatrixForm

the MAP of whole space (w.r.t. Am2) is (-2 + lam)^3

Expand[(-2+lam)^3]

Am2.Am2.Am2-6Am2.Am2+12 Am2 - 8 IdentityMatrix[4]

notice that the MAPs are not visible in the eigenvalues only, since all three matrices Am0, Am1, Am2 all share the same four eigenvalues + 2

Eigenvalues[Am0]

Eigenvalues[Am1]

Eigenvalues[Am2]

interesting is the computation of the eigenvectors

Eigenvectors[Am0]

Eigenvectors[Am1]

Eigenvectors[Am2]

the appearance of the null vector in the list of eigenvectors indicate the existence of cyclic subspaces of dimension greater than one associated with the single eigenvalue + 2

Let us define for convenience the four canonical basis vectors of Rn

e1 = {1,0,0,0};
e2 = {0,1,0,0};
e3 = {0,0,1,0};
e4 = {0,0,0,1};

The cyclic structure is clearly visible in the original form of the matrices Am0, Am1, Am2.
  We will now hide this structure through performing a change of basis using the full rank square matrix P

P = {{1,2,3,4},{17,6,7,8},{9,33,11,12},{12,14,27,16}}

Inverse[P].Am0.P

A1=Inverse[P].Am1.P

A2 = Inverse[P].Am2.P

As mentioned earlier, it is quite straightforward to pinpoint the vectors having the smallest MAP prior to the change of basis. For example, with Am1 :

(-2 IdentityMatrix[4] + Am1).e1

(-2 IdentityMatrix[4] + Am1).e2

(-2 IdentityMatrix[4] + Am1).e3

(+4 IdentityMatrix[4] - 4 Am1 +Am1.Am1).e4

(+4 IdentityMatrix[4] - 4 Am1 +Am1.Am1)

Another way of checking cyclicity, is to sucessively compute the annihilator (null space computation) of sufficiently many iterates of the A map, and computing the number of generators in the null space operator (number of generators of the annihilator ).  In the following computation we iteratively compute up to 3 times the iterate of the A map (there is no need to iterate further since the dimension of the whole space is R4). In the original coordinates (prior to change of basis with P) one notices the single dimensional cyclic subspaces associated with (respectively) e1 (first cyclic subspace of dim 1), e2 (second cyclic subspace of dim 1) and e2 (first cyclic subspac of dim 1):

Length[NullSpace[NestList[Am1.#&,#,3]]]& /@ {e1,e2,e3,e4}

Indeed, this can be deduced through the appearance of the number 3 (computational result just above) which indicates the existence of an annihilator of dimension 3. Therefore, the space is cyclic of dimension 1. However, once the change of basis is undertaken, the cyclic generators of the subspaces of dimension 1 are not easy to pinpoint, since each original canonical basis vectors (e1 or e2 or e3 or e4) are all generators of cyclic subspaces of dimension 2:

Length[NullSpace[NestList[A1.#&,#,3]]]& /@ {e1,e2,e3,e4}

Indeed, only the number 2 appears in the above list. Similar problems appear when going from Am2 to A2

Length[NullSpace[NestList[Am2.#&,#,3]]]& /@ {e1,e2,e3,e4}

And in the transformed basis, the A2 map induce that any original canonical basis vector is cyclic of order 3 (generators of the annihilator are single dimensional).

Length[NullSpace[NestList[A2.#&,#,3]]]& /@ {e1,e2,e3,e4}

What this means (using a not very rigorous justification) is that through randomly choosing an arbitrary vector, we will almost invariably end up with a vector sharing the highest cyclicity index. Let us come back to the original MAP of the whole space (w.r.t. Am1)

CoefficientList[Expand[(-2+lam)^2],lam]. NestList[Am1.#&,IdentityMatrix[4],2]

And we easily cross - check that it remains the MAP even after change of coordinates (i.e. MAP of whole space (w.r.t A1).

CoefficientList[Expand[(-2+lam)^3],lam]. NestList[A1.#&,IdentityMatrix[4],3]

One can compute this in a more flexible way using a pure function

CoefficientList[Expand[(-2+lam)^#],lam]. NestList[Am1.#&,IdentityMatrix[4],#]& @@ {2}

So that it is easily extendible to Am2 for which MAP is (-2 + lam)^3

CoefficientList[Expand[(-2+lam)^#],lam]. NestList[Am2.#&,IdentityMatrix[4],#]& @@ {3}

Which also is not affected by the change of basis

CoefficientList[Expand[(-2+lam)^#],lam]. NestList[A2.#&,IdentityMatrix[4],#]& @@ {3}

Thus, let us go back and study more closely A1

A1

e1

e1 et A.e1  generates the first cyclic subspace. Let us compute the minimal polynomial of the whole space modulo this cyclic subspace.

NullSpace[{e1,A1.e1}]

NullSpace[{e1,A1.e1,e2}]

NullSpace[{e1,A1.e1,e2,A1.e2}]

We see that A1.e2 is dependent on e2 modulo span {e1, A.e1} : This is deduced from the fact that the number of annihilators does not decrease between the annihilator of span {e1, A1.e1, e2} and the annihilator of span {e1, A1.e1, e2, A1.e2}.

albe=Solve[Thread[al e2 + A1.e2 + be e1 + gam A1.e1 == {0,0,0,0}],{al,be,gam}]

We see that the minimal polynomial relative to span {e1, A1.e1} of e2 is (-2 + lam). Let us proceed we the two additionnal vectors e3 and e4 so as to be exhaustive.

NullSpace[{e1,A1.e1,e3}]

NullSpace[{e1,A1.e1,e3,A1.e3}]

albe3=Solve[Thread[al e3 + A1.e3 + be e1 + gam A1.e1 == {0,0,0,0}],{al,be,gam}]

The same conclusion as the previous one holds for the MAP of e3.

NullSpace[{e1,A1.e1,e4}]

NullSpace[{e1,A1.e1,e4,A1.e4}]

albe4 =Solve[Thread[al e4 + A1.e4 + be e1 + gam A1.e1 == {0,0,0,0}],{al,be,gam}]

The same conclusion (as those previously mentioned) holds again for the MAP of e4. Now, because the three vectors e2, e3 , e4 are both linearly independent from each other, and obviously linearly independent from e1, the span {e2, e3, e4} contains the span of the complementary space from {e1, A1.e1}. Therefore the map of the whole space relative to span {e1, A1.e1} is (-2 + lam), since it is simultaneously the MAP of the vectors e2, e3 and e4.  We have the following factorisation (MAP of Rn) = (RMAP of Rn mod {e1, A1.e1}) (-2 + lam). Hence, define chi = (-2 + lam). Recall that e1 is a vector having MAP equal to the MAP of the whole space Rn

-2 e2 + A1.e2

-(be e1 + gam A1.e1) /. albe[[1]]

pol2 = -be - gam lam /. albe[[1]]

The theory shows that chi must be a multiple of pol2 :

Simplify[(-2 +lam)7/6 - pol2]

vect1 = e1

We then use this multiple to define a new vector as combination of e2 and e1.

vect2 = e2 - 7/6 e1

This vect2 has both RMAP and absolute MAP equal to (-2 + lam), indeed

A1.vect2-2 vect2

Let us find the two other cyclic vectors of order 1. The first one is associated with e3:

-2 e3 + A1.e3

-(be e1 + gam A1.e1) /. albe3[[1]]

pol3 = -be - gam lam /. albe3[[1]]

Simplify[(-2 +lam)9/4 - pol3]

vect3 = e3 - 9/4 e1

A1.vect3-2vect3

the second one is associated with e4

-2 e4 + A1.e4

-(be e1 + gam A1.e1) /. albe4[[1]]

pol4 = -be - gam lam /. albe4[[1]]

Simplify[(-2 +lam)4/3 - pol4]

vect4 = e4 - 4/3 e1

A1.vect4-2vect4

hence we have many different decomposition according to our cyclic subspaces. The MAP is (-2 + lam)^2 (associated with vect1) and the second polynomial is (-2 + lam) (associated with vect2, vect3 and vect4 and any linear combination of these vectors). Therefore, here are some generating vectors according to the cyclic decomposition obtained:

Det[{vect1,A1.vect1,vect2,vect3}]

Det[{vect1,A1.vect1,vect2,vect4}]

Det[{vect1,A1.vect1,vect3,vect4}]

A1.A1.vect1 - 4 A1.vect1 + 4 vect1

A1.vect2-2vect2

A1.vect3-2vect3

A1.vect4-2vect4