\documentstyle[doublespace,11pt,fullpage]{article} \marginparwidth 0pt \oddsidemargin 0pt \evensidemargin 0pt \marginparsep 0pt \topmargin 0pt \textwidth 6.3in \textheight 8.5in \setstretch{1.5} \begin{document} \mbox{ }\\ \begin{center} An Exploratory Approach to Kaplansky's Lemma Leads to a Generalized Resultant \\ \vspace{5mm} David Callan \end{center} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \vspace{10mm} Let $T:V \rightarrow V$ be a linear transformation on a vector space $V.$ If the powers $I,T,T^{2},\dots,T^{k}$ of $T$ are linearly dependent, then surely for every $v \in V,$ the vectors $v,Tv,T^{2}v,\dots,T^{k}v$ are also linearly dependent. Kaplansky noted that the converse assertion is also true. \begin{theorem} $(${\rm Kaplansky's Lemma in finite dimensions}$)$ Suppose $T:V \rightarrow V$ is a linear transformation on a finite-dimensional vector space $V$ over an arbitrary field $F$ and suppose the set of powers $\{T^{i}\}_{i=0}^{k}$ is linearly independent. Then there exists $v \in V$ such that the set $\{T^{i}v\}_{i=0}^{k}$ is linearly independent. \end{theorem} This result actually holds in arbitrary dimensions and the extension from finite to infinite dimensions is fairly straightforward \cite[p. 64]{radjavi}. Aupetit \cite{aupetit} gives an elegant proof when $F={\rm C}$ (valid for any dimensions) using Liouville's theorem from complex analysis. His proof is reproduced, slightly polished, in Prasolov's recent intriguing survey of linear algebra emphasizing modern proofs of classical results \cite[p. 46]{prasolov}. Henceforth, we assume a finite-dimensional space. So $T$ has a minimal polynomial of degree $n$, say. The maximum $k$ can be is $n-1$ and so we may as well assume $k=n-1.$ Prasolov then gives a slick proof, valid for infinite fields, using minimal vector-annihilating polynomials and their subspaces \cite[{\bf 13.1.2}, p. 73]{prasolov}. It relies on the result: a vector space cannot be expressed as a finite set-theoretic union of proper subspaces, and this of course requires the underlying field to be infinite. For arbitrary fields, one can readily construct a suitable vector $v$ using the theory of the rational canonical form \cite[p. 198]{jacobson}. This says that $T$ acts as a block diagonal matrix, the diagonal blocks being the companion matrices of the invariant factors $d_{1}(x)\,|\,d_{2}(x)\,|\,\dots \,|d_{s}(x)$ of $T.$ The vector $v$ consisting of 0's except for a 1 in the first position corresponding to the $d_{s}(x)$ block has minimal annihilating polynomial $d_{s}(x). $ This vector $v$ fits the bill since $d_{s}(x)$ is also the minimal polynomial of $T.$ But suppose out of curiosity we look for a suitable $v$ using the version of the rational canonical form involving elementary divisors \cite[p. 262]{herstein}. Now $T$ acts as a block diagonal matrix whose diagonal blocks are the companion matrices of the elementary divisors $\{p_{i}(x)^{e_{ij}}\}$ of $T.$ Here the polynomials $p_{i}(x)$ are irreducible and distinct. Let $f_{i}(x)=p_{i}(x)^{r_{i}},\ 1 \leq i \leq m,$ be the elementary divisors of highest degree, so that $\prod_{i=1}^{m} f_{i}(x)$ is the minimal polynomial of $T$ with degree $n=\sum_{i=1}^{m}\deg f_{i}.$ In fact, it is sufficient to assume these are the {\em only} elementary divisors; after dealing with this case, $v$ can be augmented with zeros to cover the general case. Thus we assume $T$ is the $n$-square matrix ${\rm diag}(A_{1},A_{2},\dots,A_{m})$ where $A_{i}$ is the companion matrix of $f_{i},\ 1 \leq i \leq m.$ Let $(v_{1}^{T},v_{2}^{T},\dots,v_{m}^{T})^{T}$ be the corresponding partition of our desired (column) vector $v.$ For $v_{i},$ let's try the simplest possible nonzero vector: just one nonzero entry---a 1, say---which should be the first entry to maximize linear independence among $\{A_{i}^{r}v_{i} \}_{r \geq 0} $ . This simple scheme would work if only we had a guarantee that the resulting $n$-square matrix $B:=(v\,|\,Tv\,|\,\cdots \,|\,T^{n-1}v)$ has linearly independent columns---equivalently, $\det B \neq 0$---based solely on the premise of pairwise relative primeness of the polynomials $f_{i}$ from which $T$ is formed. But for polynomials, relative primeness means no common root (in an algebraic closure of $F$) and so a simple numerical quantity guaranteed to be nonzero precisely when the $f_{i}$ are pairwise relatively prime is the product of all differences of roots of different $f_{i}$'s. Call this product $\Delta.$ We are thus emboldened to conjecture that $\Delta$ and $\det B$ are closely related. In fact, as we show in Theorem 2, they are equal (up to sign). To state this result in appropriate generality, let $\lambda_{ij},\ 1 \leq i \leq m,\ 1 \leq j \leq n_{i}$ be algebraically independent commuting indeterminates over $F$ (the ``roots'') and for $ 1 \leq i \leq m$ let $\sigma_{ij}, \ 1 \leq j \leq n_{i},$ denote the elementary symmetric polynomials in $\{\lambda_{ij}\}_{j=1}^{n_{i}}$ (the ``coefficients''). Then let $f_{i}(x) = x^{n_{i}} - \sigma_{i1} x^{n_{i}-1}+ \sigma_{i2} x^{n_{i}-2} - \cdots +(-1)^{n_{i}} \sigma_{in_{i}}, \ 1 \leq i \leq m,$ so that the roots of $f_{i}$ are $\{\lambda_{ij}\}_{j=1}^{n_{i}}.$ Set $n=\sum_{i=1}^{m}n_{i}$. The companion matrix of $f_{i}$ is \[ A_{i}= \left( \begin{array}{ccccc} 0 & \ \ & & & (-1)^{n_{i}-1} \sigma_{in_{i}} \\ 1 & 0 & & & \vdots \\ & 1 & \ddots & & \\ & & \ddots & 0 & -\sigma_{i2} \\ & & \ \ & 1 & \sigma_{i1} \end{array} \right) \] and the characteristic polynomial of $A_{i}$ is $f_{i}.$ Now let $A$ be the $n$-square block diagonal matrix with $A_{i}$ as its $i$th diagonal block, $1 \leq i \leq m,$ let $e_{i}$ denote the $n_{i}$-length (column) vector with 1 in the first position and 0's elsewhere, and let $e$ be the $n$-vector obtained by concatenating the $e_{i}.$ Finally, let $B$ denote the $n$-square matrix whose $j$th column is $A^{j-1}e,\ \, 1 \leq j \leq n.$ For example, when $m=3$ and $n_{1}=3,\,n_{2}=2,\,n_{3}=1,$ \newcommand{\s}{\mbox{$\sigma$}} \begin{equation} B= \left( \begin{array}{cccccc} 1 & 0 & 0 & \sigma_{13} & \sigma_{11}\sigma_{13} & \sigma_{11}^{2}\sigma_{13}-\sigma_{12}\sigma_{13} \\ 0 & 1 & 0 & - \sigma_{12} & -\sigma_{11}\sigma_{12} +\sigma_{13} & -\sigma_{11}^{2}\sigma_{12} + \sigma_{11}\sigma_{13}+ \sigma_{12}^{2} \\ 0 & 0 & 1 & \sigma_{11} & \sigma_{11}^{2} -\sigma_{12} & \sigma_{11}^{3}-2\sigma_{11}\sigma_{12}+\sigma_{13} \\ 1 & 0 & -\sigma_{22} & -\sigma_{21}\sigma_{22} & - \sigma_{21}^{2} \sigma_{22} +\sigma_{22}^{2} & -\sigma_{21}^{3}\sigma_{22}+2 \sigma_{21}\sigma_{22}^{2} \\ 0 & 1 & \sigma_{21} & \sigma_{21}^{2} - \sigma_{22} & \sigma_{21}^{3} - 2\sigma_{21}\sigma_{22} & \sigma_{21}^{4}-3\sigma_{21}^{2}\sigma_{22}+\sigma_{22}^{2} \\ 1 & \sigma_{31} &\sigma_{31}^{2} & \sigma_{31}^{3} & \sigma_{31}^{4} & \sigma_{31}^{5} \end{array} \right) \label{defb} \end{equation} \begin{theorem} For the matrix $B$ formed from the $\lambda_{ij}$ through their symmetric functions $\sigma_{ij}$ as in $($\ref{defb}$)$, \begin{equation} \det B = \prod_{1 \leq i < j \leq m} \prod_{k=1}^{n_{i}} \prod_{\ell=1}^{n_{j}} (\lambda_{j\ell} - \lambda_{ik}) \label{res} \end{equation} \end{theorem} Before proving Theorem 2 (and thereby also Kaplansky's Lemma) we make some remarks. The classical resultant of two polynomials expresses the right side of (\ref{res}) (for $m=2$) as the determinant of the {\it Sylvester matrix} \cite[p. 102]{van der waerden} also formed from the polynomials' coefficients. Thus Theorem 2 gives a form of generalized resultant, though the matrix $B$ does not coincide with the Sylvester matrix for $m=2.$ Further information about resultants (including a generalization in a different direction) and their applications in finding greatest common divisors of polynomials is given in \cite[\S 2.1]{barnett}. What does the matrix $B$ look like when expressed in terms of the $\lambda$'s? The following two propositions give some useful information. \begin{proposition} All nonzero terms in the determinant of {\em any} submatrix of $B$ have the same total degree in the $\lambda$'s $($depending only on the submatrix$)$. \end{proposition} Proof. The matrix $B$ contains various size identity matrices flush left; the other entries are polynomials in the $\sigma$'s that are easily seen to be homogeneous polynomials in the $\lambda$'s whose (total) degrees are as illustrated in Figure 1 (for $m=3;\ n_{1}=3, \ n_{2}=2, \ n_{3}=1$). Here the blanks represent zero entries in $B.$ \[ \left( \begin{array}{cccccc} 0 & - & - & 3 & 4 & 5 \\ - & 0 & - & 2 & 3 & 4 \\ - & - & 0 & 1 & 2 & 3 \\ 0 & - & 2 & 3 & 4 & 5 \\ - & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 & 4 & 5 \end{array} \right) \hspace{20mm} \left( \begin{array}{cccccc} 0 & 1 & 2 & 3 & 4 & 5 \\ -1 & 0 & 1 & 2 & 3 & 4 \\ -2 & -1 & 0 & 1 & 2 & 3 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ -1 & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 & 4 & 5 \end{array} \right) \] \hspace{42mm} Fig. 1 \hspace{55mm} Fig. 2 \\ \noindent It is possible to fill in the blanks so that each row is a sequence of consecutive integers, yielding a matrix $C$ as in Figure 2. The degree of the product of given nonzero entries in $B$ is the sum of the corresponding entries in $C$. Thus it certainly suffices to show: for any square submatrix $D$ of $C,$ the sum of the entries in a diagonal is constant over all diagonals of $D$ (a diagonal is a maximal set of entries, no two in the same row or column). Now the entries in $C$ are of the form $c_{ij}=d_{i}+e_{j}$ for some sequences $\{d_{i}\},\{e_{j}\}$ ($e_{j}$ may be taken $=j$). Thus the sum of the entries in any diagonal of $D$ is the sum of the $d_{i}$ corresponding to the rows of $D$ and the $e_{j}$ corresponding to the columns of $D$, independent of the diagonal. %the $\lambda$'s so ``degree'' means degree in the $\lambda$'s. \begin{proposition} Suppose $B$ is partitioned into $m^{2}$ submatrices $B_{ij}$ of size $n_{i}$-by-$n_{j}$ in the obvious way. Fix $i$ in $[1,m].$ Then $($i$)$ $B_{ii} = A_{i}^{n_{1}+n_{2}+\cdots +n_{i-1}}$, $($ii$)$ $\det B_{ii} = (\lambda_{i1} \lambda_{i2} \cdots \lambda_{in_{i}})^{n_{1}+n_{2}+\cdots+n_{i-1}}$, $($iii$)$ The degree $($in the $\lambda$'s$)$ of each term in $\det B_{ii}$ is $n_{i}(n_{1}+n_{2}+\cdots+n_{i-1}),$ $($iv$)$ If $B_{i}'$ is any $n_{i}$-square submatrix of $B$ involving the same rows as $B_{ii}$ but no column to the right of the rightmost column of $B_{ii}$, then the degree of each term in $\det B_{i}'$ is strictly less than $n_{i}(n_{1}+n_{2}+ \cdots + n_{i-1})$ unless $B_{i}'=B_{ii},$ $($v$)$ The degree of each term in $\det B$ is $\sum_{1 \leq i