Monthly Archives: October 2011

Compute the rational canonical form of a given matrix

Compute the rational canonical form of the following matrices.

A = \begin{bmatrix} 0 & -1 & -1 \\ 0 & 0 & 0 \\ -1 & 0 & 0 \end{bmatrix}
B = \begin{bmatrix} c & 0 & -1 \\ 0 & c & 1 \\ -1 & 1 & c \end{bmatrix}
C = \begin{bmatrix} 422 & 465 & 15 & -30 \\ -420 & -463 & -15 & 30 \\ 840 & 930 & 32 & -60 \\ -140 & -155 & -5 & 12 \end{bmatrix}

Consider the matrix A. First, we use elementary row and column operations to put xI - A in Smith Normal Form. Evidently the following sequence of ERCOs works:

  1. R_1 - xR_3 \rightarrow R_1
  2. R_1 \leftrightarrow R_3
  3. C_3 - xC_1 \rightarrow C_3
  4. R_2 - xR_3 \rightarrow R_2
  5. C_3 - (1-x^2)C_2 \rightarrow C_3
  6. R_2 \leftrightarrow R_3

The resulting matrix is \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & x^3-x \end{bmatrix}. Thus the only invariant factor of A is x^3-x, and so the rational canonical form of A is \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}.

Now consider the matrix B. Again, we use ERCOs to get xI-B in Smith Normal Form. Evidently the following sequence of operations suffices.

  1. R_1 - (x-c)R_3 \rightarrow R_1
  2. C_2 + C_1 \rightarrow C_1
  3. C_3 - (x-c)C_1 \rightarrow C_3
  4. C_2 + (x-c)C_3 \rightarrow C_2
  5. R_1 + (1-(x-c)^2)R_2 \rightarrow R_1
  6. R_1 \leftrightarrow R_3
  7. C_2 \leftrightarrow C_3
  8. -C_2 \rightarrow C_2
  9. -C_3 \rightarrow C_3

Resulting in the matrix \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & x^3 - 3cx^2 - (2-3c^2)x - c(c^2-2) \end{bmatrix}. The corresponding rational canonical form is then \begin{bmatrix} 0 & 0 & c^3-2c \\ 1 & 0 & 2-3c^2 \\ 0 & 1 & 3c \end{bmatrix}.

Finally, consider the matrix C. Again we use ERCOs to get xI-C in Smith Normal Form. Evidently the following sequence of operations suffices:

  1. R_2 - 3R_4 \rightarrow R_2
  2. R_3 + 6R_4 \rightarrow R_3
  3. R_1 + 3R_4 \rightarrow R_1
  4. \frac{1}{140}R_4 \rightarrow R_4
  5. R_1 - (x-2)R_4 \rightarrow R_1
  6. C_2 - \frac{155}{140}C_1 \rightarrow C_2
  7. C_3 - \frac{5}{140}C_1 \rightarrow C_3
  8. C_4 - \frac{x-2}{140}C_1 \rightarrow C_4
  9. \frac{155}{140}R_2 + R_1 \rightarrow R_1
  10. 3C_2 + C_4 \rightarrow C_4
  11. \frac{5}{140}R_3 + R_1 \rightarrow R_1
  12. -6C_3 + C_4 \rightarrow C_4
  13. R_1 \leftrightarrow R_4
  14. -140R_4 \rightarrow R_4

Resulting in the matrix \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & x-2 & 0 & 0 \\ 0 & 0 & x-2 & 0 \\ 0 & 0 & 0 & (x-2)(x+3) \end{bmatrix}. The rational canonical form of C is thus \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 6 \\ 0 & 0 & 1 & -1 \end{bmatrix}.

Compute the characteristic polynomial of a companion matrix

Let p(x) = \sum_{i=0}^n c_i x^i be a monic polynomial (i.e. c_n = 1) and let A = [a_{i,j}] where a_{i,j} = -c_{i-1} if j = n, 1 if i = j+1, and 0 otherwise. Show that c_A(x) = p(x).


