Definition 6.4.1.
An invariant of a mathematical object is a property of that object that is either the same for all members of an equivalence class or unchanged after some sort of transformation.
Section 6.4 Invariants
One of the fun aspects of linear algebra is that it touches so many different areas of mathematics. In this section we will connect row equivalence and similarity to the topic of mathematical invariants, which is used in many mathematical disciplines to determine whether or not two objects are related.
Subsection 6.4.1 Introduction to Invariants
Many areas of mathematics have a notion of the relatedness of the important objects of study. In linear algebra, we have already learned about vector spaces being isomorphic (Theorem 5.3.12), and this idea shows up widely. We often prove that mathematical objects are related by defining a function between them and showing that it has all the right properties.
However, showing that two mathematical objects are not related is harder when working strictly from the definitions. It is difficult to show that a function with certain properties cannot exist—not being able to find or think of such a function is not a sufficient argument! This is where invariants enter the picture.
Note 6.4.2.
In our present context, we will be thinking about equivalence relations. This is a good opportunity to think through the logic of invariants. Suppose we have two objects \(A\) and \(B\) which are related by some equivalence relation. We will write \(A \sim B\text{.}\) (This tells us that \(A\) and \(B\) are in the same equivalence class.) If there is an invariant \(f\) in view, then \(A \sim B\) implies the values of the invariant are equal—in other words, \(A \sim B\) implies \(f(A) = f(B)\text{.}\)
The contrapositive of this implication is what we end up using with great frequency. If \(f(A) \neq f(B)\text{,}\) then we know that \(A \not \sim B\text{.}\) (In other words, \(A\) and \(B\) are not related.) Importantly, knowing that \(f(A) = f(B)\) does not prove that \(A\) and \(B\) are related. The implication goes in one direction but not the other.
Before this discussion gets too vague, let’s look at an example that most readers of this book should recognize.
Example 6.4.3.
We say that two geometric objects are congruent if they have the same shape and size. Most readers will likely have spent some time considering congruent triangles in a geometry class, where they encountered several congruence theorems for triangles: Side-Side-Side, Side-Angle-Side, etc. (Note that congruent triangles are not the same as similar triangles, though there are some, ahem, similarities.)
In this example, congruence provides the relevant equivalence relation on the set of all planar triangles.
One invariant that can be used to distinguish between triangles that are not congruent is the area of the triangle. It is easy to show that if two triangles are congruent, they have the same area. Therefore, if two triangles have different areas, we can conclude that they are not congruent.
To be specific, suppose that triangle \(A\) is a 30-60-90 triangle with side lengths \((10, 10\sqrt{3}, 20)\) and triangle \(B\) is a 45-45-90 triangle with side lengths \((10\sqrt[4]{3},10\sqrt[4]{3},10\sqrt{2}\sqrt[4]{3})\text{.}\) Then since the area of a right triangle is easy to calculate using the \(\frac{1}{2}bh\) formula, we can see that both triangles \(A\) and \(B\) have an area of \(50\sqrt{3}\) square units. But these triangles are not congruent—they have different angles, after all.
In summary, the area of a triangle can be used to distinguish between triangles that are not congruent. However, area cannot be used to conclude that two triangles are congruent. In this way, area is a typical invariant.
In this text, we have discussed two equivalence relations on sets of matrices for which there exist some interesting invariants. For fixed values of \(m\) and \(n\text{,}\) row equivalence is an equivalence relation on the set \(M_{m,n}(\ff)\text{.}\) (See Exercise 1.2.10.) More recently, we have looked at similarity, which is an equivalence relation on the set \(M_n(\ff)\) for fixed values of \(n\text{.}\) (See Exercise 6.2.4.10.)
We have shown in Theorem 6.2.11 that the characteristic polynomial is an invariant for similar matrices. If two matrices are similar, they have the same characteristic polynomial, and therefore the same eigenvalues (with the same multiplicities). This means that if we know of two matrices of the same size with different eigenvalues, they cannot be similar.
Additionally—and using much the same argument—the determinant is an invariant for similar matrices. (We asked the reader to prove this in Exercise 6.2.4.12.) So, two matrices of the same size with different determinants cannot be similar.
We will summarize these two already-established facts in the following proposition.
Proposition 6.4.4.
Let \(n\) be a positive integer and let \(\ff\) be a field. The determinant and the characteristic polynomial are both invariants on the set \(M_n(\ff)\) with respect to the relation of similarity.
While the characteristic polynomial and the determinant are useful invariants for similarity, they are far from the only ones. In the second half of this section we will develop two more invariants which respect similarity, one of which is quite surprising.
Subsection 6.4.2 Rank and Trace as Invariants
We will first state and prove a few results needed to establish rank as an invariant.
Theorem 6.4.5.
Suppose that \(V\) and \(W\) are finite-dimensional vector spaces and that \(T \in L(V,W)\text{.}\) Then, for any bases \(\mcb\) of \(V\) and \(\mcc\) of \(W\text{,}\) we have
\begin{equation*}
\rank(T) = \rank([T]_{\mcb,\mcc}) \hspace{12pt} \text{and} \hspace{12pt}
\dim(\ker(T)) = \dim(\nll([T]_{\mcb,\mcc}))\text{.}
\end{equation*}
Proof.
Suppose that \(\mcb = \{ \bfv_1, \ldots, \bfv_n \}\) and let \(A = [T]_{\mcb,\mcc}\text{.}\) Since \(V = \spn(\mcb)\text{,}\) we have \(\img(T) = \spn\{T(\bfv_1), \ldots, T(\bfv_n) \}\text{.}\) By Theorem 5.5.3 we know that \(\spn\{T(\bfv_1), \ldots, T(\bfv_n) \}\) is isomorphic to
\begin{equation*}
\spn\{ [T(\bfv_1)]_{\mcc}, \ldots, [T(\bfv_n)]_{\mcc} \}\text{.}
\end{equation*}
The vectors \([T(\bfv_i)]_{\mcc}\) are exactly the columns of \(A\text{,}\) so
\begin{equation*}
\rank(T) = \dim(\img(T)) = \dim(\col(A)) = \rank(A)\text{.}
\end{equation*}
For the second equality, we refer to The Rank-Nullity Theorem. If \(\dim(V)=n\) and \(\dim(W)=m\text{,}\) then \(A\) is \(m\times n\text{.}\) We have proved that \({\rank(T) = \rank(A)}\text{,}\) and comparing the two equations in Theorem 5.4.10, we are left with \(\dim(\nll(A)) = \dim(\kerr(T))\text{,}\) as desired.
Proposition 6.4.6.
Suppose that \(V\) is an \(n\)-dimensional vector space over \(\ff\text{,}\) that \(\mcb\) is a basis of \(V\text{,}\) and that \(T \in L(V)\text{.}\) Suppose further that \(A\) and \(B\) are similar matrices in \(M_n(\ff)\) and that \(A = [T]_{\mcb}\text{.}\) Then there exists a basis \(\mcc\) of \(V\) such that \(B = [T]_{\mcc}\text{.}\)
Proof.
Let \(\mcb = \{\bfv_1, \ldots \bfv_n \}\) and suppose that \(B = SAS^{-1}\text{.}\) We define \(Q = S^{-1}\) and, for each \(j\text{,}\) we define \(\bfw_j\) by
\begin{equation*}
\bfw_j = \sum_{i=1}^n q_{ij}\bfv_i\text{,}
\end{equation*}
so that \(\mathbf{q}_j\) is the coordinate vector \([\bfw_j]_{\mcb}\text{.}\) Since \(Q\) is invertible, then \(\{\mathbf{q}_1, \ldots, \mathbf{q}_n\}\) is a basis of \(\ff^n\text{,}\) so \(\mcc = \{\bfw_1, \ldots, \bfw_n \}\) is a basis of \(V\text{.}\) (This is again due to the coordinate mapping being an isomorphism.) We also have
\begin{equation*}
P_{\mcc,\mcb} \bfe_j = P_{\mcc,\mcb} [\bfw_j]_{\mcc} = [\bfw_j]_{\mcb} = \mathbf{q}_j
\end{equation*}
for each \(j\text{,}\) so \(P_{\mcc,\mcb} = Q\text{.}\) Therefore, by Lemma 5.6.6, \(S = P_{\mcb,\mcc}\text{,}\) and so by Corollary 5.6.9, \([T]_{\mcc} = SAS^{-1} = B\text{.}\)
Note 6.4.7.
Proposition 6.4.6, along with Proposition 6.3.15 show us that two matrices are similar if and only if they represent the same linear transformation with respect to different bases.
With these two results in hand, we can state the first invariant we have been pointing toward.
Corollary 6.4.8.
Proof.
This follows from Theorem 6.4.5 (in the case where \(V = W\) and \(\mcb = \mcc\)) as well as Proposition 6.4.6.
In the following example, we put this invariant to work.
Example 6.4.9.
Let \(A, B \in M_3(\rr)\) be the following matrices:
\begin{equation*}
A = \begin{bmatrix} -3.5 \amp 5 \amp -4.5 \\
3.5 \amp -3 \amp -1.5 \\
-3 \amp 5 \amp -6
\end{bmatrix}, \hspace{6pt}
B = \begin{bmatrix} 2 \amp 3 \amp 4 \\
-2 \amp -4 \amp 0 \\
3.5 \amp -5 \amp -2
\end{bmatrix} \text{.}
\end{equation*}
Some quick row reduction shows that \(\rank(A) = 2\) while \(\rank(B)=3\text{,}\) so we know that \(A\) and \(B\) are not similar.
We now move into the development and discussion of our final invariant, the trace of a matrix. Of all the invariants we discuss, the trace is by far the easiest to calculate!
Definition 6.4.10.
Let \(A \in M_n(\ff)\text{.}\) The trace of \(A\) is the sum of the numbers along the main diagonal of \(A\text{.}\) In other words,
\begin{equation*}
\tr(A) = \sum_{i=1}^n a_{ii}\text{.}
\end{equation*}
Example 6.4.11.
Here are two matrices over \(\rr\text{:}\)
\begin{equation*}
A = \begin{bmatrix} -1 \amp 5 \\ -3 \amp 2 \end{bmatrix}, \hspace{6pt}
B = \begin{bmatrix} 2 \amp 1 \amp 0 \\ 3.5 \amp -2 \amp -3 \\ 4 \amp -2.5 \amp -2.5 \end{bmatrix}\text{.}
\end{equation*}
By summing the entries along the main diagonal, we see that \(\tr(A) = 1\) and \(\tr(B) = -2.5\text{.}\)
We need surprisingly few additional results in order to establish the trace as an invariant.
Proposition 6.4.12.
If \(A \in M_{m,n}(\ff)\) and \(B \in M_{n,m}(\ff)\text{,}\) then
\begin{equation*}
\tr(AB) = \tr(BA)\text{.}
\end{equation*}
Proof.
We begin by using the definitions of the trace and matrix multiplication:
\begin{equation*}
\tr(AB) = \sum_{i=1}^m [AB]_{ii} = \sum_{i=1}^m \sum_{j=1}^n a_{ij}b_{ji}\text{.}
\end{equation*}
Since multiplication and addition in a field are both commutative, we can switch the order of summation and multiplication. The calculation is finished using the definitions of matrix multiplication and the trace again:
\begin{equation*}
\tr(AB) = \sum_{j=1}^n \sum_{i=1}^m b_{ji}a_{ij} = \sum_{j=1}^n [BA]_{jj} = \tr(BA)\text{.}
\end{equation*}
This next result finishes our argument.
Corollary 6.4.13.
Proof.
Suppose that \(B = PAP^{-1}\text{.}\) By the associativity of matrix multiplication and Proposition 6.4.12, we have
\begin{align*}
\tr(B) \amp = \tr(PAP^{-1}) = \tr((PA)P^{-1}) = \tr(P^{-1}(PA))\\
\amp = \tr((P^{-1}P)A) = \tr(IA) = \tr(A)\text{.}
\end{align*}
We can now use the trace as an invariant.
Example 6.4.14.
Let \(A\) and \(B\) be the following matrices over \(\ff_5\text{:}\)
\begin{equation*}
A = \begin{bmatrix} 4 \amp 1 \\ 4 \amp 2 \end{bmatrix}, \hspace{6pt}
B = \begin{bmatrix} 2 \amp 2 \\ 3 \amp 0 \end{bmatrix}\text{.}
\end{equation*}
Since \(\tr(A) = 1\) and \(\tr(B) = 2\text{,}\) we know that \(A\) and \(B\) are not similar matrices.
One consequence of this invariant is that it allows us to define the trace of a linear transformation.
Corollary 6.4.15.
Let \(V\) be a finite-dimensional vector space and let \(T \in L(V)\text{.}\) If \(\mcb\) and \(\mcc\) are two bases for \(V\text{,}\) then \(\tr([T]_{\mcb}) = \tr([T]_{\mcc})\text{.}\)
Proof.
Definition 6.4.16.
Let \(V\) be a finite-dimensional vector space and let \(T \in L(V)\text{.}\) Then the trace of \(T\) is \(\tr(T) = \tr([T]_{\mcb})\text{,}\) where \(\mcb\) is any basis of \(V\text{.}\)
Example 6.4.17.
We end this section with an example of a linear transformation \(T:P_1 \to P_1\) which was defined in Example 6.3.17. In that example, we saw that
\begin{equation*}
[T]_{\mcb} = \begin{bmatrix} 1 \amp -4 \\ 3 \amp -6 \end{bmatrix}\text{,}
\end{equation*}
so we can see that \(\tr(T) = -5\text{.}\)
Reading Questions 6.4.3 Reading Questions
1.
Use only the rank invariant to answer the following questions. If that invariant does not give you enough information to answer the question, explain why that is.
\begin{equation*}
A = \begin{bmatrix} 1.5 \amp 3 \amp -1.5 \\ -0.5 \amp 0 \amp 1.5 \\ 0.5 \amp -3 \amp -4.5 \end{bmatrix}, \hspace{6pt}
B = \begin{bmatrix} 3.5 \amp -4.5 \amp -4 \\ 3.5 \amp -0.5 \amp 4 \\ -3.5 \amp -1.5 \amp 3.5 \end{bmatrix}\text{,}
\end{equation*}
\begin{equation*}
C = \begin{bmatrix} 4 \amp -2 \amp -6 \\ 2.5 \amp 5 \amp 2.5 \\ -2.5 \amp -5 \amp -2.5 \end{bmatrix}\text{.}
\end{equation*}
2.
Use only the trace invariant to answer the following questions. If that invariant does not give you enough information to answer the question, explain why that is. (The matrices for this question are the same as for the previous reading question.)
Exercises 6.4.4 Exercises
1.
Consider the following two matrices in \(M_3(\rr)\text{:}\)
\begin{equation*}
A = \begin{bmatrix}
-5 \amp 4.5 \amp 1.5 \\
-1.5 \amp 0 \amp 4.5 \\
1 \amp -1.5 \amp 1.5
\end{bmatrix}, \hspace{6pt} \text{and} \hspace{6pt}
B = \begin{bmatrix}
-3.5 \amp 3.5 \amp -3.5 \\
-4.5 \amp 3.5 \amp -2.5 \\
-4 \amp 0.5 \amp 3
\end{bmatrix}\text{.}
\end{equation*}
-
Explain why both determinant and rank are not useful invariants to say that \(A\) and \(B\) are not similar.
2.
Consider the following two matrices in \(M_3(\rr)\text{:}\)
\begin{equation*}
A = \begin{bmatrix}
1 \amp -6 \amp 2 \\
1 \amp 2 \amp 1 \\
0 \amp 6 \amp -1
\end{bmatrix}, \hspace{6pt} \text{and} \hspace{6pt}
B = \begin{bmatrix}
10 \amp 13 \amp -5 \\
-3 \amp -6 \amp -1 \\
3 \amp 3 \amp -2
\end{bmatrix}\text{.}
\end{equation*}
-
Explain why both trace and rank are not useful invariants to say that \(A\) and \(B\) are not similar.
Answer.
3.
Consider the following two matrices in \(M_3(\rr)\text{:}\)
\begin{equation*}
A = \begin{bmatrix}
-10 \amp -20 \amp -2 \\
7 \amp 14 \amp 1 \\
-5 \amp -10 \amp -1
\end{bmatrix}, \hspace{6pt} \text{and} \hspace{6pt}
B = \begin{bmatrix}
2 \amp -1 \amp 1 \\
2 \amp -2 \amp 2 \\
2 \amp -3 \amp 3
\end{bmatrix}\text{.}
\end{equation*}
-
Explain why the trace, rank, and determinant are not useful invariants to say that \(A\) and \(B\) are not similar.
Answer.
-
We find that \(\tr(A)=\tr(B)=3\text{,}\) \(\rank(A)=\rank(B)=2\text{,}\) and \(\det(A)=\det(B)=0\text{,}\) so the trace, rank, and determinant do not give us enough information to determine whether or not \(A\) and \(B\) are similar.
-
Some calculation shows that the eigenvalues for \(A\) are \(\lambda=0, -1, 4\text{,}\) while the eigenvalues for \(B\) are \(\lambda=0, 1, 2\text{.}\) Since these are different (and therefore the characteristic polynomials are different), we see that \(A\) and \(B\) are not similar.
4.
Consider the following two matrices in \(M_2(\ff_7)\text{:}\)
\begin{equation*}
A = \begin{bmatrix}
2 \amp 4 \\ 3 \amp 5
\end{bmatrix}, \hspace{6pt} \text{and} \hspace{6pt}
B = \begin{bmatrix}
4 \amp 4 \\ 5 \amp 3
\end{bmatrix}\text{.}
\end{equation*}
-
Explain why the trace and rank are not useful invariants to say that \(A\) and \(B\) are not similar.
5.
Consider the following two matrices in \(M_3(\ff_7)\text{:}\)
\begin{equation*}
A = \begin{bmatrix}
4 \amp 6 \amp 2 \\
1 \amp 5 \amp 6 \\
1 \amp 5 \amp 5
\end{bmatrix}, \hspace{6pt} \text{and} \hspace{6pt}
B = \begin{bmatrix}
2 \amp 2 \amp 2 \\
4 \amp 4 \amp 1 \\
5 \amp 5 \amp 1
\end{bmatrix}\text{.}
\end{equation*}
-
Explain why the trace, rank, and determinant are not useful invariants to say that \(A\) and \(B\) are not similar.
6.
Consider the following two matrices in \(M_3(\ff_7)\text{:}\)
\begin{equation*}
A = \begin{bmatrix}
2 \amp 2 \amp 4 \\
5 \amp 3 \amp 3 \\
4 \amp 0 \amp 0
\end{bmatrix}, \hspace{6pt} \text{and} \hspace{6pt}
B = \begin{bmatrix}
2 \amp 0 \amp 0 \\
5 \amp 4 \amp 3 \\
2 \amp 5 \amp 6
\end{bmatrix}\text{.}
\end{equation*}
-
Explain why the trace, rank, determinant, and characteristic polynomial are not useful invariants to say that \(A\) and \(B\) are not similar.
Answer.
-
We find that \(\rank(A)=\rank(B)=3\text{,}\) \(\tr(A)=\tr(B)=5\text{,}\) and \(\det(A)=\det(B)=4\text{.}\) Further, the eigenvalues for both \(A\) and \(B\) are \(\lambda = 1, 2, 2\text{.}\) These four invariants do not provide enough information to determine whether or not \(A\) and \(B\) are similar.
-
We can show that \(A\) is not diagonalizable but \(B\) is. Since diagonalizability is an invariant for similarity, this proves that \(A\) and \(B\) are not similar.
7.
There are 16 elements of the set \(M_2(\ff_2)\text{.}\) How many equivalence classes are there for this set under the similarity equivalence relation? Use as many of the invariants as you can to distinguish between matrices that are not similar to each other.
Writing Exercises
8.
Let \(A \in M_2(\ff)\) be this \(2\times 2\) matrix:
\begin{equation*}
A = \begin{bmatrix}
a \amp b \\ c \amp d
\end{bmatrix}\text{.}
\end{equation*}
-
Write out the characteristic polynomial of \(A\text{,}\) substituting \(\det(A)\) and \(\tr(A)\) where appropriate.
-
Argue that, for \(2\times 2\) matrices, the fact that the characteristic polynomial is an invariant (for similarity) implies that both the trace and determinant are invariants.
9.
Fix a positive integer \(n \ge 2\text{.}\) Is diagonalizability an invariant (for similarity) on the set \(M_n(\ff)\text{?}\) In other words, for \(A,B \in M_n(\ff)\text{,}\) if \(A\) and \(B\) are similar, must it be true that either (a) they are both diagonalizable, or (b) they are both not diagonalizable?
10.
Suppose that \(A \in M_n(\ff)\text{.}\)
-
Prove that if \(A\) has \(n\) distinct eigenvalues, then \(\tr(A)\) is the sum of the eigenvalues of \(A\text{.}\)
-
Is the result from part (a) true if \(A\) does not have \(n\) distinct eigenvalues? For example, if \(A \in M_3(\rr)\) has only two distinct eigenvalues, must \(\tr(A)\) be the sum of the eigenvalues (with multiplicity)?
11.
-
Prove that if \(A, B, C \in M_n(\ff)\text{,}\) then\begin{equation*} \tr(ABC) = \tr(BCA) = \tr(CAB)\text{.} \end{equation*}
-
Give an example of three matrices \(A, B, C \in M_n(\ff)\) such that \(\tr(ABC) \neq \tr(ACB)\text{.}\)
12.
For a matrix \(A \in M_n(\ff)\text{,}\) define the function \(S(A)\) as the sum of all of the entries of \(A\text{.}\) Prove or disprove that \(S\) is an invariant for similar matrices.
13.
Is rank an invariant for row equivalence? Justify your answer.
14.
Is the trace an invariant for row equivalence? Justify your answer.
Answer.
No, trace is not an invariant for row equivalence. Consider the following matrix \(A \in M_2(\rr)\text{:}\)
\begin{equation*}
A = \begin{bmatrix} 2 \amp 1 \\ 1 \amp 1 \end{bmatrix}\text{.}
\end{equation*}
The matrix \(A\) is invertible, so it is row equivalent to \(I_2\text{.}\) However, \(\tr(A)=3\) and \(\tr(I_2)=2\text{.}\) This proves that trace is not an invariant for row equivalence.
15.
Is the determinant an invariant for row equivalence? Justify your answer.
16.
Is invertibility an invariant for row equivalence? Justify your answer.
17.
Is invertibility an invariant for similarity? Justify your answer.
Answer.
Yes, invertibility is an invariant for similarity. This argument relies on the fact that the determinant is an invariant for similarity.
We will denote the similarity relation by \(A \sim B\text{.}\) Suppose that \(A \sim B\) and that \(A\) is invertible. This means that \(\det(A)\neq 0\text{,}\) and since \(A \sim B\text{,}\) this means that \(\det(B) \neq 0\) also. But the fact that \(\det(B) \neq 0\) means that \(B\) is invertible.
We now suppose that \(A \sim B\) and that \(A\) is not invertible. This means that \(\det(A)=0\text{,}\) and since \(A\sim B\text{,}\) this means that \(\det(B)=0\text{.}\) But \(\det(B)=0\) means that \(B\) is not invertible.
This proves that invertibility is an invariant for similarity.
