Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There appear to be a number of rational canonical forms. The best thing about standards is how many there are to choose from. However, the standard I choose seems to have a centralizer that is difficult to describe.

1) Is there a reference that chooses a specific (hopefully pretty) rational canonical form, and computes its (hopefully pretty) centralizer?

Alternatively,

2) Is there a pretty description of the centralizer of my choice of canonical form?

Matrices are over commutative (usually finite prime) fields.

Every matrix is similar to a direct sum of matrices whose minimal polynomial is of the form irr ^ pow, for some irreducible polynomial irr and some positive integer pow. While there is some disagreement on how to organize this, a common idea is to have canonical forms associated to pairs [ irr, pow ], (the other being to group coprime irr together: is it Z/2Z × Z/3Z or is it Z/6Z? we choose Z/2Z × Z/3Z).

So given a pair [ irr, pow ], I have seen two main ways to associate the canonical block: either take "the" companion matrix of irr^pow, or take a block diagonal matrix with pow blocks equal to the companion matrix of irr, and then fill in 1s on the sub/sup diagonal you used for the companion matrix. The former more clearly lays out an indecomposable direct decomposition, but it hides a composition series. The latter more subtly lays out the direct sum decomposition, but makes the composition series very clear. Both are quite pretty. In case irr has degree 1, then the latter is a Jordan block, and the former is not.

So I chose the latter. For instance, if irr = x2−x−1 is irreducible and pow = 3, then we get the block B:

`B = $\begin{bmatrix} .&1&.&.&.&.\\% 1&1&1&.&.&.\\% .&.&.&1&.&.\\% .&.&1&1&1&.\\% .&.&.&.&.&1\\% .&.&.&.&1&1\\% \end{bmatrix}$

If α is a root of x2−x−1, then I expected this guy to be the blow up of b:

`b = $\begin{bmatrix} \alpha&1&.\\ .&\alpha&1\\ .&.&\alpha\\ \end{bmatrix}$

and so I expected any scalar matrices (blown up) to be in the centralizer of B, since they are in the centralizer of b. In other words, the matrix a:

`a = $\begin{bmatrix} \alpha&.&.\\ .&\alpha&.\\ .&.&\alpha\\ \end{bmatrix}$

centralizes b, so I expected the matrix A:

`A = $\begin{bmatrix} .&1&.&.&.&.\\% 1&1&.&.&.&.\\% .&.&.&1&.&.\\% .&.&1&1&.&.\\% .&.&.&.&.&1\\% .&.&.&.&1&1\\% \end{bmatrix}$

to centralize B, but of course AB ≠ BA. For any particular B, one can just solve a bunch of equations, but at least to me the solutions do not seem easy to describe algorithmically. I worry that we might have wanted the slightly uglier canonical form that is actually the blowup of b:

$\tilde B = \begin{bmatrix} .&1&1&.&.&.\\% 1&1&.&1&.&.\\% .&.&.&1&1&.\\% .&.&1&1&.&1\\% .&.&.&.&.&1\\% .&.&.&.&1&1\\% \end{bmatrix}$

However, I have not found this form listed in any reference, and I'd like to have a reasonable reference to point to to justify my choices (especially if they choose uglier, less sparse matrices).

1′) What reference uses $\tilde B$ as the rational canonical form of B?

Or alternatively:

2′) Where are the "scalars" in the centralizer of B?

I'd much prefer to use B, but if I cannot even see the scalar matrices in this form, then it seems like a very poor form indeed.

For those curious the other leading canonical form of B is:

$\hat B = \begin{bmatrix} .&1&.&.&.&.\\% .&.&1&.&.&.\\% .&.&.&1&.&.\\% .&.&.&.&1&.\\% .&.&.&.&.&1\\% 1&3&0&-5&0&3\\% \end{bmatrix}$

It is pretty, but also non-obvious what its composition factors are. This form (along with the Z/6Z style grouping of irreducible factors) is used by GP/Pari. Transposes and alternate groupings of factors allow for a wide variety of canonical forms.

The best answer will address the ease of explicitly writing down generators of the centralizer of B over a finite prime field given just (irr,pow), or will address both writing down the canonical form from (irr,pow) and the centralizer. An inductive answer might prefer to allow non-prime fields, but added generality at the cost of clarity and explicit algorithms is not useful to me.

Edit: Both B and $\hat B$ have the nice property that given a generator w for the indecomposable module acted on by the original operator M, a basis realizing the matrix is easy to find. For B this is vi = w⋅Mj⋅irr(M)k where i−1 = k⋅deg(irr) + j and 0 ≤ j < deg(irr), for i = 1, 2, … deg(irr)⋅pow. For $\hat B$ this is vi = w⋅Mi−1, for i = 1, 2, … deg(irr)⋅pow.

