\documentclass[12pt]{amsart}
%\usepackage[french] {babel}
\usepackage{amssymb,latexsym}
%=======================================================
%le usepackage{euscript} produit des lettre style Kues...
%la macro commande est: {\EuScript}
%=======================================================
%\usepackage{euscript}
%\usepackage{graphics}
%\usepackage{stalike}
%\usepackage{theorem}
%\usepackage{epsfig}
%\input Apicmacs.tex
%\input option_keys
%=======================================================
%Double jambe.  La macro commande est:{\Bbb}
%(definit par Rene. C'est deux lignes sont équivalentes a
%un usepackage)
%=======================================================
\DeclareSymbolFont{AMSb}{U}{msb}{m}{n}
\DeclareSymbolFontAlphabet{\Bbb}{AMSb}

%\textheight 7.75 in
%\textwidth 6.5in
%\headheight 0.5in
%\topskip 0.0in
%\topmargin 0.0in
%\oddsidemargin  0.3in
%\evensidemargin 0.3in

\numberwithin{equation}{section}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
%{\theorembodyfont{\rmfamily}\newtheorem{defin}{Definition}[section]}
%{\theorembodyfont{\rmfamily}\newtheorem{examp}{Example}[section]}
%{\theorembodyfont{\rmfamily}\newtheorem{remq}{Remark}[section]}

\theoremstyle{remark}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}

%\newenvironment{definition}
% {\begin{defin}}
% {\hfill {$\triangle$}\par\end{defin}}

%\newenvironment{example}
% {\begin{examp}}
% {\hfill {$\Box$}\par\end{examp}}

%\newenvironment{preuve}{{\bf Preuve} \par}{\hfill {\Bbb j}}


\newcommand{\ds}{\displaystyle}
\renewcommand{\thefootnote}{$\fnsymbol{footnote}$}

\font\ly=lasy10 scaled 1100
\catcode`\«=\active\def«{\ofd}
\catcode`\»=\active\def»{\ffg}
\chardef\lg='050
\chardef\rg='051
\def\ofd{\leavevmode\hbox{\ly\lg\kern-0.2em\lg}}
\def\ffg{\leavevmode\hbox{\ly\rg\kern-0.2em\rg}}

%$< \hspace{-9pt}(\
%\hspace{-2pt}  >\hspace{-7pt})\,$


%
%=======================================================
%
%Fin préambule
%
%=======================================================
\begin{document}



\title[Rank of linear matrices]{Commutative/noncommutative 
rank of linear matrices and subspaces of
matrices of low rank}

\author[Marc Fortin and Christophe Reutenauer]{Marc 
Fortin$^*$ and
Christophe Reutenauer$^\dagger$}
\thanks{$^*$Marc Fortin; 
C\'egep R\'egional de Lanaudi\`ere \`a
l'Assomption, 180, rue Dorval, l'Assomption (Qu\'ebec) Canada, J5W
6C1}
\thanks{$^\dagger$Christophe Reutenauer; 
Universit\'e du Qu\'ebec \`a
Montr\'eal; Département de mathématiques; Case postale 8888,
succursale Centre-Ville, Montr\'eal (Qu\'ebec) Canada, H3C 3P8
(mailing address); e-mail: christo@math.uqam.ca.  Partially supported by
NSERC
and CRC (Canada).}
\dedicatory{ D\'edi\'e \`a notre ami Alain Lascoux}
\date{}

\begin{abstract}
A space of matrix of low rank is a vector space of rectangular matrices
whose maximum rank is stricly smaller than the number of rows and the
numbers of columns. Among these are the compression spaces, where the
rank condition is garanteed by a rectangular hole of 0's of appropriate
size. Spaces of matrices are naturally encoded by linear matrices. The
latter have a double existence: over the rational function field, and
over the free field (noncommutative). We show that a linear matrix
corresponds to a compression space if and only if its rank over both
fields is equal. We give a simple linear-algebraic algorithm in order
to decide if a given space of matrices is a compression space. We give
inequalities relating the commutative rank and the noncommutative rank
of a linear matrix.
\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 52 \rms (2004), Article~B52f\hfill}
\def\thepage{}
%
%

\setcounter{section}{0}
\section{Introduction}
We consider here {\it linear matrices}, that is, matrices whose entries are
of
the form $a_0+a_1x_1+\cdots +a_dx_d$, where the coefficients $a_i$ are taken
in
a (commutative) field $k$ and where the $x_i$ are indeterminates, which
may be commuting or noncommuting.  Such a matrix is of the form
$M_0+\sum\limits_{i=1}^dx_i\,M_i$, where the $M_i$ are all over $k$ and of
the
same size.

Linear matrices appear in several area of mathematics: Kronecker pencils
(\cite{G} chapter 2), determinantal varieties (\cite{H} chapter 9), spaces
of
matrices of low rank \cite{EH}, algebraic automata theory (\cite{E} VII. 6),
free algebras \cite{Ro}, free fields \cite{CR}, 3-tensors (\cite{K}
4.6.4).

A linear matrix $M$ has two lives: it may be considered as a matrix over the
rational function field $k(x_1,\ldots,x_d)$ in the commuting variables
$x_1,\ldots,x_d$.  It may also be considered as a matrix over the {\it free
field}
\linebreak$k< \hspace{-9pt}(\ x_1,\ldots,x_d\hspace{-2pt}
>\hspace{-7pt})\,$
(which is the noncommutative analogue of the previous one, see \cite{C1},
\cite{C2}). In both cases, $M$ has a rank, which we denote by $crk(M)$
and
$ncrk(M)$, respectively.  It is intuitively clear that $crk(M)\leq
ncrk(M)$ (see Corollary~2.2). One may have strict inequality.  For
instance,
the matrix 
$$\left({\begin{array}{ccc}
\hphantom{-}0&\hphantom{-}x&\hphantom{-}y\\
-x&\hphantom{-}0&\hphantom{-}1\\
-y&-1&\hphantom{-}0
\end{array}}\right)$$
has commutative rank 2, but is invertible over the free field, hence of
noncommutative rank 3: if one inverts this matrix, one is lead to the
element
$(yx-xy)^{-1}$, which exists only noncommutatively.

Our main result gives a necessary and sufficient condition for equality of
both
ranks.  To state it, we need some definitions.  Observe first that if the
commutative rank of $M$ is maximal with respect to its size (that is, equal
to
$\min(n,p)$ where $M$ is of size $n\times p$), then both ranks coincide, as
seen
from the previous inequality.  So we may disregard this case and may assume
that
$M$ has rank
$<\min(n,p)$. Associate to the linear matrix $M=M_0+\sum\limits_{i=1}^d
x_i\,M_i$
the subspace $H$ of $k^{n\times p}$ spanned by the matrices $M_i$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MARC FORTIN AND CHRISTOPHE REUTENAUER}{\SMALL 
RANK OF LINEAR MATRICES}
%
%

 Since the commutative rank of $M$ is $<\min(n,p),$ the rank of each element