Recall that c_A(x) = \mathsf{det}(xI - A) = \mathsf{det}([x\delta_{i,j} - a_{i,j}]), where \delta_{i,j} = 1 if i = j and 0 otherwise.

Using the Cofactor Expansion Formula along the nth column (derived here), we have \mathsf{det}(xI-A) = \sum_{i=1}^n (-1)^{i+n} (x \delta_{i,n} - a_{i,n}) \mathsf{det}(M_{i,n}), where M_{i,n} denotes the (i,n) matrix minor of xI - A.

Evidently, we have that (M_{k,n})_{i,j} = x if i = j < k, -1 if i = j \geq k, -1 if i = j+1 and i < k, x if i = j-1 and i \geq k, and 0 otherwise. So M_{k,n} = \begin{bmatrix} L & 0 \\ 0 & U \end{bmatrix}, where L is lower triangular of dimension k-1 and diagonal entries equal to x and U is upper triangular of dimension n-k and diagonal entries equal to -1. So we have \mathsf{det}(M_{k,n}) = (-1)^{n-k}x^{k-1}.

So we have c_A(x) = \sum_{i=1}^n (-1)^{i+n} (x \delta_{i,n} - a_{i,n}) (-1)^{n-i} x^{i-1} = \sum_{i=1}^n (-1)^{2n} (x\delta_{i,n} - a_{i,n}) x^{i-1} = x^n + \sum_{i=1}^n (-a_{i,n})x^{i-1} = x^n + \sum_{i=1}^n c_{i-1}x^{i-1} = x^n + \sum_{i=0}^{n-1} c_ix^i = p(x) as desired.

Compute the eigenvalues of a given matrix

Find the eigenvalues of the following matrix.

A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}

Recall that the eigenvalues of a matrix A are the roots of the polynomial c_A(x) = \mathsf{det}(xI - A). Now in this case, we have

xI - A = [a_{i,j}] = \begin{bmatrix} x & -1 & 0 & 0 \\ 0 & x & -1 & 0 \\ 0 & 0 & x & -1 \\ -1 & 0 & 0 & 0 \end{bmatrix}.

Using the Cofactor Expansion Formula for the determinant along the 4th row, (Theorem 29 on page 439 of D&F, with i = 4), we have that \mathsf{det}(xI - A) = (-1)^5 a_{4,1} \mathsf{det}(A_{4,1}) + (-1)^6 a_{4,2} \mathsf{det}(A_{4,2}) + (-1)^7 a_{4,3} \mathsf{det}(A_{4,3}) + (-1)^8 a_{4,4} \mathsf{det}(A_{4,4}). Since a_{4,2} = a_{4,3} = 0, this simplifies to

\mathsf{det}(xI - A)  =  \mathsf{det}(A_{4,1}) + x \mathsf{det}(A_{4,4})
 =  \mathsf{det} \begin{bmatrix} -1 & 0 & 0 \\ x & -1 & 0 \\ 0 & x & -1 \end{bmatrix} + x \mathsf{det} \begin{bmatrix} x & -1 & 0 \\ 0 & x & -1 \\ 0 & 0 & x \end{bmatrix}.

Note that both of these minor matrices are diagonal, and recall that the determinant of an upper- or lower-triangular matrix is the product of the diagonal entries. (To see this, consider the Leibniz formula for the determinant: \mathsf{det}([a_{i,j}]) = \sum_{\sigma \in S_n} \varepsilon(\sigma) \prod_{i=1}^n a_{\sigma(i),i}. If [a_{i,j}] is upper (lower) triangular, then for every \sigma, if \sigma moves at least one element in \{1,\ldots,n\}, then it must move some element to a strictly larger (smaller) one, in which case \prod a_{\sigma(i),i} vanishes since some factor is zero. What remains is merely \prod_i a_{i,i}.)

So we have c_A(x) = -1 + x x^3 = x^4 - 1. Clearly the roots of this polynomial, hence the eigenvalues of A, are \pm 1 and \pm i.

The determinant and trace of a matrix are the product and sum of its eigenvalues, respectively

Let A \in \mathsf{Mat}_n(F) be a matrix over a field F. Prove that the constant term of the characteristic polynomial c_A(x) is (-1)^n \mathsf{det}(A) and that the x^{n-1} term is the negative of the sum of the diagonal entries of A (called the trace of A). Deduce that \mathsf{det}(A) is the product of the eigenvalues of A, and that \mathsf{tr}(A) (the trace of A) is the sum of the eigenvalues of A.


Recall that c_A(x) = \mathsf{det}(xI - A) = \mathsf{det}([\delta_{i,j}x - a_{i,j}]), where \delta_{i,j} is 1 if i = j and 0 otherwise. So c_A(x) = \sum_{\sigma \in S_n} \varepsilon{\sigma} \prod_{i=1}^n (\delta_{\sigma(i),i} x - a_{\sigma(i), i}).

Now the constant term of c_A(x) is merely c_A(0) = \sum_{\sigma \in S_n} \varepsilon{\sigma} \prod_{i=1}^n (-a_{\sigma(i), i}) = \sum_{\sigma \in S_n} \varepsilon{\sigma} (-1)^n \prod_{i=1}^n a_{\sigma(i), i} = (-1)^n \mathsf{det}(A).

Consider now the polynomial p_\sigma(x) = \prod_{i=1}^n (\delta_{\sigma(i), i}x - a_{\sigma(i), i}). Note in particular that the degree of p_\sigma is just the number of elements in \{1,\ldots,n\} which are fixed by \sigma. No \sigma can fix n-1 elements, so that except for \sigma = 1, the polynomial p_\sigma does not contribute to the x^{n-1} term of c_A(x). That is, the x^{n-1} term of c_A(x) is just the x^{n-1} term of p_1(x) = \prod_{i=1}^n (x - a_{i,i}), which is just - \sum_{i=1}^n a_{i,i} as desired.

Now recall that the eigenvalues of A are (by definition) the roots of c_A(x). It then follows that the constant term of c_A(x) is (-1)^n times the product of the eigenvalues and that the x^{n-1} term is the negative of the sum of the eigenvalues.

The degree of the minimal polynomial of a matrix of dimension n is at most n²

Let A \in \mathsf{Mat}_n(F) be a matrix over a field F. Prove that the dimension of the minimal polynomial m_A(x) of A is at most n^2.


If V = F^n, note that the set \mathsf{End}_F(V) is isomorphic to \mathsf{Mat}_n(F) once we select a pair of bases. The set of all n \times n matrices over F is naturally an F-vector space of dimension n^2. Consider now the powers of A: 1 = A^0, A^1, A^2, …, A^{n^2}. These matrices, as elements of \mathsf{End}_F(V), are necessarily linearly dependent, so that \sum r_i A^i = p(A) = 0 for some r_i \in F. The minimal polynomial m_A(x) divides this p(x), and so has degree at most n^2.

Two nonscalar matrices of dimension 3 over a field are similar if and only if they have the same characteriscic and the same minimal polynomials

Let A, B \in \mathsf{Mat}_3(F) be matrices over a field F. Prove that A and B are similar if and only if they have the same characteristic and minimal polynomials. Show, via an explicit counterexample, that this result does not hold for matrices of dimension 4.


In this previous exercise, we showed that similar matrices have the same characteristic and minimal polynomials.

Let A and B be nonscalar matrices of dimension 3 over a field F, and suppose A and B have the same characteristic (c(x)) and minimal (m(x)) polynomials. Recall (Proposition 20 in D&F) that the characteristic polynomial of a matrix divides some power of its minimal polynomial. To show that A and B are similar, it suffices to show that the invariant factors of A (and of B) are in this case uniquely determined by c(x) and m(x). Then A and B will have the same rational canonical form, and so will be similar.

Suppose m(x) has degree 3. Then the (only) invariant factor of A and of B is m(x), whose companion matrix is the rational canonical form of A and B. So A and B are similar.