In order to use $\tilde B$, I need a similar explicit understanding of the basis defining it.

1″) How does one express a basis of k[x]/(irr^pow) in terms of the coset of 1 such that the operator corresponding to x has the form $\tilde B$, that is, block Toeplitz with the diagonal the companion matrix of irr, the super-diagonal an identity, and the other diagonals 0?

I am of course still curious about 2′. I think an answer to 1″ would both provide an answer for 2′ and be enough, even without an explicit reference, to finish Robin Chapman's answer to 1.

share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

For a start the accepted usage for "rational canonical form" in the literature is for a diagonal sum $C(f_1)\oplus C(f_2)\oplus\cdots\oplus C(f_k)$ where $C(f_i)$ is the companion matrix for a monic polynomial $f$ and $f_1\mid f_2\mid\cdots\mid f_k$. That said, if I needed to find a centralizer explcitly it isn't the canonical form I would choose.

As ever we should think of $V=k^n$ as a $k[X]$-module where $X$ acts via $A$. If the minimum polynomial of $A$ is $u_1^{a_1}\cdots u_k^{a_k}$ with the $p_i$ distinct irreducibles then $V$ splits uniquely into a direct sum of submodules $M_1\oplus\cdots\oplus M_k$, where $M_i$ is annihilated by a power of $u_i$. Both $A$ and ts centralizer fix each $M_i$, so we may reduce to the case where the minimum polynomial $u^a$ with $u$ irreducible.

Let $u$ have degree $r$ and let $C\in M_r(k)$ be the companion matrix for $u$ or any conjugate for it. I claim that $A$ is conjugate to a diagonal sum of ``Jordan-style blocks'' like $$J=\left(\begin{matrix} C&I&O&O\\\ O&C&I&O\\\ O&O&C&I\\\ O&O&O&C \end{matrix}\right).$$ This is just a question of checking this has the minimum polynomial $u^a$. As we are working in $GL(n,p)$ then $C\ne0$ and over a finite field then the diagonal sum of copies of $C$ is a polynomial in $A$ (indeed $A^{p^rs}$ for suitable $s$). Thus each matrix in the centralizer of $A$ has a block decomposition into $r$-by-$r$ blocks which commute with $C$ and so are polynomials in $C$. So, finding the centralizer of $A$ is equivalent to finding the centralizer of the matrix $A'$ over $k'=k(\alpha)$ where $\alpha$ is a zero of $u$ and $A'$ is obtained by replacing the above Jordan-style blocks by standard Jordan blocks $$J'=\left(\begin{matrix} \alpha&1&0&0\\\ 0&\alpha&1&0\\\ 0&0&\alpha&1\\\ 0&0&0&\alpha \end{matrix}\right).$$ The centralizer of $A'$ is the same as that of $A'-\alpha I$ which is a very sparse matrix. At this stage I would just find the centralizer in the matrix algebra by explicit calculation and extract the nonsingular elements as the centralizer in the matrix group.

Added (6/6/2010) I claimed that $J$ had the minimum polynomial $u^a$. Let $k'=k(\alpha)$. The matrix $J'$ gives the action of $x$ on a standard $k'$-basis for the $k'[x]$-module $k'[x]/((x-\alpha)^a)$. Therefore $J$ gives the action of $x$ on a $k$-basis for $k'[x]/((x-\alpha)^a)$ considered as a $k[x]$-module. To see that $J$ has minimum polynomial $u^a$ it suffices to show that some element of $k'[x]/((x-\alpha)^a)$ has annihilator $u^a$ over $k[x]$. But the element $1$ has annilhator $(x-\alpha)^a k'[x]$ over $k'[x]$ and so has annihilator $k[x]\cap (x-\alpha)^a k'[x]=u^a k[x]$ over $k[x]$, provided the extension $k'/k$ is separable (so that $x-\alpha$ is not a repeated factor of $u$).

So the assertion holds for finite fields, bt not necessarily for general fields of prime characteristic. It would be interesting to work out the details for inseparable irreducible polynomials.

share|improve this answer
    
So you recommend using the $\tilde B$ style form, where the scalars are very easy to see? I've only found one reference that does it similar to this (Shilov's Linear Algebra), but only for the real field, and not using companion matrices for the diagonal blocks (so the nice super diagonal is not there anyways). I'm almost convinced to use $\tilde B$, since the centralizer calculation is almost identical to the Jordan form version (and so uses the inductive solution), but I'm not sure what the basis means exactly. –  Jack Schmidt Jun 5 '10 at 7:12
    
...I'm not sure what the basis means exactly. $\hat B$ takes a module generator of your M<sub>k</sub> and applies the original operator to it until we get linear dependence. $B$ takes the generator and applies the original operator up to the degree of u, and then applies u(operator). How does one generate the basis vectors of $\tilde B$ from a module generator? –  Jack Schmidt Jun 5 '10 at 7:12
    