of
$H$ is also $<\min(n,p)$.  Moreover, if we assume that $k$ is {\it
infinite}, the
maximum rank in $H$ is equal to the commutative rank of $M$ (see Lemma~3.1).
A subspace
$H$ of $k^{n\times p}$ whose maximum rank is $<\min(n,p)$ is called a {\it
subspace of matrices of low rank}.  Such a subspace always comes from some
linear matrix (for the $M_i$, take a spanning set of $H$).

These subspaces have been considered by several authors
\cite{F}, \cite{W}, \cite{AL},
\cite{A},
\cite{B}, \cite{EH}, \cite{Re}.  They are not completely well-understood.
Among
them, the simplest one are the so called {\it compression space} (the
terminology is from Eisenbud and Harris; Westwick \cite{W} calls {\it
essentially decomposable} such a space, in the case where all nonzero
matrices in $H$ have the same rank $r$):
$H$ is a compression space if after some change of basis of rows and
columns over
$k$ (independently), the matrix
$M$ has the block form $\left({\begin{array}{cc}
A&0\\
B&C
\end{array}}\right)$, where the matrix $B$ is of size $i\times j$, and where
moreover the maximum rank in $H$ is $i+j$ (note that a matrix of this form,
with
$B$ of size $i\times j$, has necessarily rank $\leq i+j$).

Our characterization is the following (Theorem~3.1): $H$ {\it is a
compression
space if and only if the commutative and noncommutative rank of $M$ are
equal}. 
Before proving this result, we need to generalize a result of Cohn that
characterizes linear square matrices that are invertible in the free field.
We
characterize the noncommutative rank of any linear matrix (see Theorem~2.1
for a
precise statement).  As a corollary, we obtain that the noncommutative rank
of a
linear matrix $M=M_0+\sum\limits_{i=1}^d x_i\, M_i$ depends only on
the subspace $H$ spanned by the $M_i$.

In the last section, we give an efficient algorithm to solve the following
question: given a subspace $H$ of $k^{n\times p}$ of low rank, decide if $H$
is
a compression space (note that in order to know that $H$ is of low rank, it
is
enough to compute the commutative rank of $M$, which is easy), see Theorem~4.1. 
Note that in \cite{EH} is given an effective criterion for a subspace $H$ to
be
a compression space, but the underlying algorithm seems to be of high
complexity.  Our algorithm uses only techniques of linear algebra.

From Theorem~3.1 and Theorem~4.1 we may deduce two proofs of the following
fact:
the property for $H$ to be a compression space or not is invariant under
extension of the field of scalars $k$.  This is not so obvious because,
translating the definition into equations leads to a system of nonlinear
algebraic equations.

%
%=======================================================
%Section 2
%=======================================================
%
\section{Rank over the free field of linear matrices}
Let $X$ be a set of noncommuting variables and $k$ a (commutative)
field.  We denote by $k\langle X\rangle$ the $k$ -- algebra of
noncommutative polynomials over $k$ generated by the noncommuting
variables $x\in X$.  Among all the fields containing $k\langle
X\rangle$, there is one, called the {\em free field}, which is
unique up to isomorphism and which is characterized by the
following property: each square matrix $M$ over $k\langle
X\rangle$, which is full, becomes invertible over the free field.
Recall that a square matrix $M$ over a ring $R$ is called {\em full}
(over $R$) if it is not possible to have a factorization $M=PQ$,
with $P$ of size $n\times p, Q$ of size $p\times n$ and $p<n$.
Observe that the embedding of
$k\langle X\rangle$ in the free field inverts the maximum possible
matrices over $k\langle X\rangle$, since a non full matrix cannot
be invertible, in any extension field of $k\langle X\rangle$.

More generally, define the {\em inner rank} of an $n\times p$ matrix
$M$ over a ring $R$ to be the least $r$ such that $M$ has a
factorization
$M=PQ$, with $P$ of size $n\times r$ and $Q$ of size $r\times p$.
Then a fundamental result of Cohn is the following: the inner rank
of any matrix over $k\langle X\rangle$ is equal to its rank over
the free field (see \cite{C1} p. 249--250).
We denote the free
field by
$k< \hspace{-9pt}(\
X\hspace{-2pt}  >\hspace{-7pt})\,$.  See \cite{C1}, \cite{C2}
for more on the free field.

We consider now linear matrices, that is, matrices whose entries
are polynomials of degree $\leq 1$.  These matrices play a special
role for the free field, since each element of the free field is
equal to some entry of the inverse in the free field of some square linear
matrix \cite{C2}, Theorem~6.3.7.

Recall from the Introduction that to each linear matrix over $k\langle
X\rangle^{n\times p}$, we associate a subspace of $k^{n\times p}$.



We say that two subspaces $H,K$ of $k^{n\times p}$ are {\it equivalent} if
$K=UHV$ for some invertible matrices $U,V$ over $k$; equivalently, $H$ is
obtained from $K$ by row and column operations over $k$.  Now, Atkinson
and Lloyd \cite{AL} call $r-${\it decomposable} a subspace $H$ of
$k^{n\times p}$
if
$H$ is equivalent to subspace of matrices all of the form
$\left({\begin{array}{cc}
A&0\\
B&C
\end{array}}\right)$, where $B$ is of size $i\times j$ and $i+j=r$
(equivalently,
the 0 block is of size $n-i\times p-j$) .  Note that such a matrix is
necessarily
of rank
$\leq r$.  Following them, we say that a linear matrix $M$ is $r-${\it
decomposable} if its associated subspace is; equivalently, for some
invertible
matrices $U,V$ over $k$,
$U\,M\,V$ is of the above form.


The next result characterizes the rank of a linear matrix by a
linear -- algebraic property.  It extends Cohn's
characterization of full linear matrices \cite{C2} Cor. 6.3.6.

\begin{theorem}
Let $M$ be a linear matrix of size $n\times p$ over $k\langle X\rangle$
and $r<\min(n,p)$.  Its rank in the free field (equivalently, its inner rank
in
$k\langle X\rangle$) is $\leq r$ if and only if $M$ is $r$-decomposable.
\end{theorem}

Note that if the rank of a linear matrix is not $<\min(n,p)$ then it is
equal to
$\min(n,p)$: thus the theorem completely characterizes the rank of a linear
matrix
in the free field.

\bigskip
\begin{proof}

\medskip
\noindent
1)\quad
Note that
$$\left(\begin{array}{cc}
A&0\\
B&C
\end{array}\right)=
\left(\begin{array}{cc}
A&0\\
B&I_i
\end{array}\right)\ \
\left(\begin{array}{cc}
I_j&0\\
0&C
\end{array}\right)$$
where $I_l$ denotes the identity matrix of size $l\times l$; the
product is well--defined, since $A$ has $j$ columns, and $C$ has $i$
rows.  In particular, the number of columns of the first factor (=
number of rows of the second) is $j+i=r$, hence the product has
inner rank $\leq r$.

