Solve a polynomial equation over a given ring of matrices

Find (representatives of) all the similarity classes of 3 \times 3 matrices over \mathbb{Z}/(2) which satisfy p(x) = x^6 - 1. Do the same for 4 \times 4 matrices which satisfy q(x) = x^{20} - 1.


We begin by factoring p(x) into irreducibles. Note that p(x) = (x^3+1)(x^3-1) = (x^3-1)^2 since 1 = -1 in \mathbb{Z}/(2). Moreover, x^3-1 = (x-1)(x^2+x+1), and x^2+x+1 is irreducible over \mathbb{Z}/(2) since it has no roots. Thus we have the irreducible factorization p(x) = (x-1)^2(x^2-x-1)^2.

Suppose now that A is a 3 \times 3 matrix over \mathbb{Z}/(2) satisfying p(x); then the minimal polynomial of A divides p(x) and has degree at most 3 (since it divides the characteristic polynomial, which has degree 3). The divisors of p(x) having degree at most 3 are x-1, (x-1)^2, x^2-x-1, and (x-1)(x^2-x-1). Note that the third polynomial, x^2-x-1, cannot be the minimal polynomial of a 3 \times 3 matrix since no power of x^2-x-1 is divisible by a degree 3 polynomial. (See Prop. 20 in D&F.) For each remaining divisor of p(x), once fixed as the minimal polynomial of A, the remaining invariant factors are determined. The possible lists of invariant factors for A are thus as follows.

  1. x-1, x-1, x-1
  2. x-1, (x-1)^2
  3. (x-1)(x^2-x-1)

The corresponding matrices in rational canonical form are then as follows.

  1. \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}
  2. \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}
  3. \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}

(Note that these matrices are also representatives of the conjugacy classes of the representation of S_3 by permutation matrices. Does this mean anything?)

Next we factor q(x) = x^{20}-1. We have q(x) = (x^{10}+1)(x^{10}-1) = (x^{10}-1)^2, x^{10}-1 = (x^5-1)^2, and x^5-1 = (x-1)(x^4+x^3+x^2+x+1). We claim that r(x) = x^4+x^3+x^2+x+1 is irreducible over \mathbb{Z}/(2). Certainly r(x) has no roots, and thus no linear factors. Suppose now that r(x) = (x^2+ax+b)(x^2+cx+d) has a quadratic factor. Multiplying out and comparing coefficients, we have a+c=1, d+b+ac=1, ad+bc = 1, and bd=1. Now b=d=1 by the fourth equation, that ac=1 by the second. Now a=c=1. But then 1 = a+c = 0, a contradiction. So r(x) has no quadratic factors, and thus is irreducible over \mathbb{Z}/(2). So q(x) factors into irreducibles as q(x) = (x-1)^4(x^4-x^3-x^2-x-1)^4.

Suppose now that B is a 4 \times 4 matrix satisfying q(x). Then the minimal polynomial divides q(x) and has degree at most 4. The divisors of q(x) with this property are x-1, (x-1)^2, (x-1)^3, (x-1)^4, and x^4-x^3-x^2-x-1. The possible lists of invariant factors for B are then as follows.

  1. x-1, x-1, x-1, x-1
  2. x-1, x-1, (x-1)^2
  3. (x-1)^2, (x-1)^2
  4. x-1, (x-1)^3
  5. (x-1)^4
  6. x^4-x^3-x^2-x-1

The corresponding matrices in rational canonical form are thus as follows.

  1. \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}
  2. \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}
  3. \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}
  4. \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}
  5. \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}
  6. \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}

Every 4 \times 4 matrix B over \mathbb{Z}/(2) such that B^{20} = I is similar to exactly one matrix in this list.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: