<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentstyle[11pt]{article}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in} 
\begin{document}
 
 
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{defn}{Definition}[section]
\newtheorem{hyp}{Hypothesis}[section]
\newcommand{\proof}{\noindent{\bf Proof }}
\newcommand{\diag}[1]{\mbox{diag($#1$)}}
\newcommand{\ignore}[1]{\hspace{0in}}
\newlength{\boxwidth}
\setlength{\boxwidth}{\textwidth}
\addtolength{\boxwidth}{-20 pt}

\newcommand{\boxer}[1]{\begin{center} \fbox{\fbox{
      \begin{minipage}{\boxwidth}  #1 \end{minipage}}} \end{center}}


 
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qed}{\hfill\hfill\vbox{\hrule\hbox{\vrule\squarebox
   {.667em}\vrule}\hrule}\smallskip}

\newlength{\bl}

\setlength{\unitlength}{1in}
\newcommand{\boxit}[3]
{
\begin{picture}(#1,#2)
\put(0,0){
\framebox(#1,#2){#3}}
\end{picture}}
\newcommand{\iboxit}[3]
{
\begin{picture}(#1,#2)
\put(0,0){
\makebox(#1,#2){#3}}
\end{picture}}



\vspace{0.1in}
 
\title{
The Dimension of Matrices (Matrix Pencils) with Given 
Jordan (Kronecker) Canonical Forms}
\author{\sl{James W. Demmel
\thanks{Computer\ Science\ Division\ and Department of Mathematics,
University of California, Berkeley, CA 94720,
demmel@cs.berkeley.edu. Supported by NSF grants DMS-9120852,
ASC-9005933
and under a subcontract with the University of 
Tennessee under DARPA contract  DAAL03-91-C-0047.}} \\
 \sl{Alan Edelman\thanks{Department of Mathematics Room 2-380, 
Massachusetts Institute of Technology, 
Cambridge, MA 02139,
edelman@math.mit.edu.
Supported by NSF grant DMS-9120852 and
the Applied Mathematical Sciences subprogram of
the Office of Energy Research, U.S. Department of Energy under
Contract DE-AC03-76SF00098.
 }} \\
} 
\date{November 1993}
 
\maketitle




\begin{abstract}
The set of $n$ by $n$
matrices with a given Jordan canonical form defines a subset
of matrices in complex  $n^2$ dimensional space. 
We analyze one classical approach and one new
approach to count the  dimension of this set. 
The new approach is based upon and meant to give insight into
the staircase algorithm for the computation of the
Jordan Canonical Form as
well as the occasional failures of this algorithm.
We extend both techniques to count the dimension
of the more complicated set defined by the Kronecker
canonical form of an arbitrary rectangular matrix pencil
$A-\lambda B$.
\end{abstract}






\section{Introduction}

Given any 
square matrix $A$, the set of matrices similar to $A$ forms a
manifold in  complex $n^2$ dimensional space.
This manifold is, of course, the 
orbit of $A$ under the action of conjugation:
$$\mbox{orbit($A$)}=\{PAP^{-1}:\mbox{det($P$)}\ne0\},$$
The matrix pencil analog is to consider
any pair of $m$ by $n$ 
matrices $A$ and $B$, and define the 
orbit of the matrix pencil $A-\lambda B$ by the action of multiplication
on the left and right by square nonsingular matrices of the appropriate
size:
$$\mbox{orbit($A-\lambda B$)}=\{P(A-\lambda B)Q^{-1}:\mbox{det($P$)det($Q$)}\ne0\},$$
This orbit defines a manifold of pencils
in $2mn$ dimensional space.  All pencils on this manifold
are said to be
{\it equivalent} to $A-\lambda B$.
(In matrix theory, a ``pencil'' refers to a linear matrix polynomial,
often in the indeterminate $\lambda$.  See \cite{gantmacher}.)


Our concern in this work is to count the (co)dimension 
of these manifolds as objects in complex Euclidean space.
For simplicity of exposition, we sometimes  refer to these two problems
as counting the (co)dimension of a (single) matrix or of a matrix pencil, when
more properly, we would refer to counting the (co)dimension of the
orbits.
We take two approaches, one based on
classical techniques that identify
the tangent spaces of these manifolds and the other based
upon existing numerical algorithms for computing the Jordan and 
Kronecker forms
\cite{kagstrom85,kagstrom86,KR,kub,Ru,PVD,PVDT,wilk78,wilk79}.

The classical approach to solving this problem
requires the
computation of the tangent space 
to the orbits.  In the single
matrix case, the tangent vectors have the form
\be
\label{single}
XA-AX,
\ee
while in the matrix pencil case, the tangents have the form 
\be
\label{double}
X(A-\lambda B)-(A-\lambda B)Y.
\ee
Thus the codimension of the  single matrix orbit is the number of linearly
independent matrices $X$ for which (\ref{single}) vanishes, while the 
codimension of the matrix pencil orbit is related to
the number of linearly independent
matrix pairs  $X,Y$ for which (\ref{double}) vanishes.


Arnold \cite{Ar} has rederived the formula for the Jordan case 
for the purpose of defining a particular normal form for 
deformations  of a matrix with a given Jordan form. 
This form is convenient because of its minimum number of parameters
\cite{fairgrieve}.
We are unaware of any general dimension count for matrix pencils 
in the literature.  One partial result of Waterhouse \cite{Wa} 
counts the codimension of a singular pair of $n$ by $n$
matrices (i.e. the square case) to be $n+1$.

Our new approach is based on the so called {\bf staircase algorithms}
for the Jordan and Kronecker canonical forms.  The staircase algorithm
for the Jordan canonical form proceeds by computing 
the Weyr characteristics of the matrix, while the staircase canonical
form proceeds by computing a more complicated set of structural 
indices.

In this paper
we lay the groundwork for a theory that we hope might explain
the  occasional
failures of existing staircase algorithms to find the ``right'' Jordan
or Kronecker form. These algorithms are used in systems and control theory
to find the input matrix (or pencil) of highest codimension within a
user-supplied distance $\eta$ of the input data.
The structures of these
matrices or pencils reflect important physical properties of the systems
they model, such as controllability \cite{demmelkagstrom88,vandooren81}.
The user chooses $\eta$ to measure the uncertainty in the data.
The existence of a matrix or pencil
with a different structure within distance $\eta$ of the input means that the
actual system may have a different structure than the approximation supplied as
input.
So the goal of these algorithms is to perturb the input
by at most $\eta$ so as to find the matrix or pencil of
as high a codimension as possible. The algorithm is said to {\bf fail}
if there is another perturbation of size at most $\eta$ which would raise
the codimension even further.
Therefore, we need to understand how the algorithm produces outputs
of each codimension, which is explained in this paper, although this is
just a first step to explaining the failures.
In particular, this is why we need to prove a known result
(Theorem \ref{first-t}) using a new technique:
staircase form. We believe the dimension count for the matrix pencil
case (Theorem \ref{second-t}) is new.











\section{Main Results}


\begin{theorem}
\label{first-t}
The codimension of the orbit of a given matrix $A$ is
$$c_{\rm Jor}=
\sum_\lambda (q_1(\lambda)+3q_2(\lambda)+5q_3(\lambda) + \ldots),$$
where $q_1(\lambda) \ge q_2(\lambda) \ge q_3(\lambda) \ge \ldots$, denotes the 
sizes of the Jordan blocks of
$A$ corresponding to $\lambda$. 
\end{theorem}


\begin{theorem}
\label{second-t}
The codimension of the orbit of $A-\lambda B$ depends only on
its Kronecker structure. This codimension can be computed as the
sum of separate codimensions as given in the table below.
\end{theorem}

This equation is expressed more compactly in Equation \ref{compact}
in the next section.
Section \ref{examples}  provides examples of how to use these formulas.
Readers already familiar with the Kronecker form may 
wish to proceed directly to  Section
\ref{examples} before reading the proofs. 


%\begin{table}
\boxer{
\begin{center}
\sc{Breakdown of the codimension count:}
\end{center}
The codimension of the orbit of $A-\lambda B$ depends only on its
Kronecker structure.  It can be computed as the sum
$c_{\rm Total} = c_{\rm Jor} + c_{\rm Right} + c_{\rm Left} + c_{\rm Jor,Sing} +
c_{\rm Sing}$, whose components are defined as: 

\begin{enumerate}
\item The codimension of the Jordan structure:
$$c_{\rm Jor} = \sum_\lambda (q_1(\lambda)+3q_2(\lambda)+5q_3(\lambda) + \ldots),$$
where the sum is over all eigenvalues as in Theorem \ref{first-t},
including the infinite eigenvalue if it is present.

\item The codimension of the $L$ singular blocks:
$$c_{\rm Right} = \sum_{j&gt; k} (j-k-1),$$
where the sum is taken over all pairs of  
blocks $L_j$ and $L_k$ for which $j&gt;k$.

\item The codimension of the $L^T$ singular blocks:
$$c_{\rm Left} = \sum_{j&gt; k} (j-k-1),$$
where the sum is taken over all pairs of  
blocks $L_j^T$ and $L_k^T$ for which $j&gt;k$.

\item The codimensions due to interactions of the Jordan structure 
with the singular blocks:
$$c_{\rm Jor,Sing} = \mbox{(size of Jordan structure)(number of singular blocks)}.$$
Here 
the number of singular blocks counts both the left and the right
blocks.

\item The codimensions due to interactions between $L$ and $L^T$ 
singular blocks:
$$c_{\rm Sing} = \sum_{j,k} (j+k+2),$$
where the sum is taken over all pairs of  blocks
$L_j$ and  $L_k^T$.
\end{enumerate}
}
%\caption{
%\protect\parbox[t]{3.0in}
%{Breakdown of the codimension count: \protect\newline
%\hspace*{-0.6in}
%$c_{\rm Total} = c_{\rm Jor} + c_{\rm Right} + c_{\rm Left} + c_{\rm Jor,Sing} +
%c_{\rm Sing}$ \protect\newline
%For examples, see Section 7.
%}}
%\label{codim-table}
%\end{table}


These are complex codimensions, but the answers are correct
for real codimensions when the matrices or matrix pencils have 
real Jordan or Kronecker forms. For the rest of this paper
all dimensions will be complex dimensions (half the number of
real dimensions).

\section{Mathematical Preliminaries and Notation}

\subsection{Matrix Canonical Forms}

The basic notation in this area has been reinvented by
many authors.  So as to make this work self-contained and also to fix notation,
we review the basic definitions.  Further information may be found in
standard matrix theory   texts such as \cite{gantmacher} or \cite{macduffee}.

Given a matrix $A$ that has only one eigenvalue $\lambda$ it is always possible
to find a similarity that transforms $A$ into the form
\be
\label{Jordan}
J^\lambda(A)=\diag{J_{q_1}^\lambda,J_{q_2}^\lambda,\ldots}
\ee
where $J_q^\lambda$ is a $q$ by $q$ matrix with $\lambda$ on the diagonal
and $1$ on the superdiagonal known as a {\bf  Jordan block}.

For an arbitrary matrix, it is always possible to find a similarity 
that transforms $A$ into a union of blocks of the form
(\ref{Jordan}):
\be
\label{full-Jordan}
J(A)=\diag{J^{\lambda_1}(A),J^{\lambda_2}(A),\ldots},
\ee
where $\lambda_1,\lambda_2$ denotes the distinct eigenvalues of $A$.

To fix the order of the Jordan blocks within (\ref{Jordan}),
we assume $$q_1(\lambda)\ge q_2(\lambda) \ge \ldots,$$ but
we do not fix the order of the eigenvalues:

\begin{defn}
The matrix $J(A)$ defined up to eigenvalue orderings is known as
the {\bf Jordan Canonical Form} of $A$.
\end{defn}


\begin{defn}
The sequence of numbers $(q_i(\lambda))$  defined above
gives the sizes of the  Jordan blocks for the eigenvalue $\lambda$.
They are known as the {\bf  Segre characteristics} of $A$ relative to
$\lambda$.
\end{defn}

It is sometimes convenient to think of this as an infinite
sequence with $q_j(\lambda)=0$ for $j&gt;$(the number of Jordan
blocks corresponding to $\lambda$).
 
\begin{defn}
The {\bf elementary divisors} of the matrix
$A-xI$ are the polynomials $(\lambda-x)^{q_i(\lambda)}$ 
in the indeterminate $x$, where  $\lambda$ is an eigenvalue 
of $A$ and ${q_i(\lambda)}$ is a  Segre characteristic
corresponding to $\lambda$.
\end{defn}


\begin{defn}
\label{inv-fac}
The {\bf invariant factors } of the matrix
$A-xI$ are the polynomials $P_i(x)=\prod_{\lambda} (\lambda-x)^{q_i(\lambda)}$. 
It follows that if we let $p_i$ denote
the degree of the $i$th invariant factor then
$$p_i=\sum_\lambda q_i(\lambda).$$
\end{defn}

Of course $n=\sum p_i$ because this counts the sizes of all the Jordan
blocks of all the eigenvalues of $A$.


Some authors (see \cite{macduffee} pages 43 and 93) consider 
the quantity $m_i$ defined as the  degree of the greatest common
divisor of
all the $i$ by $i$ minors of the linear matrix polynomial
$A-\lambda I$.  
It can be shown that 
$m_i=p_{n+1-i}+\ldots+p_n$.



\begin{defn}
The {\bf nullity} of an $n$ by $n$  matrix $A$ is 
$n-{\rm rank}(A)$.  For $m$ by $n$ matrices the row nullity and
the column nullity are $m-{\rm rank}(A)$ and $n-{\rm rank}(A)$ respectively.
\end{defn}

\begin{defn}
Let $w_j(\lambda)$ denote the
difference 
$$
{\rm nullity}(A-\lambda I)^j-
{\rm nullity}(A-\lambda I)^{j-1}
\equiv
{\rm rank}(A-\lambda I)^{j-1}-
{\rm rank}(A-\lambda I)^j .
$$
The numbers $w_j(\lambda)$ are  the 
{\bf Weyr characteristics} of $A$ relative to $\lambda$.
\end{defn}

It turns out that the number of blocks $J_q^\lambda$ with $q \ge j$ is
exactly $w_j(\lambda)$. The dimension of the nullspace
of $(A-\lambda I)$ is $w_1(\lambda)$
(\cite{gantmacher,macduffee}).

The following lemma is critical for the construction of the
staircase algorithm.

\begin{lemma}
\label{stairlemma}
Let $Q$ be any unitary  matrix whose first $w_1$ columns
span the nullspace of $A-\lambda I$. Then
$$Q^TAQ=
\bordermatrix{
&amp;w_1&amp; n-w_1 \cr
&amp; \lambda I &amp; S \cr
&amp; 0&amp; \hat{A} \cr}
$$
where $\hat{A}$ is an $n-w_1$ by $n-w_1$ matrix. 
With the deletion of $w_1(\lambda)$,
the Weyr characteristics of $\hat{A}$ are the same as that of 
$A$.  In particular, the Weyr characteristics of the other
eigenvalues are unchanged.
\end{lemma} 

\noindent
{\bf Proof Idea} \\
Without loss of generality we may assume that $Q^TAQ$ is
already a (row and column permutation of a) Jordan form. 
The  Jordan structure of $\hat{A}$ is the same as the Jordan
structure of $A$ except that every Jordan block of $\hat{A}$
corresponding to the eigenvalue $\lambda$ is exactly
one dimension smaller. \qed





Let $A-\lambda B$ be an $m$ by $n$ matrix pencil.
(When discussing the Kronecker case, $\lambda$ is always
an indeterminate.)
It is possible to find 
an equivalent pencil Kron$(A-\lambda B)$ 
in the Kronecker Form:
\be
{\rm Kron }(A-\lambda B)=
\diag{L_{\epsilon_1},\ldots,L_{\epsilon_g},
L^T_{\eta_1},\ldots,L^T_{\eta_h},J,J^\infty }.
\ee
The $L_\epsilon$ blocks are $\epsilon$ by $\epsilon+1$
rectangular blocks with $\lambda$ on the diagonal and $1$
on the superdiagonal.
The $L_\eta^T$ blocks are $\eta+1$ by $\eta$,
with $\lambda$ on the diagonal, and $1$ on the subdiagonal.
The $\epsilon$ and $\eta$ 
(sometimes referred to as the size)
can be $0$, leading to 0 columns and
rows respectively.
The $J$ block is of the form (\ref{full-Jordan})
with the addition of $\lambda I$. 
This constitutes the Jordan structure of the finite eigenvalues.
The $J^\infty $ block is the union of blocks of size
$q_i(\infty )$ each of which has 1 on the main diagonal
and $\lambda$ on the superdiagonal.
This constitutes the Jordan structure corresponding to
the infinite eigenvalue.
Frequently there will be no need to distinguish between the
finite and infinite eigenvalues. Indeed, with an appropriate
M\"{o}bius transformation sending $A-\lambda B$ to
$(\alpha A +\beta B)-\lambda(\gamma A+\delta B)$,
all eigenvalues may be assumed finite.


The $L$ and $L^T$ blocks constitute the {\bf singular}
part of the pencil.  The Jordan structure for finite and
infinite eigenvalues constitutes the {\bf regular}
part of the pencil.
The Segre characteristics remain well defined for a matrix
pencil, but we must include the characteristics for the infinite
eigenvalue as well. 




\begin{defn}
Let $$0 \le \epsilon_1 \le \epsilon_2 \le \ldots \le \epsilon_g$$
 denote the sizes of the $g$ $L$ 
blocks of a pencil, and let
$$0 \le \eta_1 \le \eta_2 \le \ldots \le \eta_h$$ denote the sizes of the
$h$ $L^T$ blocks.
Then the numbers $\epsilon_i$ are known as the 
{\bf column minimal indices}, while the $\eta_i$ 
are the {\bf row minimal indices}.
\end{defn}


We can now recast Theorem \ref{second-t} using the notation
from the previous definitions. 
The codimension of the orbit of $A-\lambda B$ can be written compactly as 
\boxer{
\begin{eqnarray}
\label{compact}
\lefteqn{\mbox{\hspace{-0.4in}cod(orbit($A-\lambda B$))}=
(p_1+3p_2 +5p_3+\ldots)+
(g+h)\sum p_i
} \nonumber \\
&amp; &amp; 
+\sum_{\epsilon_i&gt; \epsilon_j}(\epsilon_i-\epsilon_j-1)+
\sum_{\eta_i&gt;\eta_j}(\eta_i-\eta_j-1)+
\sum_{i,j}(\epsilon_i+\eta_j+2), 
\end{eqnarray}
}
where the $p_i$ include any infinite eigenvalue blocks.

\subsection{Conjugate Partitions}

The Weyr characterists and the Segre characterists of a matrix for
a given eigenvalue are closely related.

\begin{defn}
Let $k_1 \ge k_2 \ge k_3 \ge \ldots \ge 0$ be a partition 
of the positive  integer $k$ (i.e. $k=k_1+k_2+\ldots$).
Let $l_j$ denote the number of $k_i$ that are greater than or
equal to $j$.  Then the $l_j$ form a partition of $k$ known
as the {\bf conjugate partition} of the $k_i$.
\end{defn}

It is easy to verify that the property of being a conjugate
partition is symmetric.
For example, 17=6+6+3+1+1=5+3+3+2+2+2 are conjugate partitions of
17.  This is easy to verify by reading the diagram below
(known as a Ferrers diagram) vertically and horizontally:

\begin{center}
\begin{tabular}{c|c|c|c|c|c|}
\multicolumn{1}{c}{} &amp;
\multicolumn{1}{c}{6} &amp;
\multicolumn{1}{c}{6} &amp;
\multicolumn{1}{c}{3} &amp;
\multicolumn{1}{c}{1} &amp;
\multicolumn{1}{c}{1} \\ \cline{2-6}
5 &amp;.&amp;.&amp;.&amp;.&amp;. \\ \cline{2-6}
3 &amp;.&amp;.&amp;.\\ \cline{2-4} 
3 &amp;.&amp;.&amp;.\\ \cline{2-4}
2 &amp;.&amp;.\\ \cline{2-3}
2 &amp;.&amp;.\\ \cline{2-3}
2 &amp;.&amp;.\\ \cline{2-3}
\end{tabular}
\end{center}


The idea of the conjugate partition is very simple, yet 
very powerful. It allows the interchange of  summations:
$$\sum_i \sum_j^{k_i} f(i,j) = \sum_j \sum_i^{l_j} f(i,j),$$
where $f(i,j)$ is any function of $i$ and $j$, and the $k_i$ and $l_j$
are conjugate partitions.

\begin{lemma}
\label{conjlemma}
The  Weyr characteristics and the Segre
characteristics of a matrix corresponding to a particular eigenvalue
are conjugate partitions.
\end{lemma}

The proof of this lemma is evident from the Jordan form of the matrix
\cite[p.74]{macduffee}.



\subsection{A Fundamental Codimension Count}

Our codimension counts for the Jordan and Kronecker form are
built up from the fundamental Lemma~\ref{counting-l}.
To state it, we need to introduce a little notation from manifold theory.

\ignore{
\begin{lemma}
\label{counting-l}
The codimension of the set of $m$ by $n$ matrices with
rank $r$ is $(m-r)(n-r)$,
the product of the row and column nullities.
When $m=n$ the codimension is then the square of the nullity.
\end{lemma}

\proof
Let $M_{m,n,r}$ be the set of $m$ by $n$ matrices with the two properties that 
the leading $r$  by $r$ principal minor is nonzero, while this minor's 
$(m-r)$ by $(n-r)$ Schur complement is the zero matrix; all such matrices
are of the form 
$\left[ \begin{array}{cc} B &amp; C \\ D &amp; DB^{-1} C \end{array} \right]$
where $B$ is $r$ by $r$. $M_{m,n,r}$ is thus clearly a manifold of
codimension $(m-r)(n-r)$.
Let $A$ be an $m$ by $n$ matrix with rank $r$.  Without loss of
generality, we can order the rows and columns so that $A \in M_{m,n,r}$.
this identification forms a chart for the rank $r$ matrices near $A$,
proving the lemma. \qed

We proceed to construct a more convenient local chart
for a square $n$ by $n$ matrix $A$  with rank $r$.
}

\begin{defn}
The set of $k$ dimensional subspaces
of $n$ dimensional space along with its natural manifold structure
forms the {\bf Grassmann manifold}  denoted $G_k(n)$.
\end{defn}

The Grassman manifold and its dual $G_{n-k}(n)$ are isomorphic
of dimension $k(n-k)$. In Lemma~\ref{counting-l}
we will need a {\bf full-rank parameterization} for $G_{n-k}(n)$, which
we construct as follows. (Recall that a {\bf chart} for a 
complex $d$-dimensional 
manifold $M$ is an open neighborhood $U$ in $C^{d}$ plus a homeomorphism from
$M$ into $U$. A full rank parameterization is the inverse of this
homeomorphism.)
Because of the action of the unitary
group, it suffices to specify a local full rank parameterization near any 
one element, say $E_k$, the one generated by the first $k$ coordinate vectors.
We create a parameterization from unitary matrices of the form
\be
\label{grass-chart}
Q_0=
\left(
\begin{array}{cc}
I &amp; -R^{*}\\
R &amp; I \\ 
\end{array}
\right)
\left(
\begin{array}{cc}
I+R^*R  &amp; 0\\
0 &amp; I+RR^* \\ 
\end{array}
\right)^{-1/2},
\ee
where $R$ is $n-k$ by $k$.
The homeomorphism maps complex $n-k$ by $k$ matrices $R$ to the
span of the first $k$ columns of $Q_0$.
If $Q$ is any fixed unitary matrix, the homeomorphism from 
$R \in C^{n-k \times k}$
to the space spanned by the first $k$ columns of 
$QQ_0$ provides the parameterization mapping from a neighborhood of the origin
in $C^{n-k \times k}$ to a neighborhood 
in $G_k (n)$ of the space spanned by the first $k$ columns of $Q$.

\begin{lemma}
\label{counting-l}
The set of $m$ by $n$ matrices with rank $r$ is a manifold with codimension
$(m-r)(n-r)$.
\end{lemma}
\proof
We construct a parameterization whose image is a neighborhood of a particular
$m$ by $n$ rank $r$ matrix $A$ as follows.
A neighborhood of the origin in the product space
$C^{r \times n-r} \times C^{m \times r}$  will serve as a domain for the
parameterization.
Let $Q$ be any unitary matrix whose first $n-r$ columns span
the nullspace of $A$, so that $AQ = [0 M]$ is zero in its first $n-r$ 
columns and its last $r$ columns $M$ have full rank.
Let $Q_0$ be as in (\ref{grass-chart}), with $k=n-r$.
Then the map from $(R,T) \in C^{r \times n-r} \times C^{m \times r}$ to
$[0,M+T]Q_0^*Q^*$ is the desired homeomorphism. If $m=n$, then we may
equally well use the homeomorphism mapping $(R,T)$ to 
$QQ_0 [0,M+T]Q_0^* Q^*$. Thus the dimension is $r(n-r)+mr$, and the
codimension is $mn-r(n-r)-mr = (m-r)(n-r)$.
\qed

We graphically depict the independent parameters as follows:
\renewcommand{\arraystretch}{0}
\be
\label{box1}
\begin{array}{c}
\iboxit{.43}{.25}{}
\iboxit{.3}{.25}{$n-r$}
\iboxit{1}{.25}{$r$}\\
\iboxit{.43}{.3}{$m-r$}
\boxit{.3}{.3}{\rule{.3in}{.3in}}
\boxit{1}{.3}{S} \\
\iboxit{.43}{1}{$r$}
\boxit{.3}{1}{R}   \boxit{1}{1}
{$\hat{A}$}
\end{array}
\ee
\renewcommand{\arraystretch}{1}


Here $R$ refers to the coordinates that define the null space, while
$T=[S^T, \hat{A}^T ]^T$ is the matrix in $C^{m \times r}$.
The black square in the upper left clearly indicates the codimension of 
$(m-r)(n-r)$.

Later, we will take advantage of this construction to recursively
construct further submanifolds by placing analogous rank constraints 
on $\hat{A}$, so that $\hat{A}$ still lies in a small neighborhood 
of the origin. Therefore, it will be easy to see
that we need merely add the codimensions of our constraints at each level
in order to compute the overall codimension of the final submanifold.
Indeed, the parameterization
of Lemma 3.3 is constructed explicitly at each step of the staircase
algorithm.

\section{Proofs of Theorem \protect\ref{first-t}
(Codimension Count for Jordan Form)} 


\subsection{Classical Proof}
Consider conjugating the matrix $A$ by 
$I+\delta X$, where $\delta$ is a small scalar.
This yields
$$
(I+ \delta X)^{-1} A (I+ \delta X) = A + \delta (XA-AX) + O( \delta^2 ),
$$
{from} which it is evident that the tangent space to 
orbit($A$) at $A$ consists of the matrices of the
form $XA-AX$.  The dimension of the orbit is equal to the
dimension of the tangent space so that the codimension of
the orbit is equal to the dimension of the nullspace of
the mapping that sends $X$ to $XA-AX$.  The codimension of the orbit
is then the number of linearly independent solutions to
$AX=XA$.
This number of  solutions is well known to be 
$$p_1+3p_2+5p_3+\ldots.$$
(See
page 222 of volume 1 of \cite{gantmacher}.)\qed

An
alternative expression for the number of solutions to 
$AX=XA$ is
$$n+2 (m_1+\ldots+m_{n-1}) $$
as given in \cite{macduffee}.
According to the remark following Definition \ref{inv-fac},
these expressions are identical.


\subsection{Outline of the Staircase Algorithm}

The staircase algorithm for the computation of the Jordan
Canonical Form appears in \cite{GVL,GW,KR,kub,Ru}.
Some references  refer to ``stairacase form''
to mean a slightly different concept \cite{brualdi,turnbull}. 
The staircase algorithm of interest to us computes
the Weyr characteristics. It
is built recursively upon the idea in Lemma
\ref{stairlemma}.  

$   $ \\
\noindent
{\em Staircase algorithm for computing the Jordan form for eigenvalue $\lambda$}
\begin{tabbing}
jnk \= jnk \= jnk \= jnk \kill
 \&gt; $i=0$ \\
 \&gt; $A_{tmp} = A  - \lambda I$ \\
 \&gt; while $A_{tmp}$ not full rank \\
 \&gt; \&gt; $i=i+1$ \\
 \&gt; \&gt; Let $n' = \sum_{j=1}^{i-1}w_j$ and $n_{tmp} =n-n' = dim (A_{tmp})$ \\
 \&gt; \&gt; Compute an $n_{tmp}$ by $n_{tmp}$ unitary matrix $Q$ whose leading $w_i$
       columns span the null space \\
 \&gt; \&gt; \&gt; of $A_{tmp}$ \\
 \&gt; \&gt; $A = {\rm diag}(I_{n'} , Q^* ) \cdot A \cdot {\rm diag}( I_{n'} , Q )$ \\
 \&gt; \&gt; Let $A_{tmp}$ be the lower right $n_{tmp}-w_i$ by $n_{tmp}-w_i$ corner
       of $A$ \\
 \&gt; \&gt; $A_{tmp} = A_{tmp} - \lambda I$ \\
 \&gt; endwhile
\end{tabbing}

The final $A$ is easily seen to be unitarily similar to the initial $A$.
The final $A$ is in staircase form,
as illustrated with the following example:

\begin{center}
\begin{tabular}{c|c|c|c|c|c|}
\multicolumn{1}{c}{} &amp; \multicolumn{1}{c}{$w_1$} &amp;
\multicolumn{1}{c}{$w_2$} &amp; \multicolumn{1}{c}{$w_3$} &amp; 
\multicolumn{1}{c}{$w_4$} &amp;
\multicolumn{1}{c}{$n^\prime$} \\ \cline{2-6}
$w_1$ &amp; $\lambda I$  &amp; $A_{12}$ &amp; $*$ &amp; $*$ &amp; $*$ \\ \cline{2-6} 
$w_2$ &amp; \multicolumn{1}{c|}{} &amp;$\lambda I$ &amp; $A_{23}$ &amp; $*$ &amp; $*$ \\ \cline{3-6}
$w_3$ &amp; \multicolumn{2}{c|}{}&amp;$\lambda I$  &amp; $A_{34}$ &amp; $*$ \\ \cline{4-6}
$w_4$ &amp; \multicolumn{3}{c|}{} &amp;$\lambda I$ &amp; $*$  \\ \cline{5-6}
$n^\prime$ &amp; \multicolumn{4}{c|}{} &amp; $A'$ \\ \cline{2-6}
\end{tabular}
\end{center}


Here, the superdiagonal blocks $A_{i,i+1}$ (the ``stairs'') and also 
$A^\prime - \lambda I$ are of full column rank, while the staircase region in the lower
triangle is entirely $0$.  If $A$ has only one eigenvalue
$\lambda$ then $n^\prime$ is $0$ and the last block row and block column
do not appear.
If $A$ has other eigenvalues $\lambda'$, then the staircase form
corresponding to the remaining eigenvalues may be extracted
by applying the same algorithm to $A'$.

An easy observation is that 
\begin{lemma}
The $w_i$ computed by the staircase algorithm for the
eigenvalue $\lambda$ are the Weyr characteristics corresponding
to the eigenvalue $\lambda$.
\end{lemma} 


\subsection{Second  Proof of Theorem \ref{first-t}}

Let $A$ be any matrix. 
We will show that the  staircase algorithm, in effect, creates
a parameterization for an open neighborhood
$N(A)$ of $A$ on the manifold orbit($A$).
Let $\lambda$ be an eigenvalue of $A$.  Then $A-\lambda I$ has
rank $n-w_1$. The independent parameters portrayed in
(\ref{box1}) may be used as a parameterization for a neighborhood 
of $A-\lambda I$
on the manifold of rank $n-w_1$ matrices.  Lemma 3.1 tells us that
we have a parameterization
for orbit($A$) if we make further assumptions
on the Jordan structure of $\hat{A}$.  
Notice that in a small enough neighborhood of $A$, the last
$n-r$ columns of the staircase form are full rank.
It is important to observe the independence of the $w_1(n-w_1)$
parameters in $R_1$ from the $w_1(n-w_1)$ parameters of $S_1$ and
the as of yet uncounted parameters in $\hat{A}$.
The first eigenvalue $\lambda$ is ``fully parameterized'' when
$\hat{A} - \lambda I$ has full rank.  The parameters are pictorially
depicted below in an example that recurs two more times before
$\hat{A} -  \lambda I$ has full rank.

\begin{center}
\begin{picture}(1.45,1.75)(0,-.2)
\put(0,-0.2){\makebox(.3,.2){$w_1$}}
\put(.3,-0.2){\makebox(.25,.2){$w_2$}}
\put(.55,-0.2){\makebox(.2,.2){$w_3$}}
\put(0,1.15){\framebox(.3,.3){\rule{.3in}{.3in}}}
\put(.75,0){\framebox(.7,.7){$\hat{A}$}}
\put(.3,.9){\framebox(.25,.25){\rule{.25in}{.25in}}}
\put(.55,.7){\framebox(.2,.2){\rule{.2in}{.2in}}}
\put(0,0){\framebox(.3,1.15){$R_1$}}
\put(.3,0){\framebox(.25,.9){$R_2$}}
\put(.55,0){\framebox(.20,.7){$R_3$}}
\put(.3,1.15){\framebox(1.15,.3){$S_1$}}
\put(.55,.9){\framebox(.9,.25){$S_2$}}
\put(.75,.7){\framebox(.7,.2){$S_3$}}
\put(1.45,1.15){\makebox(.2,.3){$w_1$}}
\put(1.45,.9){\makebox(.2,.25){$w_2$}}
\put(1.45,.7){\makebox(.2,.2){$w_3$}}
\end{picture}
\end{center}

This parameterization process is repeated on $\hat{A}$ with a new eigenvalue
shift in an identical manner.  This repetition continues until
$\hat{A}$ does not exist.
The areas of the black squares in the figure above indicate the codimension
that we might attribute to the eigenvalue $\lambda$.
This codimension is then
\begin{eqnarray*}
\sum_i w_i^2 &amp;=&amp;\sum_i \sum_{k=1}^{w_i} (2k-1) \\
&amp;=&amp; \sum_k \sum_{i=1}^{q_k} (2k-1) \\
&amp; =&amp; \sum_k (2k-1)q_k,
\end{eqnarray*}
using the fact that the Weyr and Segre characteristics are
conjugate partitions. 

The total codimension for the entire Jordan structure of $A$ is obtained
by summing over all the eigenvalues because of the independence of the
parameters. \qed









\section{Tangent Space Proof of Theorem \protect\ref{second-t}}


We include two proofs both of which we believe to be new.  The first proof 
requires  counting  the number of independent solutions to 
two  simultaneous
matrix equations derived by analyzing the tangent space, 
while the second proof (in Section \ref{stairsect})  requires an analysis
of the staircase algorithms for the Kronecker canonical form.


Consider an orbit preserving transformation  of the $m$ by $n$ pencil
$A-\lambda B$ obtained by multiplying on the left
by $I+\delta X$ and the right by $I-\delta Y$,
where $\delta$ is a small scalar.  This yields 
$A-\lambda B+\delta(X(A-\lambda B)-(A-\lambda B)Y)+O(\delta^2),$
from which it is evident that the
tangent space to the orbit of the
pencil consists of the pencils that can be represented in the form 
\be
\label{tans}
f(X,Y)=X(A-\lambda B)-(A-\lambda B)Y,
\ee
where $X$ is an $m$ by $m$ matrix
and $Y$ is an $n$ by $n$ matrix.   


Since (\ref{tans}) maps a space of dimension $m^2+n^2$ linearly into a space
of dimension $2mn$, the dimension of the image space is   
$m^2+n^2 -d$, where $d$ is the dimension of the kernel of $f(X,Y)$,
and so the codimension is 
\be
2mn-(m^2+n^2-d)=d-(m-n)^2.
\label{dmn2}
\ee
The term $(m-n)^2$ represents extra baggage 
due to our consideration of rectangular pencils.
As in the Jordan case, we need to calculate $d$, the number of
linearly independent solutions to $f(X,Y)=0$. 
This  can be written as the two simultaneous equations
\be
\label{9}
XA=AY \mbox{  and  } XB=BY.
\ee

Unfortunately, we can not simply quote a classical count
of the number of independent solutions to (\ref{9})
as we were able
to do in Section 4.1.
However since
$$Pf(X,Y)Q^{-1}=(PXP^{-1})P(A-\lambda B)Q^{-1}-P(A-\lambda B)Q^{-1}(QYQ^{-1}),$$
it follows that
the number of
linearly independent 
solutions to $f(X,Y)=0$ depends only on the Kronecker structure of $A-\lambda B$.
Thus, we assume that $A-\lambda B$ is already in Kronecker canonical form
$M={\rm diag}(M_1,M_2,\ldots)$.
The Kronecker case 
is more complicated than the Jordan case due to the 
greater number of possibilities for the Kronecker structure $M$.


We partition the equation $XM=MY$ conformally with
$M={\rm diag}(M_1,M_2,\ldots)$ so that
$X_{ij}M_j = M_i Y_{ij}$, where
$M_k$ is $m_k$ by $n_k$,
$X_{ij}$ is $m_i$ by $m_j$,
and $Y_{ij}$ is $n_i$ by $n_j$:
$$
\bordermatrix{
&amp;m_1&amp;m_2 \cr
m_1&amp;X_{11}&amp;X_{12}\cr
m_2&amp;X_{21}&amp;X_{22}\cr
}
\bordermatrix{
&amp;n_1&amp;n_2 \cr
m_1&amp;M_1&amp;\cr
m_2&amp;&amp;M_2 \cr
}
=
\bordermatrix{
&amp;n_1&amp;n_2 \cr
m_1&amp;M_1&amp;\cr
m_2&amp;&amp;M_2 \cr
}
\bordermatrix{
&amp;n_1&amp;n_2 \cr
n_1&amp;Y_{11}&amp;Y_{12}\cr
n_2&amp;Y_{21}&amp;Y_{22}\cr
}
$$


The next lemma allows us to compute the quantity $d$ 
mentioned before  Equation
(\ref{9})
as the sum
of the number  $d_{ij}$ of independent solutions 
of
$X_{ij}M_j = M_i Y_{ij}$
in the variables $X_{ij}$ and $Y_{ij}$.


\begin{lemma}
In terms of the  above notation 
$$d=\sum_{i,j} d_{ij}.$$
\end{lemma}

\proof
As is evident from the example
$$
\left(
\begin{array}{cc}
X_{11} &amp; X_{12} \\ 
X_{21} &amp; X_{22} \\
\end{array}
\right)
\left(
\begin{array}{cc}
 M_1  &amp; \\ &amp;  M_2  \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
 M_1  &amp; \\ &amp;  M_2  \\
\end{array}
\right)
\left(
\begin{array}{cc}
Y_{11} &amp; Y_{12} \\ 
Y_{21} &amp; Y_{22} \\
\end{array}
\right) ,
$$
the equations $X_{ij}M_j=M_iY_{ij}$, $i=1,2,\ldots$, $j=1,2,\ldots$
are all mutually independent.

\qed


Given any two blocks, $M_i$ and $M_j$ (we allow $i=j$ here)
we define their {\bf interaction} and the {\bf cointeraction}: 

\begin{defn}
Let $M_i$ be  $m_i \times n_i$ and let $M_j$ be $m_j \times n_j$.
Let $X$ be an arbitrary $m_j \times m_i$ matrix and $Y$ be an arbitrary
$n_j \times n_i$ matrix.  
We define
the {\bf interaction} $d_{ij}$ of
$M_i$ with $M_j$ as the dimension of the linear space $\{X,Y\}$ such
that $XM_j=M_iY$. 
We define the {\bf cointeraction}
of $M_i$ with $M_j$ as
$c_{ij}=d_{ij}-(m_i-n_i)(m_j-n_j)$.
We also consider the {\bf combined cointeraction} which
we define as $c_{ij}+c_{ji}$ when $i \ne j$, and simply $c_{ii}$
when $i=j$.
\end{defn}

Notice that the combined cointeraction has a different definition
depending on whether $M_i$ and $M_j$ are distinct blocks
(even if they happen to be equal) on one hand, or if $i=j$
on the other hand. Strictly speaking the combined cointeraction
is a function of $M_i$, $M_j$, and the Kronecker delta $\delta_{ij}$.


\begin{lemma}
The codimension of a matrix pencil  $M$ with Kronecker structure
${\rm diag}(M_1,M_2,\ldots)$ is
the sum of cointeractions of $M_i$ with $M_j$ for
all combinations of $i$ and $j$.
\end{lemma}


\proof
The sum of the cointeractions is
$$
\sum_{i,j} \left\{ d_{ij}-(m_i-n_i)(m_j-n_j) \right\}=
d -(m-n)^2
$$
as in Equation
(\ref{dmn2}).
\qed 








We must now  count the number of linearly independent solutions
(and the associated combined cointeractions) to
the following equations:
\begin{itemize}
\item{$XL_j=L_kY$ and $XL_j^T=L_k^TY$}
\item{$XL_j=L_k^TY$ and $XL_j^T=L_kY$}
\item{$XJ=L_jY$ and $XL_j=JY$ and related structures}
\item{$XJ=JY$}
\end{itemize}
where $J$ denotes the non-singular structure of the pencil. 





\subsection{$XL_j=L_kY$ and $XL_j^T=L_k^TY$}\label{5.1.1}

Consider the equation $XL_j=L_kY$, where $X$ is an unknown
$k$ by $j$ matrix and $Y$ is an unknown $k+1$ by $j+1$ matrix.
This equation is equivalent to the two equations
\begin{eqnarray*}
X[0 \ I_j]=[0 \ I_k ]Y \\
X[I_j \  0]=[I_k \ 0]Y,
\end{eqnarray*}
where $0$ denotes a column of zeros.  These 
two equations
are in turn equivalent
to the conditions  
\begin{eqnarray*}
&amp;X_{\alpha,\beta}=Y_{\alpha,\beta}, \ \alpha=1,\ldots,k, \ \beta=1,\ldots,j &amp; \\
&amp;Y_{\alpha,\beta}=Y_{\alpha+1,\beta+1}, \ \alpha=1,\ldots,k, \ \beta=1,\ldots,j &amp; \\
&amp;Y_{\alpha+1,1}=Y_{\alpha,j+1}=0, \ \alpha=1,\ldots,k &amp; \\
\end{eqnarray*}


If $j&lt;k$ there is only the trivial solution $X=0$ and $Y=0$. 
The interaction is $0$, so that the cointeraction is
$0-(j-(j+1))(k-(k+1))=-1$.

If $j\ge k$ then there are non-trivial solutions:
$Y$ can be any upper triangular Toeplitz matrix with
$1+j-k$ diagonals starting from the main diagonal. 
$X$ is then obtained from $Y$ by omitting the first row and column.
The interaction of $L_j$ with $L_k$ is $1+j-k$
so that the cointeraction is
$(1+j-k)-1=j-k$.

We conclude that the
combined  cointeraction of $L_j$ and $L_j$ is $0$, while 
if $j &gt; k$ then  the combined cointeraction of $L_j$ with $L_k$ is
$j-k-1$. 


Taking the transpose and interchanging the roles of $j$ and $k$,
we see that the 
same result holds  for blocks of the form $L_j^T$.
We also remark that the
analysis is correct even if $j$ or $k$ is $0$.

\subsection{ $XL_j=L_k^TY$ and $XL_j^T=L_kY$}

We proceed in a manner similar to the previous case.
Consider the equation
$XL_j=L_k^TY,$ where $X$ is an unknown $k+1$ by $j$ matrix
and $Y$ is an unknown $k$ by $j+1$ matrix.  The equations 
are equivalent to

\begin{eqnarray*}
&amp;X_{\alpha,\beta}=Y_{\alpha,\beta}, \ \alpha=1,\ldots,k, \ \beta=1,\ldots,j &amp; \\
&amp;Y_{\alpha+1,\beta}=Y_{\alpha,\beta+1}, \ \alpha=1,\ldots,k, \ \beta=1,\ldots,j &amp; \\
&amp;Y_{\alpha,1}=Y_{\alpha,j+1}=0, \ \alpha=1,\ldots,k &amp; \\
&amp;X_{k+1,\beta}=0, \beta=1,\ldots,j &amp; \\
\end{eqnarray*}


This  has only the trivial solution 
$X=Y=0$ so that
the interaction of $L_j$ with $L_k^T$ 
is $0$ and the cointeraction is
$0-(-1)(1)=1$.  


A similar examination of the equation $XL_j^T=L_kY$ shows that
the interaction of $L_j^T$ with $L_k$  is $j+k$ so the
cointeraction is $j+k-(1)(-1)=j+k+1$.
We conclude that the combined cointeraction is $j+k+2$.


\subsection{Jordan Blocks and Singular Blocks}

In one way, the computation involving Jordan blocks is easier
since the interaction is equal to the cointeraction. (This is true
simply because the Jordan block is square.) However, we must now allow
for arbitrary eigenvalues.

Assume that
$J_k$ is a single Jordan block of size $k$ corresponding
to the finite  eigenvalue $e$. (We use $e$ here so that there is no
confusion with the indeterminate $\lambda$.)
We consider solutions to $XJ_k=L_j Y$.
The reader can verify that the dimension of the space of solutions
is $k$.  Indeed the first row of the $j+1$ by $k$ matrix $Y$ can
be chosen arbitrarily and this determines the remaining elements
as follows: $Y_{\alpha 1}=Y_{11}e^{\alpha-1}$, $X$ is obtained from
$Y$ by deleting the last row, and 
$ e Y_{\alpha,\beta}+Y_{\alpha,\beta-1}=Y_{\alpha+1,\beta}$.
An analogous, though simpler argument shows that the case of infinite
eigenvalues gives the same answer. (We can also resort
to a M\"obius transformation as well.)
We conclude that the interaction of $J_k$ with $L_j$ is $k$.

The interaction of $L_j$ with $J_k$ is readily 
shown to be $0$. From 
the equation $XL_j=J_kY,$ we can conclude that $X$ is obtained
from $Y$ by deleting the last column, that the last column of $Y$
is zero, and if the $m$th column of $Y$ is 0, then so is the
$m-1$st column of $X$ and hence so is the $m-1$st column of $Y$.

The cases $XL_j^T=JY$   and $XJ=L_j^TY$ can be reduced to the previous
cases by remembering that if $J$ is a Jordan block, $J^T=PJP$ where
$P$ is the permutation that renumbers indices in backwards order.
For example, the number of independent solutions to
$XL_j^T=JY$ is the same as the number of solutions to
$(Y^TP)(PJ^TP)=(L_jX^TP)$.


\subsection{Jordan Blocks with other Jordan Blocks} 

Let $J+\lambda I $ be the entire non-singular portion of the Kronecker
structure.  If we assume that there are no infinite eigenvalues,
then the equation $X(J+\lambda I)=(J+\lambda I)Y$ implies
$X=Y$ and then we are reduced
to the case $XJ=JX$  in Theorem \ref{first-t}.  We remark that
Theorem \ref{first-t} tells us that there is no interaction
among Jordan blocks with different eigenvalues.

We omit the tedious algebra, but it is possible to show that
an infinite eigenvalue behaves exactly as if it were finite.
(A simpler argument would point out that we can rotate
the Riemann sphere to insure that all the eigenvalues are
finite, without changing the codimension count.)
We conclude that the 
combined cointeractions of the non-singular portion of the pencil
is
exactly as in  Theorem \ref{first-t}.



\subsection {Proof of Theorem \protect\ref{second-t}}

The proof follows from the analysis of the cases
presented in Sections 5.1.1 through 5.1.4. \qed

\section{Proof of Theorem  \protect\ref{second-t}
Based on the Staircase Algorithm}
\label{stairsect}


We begin by reviewing the staircase algorithm. The version we use
has three passes.  Let $A-\lambda B$ be an $m$ by $n$ matrix pencil.  
The first pass produces two sequences of numbers $s_i$ and $r_i$
and returns a pencil $A'- \lambda B'$ with no $L_j$ blocks and no zero 
eigenvalues.  The sequence satisfies
$$s_0 \ge r_0 \ge s_1 \ge r_1 \ge s_2 \ge \ldots,$$   
where
\begin{itemize}
\item {$s_i-r_i=$ the number of $L_i$ blocks and}
\item {$r_i-s_{i+1}=$ the number of $J_{i+1}^0$ blocks.}
\end{itemize}

The algorithm is as follows.

\newpage
\noindent
{\em Staircase algorithm for computing the Kronecker form for the 0 eigenvalue 
and $L_j$ blocks}
\begin{tabbing}
jnk \= jnk \= jnk \= jnk \kill
 \&gt; $i=-1$ \\
 \&gt; $A_{tmp} = A$ \\
 \&gt; while $A_{tmp}$ not full rank \\
 \&gt; \&gt; $i=i+1$ \\
 \&gt; \&gt; Let $n' = \sum_{j=0}^{i-1}s_j$ and $n_i = n-n' = \#cols (A_{tmp})$ \\
 \&gt; \&gt; Let $m' = \sum_{j=0}^{i-1}r_j$ and $m_i = m-m' = \#rows (A_{tmp})$ \\
 \&gt; \&gt; Compute an $n_i$ by $n_i$ unitary matrix $Q$ whose leading 
       $s_i = {\rm nullity} (A_{tmp})$ columns span \\
 \&gt; \&gt; \&gt; the right null space of $A_{tmp}$ \\
 \&gt; \&gt; Let $A =  A \cdot {\rm diag}( I_{n'} , Q )$ and 
           $B =  B \cdot {\rm diag}( I_{n'} , Q )$ \\
 \&gt; \&gt; $B_{tmp} = B(m'+1 \ :\ m \ ,\  n'+1\  :\  n'+s_i)$ \\
 \&gt; \&gt; Compute an $m_{i}$ by $m_{i}$ unitary matrix $P$ whose first
       $r_i = {\rm rank} (B_{tmp})$ rows span \\
 \&gt; \&gt; \&gt; the column space of $B_{tmp}$ \\
 \&gt; \&gt; Let $A =  {\rm diag}(I_{m'} , P ) \cdot A$ and
           $B =  {\rm diag}(I_{m'} , P ) \cdot B$ \\
% \&gt; \&gt; $A_{tmp} = A(m'+r_i+1:m , n'+s_i +1:n)$ \\
 \&gt; \&gt; Let $A_{tmp}$ be the last $m_i - r_i$ rows and $n_i - s_i$ columns of $A$       \\
 \&gt; endwhile
\end{tabbing}

\ignore{
\begin{enumerate}
\item{ Compute $s_0$ = the column nullity of $A$.}
\item{ Postmultiply the pencil by a unitary  $Q$ so that the first $s_0$ 
columns of $A$ vanish.}
\item{ Compute $r_0$ = the rank of the first $s_0$ columns of the transformed 
$B$}
\item{Premultiply the transformed pencil by a unitary  $P$ so that
the lower left $m-r_0$ by $s_0$ submatrix of the transformed $B$ is zero.}
\item{Repeat this on the subpencil in the lower right $
m_1=m-r_0$ rows and $n_1=n-s_0$ 
columns of the transformed pencil,
defining $s_1,r_1,m_2,n_2$, etc.}
\end{enumerate}
}

It is easy to see the final $A - \lambda B$ is unitarily
equivalent to the initial $A - \lambda B$.
We illustrate the final form of $A- \lambda B$ with the following small example:

\begin{center}
\begin{tabular}{c|c|c|c|c|c|}
\multicolumn{1}{c}{} &amp; \multicolumn{1}{c}{$s_0$} &amp;
\multicolumn{1}{c}{$s_1$} &amp; \multicolumn{1}{c}{$s_2$} &amp; 
\multicolumn{1}{c}{$s_3$} &amp;
\multicolumn{1}{c}{$n^\prime$} \\ \cline{2-6}
$r_0$ &amp; $0-\lambda B_{00}$ &amp; $A_{01}-\lambda B_{01}$ &amp; $*$ &amp; $*$ &amp; $*$ \\ 
         \cline{2-6} 
$r_1$ &amp;  &amp; $0-\lambda B_{11}$ &amp; $A_{12}-\lambda B_{12}$ &amp; $*$ &amp; $*$  \\ 
         \cline{3-6} 
$r_2$ &amp; \multicolumn{2}{c|}{}  &amp; $0-\lambda B_{22}$ &amp; $A_{23}-\lambda B_{23}$ 
      &amp; $*$ \\ \cline{4-6} 
$m'$  &amp; \multicolumn{4}{c|}{}  &amp; $A' - \lambda B'$ \\ \cline{2-6}
\end{tabular}
\end{center}

On completion, the $B_{ii}$ blocks have full row rank, and the 
$A_{i,i+1}$ blocks have full column rank.

The first pass through the inner loop of the algorithm 
postmultiplies $A$ and $B$ by a unitary $Q$ so $A$'s 
leading $s_0 = {\rm nullity}(A)$ columns are 0, 
and then premultiplies $A$ and $B$ by a unitary $P$ so that
$B_{00}$, the leading $r_0$ by $s_0$ submatrix of $B$, is full rank, 
and the remaining rows of the first $s_0$ columns of $B$ are zero.
We then repeat the process on the trailing $m-r_0$ by $n-s_0$ submatrix
of $A- \lambda B$ to get $s_1$ and $r_1$. We continue until
the trailing block of $A$ has full rank (or is null).

Just as with the Jordan form, each step of the algorithm
incrementally builds a parameterization for the set of matrices of a given
Kronecker form. Each step of the algorithm restricts the 
Kronecker form of the pencil to a set of higher codimension. 
The restrictions imposed at each step are independent for the same
reason they were in the Jordan case, so we can just add codimensions.
The increase in codimension at each step is given by
Lemma \ref{counting-l}, as the sum of the
products of the row and column nullities
of submatrices of $A$ and $B$.  
Specifically the $m_i$ by $n_i$ submatrix
of $A$ has column nullity $s_i$, rank 
$n_i-s_i$, row nullity $m_i+s_i-n_i$,
and so by Lemma \ref{counting-l} 
codimension
$(m_i+s_i-n_i)s_i$.  Similarly the codimension due
to $B$ at step $i$ is $ (m_i-r_i)(s_i-r_i)$.
The first pass through the algorithm determines the
$L$ and $J^0$ blocks so that the codimension due to these
blocks
is given by
\be
\label{messy}
\sum_i \left\{ (m_i+s_i-n_i)s_i +(m_i-r_i)(s_i-r_i) \right\}.
\ee
We proceed to show that (\ref{messy}) is the formula given in
Theorem \ref{second-t}. 

For convenience we list our notation:

\begin{center}
\begin{tabular}{ll}
$m_i$ &amp; number of rows in the lower right subpencil  at step $i $
= $m-\sum_{k=0}^{i-1} r_k$ \\
$n_i$ &amp; number of columns 
in the lower right subpencil at step $i$
 = $n-\sum_{k=0}^{i-1} s_k$ \\
$s_i$ &amp; column nullity of $A_{tmp}$ at step $i$ \\
$r_i$ &amp; row rank of $B_{tmp}$ at step $i$ \\
$l_i$ &amp; number of $L_i$ blocks in the original pencil \\
$l_i^\prime$ &amp; number of $L_i^T$ blocks in the original pencil \\
$t_i$ &amp; number of $J^0_i$ blocks in the original pencil\\
$u$ &amp; size of the regular structure corresponding to $\lambda\ne0$.
\end{tabular}
\end{center}

\subsection{Only left singular blocks}

We begin by assuming that our pencil only contains left singular blocks.
Let $l_i$ denote the number of $L_i$ blocks.  It is easy to show
by induction that the algorithm computes
\begin{eqnarray*}
&amp;&amp;m_i=\sum_{j=i}^\infty (j-i)l_j \\
&amp;&amp;n_i=\sum_{j=i}^\infty (1+j-i)l_j \\
&amp;&amp;s_i=\sum_{j=i}^\infty l_j \\
&amp;&amp;r_i=\sum_{j=i+1}^\infty l_j. \\
\end{eqnarray*}

To see this, first check that $m_0=m$ and $n_0=n$.
Indeed it is obvious that $m=\sum jl_j$ because
this counts the $j$ rows in each $L_j$ block.
It is also obvious that $n=\sum (1+j)l_j$ because
this counts the $1+j$ columns of each $L_j$ block.
Just by looking at the form of an $L_j$ block,
we see that each left singular  block makes a contribution of
one to the column nullity of the pencil, thus
$s_0$ is the total number of left singular blocks.
Finally, we have $s_0-r_0=l_0,$ the number of $L_0$ blocks.
To check the validity of the formulas for arbitrary $i$
proceed by induction using the definition and properties
of $m_i$, $n_i$, $r_i$ and $s_i$ listed immediately
above and at the beginning of Section 6.



When there are only left singular
blocks, we see that  expression (\ref{messy}) evaluates
to
\be
\label{alpha}
\alpha=\sum_{i=0}^\infty l_i \sum_{j=i+1}^\infty (j-i-1)l_j.
\ee
This corresponds to the term  $\sum_{\epsilon_i&gt;\epsilon_j}
(\epsilon_i-\epsilon_j-1)$
from (\ref{compact}) using a different notation.
In our current notation, (\ref{alpha}) counts
every pair  $(L_i,L_j)$ for which $j&gt;i$ with the weight $j-i-1$
because there are exactly $l_i l_j$ such pairs.
For example, if we have two $L_1$ blocks and two
$L_5$ blocks, then $\epsilon_1=1, \epsilon_2=1, \epsilon_3=5,$
and $\epsilon_4=5$. In the current notation
$l_1=2$ and $l_5=2$.  Either way 
the sum is $(5-1-1)=3$ four times i.e.  $12$.



\subsection{Left singular blocks and $J^0$ blocks}

We now add the assumption that there are $J^0$ blocks as well.
Let $t_i$ be the number of $J^0_i$ blocks, i.e., Jordan blocks 
of size $i$ corresponding to a zero eigenvalue.  Again by induction
it is possible to show
\begin{eqnarray*}
&amp;&amp;m_i=\sum_{j=i}^\infty (j-i)(l_j+t_j) \\
&amp;&amp;n_i=m_i+\sum_{j=i}^\infty l_j\\
&amp;&amp;s_i=\sum_{j=i}^\infty l_j +\sum_{j=i+1}^\infty t_j \\
&amp;&amp;r_i=\sum_{j=i+1}^\infty (l_j+t_j). 
\end{eqnarray*}

Now for this case Expression (\ref{messy}) evaluates
to
\be
\label{beta}
\mbox{\hspace{-0.1in}}
\beta=\sum_{i=0}^\infty \left\{
\left(\sum_{j=i+1}^\infty t_j \right)
\left(\sum_{j=i}^\infty l_j +\sum_{j=i+1}^\infty t_j \right)
+l_i \sum_{j=i+1}^\infty (j-i-1)(l_j+t_j)  \right\}
\ee
which can readily be manipulated to be
$$
\beta=\alpha+\sum_{i=0}^\infty (\sum_{j=i+1}^\infty t_j )^2
+\sum_{i=0}^\infty \left\{ \sum_{j=i}^\infty l_j \sum_{k=i+1}^\infty t_k
+
l_i \sum_{j=i+1}^\infty (j-i-1)t_j \right\},
$$
where $\alpha$ is the same interaction among the left singular blocks as
in Equation (\ref{alpha}). We recognize from Definition 3.6 that
$(\sum_{j=i+1}^\infty t_j )^2$ is $w_{i+1}^2$,
the square of the  $i+1$'st Weyr characteristic of the 
zero
eigenvalue. From our new proof of Theorem \ref{first-t} we know that
$\sum_{i=0}^\infty w_{i+1}^2$
is the codimension due to the zero eigenvalue alone.  

Lastly, we must evaluate
\begin{eqnarray*}
&amp; &amp;
\sum_{i=0}^\infty \left\{ \sum_{j=i}^\infty l_j \sum_{k=i+1}^\infty t_k
+
l_i \sum_{j=i+1}^\infty (j-i-1)t_j \right\}
 \\ &amp; &amp;
=\sum_{i=0}^\infty l_i(\sum_{j=0}^i \sum_{k=j+1}^\infty t_k
+
\sum_{k=i+1}^\infty (k-i-1)t_k)
 \\ &amp; &amp;
=\sum_{i=0}^\infty l_i \left\{ \sum_{k=1}^i\sum_{j=0}^{k-1}t_k+
\sum_{k=i+1}^\infty \sum_{j=0}^{i}t_k+\sum_{k=i+1}^\infty (k-i-1)t_k \right\}
 \\ &amp; &amp;
=(\sum_{i=0}^\infty l_i)(\sum_{k=1}^\infty kt_k)
 \\ &amp; &amp;
=\mbox{(size of Jordan structure for $\lambda=0$)(number of left singular blocks).}
\end{eqnarray*}
Therefore $\beta=\alpha+g \sum_i q_i^0$.


\subsection{Arbitrary singular blocks and arbitrary Jordan structure}

We complete the first pass through the algorithm
by defining $l_i^\prime$ to denote the number
of $L_i^T$ blocks, and $u$ to be the size of the
regular Jordan structure for $\lambda \ne 0$.
Thus, $u=\sum_i (p_i-q_i^0)$ includes the structure for
$\lambda=\infty$ which plays no special
role during the first pass through the 
algorithm.

We once again omit the details, but
it is possible to show by induction that
the algorithm computes
\begin{eqnarray*}
&amp;&amp;m_i=m_i^0+\sum_{j=0}^\infty (j+1)l_j^\prime+u \\
&amp;&amp;n_i=n_i^0+\sum_{j=0}^\infty j l_j^\prime +u \\
&amp;&amp;s_i=s_i^0 \\
&amp;&amp;r_i=r_i^0,
\end{eqnarray*}
where the superscript $0$ indicates no right singular structure and
no non-zero regular structure, i.e. as in the notation of
Section 6.2. 

We now have that the codimension expression in (\ref{messy}) 
is
$$\gamma=\beta+\sum_{i=0}^\infty 
\left\{
(\sum_{j=0}^\infty l_j^\prime)(\sum_{j=i}^\infty l_j +\sum_{j=i+1}^\infty t_j)
+
l_i(\sum_{j=0}^\infty (j+1)l_j^\prime + u)
\right\},
$$
where $\beta$ is as in (\ref{beta}).
With some algebraic manipulation, we obtain
$$
\gamma=\beta+\sum_{i,j=0}^\infty l_i l_j^\prime(i+j+2)
+u \sum_{i=0}^\infty l_i +
(\sum_{i=0}^\infty l_i^\prime)(\sum_{k=1}^\infty k t_k).
$$

The terms here are the terms
$$\gamma=\beta+\sum_{i,j} (\epsilon_i+\eta_j+2)
+
g\sum_i (p_i -q_i^0)
+
h \sum_i q_i^0.
$$

\subsection{Second and third passes through algorithm}

The first pass through the algorithm gives us a pencil
$A^\prime -\lambda B^\prime$, which may have only
$L_j^T$ blocks  and nonzero eigenvalues.
We then run the  algorithm on $(B^\prime -\lambda A^\prime)^T$,
so that the indices that gave the right singular blocks before
now give the left singular blocks.  The indices that described
$\lambda=0$ now describe $\lambda=\infty$. 
This algorithm returns a pencil with only a regular part that
has no zero or infinite eigenvalues.

If we reinvoke the previous results, we see that the second
pass through the algorithms nearly completes the entire
expression (\ref{compact}).  The only gap
is 
$$
\sum_{\lambda \not\in \{0,\infty\}} (q_1^\lambda +3q_2^\lambda+
5q_3^\lambda+\ldots).
$$
This is just the Jordan structure of the regular part other
than the zero and infinite eigenvalues.  
This is covered in the third phase of the algorithm,
completing the proof.
\qed











\section{Examples,
Observations About Genericity,
and Applications to the Waterhouse Theorems}
\label{examples}


We illustrate how these theorems may be used with a number of examples:

\begin{enumerate}
\item
Let $A$ be a matrix all of whose eigenvalues are $\lambda$.
The most generic such matrix, whose orbit has codimension $n$, is a single
Jordan block. 
The least generic such matrix, with codimension
$1+3+5+\ldots=n^2$, i.e. dimension 0, is the single point
$\lambda I$.


\item
Let $A$ be a matrix with no multiple eigenvalues.  The codimension
of its orbit
is then $\sum_\lambda 1$ or $n$.  One might intuitively think
of this as having specified the $n$ eigenvalues, but no other
information about the matrix. Indeed, if you do not wish to
specify the value of an
eigenvalue, the correct codimension for this unspecified
eigenvalue is one less:
$$ -1+q_1(\lambda)+3q_2(\lambda)+5q_3(\lambda) + \ldots .$$
In the Kronecker algorithm one sometimes specifies that
that the eigenvalues are $0$, $\infty$ or ``other''.
It would therefore be correct to subtract one for eigenvalues
classified as ``other''.

\item
Let the Kronecker structure  of a particular $8$ by $12$ pencil
be  diag$(L_0,L_2,L_3,L_3)$.  Since this
pencil has only $L_j$ blocks, the entire codimension
is to be found in $c_{\rm right}$.
It is $1+2+2=5$.  Notice that
the interactions of two $L_j$ blocks that are equal or differ
by only one, make no contribution to the codimension.
If a pencil contains only blocks of the form $L_\alpha$ or
$L_{\alpha+1}$, the codimension is $0$.
We have therefore observed

\begin{cor}
\label{gen-cor}
The generic Kronecker structure for a matrix pencil with $d=n-m&gt;0$
is
$${\rm diag}(L_\alpha,\ldots,L_\alpha,L_{\alpha+1},\ldots,L_{\alpha+1}),$$
where $\alpha=\lfloor m/d \rfloor$, the total  number of blocks 
is $d$, while the number of $L_{\alpha+1}$ blocks is
given by $m \bmod{d}$
(which is $0$ when $d$ divides $m$).
\end{cor}


The same statement holds
when $d=m-n&gt;0$ 
if we replace the $L_\alpha$ and $L_{\alpha+1}$ blocks by their transposes. 
Corollary \ref{gen-cor} was obtained by Van Dooren, Wilkinson, and
Wonham as discussed on page 3.55 of \cite{PVDT}.

\item
Let an $n$ by $n$ matrix pencil have the Kronecker structure
diag($L_j$,$L_{n-j-1}^T$), where $0 \le j &lt;n$.  From 
the $c_{\rm Sing}$ portion of the codimension, we learn that
the orbit has codimension $j+(n-j-1)+2=n+1$.
If a square pencil has any singular part at all,
it is fairly  easy to check that the smallest possible codimension is $n+1$
and it must be of this form.
We have thus reproduced a result of
Waterhouse(\cite{Wa}:
\begin{cor}
The generic singular pencils of size $n$ by $n$ have Kronecker
structures
$${\rm diag}(L_j,L_{n-j-1}^T),$$
where $j=0,\ldots,n-1$.
\end{cor}


Intuitively, we might think of this as the 
$n+1$ conditions on the coefficients of $\lambda$ that
$\det(A-\lambda B)=0$.)


More generally, \cite{Wa} has shown that
if a 
square matrix has one $L_r$ block and one $L_s^T$ block and otherwise
has a generic $n-r-s-1 \times n-r-s-1$ block
(eigenvalues unspecified),
then the codimension is
$(r+s+2)+2(n-r-s-1)=2n-(r+s)$. 
This too readily follows from our results.

\item
If an 11 by 12 pencil
has the Kronecker form diag($L_1,L_1^T,L_3,J^\infty_5$),
where here $J^\infty_5$ denotes a single 5 by 5 Jordan block
with eigenvalue $\infty$,
then $c_{\rm Jor}=5$, $c_{\rm Right}=1$, 
$c_{\rm Jor,Sing}=5 \times 3=15$,
and $c_{\rm Sing}=4+6=10$ giving a total codimension
of $31$.

\item
The $0$ pencil has a Kronecker structure consisting of $m$ $L_0^T$
blocks and $n$ $L_0$ blocks.  The codimension from
$c_{\rm Sing}$ only is $2mn$, i.e. the dimension is $0$.

\end{enumerate}


\newpage

\noindent
{\bf Acknowledgements} \\
Some of this work was performed in Toulouse, 
indeed it was begun along Rue de Fermat,
under the kind 
hospitality and support of CERFACS.  We wish to particularly thank
Mario Arioli, Dominique Bennett, and Iain Duff.
We further would like to thank the referees for 
their numerous comments which  we feel have been a great
improvement to the paper.



\noindent

\vspace{0.1in}


\def\\{\medskip\noindent\hangindent .3in{}}
\setlength{\baselineskip 11pt}
\frenchspacing
\begin{thebibliography}{99}

\bibitem{Ar}
V.I.~Arnold,
On matrices depending on parameters,
{\sl Russian Math. Surveys 26} (1971), 29--43.

\bibitem{brualdi}
R.A.Brualdi,
The Jordan Canonical Form: an old proof,
{\sl Amer. Math.  Month. 94} 
(1987), 257-267.



\bibitem{demmelkagstrom88}
J. Demmel and B. K{\aa}gstr\"{o}m,
Accurate Solutions of Ill-posed Problems in Control Theory,
{\sl {SIAM} J. Mat. Anal. Appl., 9}
(1988), 126--145.


\bibitem{fairgrieve}
T.~Fairgrieve,
{\sl The application of singularity theory to the
computation of the Jordan canonical form}, 
unpublished M.Sc. thesis, Computer Science Dept., 
University of Toronto, Canada (1986)

\bibitem{gantmacher}
F.R.~Gantmacher,
{\sl The Theory of Matrices},
Vols. 1, 2, Chelsea, New York, 1959.

\bibitem{GVL}
G.H.~Golub and C.F.~van Loan,
{\sl Matrix Computations, Second Edition},
Johns Hopkins University Press, Baltimore, 1989.

\bibitem{GW}
G.H.~Golub and J.H.~Wilkinson,
Ill-conditioned eigensystems and the computation of
the Jordan canonical form,
{\sl SIAM Review 18} (1976), 578--619

\bibitem{kagstrom85}
B.~K{\aa}gstr{\"o}m,
The generalized singular value decomposition and the general
$A- \lambda B$ problem,
{\sl BIT} 24 (1985), 568--583.

\bibitem{kagstrom86}
B.~K{\aa}gstr{\"o}m,
RGSVD: an algorithm for computing the Kronecker structure of reducing subspaces
of singular $A- \lambda B$ pencils,
{\sl SIAM J. Sci. Stat. Comp.} 7 (1986), 185--211.

\bibitem{KR}
B.~K{\aa}gstr{\"o}m and A.~Ruhe,
An algorithm for numerical computation of
the Jordan normal form of a complex  matrix,
{\sl ACM Trans. Math. Soft. 6} (1980), 398--419.

\bibitem{kub}
V.N.~Kublanovskaya,
On a method of solving the complete eigenvalue problem
for a degenerate matrix,
{\sl USSR Comp. Math. \&amp; Math. Phys. 6} (1968), 1--14.



\bibitem{macduffee}
C.C.~MacDuffee,
{\sl The Theory of Matrices},
Springer-Verlag, Berlin, 1933.

\bibitem{Ru}
A.~Ruhe,
An algorithm for the numerical determination of the structure of a
general matrix,
{\sl BIT 10,} (1970), 196--216.

\bibitem{turnbull}
H.W.Turnbull and A.C. Aitken,
{\sl An introduction to the theory of
canonical matrices}, Blackie 1932.



\bibitem{PVDT}
P.~van Dooren,
{\sl The Generalized Eigenstructure Problem},
Electronic Sciences Lab -- USCEE Report \#503,
PhD dissertation, University of Southern California,
January 1979.


\bibitem{PVD}
P.~van Dooren,
The computation of Kronecker's canonical form of a singular pencil,
{\sl Lin. Alg. Appl. 27} (1979), 103-40.


\bibitem{vandooren81}
P.~van Dooren,
The generalized eigenstructure problem in linear system theory,
{\sl {IEEE} Trans. Aut. Cntl.  AC-26} (1981), 111-128.

\bibitem{Wa}
W.C.~Waterhouse,
The codimension of singular matrix pairs,
{\sl Lin. Alg. Appl. 57} (1984), 227--245.

\bibitem{wilk78}
J.~H.~Wilkinson.
Linear differential equations and Kronecker's canonical form,
in {\sl Recent Advances in Numerical Analysis},
eds. C. de Boor and G. Golub, Academic Press, New York, (1978), 231--265.

\bibitem{wilk79}
J.~H.~Wilkinson.
Kronecker's canonical form and the QZ algorithm,
{\sl Lin. Alg. Appl.} 28 (1979), 285--303.


\end{thebibliography}
 


 
 

\end{document}



</pre></body></html>