\medskip
\noindent
2)\quad
In order to prove the converse, we may suppose that the rank of $M$
in the free field is exactly $r$.  Then we may write $M=FG$, where
$F,G$ are matrices over $k\langle X\rangle$ of size $n\times r$ and
$r\times p$.  Since $r<n$, the rank in the free field of $F$ is $\leq
r$; it is actually exactly
$r$, otherwise $M$ has rank $<r$ in the free field, a
contradiction.  This implies that $F$ is right regular, i.e.
$FH=0\Rightarrow H=0$ (otherwise, $F$ has a kernel and its rank is
$<r$).  Symmetrically, $G$ is left regular. Since $F$ is right
regular and
$G$ is left regular, and since $M=FG$ is of degree $\leq 1$ we
may apply Lemma~6.3.4 of \cite{C2}: hence we may assume that
$\deg(F)\leq 1$.

Suppose that $\deg F=0$.  This implies that the rows of $M$ are
$k$ -- linear combinations of the $r$ rows of $G$; thus the rows of
$M$ are of rank $\leq r$ over $k$, and by row operations over $k$,
we may annihilate $n-r$ of them: we obtain a rectangle of
$0^\prime$s of size $(n-r)\times p$, which proves the theorem in
this case.

We assume now that $\deg F=1$.  Then by \cite{C2}, Corollary~VI.3.3,
there exist $U\in GL_n(k)$ and $W\in GL_r(k\langle X\rangle)$ such
that
$$U\,F\,W=\left(\begin{array}{cc}
A&0\\
0&I_s\end{array}\right)\,,$$
where $A$ is {\em left monic}: this means that
$A=A_0+\sum\limits_{x\in X}xA_x$, $A_0,
\linebreak A_x\in k^{n-s\times(r-s)}$, and the rows of the $A_x,x\in
X$, span $k^{r-s}$.

Observe that this latter condition implies that
\begin{eqnarray}
\deg(AN)=1+\deg(N)
\end{eqnarray}
for each matrix $N$ over $k\langle X\rangle$; indeed, we may assume
that $N$ is homogeneous of degree $d$, and write $N=\sum wN_w$,
where the sum is over all words $w$ on $X$ of length $d$ and
where the $N_w$ are matrices over $k$.  Then the term of degree
$d+1$ in $AN$ is $\sum\limits_{x,w}xw A_xN_w$.  If it is zero, then
$A_xN_w=0$, and since the rows of the $A_x$ span $k^{r-s},N_w=0$, a
contradiction since $N$ is of degree $d$.  Hence the term of degree $d+1$ in
$AN$ is nonzero, and this proves (1).

We have $U\,M=U\,F\,G=U\,F\,W\,W^{-1}\,G$.  Let us partition
$W^{-1}G=\left(\begin{array}{c}
G_1\\
G_2
\end{array}\right)$, so that $G_1,G_2$ are of size $(r-s)\times p,
s\times p$.  Then 
$$U\,M=\left(\begin{array}{cc}
A&0\\
0&I_s
\end{array}\right)
\left(\begin{array}{c}
G_1\\
G_2
\end{array}\right)=
\left(\begin{array}{c}
A\,G_1\\
G_2
\end{array}\right).$$
This implies that $AG_1,G_2$ are linear since $UM$ is.
Moreover, by (1),
$G_1$ must be of degree 0.  Since $G$ is left regular and $W$
invertible,
$W^{-1}G$ is also left regular, and this implies that $G_1$ also
is.  Thus the rank over $k$ of $G_1\in k^{(r-s)\times p}$ is $r-s$
(in particular $r-s\leq p$), and by column operations over $k$ we may
bring
$G_1$ to the form $(I_{r-s}, 0_{r-s,p-r+s})$; in other words, there
exists
$V\in GL_p(k)$ such that $G_1V=(I_{r-s}, 0_{r-s,p-r+s})$. We obtain
finally
$$W^{-1}G\,V=
\left(\begin{array}{c}
G_1\\
G_2
\end{array}\right)V=
\left(\begin{array}{ll}
I_{r-s}&0_{r-s,p-r+s}\\
B&C
\end{array}\right)$$
and, since $U\,M\,V=U\,F\,W\,W^{-1}\,G\,V,$
$$U\,M\,V=
\left(\begin{array}{cc}
A&0\\
0&I_s
\end{array}\right)
\left(\begin{array}{ll}
I_{r-s}&0_{r-s,p-r+s}\\
B&C
\end{array}\right)=
\left(\begin{array}{ll}
A&0_{n-s,p-r+s}\\
B&C
\end{array}\right)$$
since $A$ has $n-s$ rows; this concludes the proof.
\end{proof}

\begin{corollary}
The rank of a linear matrix $M=M_0+\sum\limits_{i=1}^d x_i\,M_i$ over the
free
field $k< \hspace{-9pt}(\ x_1,\ldots,x_d\hspace{-2pt}  >\hspace{-7pt})\,$
depends
only on the subspace of $k^{n\times p}$ spanned by the matrices $M_i$.
\end{corollary}

