Séminaire Lotharingien de Combinatoire 52 (2004), Article B52f

COMMUTATIVE/NONCOMMUTATIVE RANK OF LINEAR MATRICES AND SUBSPACES OF MATRICES

OF LOW RANK

MARC FORTIN^{∗} AND CHRISTOPHE REUTENAUER^{†}

Dédié à notre ami Alain Lascoux

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.

1. Introduction

We consider here linear matrices, that is, matrices whose entries are of the form a_{0} + a_{1}x_{1} + ⋯ + a_{d}x_{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} + ∑_{i=1}^{d} x_{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 ([G] chapter 2), determinantal varieties ([H] chapter 9), spaces of matrices of low rank [EH], algebraic automata theory ([E] VII. 6), free algebras [Ro], free fields [CR], 3-tensors ([K] 4.6.4).

∗Marc Fortin; Cégep Régional de Lanaudière à l’Assomption, 180, rue Dorval, l’Assomption (Québec) Canada, J5W 6C1.

†Christophe Reutenauer; Université du Québec à Montréal; Dpartement de mathmatiques; Case postale 8888, succursale Centre-Ville, Montréal (Québec) Canada, H3C 3P8 (mailing address); e-mail: christo@math.uqam.ca. Partially supported by NSERC and CRC (Canada).

A linear matrix M has two lives: it may be considered as a matrix over the rational function field k(x_{1}, …, x_{d}) in the commuting variables x_{1}, …, x_{d}. It may also be considered as a matrix over the free field k <( x_{1}, …, x_{d} > ) (which is the noncommutative analogue of the previous one, see [C1], [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) ≤ ncrk(M) (see Corollary 2.2). One may have strict inequality. For instance, the matrix

( \begin{matrix}0 & x & y \\ −x & 0 & 1 \\ −y & −1 & 0 \end{matrix} )

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 × 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} + ∑_{i=1}^{d} x_{i} M_{i} the subspace H of k^{n×p} spanned

by the matrices M_{i}.

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 infinite, the maximum rank in H is equal to the commutative rank of M (see Lemma 3.1). A subspace H of k^{n×p} whose maximum rank is < min(n, p) is called a 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 [F], [W], [AL], [A], [B], [EH], [Re]. They are not completely well-understood. Among them, the simplest one are the so called compression space (the terminology is from Eisenbud and Harris; Westwick [W] calls 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 ( \begin{matrix}A & 0 \\ B & C \end{matrix} ), where the matrix B is of size i × j, and

where moreover the maximum rank in H is i + j (note that a matrix of this form, with B of size i × j, has necessarily rank ≤ i + j).

Our characterization is the following (Theorem 3.1): H 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} + ∑_{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×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 [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.

2. 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⟨X⟩ the k – algebra of noncommutative polynomials over k generated by the noncommuting variables x ∈ X. Among all the fields containing k⟨X⟩, there is one, called the free field, which is unique up to isomorphism and which is characterized by the following property: each square matrix M over k⟨X⟩, which is full, becomes invertible over the free field. Recall that a square matrix M over a ring R is called full (over R) if it is not possible to have a factorization M = P Q, with P of size n × p, Q of size p × n and p < n. Observe that the embedding of k⟨X⟩ in the free field inverts the maximum possible matrices over k⟨X⟩, since a non full matrix cannot be invertible, in any extension field of k⟨X⟩.

More generally, define the inner rank of an n × p matrix M over a ring R to be the least r such that M has a factorization M = P Q, with P of size n × r and Q of size r × p. Then a fundamental result of Cohn is the following: the inner rank of any matrix over k⟨X⟩ is equal to its rank over the free field (see [C1] p. 249–250). We denote the free field by k <( X > ) . See [C1], [C2] for more on the free field.

We consider now linear matrices, that is, matrices whose entries are polynomials of degree ≤ 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 [C2], Theorem 6.3.7.

Recall from the Introduction that to each linear matrix over k⟨X⟩^{n×p}, we associate a subspace of k^{n×p}.

We say that two subspaces H, K of k^{n×p} are 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 [AL] call r−decomposable a subspace H of k^{n×p} if H is equivalent to

subspace of matrices all of the form ( \begin{matrix}A & 0 \\ B & C \end{matrix} ), where B is of size i×j

and i + j = r (equivalently, the 0 block is of size n − i × p − j) . Note that such a matrix is necessarily of rank ≤ r. Following them, we say that a linear matrix M is r−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 [C2] Cor. 6.3.6.

Theorem 1. Let M be a linear matrix of size n × p over k⟨X⟩ and r < min(n, p). Its rank in the free field (equivalently, its inner rank in k⟨X⟩) is ≤ r if and only if M is r-decomposable.

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.

Proof. 1) Note that

( \begin{matrix}A & 0 \\ B & C \end{matrix} ) = ( \begin{matrix}A & 0 \\ B & I_{i} \end{matrix} ) ( \begin{matrix}I_{j} & 0 \\ 0 & C \end{matrix} )

where I_{l} denotes the identity matrix of size l × 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 ≤ r.

2) 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 = F G, where F, G are matrices over k⟨X⟩ of size n × r and r × p. Since r < n, the rank in the free field of F is ≤ 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. F H = 0 ⇒ 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 = F G is of degree ≤ 1 we may apply Lemma 6.3.4 of [C2]: hence we may assume that deg(F) ≤ 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 ≤ r over k, and by row operations over k, we may annihilate n − r of them: we obtain a rectangle of 0′s of size (n − r) × p, which proves the theorem in this case.

We assume now that deg F = 1. Then by [C2], Corollary VI.3.3, there exist U ∈ GL_{n}(k) and W ∈ GL_{r}(k⟨X⟩) such that

U F W = ( \begin{matrix}A & 0 \\ 0 & I_{s} \end{matrix} ) ,

where A is left monic: this means that A = A_{0} + ∑_{x∈X} xA_{x}, A_{0},

A_{x} ∈ k^{n−s×(r−s)}, and the rows of the A_{x}, x ∈ X, span k^{r−s}.

Observe that this latter condition implies that

deg(AN) = 1 + deg(N) (2.1)

for each matrix N over k⟨X⟩; indeed, we may assume that N is homogeneous of degree d, and write N = ∑ 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 ∑_{x,w} xwA_{x}N_{w}. If it is zero,

then A_{x}N_{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 =

( \begin{matrix}G_{1} \\ G_{2} \end{matrix} ), so that G_{1}, G_{2} are of size (r − s) × p, s × p. Then

U M = ( \begin{matrix}A & 0 \\ 0 & I_{s} \end{matrix} ) ( \begin{matrix}G_{1} \\ G_{2} \end{matrix} ) = ( \begin{matrix}A G_{1} \\ G_{2} \end{matrix} ) .

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} ∈ k^{(r−s)×p} is r−s (in particular r−s ≤ 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 ∈ GL_{p}(k) such that G_{1}V = (I_{r−s}, 0_{r−s,p−r+s}). We obtain finally

W^{−1}G V = ( \begin{matrix}G_{1} \\ G_{2} \end{matrix} ) V = ( \begin{matrix}I_{r−s} & 0_{r−s,p−r+s} \\ B & C \end{matrix} )

and, since U M V = U F W W^{−1} G V,

U M V = ( \begin{matrix}A & 0 \\ 0 & I_{s} \end{matrix} ) ( \begin{matrix}I_{r−s} & 0_{r−s,p−r+s} \\ B & C \end{matrix} ) = ( \begin{matrix}A & 0_{n−s,p−r+s} \\ B & C \end{matrix} )

since A has n − s rows; this concludes the proof. □

Corollary 1. The rank of a linear matrix M = M_{0} + ∑_{i=1}^{d} x_{i} M_{i} over the

free field k <( x_{1}, …, x_{d} > ) depends only on the subspace of k^{n×p} spanned by the matrices M_{i}.

Hence this rank gives an invariant of subspaces of matrices. It seems not easy to calculate. The algorithm of [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 Grbner bases. It would be interesting to find an algorithm which uses only linear algebra techniques.

The following result compares the commutative and noncommutative ranks.

Corollary 2. Let M be a linear matrix. Then crk(M) ≤ ncrk(M) ≤ 2crk(M).

Proof. The first inequality follows from the theorem.

For the second, we use a result of [F] (Lemma 1): if a subspace H of k^{n×p} has maximum rank r, then it is equivalent to a subspace, all

matrices of which are of the form ( \begin{matrix}A & 0 \\ B & C \end{matrix} ), where B is square of

order r. Hence, we may suppose that M is of this form. Thus the theorem implies that ncrk(M) ≤ 2r. □

Remark 1. The first inequality in the corollary is evidently sharp: indeed, take a linear matrix of size n × 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 equivalent (after change of bases over k in the spaces of rows and of columns) to a matrix of the form

( \begin{matrix}0 & ⋯ & 0 & ∗ \\ 0 & ⋯ & 0 & ∗ \\ ⋮ & & ⋮ & ⋮ \\ 0 & ⋯ & 0 & ∗ \end{matrix} )

or its transpose.

The case of rank 2 and 3 may also be handled by results of Atkinson [A] and Eisenbud-Harris [EH]. Suppose that M is of commutative rank 2 and let H be the span in k^{n×p} of the M′_{i}s. Then it follows from Theorem 1.1 in [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 [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) ≤ \frac{3}{2}crk(M), which would certainly be sharp.

3. 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 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 rank of H is the maximum rank of its elements. We say that H is of low rank if its rank is smaller than min(n, p).

Among subspaces of low rank are the following ones: H is a compression space if for some subspaces E′ of E and F′ of F one has:

1) codim E′ + dim F′ = rank of H;

2) any element of H maps E′ into F′.

Taking bases of E and F, containing bases of E′ and F′, we see that

the matrices representing H are of all the form ( \begin{matrix}× & 0 \\ × & × \end{matrix} ), where the

0 matrix has codim F′ lines and dim E′ columns. In other words, in the terminology of [AL], H is a compression space if H is r-decomposable and of rank r.

8 MARC FORTIN AND CHRISTOPHE REUTENAUER

Lemma 1. Let M = M_{0} + ∑_{i=1}^{d} x_{i}M_{i} be a linear matrix, and H the subspace spanned by the matrices M_{0}, M_{1}, …, M_{d}. Then the maximum rank in H is equal to the commutative rank of M (k is infinite).

Proof. Note that, for square matrices A_{i} over k, det (x_{0}A_{0} + ∑_{i=1}^{d} x_{i}A_{i})

vanishes if and only so does det (A_{0} + ∑_{i=1}^{d} x_{i}A_{i}), 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 ∑_{i=0}^{d} x_{i}M_{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. □

Given a subspace H of Hom (E, F), viewed in matrix form, we associate to H a linear matrix as follows: let M_{1}, …, M_{d} be a spanning set of H, let x_{1}, …, x_{d} be indeterminates; then the linear matrix is

M = ∑_{i=1}^{d} x_{i}M_{i}.

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 × p matrix over any field has rank ≤ 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.

Theorem 2. 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.

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 ( \begin{matrix}A & 0 \\ B & C \end{matrix} ), where

the zero matrix is of size (n − i) × (p − j), with i + j = r. Let E′ be the subspace of E spanned by the last p − j basis vectors, and F′ the subspace of F spanned by the last i basis vectors. Then we see that each element of H maps E′ into F′. Moreover, codim E′+dim F′ = 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 ( \begin{matrix}A & 0 \\ B & C \end{matrix} ), where A has codim E′ columns, and C has dim F′

rows, with r = codim E′ + dim F′. Then M is also of this form, and its noncommutative rank is ≤ r by Theorem 2.1. Hence, by Corollary 2.2, it is exactly r. □

Corollary 3. Let k ⊂ k′ be an extension of commutative fields. Let H be a vector space of matrices of low rank over k, and H′ its extension to k′. Then H is a compression space if and only H′ is a compression space.

Proof. Let M be the associated linear matrix; M has coefficients in k. Its commutative rank is unchanged under the extension k ⊂ k′. Furthermore, its noncommutative rank is also unchanged, since the free field k <( x_{1}, …, x_{d} > ) embeds in the free field k′ < ( x_{1}, …, x_{d} > ) (see [C2] Theorem 6.4.6). Thus, the corollary follows form the theorem. □

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

4. An algorithm

Let E, F be vector spaces of dimension n, p and let H ⊂ Hom (E, F) be a subspace of low rank r < min(n, p). Select an f ∈ 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 ≥ 1, recursively,

E_{i} = f^{−1}(F_{i−1}), F_{i} = ∑_{g∈H} g(E_{i}). (∗)

For effective computations, note that, if H is given, by a basis (g_{j}) for instance, one has F_{i} = ∑_{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} ⊆ F_{1}, and: F_{i−1} ⊆ F_{i} ⇒ E_{i} ⊆ E_{i+1} and F_{i} ⊆ 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 ∀g ∈ H, g(E_{p}) ⊆ F_{p}.

Theorem 3. With the previous notations, H is a compression space if and only if codim E_{p} + dim F_{p} = r.

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′, F′ of E, F, we have codim E′ + dim F′ = r, and each element of H maps E′ into F′. In particular f(E′) ⊆ F′.

We claim that f(E′) = F′ and f^{−1}(F′) = E′. Indeed let f̄ be the composition E ⟶^{f} F ⟶ F/F′, where the second mapping is the canonical one. Then Ker f̄ = f^{−1}(F′). We have E′ ⊆ Ker f̄, since f(E′) ⊆ F′, so that dim E′ ≤ dim(Ker f̄).

Now, rank (f) = r, hence rank (f̄) ≥ r − dim F′ with equality if and only if F′ ⊆ f(E). We have by hypothesis r − dim F′ = codim E′ = dim E − dim E′ = rank (f̄) + dim(Ker f̄) − dim E′; hence the previous inequality implies dim(Ker f̄) ≤ dim E′, which implies equality and E′ = Ker f̄ = f^{−1}(F′). Using dim(Ker f̄) = dim E′, the same computation shows that rank (f̄) = r − dim F′. This implies by a previous remark that F′ ⊆ f(E′) and finally, that f(E′) = F′.

Observe that F_{0} ⊆ F′. If F_{i−1} ⊆ F′, then by the claim E_{i} =

f^{−1}(F_{i−1}) ⊆ f^{−1}(F′) = E′, and F_{i} = ∑_{g∈H} g(E_{i}) ⊆ ∑_{g∈H} g(E′) ⊆ F′.

Thus, we obtain by induction that E_{i} ⊆ E′, and F_{i} ⊆ F′ 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′ and a subspace B of F′ such that: ∀g ∈ H, g(A) ⊆ B and f^{−1}(B) = A.

We show that codim A + dim B = r, which will prove the theorem. Choose a subspace A′ of E′ such that A ⊕ A′ = E′. We claim that the composition u : A′ ⟶^{f} F′ ⟶ F′/B is an isomorphism.

Taking the claim for granted, we obtain dim A′ = dim F′ − dim B, thus r = codim E′ + dim F′ = dim E − dim E′ + dim F′ = dim E − dim A − dim A′ + dim F′ = dim E − dim A + dim B = codim A + dim B.

Let us prove the claim. We have f(A) ⊆ B. In fact, f(A) = B; indeed, if b ∈ B, then, since f(E′) = F′, b = f(e′) for some e′ ∈ E′; then e′ ∈ f^{−1}(b) ⊆ f^{−1}(B) = A, hence e′ ∈ A and b ∈ f(A), which shows that B ⊆ f(A).

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

Now, u is also injective, since Ker u = f^{−1}(B) ∩ A′ = A ∩ A′ = {0}. □

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 × 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 ≤ dim F such that F_{p−1} = F_{p} as above. It is enough then to check if codim E_{p} + dim F_{p} = r and apply the theorem.

Note that in [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öbner bases, so are of high complexity (see [EH] p. 150–151).

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} ⊗_{k} k′ = F_{p} ⊗_{k} k′, 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. □

References

[A] M.D. Atkinson, Primitive spaces of matrices of bounded rank II, J. Austral. Math. Soc. Ser. A 34, 1983, 306–315.

[AL] M.D. Atkinson, S. Lloyd, Large spaces of matrices of bounded rank, Quarterly Journal of Mathematics Oxford 31, 1980, 253–262.

[B] L.B. Beasley, Null spaces of matrices of bounded rank, Current trends in matrix theory, 45–50, North Holland, New York, 1987.

[C1] P.M. Cohn, Free rings and their relations, Academic Press, 1985 (first edition 1971).

[CR] P.M. Cohn, C. Reutenauer, On the construction of the free field, Intern. J. Alg. Computation 9, 1999, 307–323.

[C2] P.M. Cohn, Skew fields, theory of general division rings, Cambridge University Press, 1995.

[C3] P.M. Cohn, The word problem for free fields, J. Symb. Logic 38, 1973, 309–314; correction and addendum 40, 1975, 69–74.

[E] S. Eilenberg, Automata, languages and machines, vol. A, Academic Press, 1974.

[EH] D. Eisenbud, J. Harris, Vector spaces of matrices of low rank, Advances Math. 70, 1988, 135–155.

[F] H. Flanders, On spaces of linear transformations with bounded rank, J. London Math. Soc. 37, 1962, 10–16.

[G] F.R. Gantmacher, Applications of the theory of matrices, Interscience, 1959.

[H] J. Harris, Algebraic geometry, a first course, Springer, 1993.

[K] D.E. Knuth, The art of computer programming, vol. 2, Seminumerical problems, Addison Wesley, 1981.

[Re] R. Re, A note on linear subspaces of determinantal varieties, Le Matematiche 50, 1995, 173–178.

[Ro] M.L. Roberts, Endomorphism rings of finitely presented modules over free algebras, J. London Math. Soc. 30, 1984, 197–209.

[W] R. Westwick, Spaces of linear transformations of equal rank, Linear Algebra and Its Applications 5, 1972, 49–64.