## 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 $n$th 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.