Hence this rank gives an invariant of subspaces of matrices.  It seems not
easy
to calculate.  The algorithm of \cite{CR} (which decides if a linear matrix
is
full) may be easily adapted to compute the rank of a linear matrix over the
free
field; it is however of high complexity, since it uses Gröbner bases.  It
would
be interesting to find an algorithm which uses only linear algebra
techniques.

The following result compares the commutative and noncommutative ranks.
\begin{corollary}
Let $M$ be a linear matrix.  Then $crk(M)\leq ncrk(M)\leq 2 crk(M)$.
\end{corollary}

\begin{proof}
The first inequality follows from the theorem.

For the second, we use a result of \cite{F} (Lemma~1): if a subspace $H$
of $k^{n\times p}$ has maximum rank $r$, then it is equivalent to a
subspace,
all matrices of which are of the form $\left({\begin{array}{cc}
A&0\\
B&C
\end{array}}\right)$, where $B$ is square of order $r$.  Hence, we may
suppose that $M$ is of this form.  Thus the theorem implies that
$ncrk(M)\leq 2r.$
\end{proof}
\begin{remark}
The first inequality in the corollary is evidently sharp: indeed, take a
linear matrix of size $n\times p$ and of commutative rank $\min(n,p)$.
However,
the second is not.  Indeed, if
$M$ has commutative rank 1, then  necessarily it has also noncommutative
rank 1;
this is because, classically, such a matrix is equi\-valent (after change of
bases over
$k$ in the spaces of rows and of columns) to a  matrix of the form
$$\left({\begin{array}{cccc}
0&\cdots&0&\ast\\
0&\cdots&0&\ast\\
\vdots&&\vdots&\vdots\\
0&\cdots&0&\ast
\end{array}}\right)$$
or its transpose.

The case of rank 2 and 3 may also be handled by results of Atkinson \cite{A}
and
Eisenbud-Harris \cite{EH}.  Suppose that $M$ is of commutative rank 2 and
let
$H$ be the span in $k^{n\times p}$ of the $M_i^\prime s$.  Then it follows
from
Theorem~1.1 in \cite{EH} that its noncommutative rank is 2 or 3 (since the
matrix
in the Introduction has noncommutative rank 3).

Similarly, suppose that $M$ has commutative rank 3.  Then it follows from
Theorem~1.2 in \cite{EH} that $M$ has noncommutative rank 3 or 4.

Note that, by direct sum of the matrix of the Introduction, one may find a
square linear matrix of order $3n$, which is of noncommutative rank $3n$,
and of
commutative rank $2n$. So, one could expect an inequality of the form
$ncrk(M)\leq \frac{3}{2}crk(M)$, which would certainly be sharp.
\end{remark}


%
%=======================================================
%Section 3
%=======================================================
%
\section{Compression spaces}
We recall the definitions of the Introduction, and we choose the language
of linear mappings, instead of matrices.

We consider a subspace $H$ of $\mbox{Hom}\,(E,F)$, where $E,F$ are
vectors spaces over $k$, of dimension $n,p$ respectively.  We assume
that $k$ is infinite.

By definition, the {\em rank} of $H$ is the maximum rank of its
elements.  We say that $H$ is of {\em low rank} if its rank is
smaller than $\min(n,p)$.

Among subspaces of low rank are the following ones:  $H$ is a {\em
compression space} if for some subspaces $E^\prime$ of $E$ and
$F^\prime$ of $F$ one has:
\begin{enumerate}
\item[1)]
$\mbox{codim}\,E^\prime+\dim F^\prime=$ rank of $H$;
\item[2)]
any element of $H$ maps $E^\prime$ into $F^\prime$.
\end{enumerate}

Taking bases of $E$ and $F$, containing bases of $E^\prime$ and
$F^\prime$, we see that the matrices representing $H$ are of all
the form $\left(\begin{array}{cc}
\times&0\\
\times&\times
\end{array}\right)$, where the 0 matrix has
$\mbox{codim}\,F^\prime$ lines and $\dim E^\prime$ columns.  In other words,
in
the terminology of \cite{AL}, $H$ is a compression space if $H$ is
$r$-decomposable and of rank $r$.

\begin{lemma}
Let $M=M_0+\sum\limits_{i=1}^d x_iM_i$ be a linear matrix, and $H$ the
subspace spanned by the matrices $M_0,M_1,\ldots,M_d$.  Then the maximum
rank in $H$ is equal to the commutative rank of $M$ ($k$ is infinite).
\end{lemma}

