Tag: Tricks

Universality and Characteristic Polynomials

Today I’m going to describe a simple, yet powerful, trick to deduce specific problems from a “universal” case. The construction is common in algebra; given an object {O} and a property {P} that we would like to deduce about this object, we construct a certain “universal” object {U} such that

  1. {U} has property {P};
  2. there exists a surjective homomorphism {\varphi : U \rightarrow O} that “preserves” {P}.

In order to justify this abstraction, it should be easier to show that {U} satisfies {P} than it is to show that {O} satisfies {P}. However, {U} should not be a “trivial” object that vacuously satisfies {P}. Instead, {U} should have several “nice” properties that {O} does not have, but it should not have properties that you feel are irrelevant to the current problem. Terry tao discusses a similar trick in analysis (trick 10) in his “problem solving strategies,” post.

One of my favorite examples of this strategy is the following standard qual problem:

Problem 1 Let {R} be a commutative ring with unity. Let {M} and {N} be {n\times n} matrices with entries in {R}. Then {MN} and {NM} have the same characteristic polynomial.

The first thing we notice is that if {M} or {N} is invertible, the problem is easy. Indeed, if {M} is invertible, then {MN = MNMM^{-1}} so

\displaystyle \begin{array}{rcl} \det(I X- MN) &=& \det(IX-MNMM^{-1}) \\ &=& \det(MM^{-1}X - M\left(NM\right)M^{-1}) \\ &=& \det(M)\det(IX - NM)\det(M)^{-1} \\ &=& \det(IX - NM). \end{array}

This observation shows that a possible candidate for a universal space {U}, should contain a lot of invertible matrices. This may not be the case for {R} because it may have many zero divisors and few units. Even if {M} has a non-zero determinant, it might not be invertible. Another possible reduction could involve working over a field. Indeed, in this case, a proof involving row and column operations exists, but it is tedious.

A clever way of proceeding, is to consider the following ring:

\displaystyle \begin{array}{rcl} U &:=& \mathbf{Z}[X_{ij}, Y_{kl} : i,j, k, l \in \{1, \cdots, n\}], \end{array}

where {X_{ij}} and {Y_{lk}} are indeterminates. Define the matrices {M' = (X_{ij})_{i,j \in \{1, \cdots, n\}}} and {N' = (Y_{kl})_{k, l \in \{1, \cdots, n\}}}. We consider the the quotient field

\displaystyle \begin{array}{rcl} K = \text{quot}(U) = \mathbf{Q}(X_{ij}, Y_{kl} : i,j, k, l \in \{1, \cdots, n\}) \end{array}

Observe that over {K}, {\det(M')} and {\det(N')} are non-zero. Hence, {M'} is invertible. Our remark before shows that the characteristic polynomial of {M'N'} is the characteristic polynomial of {N'M'}. Moreover, the characteristic polynomial of {M'N'} has integer coefficients by the definition of the determinant. Thus, the remark is almost trivially true over {U}. Further, we can define a map

\displaystyle \begin{array}{rcl} \varphi : U &\rightarrow& R \\ X_{ij} &\mapsto& a_{ij} \\ Y_{kl} &\mapsto& b_{kl} \\ 1 &\mapsto& 1, \end{array}

where {M = (a_{ij})_{i, j \in \{1, \cdots, n\}}} and {N = (b_{kl})_{k, l \in \{1, \cdots, n\}}}. Because the coefficients of {P(X)}, the characteristic polynomial of {M'N' }, has coefficients that are polynomials in the entries of {M'N'}, with a bit of thought, we see that the characteristic polynomial of {MN} is equal to {P^\varphi}. The same statement holds for {N'M'} and {NM}. Thus, {MN} and {NM} have the same characteristic polynomial.

Because {\mathbf{Z}} is the initial object in the category of commutative rings with unity, we can always define such a map. If {R} does not contain an identity element, is it possible to apply this proof to that case as well? The map {\varphi} is not so well defined in this case. However, this technique exposes this problem for what it really is, (symbol manipulation), so it appears that the result should continue to hold.