Re: computing nullspace
- To: mathgroup at smc.vnet.net
- Subject: [mg34163] Re: [mg34105] computing nullspace
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 7 May 2002 03:54:01 -0400 (EDT)
- References: <200205040828.EAA01692@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Chris Krook wrote:
>
> Given a matrix M, where all entries come from the ring S=Z[X]/(f(X)) where
> f(X) is an irreducible polynomial, is it possible in mathematica to compute
> the nullspace of this matrix in this ring S. I can't find this anywhere.
>
> thanks, Chris
I'll illustrate one way to do this using a 2x3 matrix mat with entries
m[j,k]. We will call the polynomial modulus poly.
Elements in the null space satisfy
m[1,1]*x1 + m[1,2]*x2 + m[1,3]*x3 + poly*k1 + 0*k2 == 0
m[2,1]*x1 + m[2,2]*x2 + m[2,3]*x3 + 0*k1 + poly*k2 == 0
where the null vector is {x1,x2,x3} and k1 and k2 are auxiliary
polynomials that are used to allow multiples of the modulus poly. So we
have an "augmented" null system in 5 variables {x1,x2,x3,k1,k2}. We'll
solve it and then post-process to obtain null vectors of interest.
Here is a concrete example.
mat = {{x^3-3*x+1, x^2+5*x+2, x^3-2*x+2}, {x^2-4, x^3+x+1, x^2+5*x-2}};
poly = x^4+2*x^3+5*x-3;
We form the augmented matrix corresponding to the equations above.
mat2 = Transpose[Join[Transpose[mat], poly*IdentityMatrix[Length[mat]]]]
We find the null space.
In[23]:= InputForm[nulls = NullSpace[mat2]]
Out[23]//InputForm=
{{-((6 + 5*x - 22*x^2 - 9*x^3 - 12*x^4 - 7*x^5 - x^6)/
(9 + 18*x - x^2 - 3*x^3 - 3*x^4 + x^6)),
-(((1 - 3*x + x^3)*(-3 + 5*x + 2*x^3 + x^4))/(9 + 18*x - x^2 - 3*x^3 -
3*x^4 + x^6)), 0, 0, 1},
{-(((1 + x + x^3)*(-3 + 5*x + 2*x^3 + x^4))/(9 + 18*x - x^2 - 3*x^3 -
3*x^4 + x^6)), ((-4 + x^2)*(-3 + 5*x + 2*x^3 + x^4))/
(9 + 18*x - x^2 - 3*x^3 - 3*x^4 + x^6), 0, 1, 0},
{-((6 - 27*x^2 - 7*x^3 - 2*x^4 + x^6)/(9 + 18*x - x^2 - 3*x^3 - 3*x^4 +
x^6)), -((6 + 3*x - 16*x^2 + x^3 + 5*x^4)/(9 + 18*x - x^2 - 3*x^3 -
3*x^4 + x^6)), 1, 0, 0}}
This looks to have too many vectors and also it contains denominators.
First we will remove those denominators.
vectorDenominator[vec_List] :=
PolynomialLCM[Apply[Sequence,Map[Denominator,vec]]]
In[25]:= InputForm[fracfreenulls = Map[# * vectorDenominator[#] &,
nulls]]
Out[25]//InputForm=
{{-6 - 5*x + 22*x^2 + 9*x^3 + 12*x^4 + 7*x^5 + x^6,
-((1 - 3*x + x^3)*(-3 + 5*x + 2*x^3 + x^4)), 0, 0,
9 + 18*x - x^2 - 3*x^3 - 3*x^4 + x^6},
{-((1 + x + x^3)*(-3 + 5*x + 2*x^3 + x^4)),
(-4 + x^2)*(-3 + 5*x + 2*x^3 + x^4), 0, 9 + 18*x - x^2 - 3*x^3 - 3*x^4
+
x^6, 0}, {-6 + 27*x^2 + 7*x^3 + 2*x^4 - x^6,
-6 - 3*x + 16*x^2 - x^3 - 5*x^4, 9 + 18*x - x^2 - 3*x^3 - 3*x^4 + x^6,
0,
0}}
Next we mod out by our polynomial.
In[26]:= InputForm[modfracfreenulls = PolynomialMod[fracfreenulls,
poly]]
Out[26]//InputForm=
{{0, 0, 0, 0, 12 + 7*x + 12*x^2 - 10*x^3},
{0, 0, 0, 12 + 7*x + 12*x^2 - 10*x^3, 0}, {-12 + 16*x + 14*x^2 +
16*x^3,
-21 + 22*x + 16*x^2 + 9*x^3, 12 + 7*x + 12*x^2 - 10*x^3, 0, 0}}
We see that the first two "null" vectors were trivial insofar as they do
not involve the original matrix parameters. We'll use appropriate code
to remove such.
In[28]:= InputForm[Select[modfracfreenulls,
(#[[1]]=!=0 || #[[2]]=!=0 || #[[3]]=!=0)&]]
Out[28]//InputForm=
{{-12 + 16*x + 14*x^2 + 16*x^3, -21 + 22*x + 16*x^2 + 9*x^3,
12 + 7*x + 12*x^2 - 10*x^3, 0, 0}}
We have our single null vector. I should remark that for generic systems
one need not use the augmented matrix; it generally suffices to find the
null space over Q(x) and clear denominators. It is only when there are
null vectors for the homomorphic image that are not null over Q(x) that
the unaugmented approach can fail. Even then I think it may work fine if
one first mods by poly, though I am not entirely sure about this
offhand.
Daniel Lichtblau
Wolfram Research
- References:
- computing nullspace
- From: "Chris Krook" <c.krook@student.tue.nl>
- computing nullspace