Re: The companion matrix of a polynomial.

[Hongyi Zhao <hongyi.zhao@gmail.com>]

On Sun, Jan 15, 2023 at 8:45 PM Hongyi Zhao <hongyi.zhao@gmail.com> wrote:
>
> On Sun, Jan 15, 2023 at 5:19 PM Bill Allombert
> <Bill.Allombert@math.u-bordeaux.fr> wrote:
> >
> > On Sun, Jan 15, 2023 at 09:12:07AM +0800, Hongyi Zhao wrote:
> > > On Sat, Jan 14, 2023 at 9:58 PM Charles Greathouse
> > > <crgreathouse@gmail.com> wrote:
> > > >
> > > > I'm not at all sure what you're doing here. The GAP source
> > > > https://github.com/gap-system/gap/blob/3d47e2bc40869ea1b232a0a658d47b1897880fec/lib/upolyirr.gi#L82
> > > > seems to require that the input to CompanionMat be a polynomial or a list of coefficients of a polynomial. It doesn't seem like it can do anything meaningful to a matrix.
> > >
> > > I want to get the companion matrix of matrix A in GP, which can be
> > > generated in GAP, as shown below:
> >
> > > gap> A:=[[-1,3,-1,0,-2,0,0,-2],
> > > > [-1,-1,1,1,-2,-1,0,-1],
> > > > [-2,-6,4,3,-8,-4,-2,1],
> > > > [-1,8,-3,-1,5,2,3,-3],
> > > > [0,0,0,0,0,0,0,1],
> > > > [0,0,0,0,-1,0,0,0],
> > > > [1,0,0,0,2,0,0,0],
> > > > [0,0,0,0,4,0,1,0]];;
> > > gap> P:=RationalCanonicalFormTransform(A);;
> > > gap> C:=A^P;
> > > [ [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 1, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0,
> > > 0, 0, 0, 0, -1 ], [ 0, 0, 1, 0, 0, 0, 0, -4 ],
> > >   [ 0, 0, 0, 1, 0, 0, 0, -4 ], [ 0, 0, 0, 0, 1, 0, 0, 2 ], [ 0, 0, 0,
> > > 0, 0, 1, 0, 4 ], [ 0, 0, 0, 0, 0, 0, 1, 0 ] ]
> >
> > This is the rational canonical form (aka the Frobenius form), not the companion matrix.
>
> There are the following very similar concepts:
>
> https://encyclopediaofmath.org/wiki/Frobenius_matrix
> https://en.wikipedia.org/wiki/Companion_matrix
>
> It seems to me that the explanation and form given in the links above
> are no different from Frobenius form.
>
> > In GP, it is matfrobenius. There is a flag to the the transform. Read the doc.
>
> I calculated it as follows:
>
> ? M=[ -1,3,-1,0,-2,0,0,-2;
> -1,-1,1,1,-2,-1,0,-1;-2,-6,4,3,-8,-4,-2,1;-1,8,-3,-1,5,2,3,-3;0,0,0,0,0,0,0,1;0,0,0,0,-1,0,0,0;1,0,0,0,2,0,0,0;0,0,0,0,4,0,1,0];
>
> ? [F,B]=matfrobenius(A,2);
> ? M==B^-1*F*B
> %14 = 1
> ? F
> %15 =
> [0 0 0 0 0 -1 0 0]
>
> [1 0 0 0 0 -4 0 0]
>
> [0 1 0 0 0 -4 0 0]
>
> [0 0 1 0 0  2 0 0]
>
> [0 0 0 1 0  4 0 0]
>
> [0 0 0 0 1  0 0 0]
>
> [0 0 0 0 0  0 0 1]
>
> [0 0 0 0 0  0 1 1]
>
>
> As you can see, the form above is not exactly the same as the result
> of GAP and I tried to verify the isomorphism between them in GAP, but
> failed:
>
> gap> P:=RationalCanonicalFormTransform(A);;
> gap> C:=A^P;
> [ [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 1, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0,
> 0, 0, 0, 0, -1 ], [ 0, 0, 1, 0, 0, 0, 0, -4 ],
>   [ 0, 0, 0, 1, 0, 0, 0, -4 ], [ 0, 0, 0, 0, 1, 0, 0, 2 ], [ 0, 0, 0,
> 0, 0, 1, 0, 4 ], [ 0, 0, 0, 0, 0, 0, 1, 0 ] ]
> gap> F:=[[0,0,0,0,0,-1,0,0],
> > [1,0,0,0,0,-4,0,0],
> > [0,1,0,0,0,-4,0,0],
> > [0,0,1,0,0,,2,0,0],
> > [0,0,0,1,0,,4,0,0],
> > [0,0,0,0,1,,0,0,0],
> > [0,0,0,0,0,,0,0,1],
> > [0,0,0,0,0,,0,1,1]];
> [ [ 0, 0, 0, 0, 0, -1, 0, 0 ], [ 1, 0, 0, 0, 0, -4, 0, 0 ], [ 0, 1, 0,
> 0, 0, -4, 0, 0 ], [ 0, 0, 1, 0, 0,, 2, 0, 0 ],
>   [ 0, 0, 0, 1, 0,, 4, 0, 0 ], [ 0, 0, 0, 0, 1,, 0, 0, 0 ], [ 0, 0, 0,
> 0, 0,, 0, 0, 1 ], [ 0, 0, 0, 0, 0,, 0, 1, 1 ] ]
> gap> TransformingPermutations(F,C);
> Error, no method found! For debugging hints type ?Recovery from NoMethodFound
> Error, no 1st choice method found for `TransformingPermutations' on 2
> arguments at /home/werner/Public/repo/github.com/gap-system/gap.git/lib/methsel2.g:249
> called from
> <function "HANDLE_METHOD_NOT_FOUND">( <arguments> )
>  called from read-eval loop at *stdin*:36
> type 'quit;' to quit to outer loop
> brk>

Sorry, due to typo, there are several redundant commas in matrix F in
my above test. In fact, they are isomorphic:

gap> A:=[[-1,3,-1,0,-2,0,0,-2],
> [-1,-1,1,1,-2,-1,0,-1],
> [-2,-6,4,3,-8,-4,-2,1],
> [-1,8,-3,-1,5,2,3,-3],
> [0,0,0,0,0,0,0,1],
> [0,0,0,0,-1,0,0,0],
> [1,0,0,0,2,0,0,0],
> [0,0,0,0,4,0,1,0]];;
gap> P:=RationalCanonicalFormTransform(A);;
gap> C:=A^P;
[ [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 1, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0,
0, 0, 0, 0, -1 ], [ 0, 0, 1, 0, 0, 0, 0, -4 ],
  [ 0, 0, 0, 1, 0, 0, 0, -4 ], [ 0, 0, 0, 0, 1, 0, 0, 2 ], [ 0, 0, 0,
0, 0, 1, 0, 4 ], [ 0, 0, 0, 0, 0, 0, 1, 0 ] ]
gap> F:=[[0,0,0,0,0,-1,0,0],
> [1,0,0,0,0,-4,0,0],
> [0,1,0,0,0,-4,0,0],
> [0,0,1,0,0,2,0,0],
> [0,0,0,1,0,4,0,0],
> [0,0,0,0,1,0,0,0],
> [0,0,0,0,0,0,0,1],
> [0,0,0,0,0,0,1,1]];;
gap> TransformingPermutations(F,C);
rec( columns := (1,3,5,7)(2,4,6,8), group := Group([ (3,4) ]), rows :=
(1,3,5,7)(2,4,6,8) )

>
> Any tips for this problem?
>
> > Cheers,
> > Bill.
>
> Best,
> Zhao