Suppose m(x) has degree 2. Now c(x)|m(x)^t for some t; say c(x)d(x) = m(x)^t. If m(x) is irreducible, we have c(x)|m(x), a contradiction since c(x) has degree 3. If m(x) is reducible, we have m(x) = (x-\alpha)(x-\beta) for some \alpha,\beta \in F (not necessarily distinct). Since c(x) is the product of the invariant factors of A, and since the invariant factors (one of which is m(x)) divide m(x), without loss of generality the invariant factors of A are (x-\alpha) and (x-\alpha)(x-\beta). Now c(x) = (x-\alpha)^2(x-\beta), and in fact the invariant factors of B are also (x-\alpha) and (x-\alpha)(x-\beta). So A and B have the same rational canonical form and are thus similar.

Suppose m(x) = x-\alpha has degree 1. Now the invariant factors of A (and of B) are all x-\alpha, so that A and B are similar to scalar matrices, and thus are themselves scalar.

To construct a counterexample for dimension 4 matrices, it suffices to exhibit two matrices A and B which have the same minimal polynomial and characteristic polynomial but different lists of invariant factors. For example, consider matrices whose invariant factors are \{(x-\alpha)^2, (x-\alpha)^2\} and \{x-\alpha,x-\alpha, (x-\alpha)^2\}.

Nonscalar matrices of dimension 2 over a field are similar if and only if they have the same characteristic polynomial

Let A,B \in \mathsf{Mat}_2(F) be nonscalar matrices over a field F. Prove that A and B are similar if and only if they have the same characteristic polynomial.


We showed in this previous exercise that similar matrices have the same characteristic polynomial. Thus it suffices to show that two nonscalar matrices of dimension 2 having the same characteristic polynomial are similar. To do this, it suffices to show that two such matrices have the same rational canonical form.

To this end, let A and B be 2 \times 2 matrices over F having the same characteristic polynomial. Note that p(x) = \mathsf{char}_A(x) = \mathsf{char}_B(x) has degree 2.

Let m_A(x) be the minimal polynomial of A. If m_A(x) = x-\alpha has degree 1, then p(x) = (x-\alpha)^2 by Proposition 20 in D&F, and the invariant factors of A are x-\alpha and x - \alpha. But now A is similar to the diagonal matrix \alpha I = \begin{bmatrix} \alpha & 0 \\ 0 & \alpha \end{bmatrix}. But if Q^{-1}AQ = \alpha I, then in fact A = \alpha I, a contradiction. So m_A(x) has degree 2. Since m_A(x) divides the characteristic polynomial of A (being the divisibility-largest invariant factor, while the characteristic polynomial is the product of the invariant factors) and both are monic, we have m_A(x) = p(x).

Similarly, we have m_B(x) = p(x).

So A and B have the same minimal polynomial m(x) = p(x), which is in fact their (only) invariant factor. So A and B have the same rational canonical form. By Theorem 15 in D&F, A and B are similar.

The minimal polynomial of a direct sum is the least common multiple of minimal polynomials

Let M = A \oplus B = \begin{bmatrix} A & 0 \\ 0 & B \end{bmatrix} be a direct sum of square matrices A and B. Prove that the minimal polynomial of M is the least common multiple of the minimal polynomials of A and B.


Given a linear transformation T on V, we let \mathsf{Ann}_T(V) denote the annihilator in F[x] of V under the action induced by x \cdot v = T(v).

Let p(x) \in \mathsf{Ann}_M(V). If p(x) = \sum r_ix^i, we have \sum a_iM^i = 0 as a linear transformation. Note that M^k = \begin{bmatrix} A^k & 0 \\ 0 & B^k \end{bmatrix}. So we have \begin{bmatrix} \sum r_i A^i & 0 \\ 0 & \sum r_i B^i \end{bmatrix} = 0, and thus \sum r_i A^i = 0 and \sum r_i B^i = 0. So p(x) \in \mathsf{Ann}_A(W_1) \cap \mathsf{Ann}_B(W_2), where V = W_1 \oplus W_2. Conversely, if p(x) \in \mathsf{Ann}_A(W_1) \cap \mathsf{Ann}_B(W_2), then p(A) = 0 and p(B) = 0 as linear transformations. Then p(M) = \sum r_i M^i = \begin{bmatrix} \sum r_iA^i & 0 \\ 0 & \sum r_iB^i \end{bmatrix} = 0, so that p(x) \in \mathsf{Ann}_M(V). So we have \mathsf{Ann}_M(V) = \mathsf{Ann}_A(W_1) \cap \mathsf{Ann}_B(W_2).