\pagebreak
\begin{proof}
Note that, for square matrices $A_i$ over $k$, $\det
\left({x_0A_0+\sum\limits_{i=1}^d x_iA_i}\right)$ vanishes if and only so
does $\det
\left({A_0+\sum\limits_{i=1}^d x_iA_i}\right)$, since the first is an
homogeneous polynomial of degree the order of the $A_i$'s. If we apply
this to the minors of $M$, we see that it is enough to prove the lemma for
the linear matrix $\sum\limits_{i=0}^d x_iM_i$.  Now, since $k$ is
infinite, a polynomial vanishes if and only if it vanishes for all values
of the variables in $k$.  This implies the lemma.
\end{proof}

\medskip
Given a subspace $H$ of $\mbox{Hom}\,(E,F)$, viewed in matrix form,
we associate to $H$ a linear matrix as follows: let
$M_1,\ldots,M_d$ be a spanning set of $H$, let $x_1,\ldots,x_d$ be
indeterminates; then the linear matrix is
$M=\sum\limits_{i=1}^dx_iM_i$.

\medskip
We know from Lemma~3.1 that
$crk(M)$ = rank$(H)$.  Suppose that $H$ is not of low rank;
equivalently, its rank is $\min(n,p)$.  Then, since a $n\times p$
matrix over any field has rank $\leq\min(n,p)$, we deduce that $crk(M)=$
 $ncrk(M)$ if $H$ is not of low rank.

The striking fact is that, when $H$ is of low rank, then this
equality characterizes compression spaces.
\begin{theorem}
Let $H$ be a space of matrices of low rank and $M$ its
associated linear matrix.  Then $H$ is a compression space if and
only if the commutative rank of $M$ and its noncommutative rank
coincide.
\end{theorem}
\begin{proof}
Suppose that $crk(M)=r=$ $ncrk(M)$.  Note that $r<\min(n,p)$
since $H$ is of low rank.  Then by Theorem~2.1, after suitable change of
bases in
$E,F$ we may assume that
$M$ is of the form
 $\left(\begin{array}{cc }
A&0\\
B&C
\end{array}\right)$, where the zero matrix is of size
$(n-i)\times(p-j)$, with $i+j=r$.  Let $E^\prime$ be the subspace
of $E$ spanned by the last $p-j$ basis vectors, and $F^\prime$ the
subspace of $F$ spanned by the last $i$ basis vectors.  Then we see
that each element of $H$ maps $E^\prime$ into $F^\prime$.
Moreover, $\mbox{codim}\,E^\prime+\dim F^\prime=j+i=r$.  Hence
$H$ is a compression space.

Conversely, if $H$ is a compression space, let $r$ be its rank.
Then, by definition, we may after change of basis in $E,F$ bring $H$
into the form $\left(\begin{array}{cc}
A&0\\
B&C\end{array}\right)$, where $A$ has $\mbox{codim}\,E^\prime$
columns, and $C$ has $\dim F^\prime$ rows, with
$r=\mbox{codim}\,E^\prime+\dim F^\prime$.  Then $M$ is also of
this form, and its noncommutative rank is $\leq r$ by Theorem~2.1.  Hence,
by
Corollary~2.2, it is exactly $r$.
\end{proof}
\begin{corollary}
Let $k\subset k^\prime$ be an extension of commutative fields.  Let
$H$ be a vector space of matrices of low rank over $k$, and
$H^\prime$ its extension to $k^\prime$.  Then $H$ is a compression
space if and only
$H^\prime$ is a compression space.
\end{corollary}
\begin{proof}
Let $M$ be the associated linear matrix; $M$ has coefficients in
$k$.  Its commutative rank is unchanged under the extension
$k\subset k^\prime$.  Furthermore, its noncommutative rank is also
unchanged, since the free field $k< \hspace{-9pt}(\
x_1,\ldots,x_d\hspace{-2pt}>\hspace{-7pt})$\,
embeds in the free field $k^\prime<\hspace{-10pt}(\
x_1,\ldots,x_d\hspace{-2pt}>\hspace{-7pt})$\, (see \cite{C2}
Theorem~6.4.6).  Thus, the corollary follows form the theorem.
\end{proof}

\medskip
A more elementary proof of this corollary will be given in Section~4. 

%
%=======================================================
%Section 4
%=======================================================
%
\section{An algorithm}
Let $E,F$ be vector spaces of dimension $n,p$ and
let $H\subset\mbox{Hom}\,(E,F)$ be a subspace of low rank $r<\min(n,p)$.
Select
an
$f\in H$ with rank $(f)=r$.

Define the sequence of subspaces $(E_i)$ of $E$ and $(F_i)$ of $F$
by:
$F_0=\{0\}$, and for
$i\geq 1$, recursively,
$$E_i=f^{-1}(F_{i-1}),\ F_i=\sum\limits_{g\in
H}g(E_i).\hspace{24pt}(\ast)$$

For effective computations, note that, if $H$ is given, by a basis
$(g_j)$ for instance, one has $F_i=\sum\limits_j g_j(E_i)$,
so that the sequence may effectively be computed.

