Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Evaluating a polynomial on a matrix; matrix computations over a finite field

• To: mathgroup at smc.vnet.net
• Subject: [mg43139] Re: [mg43123] Evaluating a polynomial on a matrix; matrix computations over a finite field
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 14 Aug 2003 05:07:55 -0400 (EDT)
• References: <200308131149.HAA28291@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Lot-o-fun wrote:
> 
> How do I compute p(A), where p is a polynomial and A is a matrix?
> 
> For example, if
> 
> p[x_] := x^2 - 3x + 2
> 
> and
> 
> A = {{1,2},{3,4}}, then I want to compute
> 
> p(A) = A^2 - 3A + 2I = {{6,4},{6,12}}
> 
> Is there some way of doing this?
> 
> I'd also like to be able to do various matrix computations over finite
> fields.  For example, I'd like to compute the minimal polynomial of a
> matrix over Z_2.
> 
> Thanks!
> 
> -Lotofun


For the question of computing a minimal polynomial, offhand I can think
of two methods. One would be to compute the characterisctic polynomial,
then, if it is not square-free, check whether the matrix polynomial
vanishes on any proper factors thereof that include every square free
factor at least to power 1. A generally more efficient method is to
compute null spaces of matrices formed from "flattened" matrix powers.
Below is a simple example illustrating this latter approach.

SeedRandom[11111]
mod = 19;
mat = Table[Random[Integer,{0,mod-1}], {6}, {6}];
matpowers = Mod[Table[MatrixPower[mat,j], {j,0,6}], mod];

Note that one can compute matpowers more efficiently by interleaving Mod
with powering, but that's not important for this example.

To get coefficients for a polynomial that vanishes on mat, we find a
null vector for the full list of matrix powers.

In[28]:= nullvec = First[NullSpace[Transpose[Map[Flatten,matpowers]],
  Modulus->mod]]
Out[28]= {13, 17, 12, 0, 12, 8, 1}

We check that there is no null space if we take fewer powers of mat.

In[29]:= nulls2 = NullSpace[Transpose[Map[Flatten,Take[matpowers,6]]],
  Modulus->mod]
Out[29]= {}

We also check that we really obtained coefficients for a polynomial that
annihilates mat.

In[30]:= Max[Abs[Mod[nullvec . matpowers, mod]]]
Out[30]= 0

So your minimal polynomial, in the variable x, is

In[37]:= InputForm[nullvec . x^Range[0,6]]
Out[37]//InputForm= 13 + 17*x + 12*x^2 + 12*x^4 + 8*x^5 + x^6

Note that this is what we get from the roundabout method of computing
the characteristic polynomial non-modularly (because we do not support a
modulus option for this, possibly an oversight on our part), and then
reducing by the modulus.

In[45]:= InputForm[charpoly = PolynomialMod[
  CharacteristicPolynomial[mat, x], mod]]
Out[45]//InputForm= 13 + 17*x + 12*x^2 + 12*x^4 + 8*x^5 + x^6


Daniel Lichtblau
Wolfram Research

• References:
  • Evaluating a polynomial on a matrix; matrix computations over a finite field
    • From: Lot-o-fun <lotofun@hotmail.com>