Is there a way to calculate the Rational Canonical Form of an $n\times n$ integer matrix using Mathematica?
I have been perusing the documentation and web, but nothing so far.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
I found the problem. What is needed is to factor the CharacteristicPolynomial by the MatrixMinimalPolynomial continously in order to obtain all minimal polynomials.
I did not know how to do that using one of the polynomial functions in Mathematica, so I wrote a function to do it.
Result
This shows test matrices. The left side is the matrix, and the right side is the matrix rational form. This function called rationalMatrixForm requires 2 helper functions: companionMatrix and MatrixMinimalPolynomial
This is not optimal function by any means (uses AppendTo for example), and I am sure it can be improved, but first I wanted to make sure it is correct. I tested it on number of matrices and the results agrees with wikipdia example and mupad results. If you find a bug in it, please let me know.
rationalMatrixForm[{{2, -2, 14}, {0, 3, -7}, {0, 0, 2}}]
Grid[{MatrixForm[#], MatrixForm@rationalMatrixForm[#]} & /@ tests, Frame -> All]
Code
CompanionMatrix[p_, x_] := Module[
{n, w = CoefficientList[p, x]},
w = -w/Last[w];
n = Length[w] - 1;
SparseArray[{{i_, n} :> w[[i]], {i_, j_} /; i == j + 1 -> 1}, {n,
n}]]
MatrixMinimalPolynomial[a_List?MatrixQ, x_] :=
Module[{i, n = 1, qu = {},
mnm = {Flatten[IdentityMatrix[Length[a]]]}},
While[Length[qu] == 0, AppendTo[mnm, Flatten[MatrixPower[a, n]]];
qu = NullSpace[Transpose[mnm]];
n++];
First[qu].Table[x^i, {i, 0, n - 1}]]
and
rationalMatrixForm[a_?(MatrixQ[#, NumericQ] &)] := Module[(*version 8/24/13 2PM*)
{p, q, min, c = {}, moreFactors = True, z, x},
p = CharacteristicPolynomial[a, x];
min = MatrixMinimalPolynomial[a, x];
While[moreFactors,
q = PolynomialQuotient[p, min, x];
If[q === 0,
moreFactors = False;
If[Not[FreeQ[p, x]],
z = CompanionMatrix[p, x];
AppendTo[c, z]
],
z = CompanionMatrix[min, x];
AppendTo[c, z];
p = q
] (* if *)
]; (*end WHILE more factorization needed*)
SparseArray[Band[{1, 1}] -> c]
]
test matrices
tests = {
{{2, -2, 14}, {0, 3, -7}, {0, 0, 2}},
{{3, 4, 0}, {-1, -3, -2}, {1, 2, 1}},
{{-2, -1, -2, -1, 1, 0}, {-2, -1, -2, -1, 1, 1}, {2, 1, 2, 1, 0,
0}, {2, 1, 0, 1, -3, -1}, {-2, 0, -2, 0, 0, 0}, {2, -2, 0, 0, 0,
0}},
{{0, -4, 85}, {1, 4, -30}, {0, 0, 3}},
{{2, -2, 14, 5, 6, 7}, {0, 3, -7, 9, 20, 33}, {0, 0, 2, 9, 0,
3}, {2, -2, 14, 5, -8, 7}, {2, 2, 14, 23, 6, 7}, {2, 2, 14, 23,
6, 70}}
};
-
$\begingroup$ Very nice, however produces an incorrect result for mat = {{2, -2, 14}, {0, 3, -7}, {0, 0, 2}}, but correct for mat = {{0, -4, 85}, {1, 4, -30}, {0, 0, 3}}. These have same characteristic polynomial, but different rational canonical forms. Regards $\endgroup$– AmzotiAug 23, 2013 at 5:08
-
$\begingroup$ @Nasser: Are you saying no way to easily fix? $\endgroup$– AmzotiAug 23, 2013 at 5:19
-
$\begingroup$ @Nasser: It might have to do with the fact that the first matrix in my comment has a minimal polynomial $(x-2)(x-3)$ while the second has $(x-2)^2(x-3)$, even though they both have the same characteristic polynomial. $\endgroup$– AmzotiAug 23, 2013 at 5:23
-
$\begingroup$ @Nasser: Is there a way to print $P$, as in $P^{-1}AP=r$. In other words, you found $r$, but is it possible to also provide $P$? $\endgroup$– AmzotiAug 23, 2013 at 5:25
-
1$\begingroup$ For all future readers, this code is NOT strictly correct. For example, the matrix {{0,1,1,1},{1,0,1,1},{1,1,0,1},{1,1,1,0}} has eigenvalues with $(\lambda-3)(\lambda+1)^3$. This code gives the rational canonical form as {{0, 3, 0, 0}, {1, 2, 0, 0}, {0, 0, 0, 3}, {0, 0, 1, 2}}, which has eigenvalues $(\lambda-3)^2(\lambda+1)^2$, so the two matrices can't be similar. The correct RCF would be {{0, 3, 0, 0}, {1, 2, 0, 0}, {0, 0, -1, 0}, {0, 0, 0,-1}}. $\endgroup$– user273Feb 15, 2017 at 18:25