Note that both sequences  $(F_i),(E_i)$ are increasing, since
$F_0=\{0\}\subseteq F_1$, and: $F_{i-1}\subseteq
F_i\Rightarrow E_i\subseteq E_{i+1}$ and $F_i\subseteq F_{i+1}$.

Thus, there is some $p$ such that $F_{p-1}=F_p$, and for this $p$
one has: $E_p=f^{-1}(F_{p-1})=f^{-1}(F_p)$, thus
$f^{-1}(F_p)=E_p$ and $\forall g\in H, g(E_p)\subseteq F_p$.

\begin{theorem}
With the previous notations, $H$ is a compression space if and only
if $\mbox{\em{codim}}\, E_p+\dim F_p=r$.
\end{theorem}
\begin{proof}
If this last equality holds, surely $H$ is a compression space,
since each $g$ in $H$ maps $E_p$ into $F_p$.

Conversely, suppose that $H$ is a compression space. Then for some
subspace $E^\prime,F^\prime$ of $E,F$, we have
$\mbox{codim}\,E^\prime+\dim F^\prime=r$, and each element of $H$
maps $E^\prime$ into $F^\prime$.
In particular $f(E^\prime)\subseteq F^\prime$.

  We claim that
$f(E^\prime)=F^\prime$ and $f^{-1}(F^\prime)=E^\prime$.
Indeed let $\bar f$ be the composition
$E\buildrel{f}\over\longrightarrow F\longrightarrow
F/F^\prime$, where the second mapping is the canonical one.
Then
$\mbox{Ker}\,\bar f=f^{-1}(F^\prime)$.  We have
$E^\prime\subseteq \mbox{Ker}\,\bar f$, since $f(E^\prime)
\subseteq F^\prime$, so that $\dim
E^\prime\leq\dim(\mbox{Ker}\,\bar f)$.

Now, rank $(f)=r$, hence rank $(\bar f)\geq r-\dim
F^\prime$ with equality if and only if $F^\prime\subseteq f(E)$. We
have by hypothesis
$r-\dim F^\prime=\mbox{codim}\, E^\prime=\dim E-\dim E^\prime=$ rank
$(\bar f)+\dim(\mbox{Ker}\, \bar f)-\dim E^\prime$; hence
the previous inequality implies $\dim(\mbox{Ker}\,\bar f)
\leq\dim E^\prime$,
 which implies equality and
$E^\prime=\mbox{Ker}\,\bar f=f^{-1}(F^\prime)$.  Using
$\dim(\mbox{Ker}\,\bar f)=\dim E^\prime$, the same
computation shows that rank $(\bar f)=r-\dim
F^\prime$. This implies by a previous remark that
$F^\prime \subseteq f(E^\prime)$ and finally, that
$f(E^\prime)=F^\prime$.

%\Bloc 1 fin

%Debut bloc 2
Observe that $F_0\subseteq F^\prime$.  If $F_{i-1}\subseteq
F^\prime$, then by the claim $E_i=f^{-1}(F_{i-1})\subseteq
f^{-1}(F^\prime)=E^\prime,$ and
$F_i=\sum\limits_{g\in H}g(E_i)\subseteq\sum\limits_{g\in
H}g(E^\prime)\subseteq F^\prime$.  Thus, we obtain by induction that
$E_i\subseteq E^\prime$, and
$F_i\subseteq F^\prime$ for each $i$.

This is true in particular for $i=p$, so that, changing notations
$(A=E_p,B=F_p)$, we have a subspace $A$ of $E^\prime$ and a subspace
$B$ of
$F^\prime$ such that: $\forall g\in H, g(A)\subseteq B$ and
$f^{-1}(B)=A$.

We show that $\mbox{codim}\, A+\dim B=r$, which will prove the
theorem.  Choose a subspace $A^\prime$ of $E^\prime$ such that
$A\oplus A^\prime=E^\prime$.  We claim that the composition
$u:A^\prime \buildrel{f}\over\longrightarrow
F^\prime\longrightarrow  F^\prime/B$ is an isomorphism.

Taking the claim for granted, we obtain $\dim A^\prime=\dim F^\prime-\dim
B$,
thus $r=\mbox{codim}\, E^\prime+\dim F^\prime=\dim E-\dim E^\prime +\dim
F^\prime=\dim E-\dim A-\dim A^\prime+\dim F^\prime
=\dim E-\dim A+\dim B
=\mbox{codim}\, A+\dim B$.

Let us prove the claim. We have $f(A)\subseteq B$.  In fact,
$f(A)=B$; indeed, if $b\in B$, then, since $f(E^\prime)=F^\prime,
b=f(e^\prime)$ for some $e^\prime\in E^\prime$; then $e^\prime\in
f^{-1}(b)\subseteq f^{-1}(B)=A$, hence $e^\prime \in A$ and $b \in
f(A)$, which shows that $B\subseteq f(A)$.