That is, (m_M) = (m_A) \cap (m_B), where m_T is the minimal polynomial of T.

Lemma: In a principal ideal domain R, if (a) \cap (b) = (c), then c is the least common multiple of a and b. Proof: Certainly c \in (a) and c \in (b), so that c is a multiple of both a and b. If d is a multiple of a and of b, then d \in (a) \cap (b) = (c), so that latex d$ is a multiple of c. \square

The result then follows.

Similar linear transformations have the same characteristic and minimal polynomials

Let V be an n-dimensional vector space over a field F. Prove that similar linear transformations on V have the same characteristic and the same minimal polynomial.


Suppose A and B are similar matrices (i.e. linear transformations) on V. Then we have an invertible matrix P such that B = P^{-1}AP.

Now \mathsf{char}(B) = \mathsf{det}(xI - B) = \mathsf{det}(xI - P^{-1}AP) = \mathsf{det}(P^{-1}xP - P^{-1}AP) = \mathsf{det}(P^{-1})\mathsf{det}(xI - A)\mathsf{det}(P) = \mathsf{det}(xI - P) = \mathsf{char}(A). So A and B have the same characteristic polynomial.

Recall that the minimal polynomial of a transformation T is the unique monomial generator of \mathsf{Ann}(V) in F[x] (under the usual action of F[x] on V). Thus, to show that A and B have the same minimal polynomial, it suffices to show that they have the same annihilator in F[x] under their respective actions on V.

To this end, suppose p(x) \in \mathsf{Ann}_A(V) (where \mathsf{Ann}_A denotes the annihilator induced by A). Then as a linear transformation, we have p(A) = 0. Say p(x) = \sum r_ix^i; then \sum r_iA^i = 0. But A^i = PB^iP^{-1}, so that \sum r_iPB^iP^{-1} = 0, and thus (left- and right-multiplying by P^{-1} and P, respectively) \sum r_iB^i = 0. So p(B) = 0 as a linear transformation, and we have p(x) \in \mathsf{Ann}_B(V). The reverse inclusion is similar, so that \mathsf{Ann}_A(V) = \mathsf{Ann}_B(V) as desired.

Over a PID which is not a field, no finitely generated module is injective

Let R be a principal ideal domain which is not a field. Prove that no finitely generated R-module is injective.


Let M be a finitely generated R-module. By Theorem 5 (FTFGMPID), we have M \cong_R R^t \oplus \mathsf{Tor}(M) for some t \in \mathbb{N}. By this previous exercise, M is injective if and only if R^t and \mathsf{Tor}(M) are injective. We claim that if M is injective, then M = 0.

We begin with a lemma.

Lemma: If M is a finitely generated torsion module over a principal ideal domain, then there exists a nonzero element r \in R such that rM = 0. Proof: By FTFGMPID, we have M \cong \bigoplus_i R/(p_i^{k_i}) for some primes p_i \in R and nonnegative natural numbers k_i. Now r = \prod_i p_i^{k_i} is nonzero and clearly annihilates M. \square

By Proposition 36 on page 396 of D&F, \mathsf{Tor}(M) (if nontrivial) cannot be injective, since we have rM = 0 for some r. So if M is injective, then \mathsf{Tor}(M) = 0.

Consider now R^t; if t \geq 1, it suffices to consider a single copy of R. If p \in R is not a unit, then pR = (p) \subsetneq R. So again by Proposition 36 on page 396, R is not injective, so that R^t is not injective if t \geq 1.

So if M is injective, then M = 0.

Conversely, the zero module is trivially injective since every short exact sequence 0 \rightarrow 0 \rightarrow M \rightarrow N \rightarrow 0 splits (trivially).

So over a principal ideal domain R which is not a field, no nontrivial module is injective.