Comments are hard to format, so I rewrote the question part of the comment into the question. I like your answer, because working over k(α) just makes sense. If I can do it that way, then I will. However, I have not yet figured out how to constructively find this version of the RCF (field extensions can be prohibitively expensive as they stop using optimized field arithmetic, so I need to do it at a simpler level). I wrote out the answers for B and $\hat B$, and surely $\tilde B$ has a similar easy answer, but it continues to elude me. –  Jack Schmidt Jun 5 '10 at 15:13
    
I'm not sure what you are getting at in your comments but I suppose I am advocating using what you call the $\hat B$ form. Another way of describing this starts with a Jordan block of size $t$ with diagonal elements $\alpha$. This gives an endomorphism of the vector space $k(\alpha)^t$ over $k(\alpha)$. But we can identify $k(\alpha)^t$ with $k^{rt}$ by choosing a $k$-basis of $k(\alpha)$. This gives a matrix of the form $\hat B$. (Choosing the basis $1,\alpha,\alpha^2,\ldots,\alpha^{r-1}$ gives a companion matrix for $C$.) –  Robin Chapman Jun 5 '10 at 15:28
    
I'm not sure what you are getting at in your comment, but I gave the entries of $\hat B$. It is clearly not in the form you describe. I asked for a basis for M, not for k(α). –  Jack Schmidt Jun 5 '10 at 16:11
show 2 more comments

Here is part 1″ solved, but the answer is complex and too long for a comment or edit. Notation is similar but not identical to before:

Let f be a separable, irreducible polynomial of degree d. Let B be the block-Toeplitz matrix whose diagonal blocks are the companion matrix of f, whose first super-diagonal blocks are the identity matrix, and whose other blocks are 0. Let b be the number of diagonal blocks. Let { vi : i = 1,...,b*d } be the standard basis. We wish to express each vi for i≥2 in terms of v1, f, and b. In terms of k[x]-modules, B is the action of x on the module M = k[x]/(f^b) in the basis where v1 = 1 + (f^b), and vi are unknown polynomials related to f and b.

The matrix explicitly says that vi⋅B = vi+1 + vi+d when d does not divide i−1. This can be solved for:

vi+1 = vi⋅B − vi+d, for d not dividing i−1

which can be iterated to express:

vk⋅d+i+1 = vk⋅d+1⋅Bi − i⋅v(k+1)⋅d+1⋅Bi-1 for k a non-negative integer and i a positive integer.

In particular, once we know vk⋅d+1 for k=0,...,b-1, we know the entire basis. If we only desire that our matrix be block-upper triangular with the correct diagonal blocks, then we can choose these basis vectors freely amongst the generators of the submodules (f^k)/(f^b) ≤ M. In other words, we can choose them freely from the null-space of f^k as long as they are not in the null space of f^(k+1).

Let wk = vk⋅d+1. In order to get exactly the right blocks above the diagonal we use the relationship:

$$\sum_{k=0}^{b-1} w_{(k+K)} \cdot \frac{(-1)^k}{k!} f^{(k)}(B) = 0$$

where we extend wk = 0 for k ≥ b, and K is any non-negative integer. Here we need a reduced derivative f(k)(x) / (k!) which can be written without division, and so is valid even for characteristic dividing k!.

This relationship lets us solve for wk+1 in terms of wk and wk+i for i ≥ 2. This requires division by f′(B), and so f must be separable. In order to solve this recurrence, I found it easiest to solve from wb−1 back to w2, to avoid any circular solutions. If b or d is small (say ≤ 3), this can be done quite easily by hand, but beyond this the results are better viewed as recursive algorithms rather than as explicit formulas.

For instance, if Min(b-1,d) ≤ 2, then:

wk+1 = wk ⋅ f(B) / f′(B)

and if Min(b-1,d) ≤ 3, then:

wk+1 = wk ⋅ f(B) / ( f′(B) − f(B)⋅f″(B) / ( 2⋅f′(B) ) )

The next expression is quite long.

It seems strange that two of the other canonical forms have such nice bases, while this one encodes the Taylor series of f. In terms of polynomials, the basis for d=2, b=3 is:

{ 1, x − f/f′, f/f′, x⋅f/f′ − (f/f′)2 , (f/f′)2, x⋅(f/f′)2 }

I believe this means it would be difficult to understand how the scalars are embedded in my originally preferred canonical form unless b or d was quite small.

It seems to me that when f is not separable, the matrix B still has the correct minimal polynomial, but that the various canonical forms need not be conjugate. In particular, for f(x)=x2−t over Z/2Z(t), it seems plausible that the companion matrix of f2 is not conjugate to the block diagonal matrix called "B" in this answer.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.