Thus we have $f(A)=B\Rightarrow
F^\prime=f(E^\prime)=f(A)+f(A^\prime)=B+f(A^\prime)$ and this
implies that the restriction to $f(A^\prime)$ of the canonical
mapping
$F^\prime\to F^\prime/B$ is surjective; in other words, $u$ is
surjective.

Now, $u$ is also injective, since $\mbox{Ker}\, u=f^{-1}(B)\cap
A^\prime=A\cap A^\prime=\{0\}.$
\end{proof}


Now, the algorithm works as follows.  By using the linear matrix
$M$ associated to $H$, compute the maximal rank $r$ of $H$; by
finding in the infinite field $k$ values of the variables appearing
in $M$ that do not annihilate some nonzero $r\times r$ minor of
$M$, one obtains an element $f$ in $H$ of rank $r$.  Then one
computes the suspaces $E_i,F_i$ described at the beginning of the
section; note that this computation is of low complexity, since it
amounts to solve linear equations.  Then one finds $p\leq\dim F$
such that $F_{p-1}=F_p$ as above.  It is enough then to check if
$\mbox{codim}\, E_p+\dim F_p=r$ and apply the theorem.
%bloc 3fin

Note that in \cite{EH}, an effective criterion is given for a
space
$H$ of matrices of low rank to be a compression space;
however, the computations use Gr\"{o}bner bases, so are of
high complexity (see \cite{EH} p. 150--151).

\bigskip
\noindent
\begin{proof}[Second proof of Corollary 3.1] The spaces $E_i, F_i$
are all defined over $k$, since so are $H$ and $f$.  Moreover, $F_{p-1}=F_p$
if and only if
$F_{p-1}\otimes_k k^\prime=F_p\otimes_k k^\prime$, and
the condition of the theorem is invariant under extension, since
the rank of $H$ does not change under commutative field
extension.
This proves the
corollary.
\end{proof}

%
%=======================================================
%References
%=======================================================
%
%\bibliographystyle{plain}
\begin{thebibliography}{45}
\bibitem[A]{A}
M.D. Atkinson, Primitive spaces of matrices of bounded rank II,
\textit{J. Austral. Math. Soc. Ser. A} 34, 1983, 306--315.
\bibitem[AL]{AL}
M.D. Atkinson, S. Lloyd, Large spaces of matrices of bounded rank,
\textit{Quarterly Journal of Mathematics Oxford 31}, 1980, 253--262.
\bibitem[B]{B}
L.B. Beasley, \textit{Null spaces of matrices of bounded rank},
Current trends in matrix theory, 45--50, North Holland, New York,
1987.
\bibitem[C1]{C1}
P.M. Cohn, \textit{Free rings and their relations}, Academic
Press, 1985 (first edition 1971).
\bibitem[CR]{CR}
P.M. Cohn, C. Reutenauer, On the construction of the free field,
\textit{Intern. J. Alg. Computation} 9, 1999, 307--323.
\bibitem[C2]{C2}
P.M. Cohn, \textit{Skew fields, theory of general division
rings}, Cambridge University Press, 1995.
\bibitem[C3]{C3}
P.M. Cohn, The word problem for free fields, \textit{J. Symb.
Logic} 38, 1973, 309--314; correction and addendum 40, 1975,
69--74.
\bibitem[E]{E}
S. Eilenberg, \textit{Automata, languages and machines}, vol.~A, Academic
Press,
1974.
\bibitem[EH]{EH}
D. Eisenbud, J. Harris, Vector spaces of matrices of low rank,
\textit{Advances Math.} 70, 1988, 135--155.
\bibitem[F]{F}
H. Flanders, On spaces of linear transformations with bounded
rank, \textit{J. London Math. Soc.} 37, 1962, 10--16.
\bibitem[G]{G}
F.R. Gantmacher, \textit{Applications of the theory of matrices},
Interscience,
1959.
\bibitem[H]{H}
J. Harris, \textit{Algebraic geometry, a first course}, Springer, 1993.
\bibitem[K]{K}
D.E. Knuth, \textit{The art of computer programming}, vol. 2,
Seminumerical problems, Addison Wesley, 1981.

\bibitem[Re]{Re}
R. Re, A note on linear subspaces of determinantal varieties,
\textit{Le Mate\-matiche} 50, 1995, 173--178.
\bibitem[Ro]{Ro}
M.L. Roberts, Endomorphism rings of finitely presented modules over free
algebras, \textit{J. London Math. Soc. 30}, 1984, 197--209.
\bibitem[W]{W}
R. Westwick, \textit{Spaces of linear transformations of equal rank},
Linear Algebra and Its Applications 5, 1972, 49--64.
\end{thebibliography}

\end{document}




