Jairo Bochi

Nicolas Gourmelon
email: nikolaz.gourmelon@gmail.com

UNIVERSAL REGULAR CONTROL FOR GENERIC SEMILINEAR SYSTEMS

Keywords: Mathematics Subject Classification. 93C10, 93B05, 93C55 Discrete-time systems, semilinear systems, bilinear systems, universal regular control. J.B

We consider discrete-time projective semilinear control systems ξ t`1 " Aputq ¨ξt, where the states ξt are in projective space RP d´1 , inputs ut are in a manifold U of arbitrary dimension, and A : U Ñ GLpd, Rq is a differentiable mapping.

An input sequence pu 0 , . . . , u N ´1q is called universally regular if for any initial state ξ 0 P RP d´1 , the derivative of the time-N state with respect to the inputs is onto.

In this paper we deal with the universal regularity of constant input sequences pu 0 , . . . , u 0 q. Our main result states that for generic such control systems, all constant inputs of sufficient length N are universally regular, except for a discrete set. More precisely, the conclusion holds for a C 2 -open and C 8 -dense set of maps A. We also show that the inputs on that discrete set are nearly universally regular; indeed there is a unique non-regular initial state, and its corank is 1.

In order to establish the result, we study the spaces of bilinear control systems. We show that the codimension of the set of systems for which the zero input is not universally regular coincides with the dimension of the control space. The proof is based on careful matrix analysis and some elementary algebraic geometry. Then the main result follows by applying standard transversality theorems.

1. Introduction 1.1. Basic definitions and some questions. Consider discrete-time control systems of the form:

(1.1)

x t`1 " F px t , u t q, pt " 0, 1, 2, . . . q where F : X ˆU Ñ X is map. We will always assume that the space X of states and the space U of controls are manifolds, and that the map F is continuously differentiable.

A sequence px 0 , . . . , x N ; u 0 , . . . , u N ´1q satisfying (1.1) is called a trajectory of length N ; it is uniquely determined by the initial state x 0 and the input pu 0 , . . . , u N ´1q. Let φ N denote the time-N transition map, which gives the final state as a function of the initial state and the input:

(1.2)

x N " φ N px 0 ; u 0 , . . . , u N ´1q.

We say that the system (1.1) is accessible from x 0 in time N if the set φ N ptx 0 u Û N q of final states that can be reached from the initial state x 0 has nonempty interior.

The implicit function theorem gives a sufficient condition for accessibility. If the derivative of the map φ N px 0 ; ¨q at input pu 0 , . . . , u N ´1q is an onto linear map 1 then we say that the trajectory determined by px 0 ; u 0 , . . . , u N ´1q is regular. So the existence of such a regular trajectory implies that the system is accessible from x 0 in time N .

Let us call an input pu 0 , . . . , u N ´1q universally regular if for every x 0 P X , the trajectory determined by px 0 ; u 0 , . . . , u N ´1q is regular; otherwise the input is called singular.

The concept of universal regularity is central in this paper; it was introduced by Sontag 2 in [So] in the context of continuous-time control systems. The discretetime analogue was considered by Sontag and Wirth in [SW]. They showed that if the system (1.1) is accessible from every initial condition x 0 in uniform time N then universally regular inputs do exist, provided one assumes the map F to be analytic. In fact, under those hypotheses they showed that universally regular inputs are abundant: in the space of inputs of sufficiently large length, singular ones form a set of positive codimension.

In this paper, we are interested in control systems (1.1) where the next state x t`1 depends linearly on the previous state x t (but non-linearly on u t , in general). This means that the state space is K d , where K is either R or C, and that (1.1) now takes the form:

(1.3)

x t`1 " Apu t q ¨xt , where A : U Ñ Mat dˆd pKq.

Following [START_REF] Colonius | Linear control semigroups acting on projective space[END_REF], we call this a semilinear control system.

In the case that the map A above takes values in the set GLpd, Kq of invertible matrices of size d ě 2, we consider the corresponding projectivized control system:

(1.4) ξ t`1 " Apu t q ¨ξt , where the states ξ t take value in the projective space KP d´1 " K d ˚{K ˚. We call this a projective semilinear control system. The projectivized system is also a useful tool for the study of the original system (1.3): see e.g. [START_REF] Wirth | Dynamics of time-varying discrete-time linear systems: spectral theory and the projected system[END_REF][START_REF]The dynamics of control[END_REF].

Universally regular inputs for projective semilinear control systems were first considered by Wirth in [Wi]. Under his working hypotheses, the existence and abundance of such inputs is guaranteed by the aforementioned result of [SW]; then he uses universally regular inputs to obtain global controllability properties.

The purpose of this paper is to establish results on the existence and abundance of universally regular inputs for projective semilinear control systems. Differently from [SW, Wi], we will not necessarily assume our systems to be analytic. Let us consider systems (1.4) with K " R and A : U Ñ GLpd, Rq a map of class C r , for some fixed r ě 1. To compensate for less rigidity, we do not try to obtain results that work for all C r maps A, but only for generic ones, i.e., those maps in a residual 3 subset, or, even better, in an open dense subset.

To make things more precise, assume U is a C 8 (real) manifold without boundary. 4 We will always consider the space C r pU , GLpd, Rqq endowed with the strong C r topology 5 .

Hence the first question we pose is this:

Taking N sufficiently large, is it true that for C r -generic maps A, the set of universally regular inputs in U N is itself generic? It turns out that this question has a positive answer. Actually, we show in [START_REF]Universal regular control for generic semilinear systems: general inputs[END_REF] that for r great enough, for maps A in a C r open and dense set, all inputs in U N are universally regular, except for those in a stratified closed set of positive codimension. So another natural question is this:

Fixed parameters d, dim U , N , and r, what is the minimum codimension of the set of singular inputs in U N that can occur for C r -generic maps A : U Ñ GLpd, Rq? This question seems to be very difficult. However, we do have a sharp estimate if we restrict ourselves to the subset of U N formed by non-resonant inputs, namely those inputs pu 0 , . . . , u N ´1q such that u i ‰ u j whenever i ‰ j (see [START_REF]Universal regular control for generic semilinear systems: general inputs[END_REF]). To investigate what happens for resonant inputs is a much tougher job.

In this paper we consider the most resonant case. Define a constant input of length N as an element of U N of the form pu 0 , u 0 , . . . , u 0 q. We propose ourselves to study universal regularity of inputs of this form. A possible interpretation is this: Suppose the system is controlled by a "lever" that is very hard to move. Then we want to know what positions of the lever are universally regular. For those positions it is possible to perturb the state of the system in any desired direction with only slight moves on the lever.

1.2. The main result. Our main result says that generically the singular constant inputs form a very small set: Theorem 1.1. Given d ě 2 and m ě 1, there exists N ě 1 with the following properties. Let U be a smooth m-dimensional manifold without boundary. Then there exists a C 2 -open C 8 -dense subset O of C 2 pU , GLpd, Rqq such that for every system (1.4) with A P O, all constant inputs of length N are universally regular, except for those in a zero-dimensional (i.e., discrete) set.

By saying that a subset O of C 2 pU , GLpd, Rqq is C 8 -dense, we mean that for all r ě 2, the intersection of O with C r pU , GLpd, Rqq is dense in C r pU , GLpd, Rqq.

It is remarkable that the generic dimension of the set of singular constant inputs (namely, 0) does not depend on the dimension m of the control space U , neither on the dimension d´1 of the state space. A partial explanation for this phenomenon is the following: First, the obstruction to universal regularity of the input pu, u, . . . , uq is the combined degeneracy of the matrix Apuq and of the derivatives of A at u. If m is small then the image of the generic map A will avoid too degenerate matrices, which increases the chances of obtaining universal regularity. If m is large then more degenerate matrices Apuq will inevitably appear; however the large number of control parameters compensates, so universal control is still likely.

The singular inputs that appear in Theorem 1.1 are not only rare; we also show that they are "almost" universally regular: Theorem 1.2 (Addendum to Theorem 1.1). The set O Ă C 2 pU , GLpd, Rqq in Theorem 1.1 can be taken with the following additional properties: If A P O and a constant input pu, . . . , uq of length N is singular then:

1. There is a single direction ξ 0 P RP d´1 for which the corresponding trajectory of system (1.4) is not regular. 2. The derivative of the map φ N pξ 0 ; ¨q at input pu, . . . , uq has corank6 1.

To sum up, for generic systems (1.4), the universal regularity of constant inputs can fail only in the weakest possible way: there is at most one non-regular state, which can be moved in all directions but one.

Remark 1.3. We actually have a very precise description of the singular inputs that appear in Theorem 1.2. We show that these singular inputs can be unremovable by perturbations, and therefore Theorem 1.1 is optimal in the sense that there are C 2 -open (actually even C 1 -open) sets of maps A for which the set of singular constant inputs is nonempty. Also, by C 1 -perturbing any A in those C 2 -open sets, one can obtain an infinite number of singular constant inputs. In particular, it is not possible to choose O to be C 1 -open in the statement of the Theorem 1.1. See Appendix B.

Remark 1.4. The integer N is a function of d and m we did not try to estimate precisely. However, we know that it is at most d 2 (see Remark 1.7).

Remark 1.5. In the case of complex matrices (i.e., K " C), we have a corresponding version of Theorem 1.1 where the maps A are analytic; see Appendix C.

1.3. Reduction to the study of the set of poor data. The bulk of the proof of Theorem 1.1 consists on the computation of the dimension of certain canonical sets, as we now explain.

We fix A : U Ñ GLpd, Kq and consider the projective semilinear system (1.4). Recall that 1-jet of the map A at a point u P U consists of the first order Taylor approximation of A around u. By the chain rule, the universal regularity of an input pu 0 , u 1 , . . . , u N ´1q depends only on the 1-jets of A at points u 0 , . . . , u N ´1.

Let us discuss the case of constant inputs pu 0 , . . . , u 0 q. If we take local coordinates such that u 0 " 0 and replace the matrix map A : U Ñ GLpd, Kq by its linear approximation, system (1.4) becomes:

(1.5) ξ t`1 " ˜A `m ÿ j"1 u t,i C j ¸ξt , pt " 0, 1, 2, . . . q, where A " Apu 0 q and C 1 , . . . , C m are the partial derivatives at 0. This is the projectivization of a bilinear control system (see [El]). For these systems, the zero input is a distinguished one and the focus of more attention.

To study system (1.5) it is actually more convenient to consider normalized derivatives B j " C j A ´1, which intrinsically take values in the Lie algebra glpd, Kq. Consider the matrix data A " pA, B 1 , . . . , B m q. We will explain how the universal regularity of the zero input is expressed in linear algebraic terms. Recall that the adjoint operator of A acts on glpd, Kq by the formula Ad A pBq " ABA ´1. Consider the linear subspace Λ N pAq of glpd, Kq spanned by the matrices Id and pAd A q i pB j q, pi " 0, . . . , n ´1, j " 1, . . . , mq.

(The identity matrix appears because of the projectivization.) Then:

Proposition 1.6. The constant input p0, . . . , 0q of length N is universally regular for system (1.5) if and only if the space Λ N pAq acts transitively on the set K d ˚of nonzero vectors.

If Λ N pAq acts transitively on K d ˚for some N , then the data A is called rich; otherwise it is called poor.

Remark 1.7. The spaces ΛN pAq form a nested sequence, which thus stabilize after finitely many steps. It is actually easy to see that stabilization occurs at most at time N " d 2 . Therefore there are two possibilities: either the zero input of length d 2 is universally regular, or the zero inputs of all lengths are singular. 7Let P pKq m denote the set of poor data. 8 A major part of our work is to study these sets. We prove:

Theorem 1.8. The set P pRq m is closed and semialgebraic, and its codimension in GLpd, Rq ˆpglpd, Rqq m is m.

Theorem 1.9. The set P pCq m is algebraic, and its (complex) codimension in GLpd, Cqp glpd, Cqq m is m.

So Theorems 1.8 and 1.9 say how frequent universal regularity of the zero input is in the space of projective bilinear control systems (1.5) 1.4. Overview of the proofs. Theorem 1.1 follow rather directly from Theorem 1.8 by applying standard results from transversality theory. More precisely, the fact that the set P pRq m is semialgebraic implies that it has a canonical stratification. This permits us to apply Thom's jet transversality theorem and obtain Theorem 1.1.

On the other hand, Theorem 1.8 follows from its complex version Theorem 1.9 by simple abstract arguments.

Thus everything is based on Theorem 1.9. One part of the result is easily obtained: we give examples of small disks of codimension m formed by poor data, so concluding that the codimension of P pCq m is at most m. To prove the other inequality, one could try to exhibit an explicit codimension m set containing all poor data. For m " 1 this task is feasible (and we actually perform it, because with these conditions we can actually check universal regularity in concrete examples). However, for m " 2 already the task would be very laborious, and to expect to find a general solution seems unrealistic.

Our actual approach to prove the lower bound on the codimension of P pCq m is indirect. Crudely speaking, after careful matrix computations, we find some sets in the complement of P pCq m that are reasonably "large" (basically in terms of dimension). Then, by using some abstract results of algebraic geometry, we are able to show that P pCq m is "small", thus proving the other half of Theorem 1.9. Let us give more detail about this strategy. We decompose the set P m " P pCq m into fibers:

P m " ď APGLpd,Cq tAu ˆPm pAq, P m pAq Ă rglpd, Cqs m .
It is not very difficult to show that for generic A in GLpd, Cq, the fiber P m pAq has precisely the wanted codimension m. However, for degenerate matrices A, the fiber P m pAq may be much bigger. (For example, one can show that if A is an homothecy and m ď 2d ´3 then P m pAq is the whole rglpd, Cqs m .) In order to show that codim P m ě m, we need to make sure that those degenerate matrices with do not form a large set. More precisely, we show that:

(1.6) @k P t0, . . . , mu, codim A P GLpd, Cq; codim P m pAq ď m ´k( ě k.

Let us explain how we prove (1.6). In order to estimate the dimension of P m pAq for any matrix A P GLpd, Cq, we consider a quantity r " rpAq which is the least number such that a rich data of the form pA, C 1 , . . . , C r q exists. In particular, if r " rpAq ď m then the following affine space (1.7) pC 1 , C 2 , . . . , C r , B r`1 , . . . , B m q; B j P glpd, Cq ( is contained in the complement of P m pAq.

8 A more precise notation would be P pKq m,d . However, we can think d as fixed; on the other hand it is sometimes useful to change m.

In certain situations, if two algebraic subsets have large enough dimensions then they necessarily intersect; for example, two algebraic curves in the complex projective plane CP 2 always intersect. This kind of phenomenon happens here: the dimension of the affine space (1.7) forces a lower bound for the codimension of P m pAq, namely:

(1.8) codim P m pAq ě m `1 ´rpAq.

So we need to show that matrices A with large rpAq are rare. A careful matrix analysis provides an upper bound to rpAq based on the numbers and sizes of the Jordan blocks of A, and on the occasional algebraic relations between the eigenvalues. This bound together with (1.8) implies (1.6) and therefore concludes the proof of Theorem 1.9.

In fact, the results of this analysis are even better, and we conclude that the codimension inequality (1.6) is strict when k ě 1. This implies that poor data pA, B 1 , . . . , B m q for which the matrix A is degenerate form a subset of P pCq m with strictly bigger codimension. Thus we can show that the poor data that appear generically are well-behaved, which leads to Theorem 1.2. 1.5. Other remarks. One can also study uniform regularity of periodic inputs of higher period. Using our results for constant inputs, it is not difficult to derive some (non-sharp) dimension bounds for singular periodic inputs. However, for highly resonant non-periodic inputs, we have no idea on how to obtain reasonable dimension estimates.

As mentioned above, in paper [START_REF]Universal regular control for generic semilinear systems: general inputs[END_REF] we have dimension estimates for general inputs. These estimates are basically obtained by avoiding highly resonant inputs (which have large codimension themselves). Thus the results of [START_REF]Universal regular control for generic semilinear systems: general inputs[END_REF] are independent from those of these paper. The proofs there are less involved from the point of view of matrix computations, but use more sophisticated transversality theorems.

Of course, it would be interesting to consider these kind of problems for other Lie groups of matrices, but we will not pursue this issue here.

1.6. Organization of the paper. Section 2 contains some basic results about transitivity of spaces of matrices and its relation with universal regularity. We also obtain the easy parts of Theorems 1.8 and 1.9, namely (semi)algebraicity and the upper codimension inequalities.

In Section 3 we introduce the concept of rigidity, which is related to the quantity rpAq mentioned above. We state the central rigidity estimates (Theorem 3.7), which consist into two parts. The first and easier part is proved in the same Section 3, while the whole Section 4 is devoted to the proof of the second part.

Section 5 starts with some preliminaries in elementary algebraic geometry. Then we use the rigidity estimates to prove Theorem 1.9, following the strategy outlined above ( § 1.4). Theorem 1.8 follows easily. We also obtain a lemma that is needed for the proof of Theorem 1.2.

In Section 6 we collect some basic facts about stratifications and transversality, and then apply them together with the previous results to obtain Theorems 1.1 and 1.2.

The paper also has some appendices: Appendix A basically reobtains the major results in the special case m " 1, where we actually gain additional information of practical value: as mentioned in § 1.4, it is possible to describe explicitly what 1-jets the map A should avoid in order to satisfy the conclusions of Theorems 1.1 and 1.2. The arguments necessary for the m " 1 case are much simpler and more elementary than those in Sections 3 to 5. Therefore the appendix is also useful to give the reader some intuition about the general problem, and as a source of examples. Appendix A is written in a slightly informal way, and it can be read after Section 2 (though the final part requires Lemmas 3.1 and 3.2).

In Appendix B we take a closer look to the generic singular constant inputs, and in particular we justify Remark 1.3. We also discuss the generic validity of some control-theoretic properties related to accessibility and regularity.

In Appendix C we apply Theorem 1.9 to prove a version of Theorem 1.1 for holomorphic mappings.

Finally, Appendix D proves the algebraic-geometric result which allows us to obtain estimate Eq. (1.8).

Preliminary facts on the poor data

In this section, we review some basic properties related to poorness, and prove the easy inequalities in Theorems 1.8 and 1.9.

2.1. Transitive spaces. Let E and F be finite-dimensional vector spaces over the field K. Let LpE, F q be the space of linear maps from E to F . A vector subspace Λ of LpE, F q is called transitive if for every v P E t0u, we have Λ ¨v " F , where Λ ¨v " tLpvq; L P Λu.

Under the identification LpK m , K n q " Mat mˆn pKq, we may also speak of transitive spaces of matrices.

‹ ‹ ‹ ‹ ‹ ‹ ' , resp. ¨h1 ¨¨¨h d´1 h d . . . h d`1 h d´1 . . . h d h d`1 ¨¨¨h 2d´1 ‹ ‹ ‹ ‹ ‹ ‹ ‹ ' ,
The set of Toeplitz matrices and the set of complex Hankel matrices constitute examples transitive subspaces of glpd, Kq. Transitivity of the Toeplitz space is a particular case of Example 2.2, and transitivity of Hankel space follows from Remark 2.3. For K " C, these spaces are optimal, in the sense that they have the least possible dimension; see [Az].

Example 2.2. A generalized Toeplitz space is a subspace Λ of Mat dˆd pKq (where d ě 2) with the following property: For any two matrix entries pi1, j1q and pi2, j2q which are not in the same diagonal (i.e., i1 ´j1 ‰ i2 ´j2), the linear map pbi,jqi,j P Λ Þ Ñ pbi 1 ,j 1 , bi 2 ,j 2 q P C 2 is onto. Equivalently, a space is generalized Toeplitz if it can be defined by a number of linear relations between the matrix coefficients so that each relation involves only the entries on a same diagonal, and so that the relations do not force any matrix entry to be zero. We will prove later (see § 3.3) that every generalized Toeplitz space is transitive.

Remark 2.3. If Λ is a transitive subspace of LpE, F q and P P LpE, Eq, Q P LpF, F q are invertible operators then P ¨Λ ¨Q :" tP LQ; L P Λu is a transitive subspace of LpE, F q.

Let us see that transitivity is a semialgebraic or algebraic property, according to the field. Recall that:

' A subset of K n is called algebraic if it is expressed by polynomial equations with coefficients in K. ' A subset of R n is called semialgebraic if it is expressed by finitely many polynomial equations or inequalities with coefficients in R.

Proposition 2.4. Let N pKq m,n,k be the set of pB 1 , . . . , B k q P rMat mˆn pKqs k " K mnk such that spantB 1 , . . . , B k u is not transitive. Then:

1. The set N pRq m,n,k is semialgebraic. 2. The set N pCq m,n,k is algebraic.
Proof. Consider the set of pB 1 , . . . , B k , vq P rMat mˆn pKqs k ˆKn ˚such that spantB 1 , . . . , B k u ¨v ‰ K m . This is an algebraic set, because it is expressed by the vanishing of certain determinants. Taking K " R and projecting this set along the R n ˚fiber we obtain N pRq m,n,k ; so, by the Tarski-Seidenberg theorem (see [START_REF] Bochnak | Real algebraic geometry[END_REF]p. 26]), this set is semialgebraic, proving part 1.

To see part 2, we take K " C and projectivize the C n ˚fiber, obtaining an algebraic subset rMat mˆn pCqs k ˆCP n´1 whose projection along the CP n´1 fiber is N pCq m,n,k . So part 2 follows from the fact that projections along projective fibers are closed maps with respect to the Zariski topology (see Proposition 5.1 below).

Another important fact is that complex transitivity of real matrices is a stronger property than real transitivity:

Proposition 2.5. The real part of N pCq m,n,k (that is, its intersection with rMat mˆn pRqs k ) contains N pRq m,n,k . Moreover, the inclusion can be strict. The explanation is this: real matrix data can be R-transitive without being C-transitive because the directions that detect non-transitivity are non-real. A formal proof and examples are provided in [START_REF] Bochi | Transitivity of spaces of matrices[END_REF].

Remark 2.6. The codimension of N pCq m,n,k is computed in [START_REF] Bochi | Transitivity of spaces of matrices[END_REF]: it is maxpk´m´n`2, 0q. We also observe in [START_REF] Bochi | Transitivity of spaces of matrices[END_REF] that N pRq m,n,k can fail to be real-algebraic. But we will not need those results in the present paper.

2.2. Universal regularity for constant inputs and richness. In this subsection we prove Proposition 1.6; in fact we prove a more precise result, and also fix some notation.

Recall that if A P GLpd, Kq then the adjoint of A is the linear operator Ad A on glpd, Kq given by the formula Ad A pBq " ABA ´1.

If A : U Ñ GLpd, Cq is a differentiable map then the normalized derivative of A at a point u is the linear map T u U Ñ glpd, Rq given by h Þ Ñ pDApuq ¨hq ˝A´1 puq.

Let φ N pξ 0 , ûq be the state ξ N P KP d of the system (1.4) determined by the initial state ξ 0 and the input sequence û P U N . Let B 2 φ N pξ 0 , ûq be the derivative of the map φ N pξ 0 , ¨q at û. Fix a constant input û " pu, . . . , uq P U N , and local coordinates on U around u. Let B j be the normalized partial derivatives of the map A at u with respect to the i th coordinate. Consider the data A " pA, B 1 , . . . , B m q, where A " Apuq. Define the following subspace of glpd, Kq:

(2.1) Λ N pAq " K ¨Id `span 0ďnăN ´1 1ďjďm
Ad n A pB j q ( , Proposition 2.7. For all ξ 0 P KP d´1 and any

x 0 P K d t0u representing ξ 0 , rank B 2 φ N pξ 0 , ûq " dim " Λ N pAq ¨pA N x 0 q ‰ ´1.
In particular (since A " Apuq is invertible), the input û is universally regular if and only if Λ N pAq is a transitive space, which is the statement of Proposition 1.6.

Proof of Proposition 2.7. Let ξ 0 " rx 0 s, where x 0 P K d t0u. Let ψ N px 0 , ûq be the final state of the non projectivized system (1.3) determined by the initial state x 0 and by the sequence of controls û P U N . Using local coordinates with u in the origin, we have the following first order approximation for û » 0:

ψ N px 0 , ûq » A N x 0 `ÿ 1ďjďm 0ďtăN u t,j A N ´t´1 B j A t`1 x 0 " ¨Id `ÿ 1ďjďm 0ďnăN u N ´1´n,j Ad n A pB j q 'x N ,
where x N " ψ N px 0 , 0q " A N x 0 . Therefore the image of B 2 ψ N px 0 , ûq is the following subspace of

T A N x0 K d : V " ˜span 1ďjďm 0ďnăN Ad n A B j ¸¨x N ,
The image of B 2 φ N pξ 0 , ûq equals Dπpx N qpV q, where π : K d t0u Ñ KP d´1 is the canonical projection. Notice that Ker Dπpxq " Kx for any

x P K d t0u. It follows that rank B 2 φ N pξ 0 , ûq " dim rDπpx N qpV qs " dim " Dπpx N q `Kx N `V ˘‰ " dimrKx N `V s ´1
Since Kx N `V " Λ N pAq ¨xN , the proposition is proved.

The discussion above motivates the introduction of a more general notation, which will be convenient later. Consider a linear operator H : E Ñ E, where E is a finite-dimensional vector space over the field K. Given a vector v P E, the orbit of v under H is the set tH n v; n ě 0u. Denote the space spanned by the orbit by sorb H v. We have sorb H v " f pHq ¨v; f is a polynomial with coefficients in K ( .

It follows from the Cayley-Hamilton theorem that sorb H v is the space spanned by the first dim E iterates of v:

sorb H v " spantH n v; n " 0, . . . , dim E ´1u.
Let us also denote

sorb H pv 1 , . . . , v n q " sorb H v 1 `¨¨¨`sorb H v n .
In this notation, the union ΛpAq :" Ť N Λ N pAq of the elements of the sequence (2.1) is expressed as

(2.2)
ΛpAq " sorb Ad A pId, B 1 , . . . , B m q, where A " pA, B 1 , . . . , B m q.

We have Λ N pAq " ΛpAq for all N ě d 2 , as stated in Remark 1.7. Let us also note that the sets of poor data are saturated in the sense of the following definition: A set Z Ă rMat dˆd pKqs 1`m will be called saturated if pA, B 1 , . . . , B m q P Z implies that:

2.3.

' For all P P GLpd, Kq, the tuple pP ´1AP, P ´1B 1 P, . . . , P ´1B m P q belongs to Z. ' For all Q " pq ij q P GLpm, Kq, the tuple pA, B 1 1 , . . . , B 1 m q, where B 1 i " ř j q ij B j , belongs to Z.

Remark 2.8. 1. A subset rMat dˆd pKqs 1`m is saturated if and only if it is invariant under a certain action of the group GLpd, Kq ˆGLpm, Kq. 2. The real part of a complex saturated set is saturated (in the real sense).

2.4. The easy codimension inequality of Theorems 1.8 and 1.9. Here we will discuss the simplest examples of poor data.

To begin, notice that if A P GLpd, Cq is diagonalizable then so is Ad A . Indeed, assume without loss of generality that A " Diagpλ 1 , . . . , λ d q. Consider the basis tE i,j ; i, j P t1, . . . , duu of glpd, Cq, where (2.4) E i,j is the matrix whose only nonzero entry is a 1 in the pi, jq position.

Then Ad A pE i,j q " λ i λ ´1 j E i,j . We summarize this fact as:

(2.5) Ad A " Diag ¨1 λ 1 λ ´1 2 ¨¨λ 2 λ ´1 1 1 . . . . . . ‹ ' .
So if f is a polynomial and B " pb ij q then (2.6) the pi, jq-entry of the matrix pf pAd A qqpBq is f pλ i λ ´1 j qb ij .

The data A " pA, B 1 , . . . , B m q P GLpd, Kq ˆglpd, Kq m is called conspicuously poor if there exists a change of bases P P GLpd, Kq such that:

' the matrix P ´1AP is diagonal; ' the matrices P ´1B k P have a zero entry in a common off-diagonal position; more precisely, there are indices i 0 , j 0 P t1, . . . , du with i 0 ‰ j 0 such that for each k P t1, . . . , mu, the pi 0 , j 0 q entry of the matrix P ´1B k P vanishes.

(As in the definition of poorness, the concept depends on the field K.)

Lemma 2.9. Conspicuously poor data are poor.

Proof. Let A " pA, B 1 , . . . , B m q be conspicuously poor. With a change of basis we can assume that A is diagonal. Let pe 1 , . . . , e d q be the canonical basis of K d . Let pi, jq be the entry position where all B i 's have a zero entry. By (2.6), all matrices in the space ΛpAq given by (2.2) have a zero entry in the pi 0 , j 0 q position. In particular, there is no L P ΛpAq such that L ¨ej0 " e i0 , showing that this space is not transitive.

The converse of this lemma is certainly false. (Many examples appear in Appendix A; see also Example 3.6.) However, we will see in § 2.5 that the converse holds for generic A.

We will use Lemma 2.9 to prove the easy codimension inequalities for Theorems 1.8 and 1.9; first we need to recall the following 9 : 9 Proposition 2.10 follows from the implicit function theorem; for a proof using complex analysis, see [START_REF] Kato | Perturbation theory for linear operators[END_REF]p. 67].

Proposition 2.10. Suppose A P Mat dˆd pKq is diagonalizable over K and with simple eigenvalues only. Then there is a neighborhood of A where the eigenvalues vary smoothly, and where the eigenvectors can be chosen to vary smoothly.

Proposition 2.11 (Easy half of Theorems 1.8 and 1.9). For both K " R or C, we have codim K P pKq m ď m. Proof. Using Proposition 2.10, we can exhibit smoothly embedded disks of codimension m inside GLpd, Kq ˆglpd, Kq m formed by conspicuously poor data.

2.5. Unconstrained matrices. The material from this subsection is used in the proof of Theorem 1.2, but not in the proof of Theorem 1.1. It is also used in Appendix A.

If p is an irreducible factor of the polynomial λ i λ ℓ ´λj λ k then the relation p " 0 is called an elementary constraint in the variables λ 1 , . . . , λ d . Every elementary constraint can be written, after a permutation of the indices 1, . . . , d, as one of the following:

' a type 1 constraint:

λ 1 λ 3 " λ 2 2 . ' a type 2 constraint: λ 1 λ 4 " λ 2 λ 3 . ' a type 3 constraint: λ 1 " ´λ2 . ' a type 4 constraint: λ 1 " λ 2 .
We say that a matrix A P GLpd, Rq is unconstrained if its eigenvalues, counted with multiplicity, do not satisfy any elementary constraint.

Remark 2.12. A matrix A is unconstrained if and only if AdA has the maximal possible number of distinct eigenvalues, namely, d 2 ´d`1. This is obvious from (2.5) if one restricts to diagonalizable matrices A. The general case follows from the fact (which we will prove rigorously in § 4.3) that the multiplicities of the eigenvalues of AdA are those "predicted" by formula (2.5).

Let us see that the converse of Lemma 2.9 holds for unconstrained A: Lemma 2.13. Suppose that the data A " pA, B 1 , . . . , B m q P GLpd, Kq ˆglpd, Kq m is poor and that the matrix A is unconstrained. Then A is conspicuously poor.

Proof. Suppose A is unconstrained. In particular, A has simple spectrum. With a change of basis we can assume that A is diagonal. Now suppose that A " pA, B 1 , . . . , B m q is not conspicuously poor. This means that for each off-diagonal position there is at least of of the matrices B k that has a non-zero entry in that position. (Notice that this fact does not depend on the change of basis chosen before.)

Since A is unconstrained, the values λ i λ ´1 j , where pi, jq runs on the matrix positions outside the diagonal, are pairwise different, and all different from 1. Recall that one can always (using Lagrange formula) find a polynomial whose values at finitely many different points are prescribed. So It follows from (2.6) that the space ΛpAq contains all matrices py ij q such that y 11 " ¨¨¨" y dd , and in particular, all Toeplitz matrices. So ΛpAq is transitive, i.e., A is not poor. This proves the lemma.

Let us establish another simple result, which is related to Theorem 1.2. Denote by pe 1 , . . . , e d q the canonical basis of C d . Lemma 2.14. Suppose that the data A " pA, B 1 , . . . , B m q P GLpd, Cq ˆglpd, Cq m has the following properties:

1. A is an unconstrained diagonal matrix; 2. there are indices i 0 , j 0 P t1, . . . , du with i 0 ‰ j 0 such that for each k P t1, . . . , mu, the pi 0 , j 0 q entry of the matrix B k vanishes;

3. the off-diagonal vanishing entry position pi 0 , j 0 q above is unique.

Then:

1. There is a single direction rvs P CP d´1 such that ΛpAq¨v ‰ C d , namely re j0 s.

2. The space ΛpAq ¨ej0 has codimension 1; in fact, it equals spante i ; i ‰ i 0 u.

Proof. Under the assumptions on A, the space ΛpAq contains py ij q P glpd, Cq; y 11 " ¨¨¨" y dd , y i0j0 " 0 ( .

The conclusions follow easily.

After the preliminaries above, the optional Appendix A can be read (as we mentioned in § 1.6).

Rigidity

The aim of this section is to state Theorem 3.7 and prove its first part. Along the way we will establish several lemmas which will be reused in the proof of the second part of the theorem in Section 4.

3.1. Acyclicity. Consider a linear operator H : E Ñ E, where E is a finitedimensional complex vector space.

The operator H is called cyclic if it has a cyclic vector, that is, some v P E such that sorb H v is the whole space E. The following two lemmas are useful to find cyclic vectors, when they exist: Lemma 3.1. Suppose that E " C ℓ and that H is a Jordan block:

H " ¨λ 1 1 λ ‹ ‹ ' .
Then a vector v " px 1 , . . . , x ℓ q is cyclic for H if and only if x ℓ ‰ 0.

Proof. For any polynomial f we have (see [START_REF] Gantmacher | The theory of matrices[END_REF]page 100]):

f pHq " ¨f pλq f 1 pλq 1! f 2 pλq 2! ¨¨¨f pℓ´1q pλq pℓ´1q! . . . f 2 pλq 2! f 1 pλq 1! f pλq ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ' .
So the space spanned by the powers of H is the space of upper triangular Toeplitz matrices. The rest of the proof is an easy exercise.

Lemma 3.2. Let E be a finite-dimensional complex vector space and let H : E Ñ E be a linear operator. Assume that E 1 , . . . , E k Ă E are H-invariant subspaces and that the spectra of

A|E i (1 ď i ď k) are pairwise disjoint. If v 1 P E 1 , . . . , v k P E k then sorb H pv 1 , . . . , v k q " sorb H pv 1 `¨¨¨`v k q .
Proof. The Ą part is trivial; let us show the Ă part. Take w P sorb H pv 1 , . . . , v k q, so w " ř f i pHq ¨vi , where each f i is a polynomial. Let p i be the minimal polynomial of H|E i , and let q i " ś j‰i p j . Since the spectra of A|E i are pairwise disjoint, the polynomials p i are pairwise relatively prime, and so the polynomials q i are jointly relatively prime. Since polynomials form a principal ideal domain, there exist polynomials g i such that ř g i q i " 1. Using that q i pHq ¨vj " 0 if i ‰ j, we have:

w " ÿ i f i pHq ¨vi " ÿ i f i pHq ˜ÿ j g j pHqq j pHq ¸¨v i " ÿ i f i pHqg i pHqq i pHq ¨vi " ˜ÿ i f i pHqg i pHqq i pHq ¸¨ÿ j v j .
That is, w " f pHq ¨řj v j for some polynomial f , as we wanted to show.

We define the acyclicity of H as the least number n of vectors v 1 , . . . , v n P E such that sorb H pv 1 , . . . , v n q " E. We denote n " acyc H. So acyc H " 1 means that H is a cyclic operator.

Let us relate acyclicity with the Jordan normal form of H. The geometric multiplicity of an eigenvalue λ of H is the number of corresponding Jordan blocks or, equivalently, the dimension of the kernel of H ´λId. The following fact is probably well-known, but since we could not find a precise reference we provide a proof: 10 Proposition 3.3. The acyclicity of an operator equals the maximum of the geometric multiplicities of its eigenvalues.

Proof. Let λ 1 , . . . , λ k be the eigenvalues of H, counted without multiplicity, and E " E 1 ' ¨¨¨' E k be the splitting into generalized eigenspaces. Let n i be the geometric multiplicity of λ i , and let n " max n i .

Using Lemma 3.1, we find v i,1 , . . . , v i,ni P E i such that sorb H pv i,1 , . . . , v i,ni q " E i . Define v i,j " 0 for n i ă j ď n. Consider w j " ř k i"1 v i,j , for j " 1, . . . , n. By Lemma 3.2, sorb H w j " sorb H pv 1,j , . . . , v k,j q. So sorb H pw 1 , . . . , w n q "

ÿ j sorb H pv 1,j , . . . , v k,j q " ÿ i sorb H pv i,1 , . . . , v i,n q " E.
This shows that acyc H ď n.

To show the reverse inequality, assume that n " n 1 , for example. For each vector in E, write its coordinates with respect to the Jordan basis, and the consider only the coordinates corresponding to the rightmost columns of the Jordan blocks for λ 1 . This defines a linear map P : E Ñ C n such that P H " λ 1 P . Now take any vectors u 1 , . . . , u n´1 P E. Then the space S " sorb H pu 1 , . . . , u n´1 q is sent by P to the vector space spantP u 1 , . . . , P u n´1 u, which has dimension ď n. Since P is onto C n , the space S cannot be the whole E. This shows that acyc H ě n, completing the proof.

Remark 3.4. The operators which interest us most are H " AdA, where A P GLpd, Cq. It is useful to observe that the geometric multiplicity of 1 as an eigenvalue of AdA equals the the codimension of the conjugacy class of A inside GLpd, Cq. To prove this, consider the map ΨA : GLpd, Cq Ñ GLpd, Cq given by ΨApXq " AdX pAq. The derivative at X " Id is H Þ Ñ HA ´AH; so Ker DΨApIdq " KerpAdA ´idq. Therefore when X " Id, the rank of DΨApXq equals the geometric multiplicity of 1 as an eigenvalue of AdA. To see that this is 10 The usual textbook approach is the other way around: one uses results about cyclic operators to obtain the Jordan normal form; see e.g. [Ga].

true for any X, notice that ΨA " Ψ Ad X pAq ˝RX ´1 (where R denotes a right-multiplication diffeomorphism of GLpd, Cq).

We will see later (Lemma 4.15) that 1 is the eigenvalue of AdA with the biggest geometric multiplicity. By Proposition 3.3, we conclude that acyc AdA equals the codimension of the conjugacy class of A.

3.2. Definition of rigidity, and the main rigidity estimate. Let E and F be finite-dimensional complex vector spaces. Let H be a linear operator action on the space LpE, F q. We define the rigidity of H, denoted rig H, as the least n such that there exist L 1 , . . . , L n P LpE, F q so that sorb H pL 1 , . . . , L n q is transitive. Therefore

1 ď rig H ď acyc H .
For technical reasons, we also define a modified rigidity of H, denoted rig `H . The definition is the same, with the difference that if E " F then L 1 is required to be the identity map in LpE, Eq. Of course, rig H ď rig `H ď rig H `1.

We want to give a reasonably good estimate of the modified rigidity of Ad A for any fixed A P GLpd, Cq. (This will be achieved in Lemma 4.18.) We assume that d ě 2; so rig `Ad A ě 2. The next example shows that "most" matrices A have the lowest possible rig `Ad A .

Example 3.5. If A P GLpd, Cq is unconstrained (see § 2.5) then rig `AdA " 2. Indeed if we take a matrix B P glpd, Cq whose expression in the base that diagonalizes A has no zeros off the diagonal then, by Lemma 2.13, ΛpA, Bq " sorb Ad A pId, Bq is rich.

More generally, if A P GLpd, Cq is little constrained (see Appendix A) then it follows from Proposition A.2 that rig `AdA " 2.

Example 3.6. Consider A " Diagp1, α, α 2 q where α " e 2πi{3 . (In the terminology of § 2.5, A has constraints of type 1.) Since Ad 3

A is the identity, we have dim sorb Ad A pId, Bq ď 4 for any B P glp3, Cq. By the result of Azoff [Az] already mentioned at Example 2.1, the minimum dimension of a transitive subspace of glp3, Cq is 5. This shows that rig `AdA ě 3. (Actually, equality holds, as we will see in Example 3.10 below.)

Let T be the set of roots of unity. Define an equivalence relationon the set C ˚of nonzero complex numbers by:

(3.1) λ -λ 1 ô λ{λ 1 P T.
We also say that λ, λ 1 are equivalent mod T .

For A P GLpd, Cq, we denote (3.2) cpAq :" number of different classes mod T of the eigenvalues of A.

We now state a technical result which has a central role in our proofs, as explained informally in § 1.4: Theorem 3.7. Let d ě 2 and A P GLpd, Cq. Then:

1. If cpAq " d then rig `Ad A " 2. 2. If cpAq ă d then rig `Ad A ď acyc Ad A ´cpAq `1.
Remark 3.8. When cpAq " d, we have acyc AdA " d (this will follow from Lemma 4.15); so the conclusion of part 2 does not hold in this case.

Remark 3.9. The conditions of A being unconstrained and A having cpAq " d both mean that A in "non-degenerate". Both of them imply small rigidity, according to Example 3.5 and part 1 of Theorem 3.7. It is important, however, not to confuse the two properties; in fact, none implies the other.

Example 3.10. Consider again A as in Example 3.6. The eigenvalues of AdA are 1, α, and α 2 , each with multiplicity 3; so Proposition 3.3 gives acyc AdA " 3. So Theorem 3.7 tell us that rig `AdA ď 3, which is actually sharp.

The proof of part 1 of Theorem 3.7 will be given in § 3.5 after a few preliminaries ( § § 3.3 and 3.4). These preliminaries are also used in the proof of the harder part 2, which will be given in Section 4.

3.3.

A criterion for transitivity. We will show the transitivity of certain spaces of matrices that remotely resemble Toeplitz matrices.

Let t, s be positive integers. Let R 1 be a partition of the interval r1, ts " t1, . . . , tu into intervals, and let R 2 be a partition of r1, ss into intervals. Let R be the product partition. We will be interested in matrices of the following special form:

(3.3) M " pm i,j q 1ďiďt 1ďjďs " ¨˚0 0 0 M R 0 0 0 ˚‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ '
, where R is an element of the product partition R, and M R is the submatrix pm i,j q pi,jqPR . Let Λ be a vector space of t ˆs matrices. For each R P R, say of size k ˆℓ, we define the following space of matrices:

(3.4) Λ rRs " N P Mat kˆℓ pCq ; D M P Λ of the form (3.3) with M R " N ( .
We regard Λ as a subspace of LpC t , C s q. If the rectangle R is rp, p `ks ˆrq, q `ℓs, we regard the space Λ rRs as a subspace of L `t0u p´1 ˆCk ˆt0u t´p´k , t0u q´1 ˆCℓ ˆt0u s´q´ℓ ˘.

Lemma 3.11. Assume that Λ rRs is transitive for each R P R. Then Λ is transitive.

An interesting feature of the lemma which will be useful later is that it can be applied recursively. Before giving the proof of the lemma, we illustrate its usefulness by showing the transitivity of generalized Toeplitz spaces:

Proof of Example 2.2. Consider the partition of r1, ds 2 into 1 ˆ1 "rectangles". If Λ is a generalized Toeplitz space then Λ rRs " Mat 1ˆ1 pCq " C for each rectangle R. These are transitive spaces, so Lemma 3.11 implies that Λ is transitive.

Before proving Lemma 3.11, notice the following dual characterization of transitivity, whose proof is immediate: Lemma 3.12. A subspace Λ Ă LpC t , C s q is transitive iff for any non-zero vector u P C t and any non-zero linear functional φ P pC s q ˚there exists M P Λ such that φpM ¨uq ‰ 0.

Proof of Lemma 3.11. Take any non-zero vector u " pu 1 , . . . , u t q in C t and a nonzero functional φpv 1 , . . . , v s q " ř s j"1 φ j v j in pC s q ˚. By Lemma 3.12, we need to show that there exists M " px ij q P Λ such that (3.5) φpM ¨uq "

t ÿ i"1 s ÿ j"1 φ j x ij u i is non-zero.
Let i 0 be the least index such that u i ‰ 0, and let j 0 be the greatest index such that φ j ‰ 0. Let R be the element of R that contains pi 0 , j 0 q. Notice that if M is of the form (3.3) then the pi, jq-entries of M that are above left (resp. below right) of R do not contribute to the sum (3.5), because φ i (resp. u j ) vanishes. That is, φpM ¨uq depends only on M R and is given by ř pi,jqPR φ j x ij u i ; Since Λ rRs is transitive, by Lemma 3.12 there is a choice of a matrix M P Λ of the form (3.3) so that φpM ¨uq ‰ 0. So we are done.

3.4. Preorder in the complex plane. We consider the set C ˚{T of equivalence classes of the relation (3.1). Since T is the torsion subgroup of C ˚, the quotient C ˚{T is an abelian torsion-free group. Therefore it admits a multiplication-invariant total order ď, by a result of Levi [Le]. 11 Let rzs P C ˚{T denote the equivalence class of z P C ˚. Let us extend the notation, writing z ď z 1 if rzs ď rz 1 s. Then ď becomes a multiplication-invariant total preorder on C ˚that induces the equivalence relation -. In other words, for all z, z 1 , z 2 P C ˚we have:

' z ď z 1 or z 1 ď z; ' z ď z 1 and z 1 ď z ðñ z -z 1 ; ' z ď z 1 and z 1 ď z 2 ùñ z ď z 2 ; ' z ď z 1 ùñ zz 2 ď z 1 z 2 . It follows that: ' z ď z 1 ùñ pz 1 q ´1 ď z ´1.
We write z ă z 1 when z ď z 1 and z ffi z 1 . 3.5. Proof of the easy part of Theorem 3.7.

Proof of part 1 of Theorem 3.7. If cpAq " d then in particular all eigenvalues are different and so the matrix A is diagonalizable. So with a change of basis we can assume that A " Diagpλ 1 , . . . , λ d q. We can also assume that the eigenvalues are increasing with respect to the preorder introduced in § 3.4:

λ 1 ă λ 2 ă ¨¨¨ă λ d .
Fix any matrix B with only nonzero entries, and consider the space Λ " sorb Ad A X, which is described by (2.6). We will use Lemma 3.11 to show that Λ is transitive. Let R be the partition of r1, ds 2 into 1ˆ1 rectangles. Given a cell R " tpi 0 , j 0 qu P R and a coefficient t P C, there exists a polynomial f such that f pλ i λ ´1 j q equals t if λ i λ ´1 j " λ i0 λ ´1 j0 and equals 0 otherwise. Because the eigenvalues are ordered, M " f pAd A q ¨B is a matrix in Λ of the form (3.3). Also, M R " ptq. So Λ rRs " C, which is transitive. This shows that rig Ad A " 1, and rig `Ad A ď 2. Thus, as d ě 2, we have rig `Ad A " 2.

Proof of the hard part of the rigidity estimate

This section is wholly devoted to prove part 2 of Theorem 3.7. In the course of the proof we need to introduce some terminology and to establish several intermediate results. None of these are used in the rest of the paper, apart form a simple consequence, which is Remark 4.16.

11 Let us give a direct proof of the existence of an invariant order on C˚{T . There is an isomorphism between R ' pR{Qq and C˚{T , namely px, yq Þ Ñ exppx `2πiyq. So it suffices to find an invariant order in R{Q (and then take the lexicographic order). Take a Hamel basis B of the Q-vector space R so that 1 P B. Then R{Q is a direct sum of abelian groups À xPB, x‰1 xQ. Order each xQ in the usual way, take any total order on B, and consider the induced lexicographic order on R{Q.

4.1. The normal form. Let A P GLpd, Cq. In order to describe the estimate on rig `Ad A , we need to put A in a certain normal form, which we now explain.

We fix a preorder ď on C ˚as in § 3.4. Let λ 1 , . . . , λ r be the eigenvalues of A, listed without repetitions, and with respective multiplicities s 1 , . . . , s r . Assume they are ordered:

(4.1) λ 1 ď ¨¨¨ď λ r .
Reindex the sequence of eigenvalues λ 1 , . . . , λ r as

λ 1,1 -λ 1,2 -¨¨¨-λ 1,r1 ă λ 2,1 -λ 2,2 -¨¨¨-λ 2,r2 ă ¨¨Ẅ
rite each eigenvalue in polar coordinates:

λ i,j " r i exppθ i,j ? ´1q
, where r i ą 0 and 0 ď θ i,j ă 2π.

Reorder the eigenvalues so that, for each i,

θ i,1 ă θ i,2 ă ¨¨¨ă θ i,ri .
With a change of basis, we can assume that A has modified Jordan form:

(4.2) A " ¨A1 . . . A r ‹ ', A k " ¨λk D t k,1 . . . λ k D t k,τ k ‹ ',
where t k,1 `¨¨¨`t k,τ k " s k and D t is the following t ˆt Jordan block:

(4.3) D t " ¨1 1 1 1 ‹ ‹ ' .
The matrix A will be fixed from now on.

4.2. Geography. This subsection contains several definitions which will be fundamental in all arguments until the end of the section. We will define certain subregions of the set t1, . . . , du 2 of matrix entry positions, which depend on the normal form of the matrix A. Later we will see they are related to Ad A -invariant subspaces. We will use "geographical" terms for those regions: islands, cities, and districts. The regions will have some numerical attributes (banner, area, population); these attributes may seem mysterious initially, but later we will relate them with numerical invariants of Ad A (eigenvalues, multiplicities, geometric multiplicities). We also introduce other attributes of the regions (northern and southern cities, latitude of a district) which will be useful later in the proofs of our rigidity estimates.

Recall A is a matrix in normal form as explained in § 4.1. Define three partitions P i , P c , P d of the set r1, ds " t1, . . . , du into intervals:

' The partition P i corresponds to equivalence classes of eigenvalues under the relation -: the right endpoints of its atoms are the numbers s 1 `¨¨¨`s k where k " r or k is such that λ k ă λ k`1 . ' The partition P c corresponds to eigenvalues: the right endpoints of its atoms are the numbers s 1 `¨¨¨`s k , where 1 ď k ď r. So P c refines P i . ' The partition P d corresponds to Jordan blocks: the right endpoints of its atoms are the numbers s 1 `¨¨¨`s k´1 `tk,1 `¨¨¨`t k,ℓ , where 1 ď k ď r and 1 ď ℓ ď τ k . So P d refines P c .

For ˚" i, c, d, let P 2 ˚be the partition of the square r1, ds 2 into rectangles that are products of atoms of P ˚. The elements of P 2 i are called islands, the elements of P 2 c are called cities, and elements of P 2 d are called districts. Thus the world W " r1, ds 2 is a disjoint union of islands, each of them is a disjoint union of cities, each of them is a disjoint union of districts.

Example 4.1. Suppose d " 17, A has r " 5 eigenvalues λ1 " exp 1 2 πi, λ2 " exp 7 6 πi, λ3 " exp 11 6 πi, λ4 " 2 exp 1 6 πi, λ5 " 2 exp 5 6 πi with respective Jordan blocks of sizes 4, 2, 1; 3, 2; 2; 2, 1. Then there are 4 islands, 25 cities, and 64 districts. See Fig. 1. For each city (or district) we define its row eigenvalue and its column eigenvalue in the obvious way: If a city C equals I k ˆIℓ where I k and I ℓ are intervals with right endpoints s 1 `¨¨¨`s k and s 1 `¨¨¨`s ℓ , respectively, then the row eigenvalue of C is λ k and the column eigenvalue of C is λ ℓ . The row and column eigenvalues of a district D are defined respectively as the row and column eigenvalues of the city that contains D.

Let C be a city with row eigenvalue λ i,j and column eigenvalue λ k,ℓ . The banner of C is defined by λ ´1 k,ℓ λ i,j . The argument of the city is the quantity θ k,ℓ ´θi,j P p´2π, 2πq. (It coincides, modulo 2π, with the argument of the banner.) The city is called southern within its island if it has strictly negative argument, and northern within its island otherwise.

Each district D has an address of the type "i th row, j th column, city C"; then the latitude of the district D within the city C is defined as j ´i. See an example in Fig. 1.

If two cities lie in the same island then their banners are equivalent mod T . Thus every island has a well-defined banner class in C ˚{T .

If a district, city, or island intersects the diagonal tp1, 1q, . . . , pd, dqu then we call it equatorial. Equatorial regions are always square. Thus every equatorial city has banner 1 and every city with banner 1 lies on a equatorial island.

The area of a district, city, island or world is defined as the product of its sides. The population of a district is defined as the minimum of its sides. Populations of cities, islands and world are defined as the sum of the areas and populations of the corresponding districts.

Let us notice some facts on the location of the banners (which will be useful to apply Lemma 3.11): Let β be the banner of the city C, and let rβs be the banner class of the island I. Then:

1. All the islands with banner class rβs are inside the regions marked with ˆ. 2. If the city C is northern (resp. southern) within I then the all the northern (resp. southern) cities with same banner β are inside the regions marked with `.

Proof. In view of the ordering of the eigenvalues (4.1), the banner class increases strictly (with respect to the order ă, of course) when we move rightwards or upwards to another island. So Claim (1) follows.

The argument of a city takes values in the interval p´2π, 2πq. It increases strictly by moving rightwards or upwards inside I. If two cities in the same island are both northern or both southern then they have the same banner if and only if they have the same argument. So Claim (2) follows.

4.3. The adjoint in geographical terms. Given any d ˆd matrix X " px i,j q and a district, city or island R " rp, p `ts ˆrq, q `ss we define the submatrix of X corresponding to R as px i,j q pi,jqPR . We regard the space of R-submatrices as L `t0u p´1 ˆCt ˆt0u d´p´t , t0u q´1 ˆCs ˆt0u d´q´s ˘, or as the set of d ˆd matrices whose entries outside R are all zero. Such spaces are denoted by R ˝, and are invariant under Ad A . Indeed, if R " D is a district then identifying D ˝with Mat tˆs pCq, the action of Ad A |D ˝is given by

X Þ Ñ λ k λ ´1 ℓ D t XD ´1
s , where λ k λ ´1 ℓ is the banner of D, and D t , D s are Jordan blocks defined by (4.3).

If R is an equatorial district, city, or island we will refer to the d ˆd-matrix in R whose R-submatrix is the identity as the identity on R ˝. The following observation will be useful: Lemma 4.3. If D is an equatorial district then the identity on D ˝is a eigenvalue of the operator Ad A |D ˝corresponding to a Jordan block of size 1 ˆ1.

Proof. Suppose D has size t ˆt. Assume that the claim is false. This means that there exists a matrix X P Mat tˆt pCq such that D t XD ´1 t " X `Id, which is impossible because X and X `Id have different spectra.

We are going to prove the following: Lemma 4.4. For each district D, the only eigenvalue of Ad A |D ˝is the banner of the city that contains D. Moreover, the geometric multiplicity of the eigenvalue is the population of the district.

The following facts are immediate consequences:

' The eigenvalues of Ad A are the banners of cities.

' The multiplicity of the eigenvalue β for the operator Ad A is the total area of cities of banner β. ' The geometric multiplicity of the eigenvalue β for Ad A is the total population of cities of banner β.

Lemma 4.4 is equivalent to the following:

Lemma 4.5. Let U t,s be the linear operator on Mat tˆs pCq given by U t,s pXq " D t XD ´1 s , where D t , D s are Jordan blocks defined by (4.3). Then the only eigenvalue of U t,s is 1, and its geometric multiplicity is minpt, sq.

The rest of this subsection is devoted to prove Lemma 4.5. To begin, notice that:

(4.4) D ´1 s " ¨1 ´1 1 ¨¨¨p´1q s´1 . . . 1 ´1 1 ‹ ‹ ‹ ‹ ‹ ‹ ' .
To describe U t,s , it suffices to describe its action on the matrices E i,j whose unique nonzero entry is a 1 in the pi, jq position. Using (4.4), we obtain U t,s pE i,j q " s ÿ p"j p´1q k´j pE i,p `Ei´1,p q , or, visually:

U t,s ¨1 ‹ ‹ ‹ ‹ ‹ ‹ ‹ ' " ¨1 ´1 1 ¨¨¨˘1 1 ´1 1 ¨¨¨˘1 ‹ ‹ ‹ ‹ ‹ ‹ ‹ ' .
The picture above suggests a way of "embedding" all the maps U t,s into a single infinite-dimensional model. More precisely, consider the space M of infinite matrices of the form X " px k,ℓ q k,ℓď0 , where k, ℓ are non-positive integers, that have only finitely many non-zero entries. For each pair of positive integers t, s, define a monomorphism ι t,s : Mat tˆs pCq Ñ M by pb i,j q i,j Þ Ñ px k,ℓ q k,ℓ where x k,ℓ "

# b t`k,s`ℓ if k ą ´t and ℓ ą ´s, 0 otherwise Define a linear operator U : M Ñ M by px k,ℓ q k,ℓ Þ Ñ py k,ℓ q k,ℓ where y k,ℓ " ℓ ÿ q"´8
p´1q ℓ´q px k,q `xk´1,q q , Then the following diagram commutes:

Mat tˆs pCq ιt,s / / Ut,s M U Mat tˆs pCq ιt,s / / M
Let us prove a few facts about the operator U . It is convenient to consider also N " U ´id.

If X " px k,ℓ q P M and n " 1, 2, . . . , then we define the n th diagonal of X as the n-tuple px 0,´pn´1q , x ´1,´pn´2q , . . . , x ´pn´1q,0 q. Define the height hpXq of X as 0 if X " 0, otherwise hpXq is the maximal n such that X has a nonzero n th diagonal. It is clear that (4.5) hpN pXqq ă hpXq if X ‰ 0.

It follows that the operator N is nilpotent, in the sense that every orbit eventually hits zero.

Lemma 4.6. Let X " px k,ℓ q P M and let Z " pz k,ℓ q " N pXq. If hpXq ď n then the n th diagonal of X can be determined from its first element and the pn ´1q th diagonal of Z by the formula

x ´p,´pn´1´pq " x 0,´pn´1q `p´1 ÿ q"0 z ´q,´pn´2´qq , pp " 0, 1, . . . , n ´1q.

Proof. It suffices to see that, for each q " 0, 1, . . . , n ´2, z ´q,´pn´2´qq " x ´pq`1q,´pn´2´qq ´x´q,´pn´1´qq .

For each t " 1, 2, . . . , let I t P M denote the image under ι t,t of the t ˆt identity matrix. A linear combination of matrices of this type is a matrix with constant diagonals and so will be called a Toeplitz matrix.

Lemma 4.7. U pXq " X if and only if X is a Toeplitz matrix.

Proof. Since the t ˆt identity is fixed by the U t,t , we conclude that I t is fixed by U , proving the "if" part.

To see the converse, take X " px k,ℓ q in the kernel of N . Let n " hpXq be height of X. By Lemma 4.6, the n th diagonal of X is constant, say pc, c, . . . , cq. Thus X ´cI n has height at most n ´1, and belongs to the kernel of N . It follows by induction in n that X is a Toeplitz matrix.

Proof of Lemma 4.5. Since U ´id is nilpotent, so is U t,s ´id, which means that the only eigenvalue of U t,s is 1.

The matrices I 1 , I 2 , . . . , I minpt,sq belong to the image of ι t,s ; therefore their inverse images are eigenvectors of U t,s . The space V spanned by these eigenvectors is exactly M P Mat tˆs pCq; ι t,s pM q is a Toeplitz matrix ( . By Lemma 4.7, V is also the space of the eigenvectors of U t,s . This proves that the geometric multiplicity of U t,s is minpt, sq.

Remark 4.8. It is natural to ask what are the sizes of the Jordan blocks corresponding to the eigenvectors exhibited in the proof of Lemma 4.4. We don't know the answer, except for the last eigenvector ι ´1 t,s pI minpt,sq q, which corresponds to a 1 ˆ1 Jordan block. This fact, which generalizes Lemma 4.3, can be easily shown using Lemma 4.6.

4.4. Rigidity estimates for districts and cities. Lemma 4.9. For any district D, we have rig `pAd A |D ˝q ď pop D.

Proof. By Lemma 4.4 (and Proposition 3.3), Ad A |D ˝has acyclicity n " pop D, that is, there are matrices X 1 , . . . , X n P D ˝such that sorb Ad A pX 1 , . . . , X n q is the whole D ˝(and, in particular, is transitive in D ˝). So rigpAd A |D ˝q ď n, which proves the lemma for non-equatorial districts.

If D is an equatorial district then, by Lemma 4.3, D ˝splits invariantly into two subspaces, one of them spanned by the the identity matrix on D ˝. So we can choose the matrices X i above so that X 1 is the identity. This shows that rig `pAd A |D ˝q ď n.

In all that follows, we adopt the convention max ∅ " 0. Proof. For each district D in C, let rpDq " rig `pAd A |D ˝q. Take matrices X D,1 , . . . , X D,rpDq such that Λ D :" sorb Ad A `XD,1 , . . . , X D,rpDq ˘is a transitive subspace of D ˝, and X D,1 is the identity matrix in D ˝if D is an equatorial district. Define X D,j " 0 for j ą rpDq. For each latitude ℓ, let n ℓ be the maximum of rpDq over the districts D of C with latitude ℓ, and let

Y ℓ,j " ÿ D is a district of C with latitude ℓ X D,j , for 1 ď j ď n ℓ .
Notice that if C is an equatorial city then Y 0,1 is the identity matrix in C ˝. Consider the space ∆ " sorb Ad A Y ℓ,j ; ℓ is a latitude, 1 ď j ď n ℓ ( . We claim that for every district D in C and for every M P Λ D , we can find some N P ∆ with the following properties:

' the submatrix N D equals M ; ' for every district D 1 in D that has a different latitude than D, the submatrix N D 1 vanishes.

Indeed, if M " ř rpDq j"1 f j pAd A qX D,j for certain polynomials f j , we simply take N " ř rpDq j"1 f j pAd A qY ℓ,j , where ℓ is the latitude of D.

In notation (3.4), the claim we have just proved means that ∆ rDs Ą Λ D . So we can apply Lemma 3.11 and conclude that ∆ is a transitive subspace of C ˝. Therefore rig `pAd A |C ˝q ď ř n ℓ , as we wanted to show.

Example 4.11. Using Lemmas 4.9 and 4.10, we see that the city C whose district populations are indicated in Fig. 1 has rig `pAdA|C ˝q ď 5.

In fact, we will not use Lemmas 4.9 and 4.10 directly, but only the following immediate consequence: Lemma 4.12. For every city C we have rig `pAd A |C ˝q ď pop C. The inequality is strict if has more than one row of districts and more that one column of districts.

4.5. Comparative demographics. If R is a district, city or island, we define its row projection π r pRq as the unique equatorial district, city or island (respectively) that is in the same row as R. Analogously, we define the column projection π c pRq.

Lemma 4.13. For any city C, we have

pop C ď pop π r pCq `pop π c pCq 2 .
Moreover, equality implies that the number of rows of districts for C equals the number of columns of districts.

This is a clear consequence of the abstract lemma below, taking x α , α P F 0 (resp. α P F 1 ) as the sequence of heights (resp. widths) of districts in C, counting repetitions.

Lemma 4.14. Let F be a nonempty finite set, and let x α be positive numbers indexed by α P F . Take any partition F " F 0 \ F 1 . For ǫ, δ P t0, 1u, let

Σ ǫδ " ÿ pα,βqPFǫˆF δ minpx α , x β q . Then Σ 01 " Σ 10 ď Σ 00 `Σ11 2 .
Moreover, equality implies that F 0 and F 1 have the same cardinality.

Proof. We will in fact prove the stronger fact:

(4.6) Σ 00 ´2Σ 01 `Σ11 ě `|F 0 | ´|F 1 | ˘2 min αPF x α ,
where |¨| denotes set cardinality. The proof is by induction on |F |. It clearly holds for |F | " 1. Fix some n and assume that (4.6) always holds when |F | " n. Take a set F with |F | " n `1, and take positive numbers x α , α P F . We can assume that F " t1, . . . , n `1u and that x 1 ě ¨¨¨ě x n`1 . Take any partition F " F 0 \ F 1 . Without loss of generality, assume that n `1 P F 0 . Apply the induction hypothesis to F 1 " t1, . . . , nu, obtaining

Σ 1 00 ´2Σ 1 01 `Σ1 11 ě `|F 0 | ´1 ´|F 1 |q 2 x n . We have Σ 00 " Σ 1 00 ``2|F 0 | ´1˘x n`1 , Σ 01 " Σ 1 01 `|F 1 |x n`1
, and Σ 11 " Σ 1 11 , so (4.6) follows.

If R is an island or the world, let pop 1 R denote the banner 1 population on R, that is, the sum of the populations of the cities in R with banner 1.

Let us give the following useful consequence of Lemma 4.13:

Lemma 4.15. acyc Ad A " pop 1 W.

Proof. By Proposition 3.3, acyc Ad A is the maximum of the geometric multiplicities of the eigenvalues of Ad A . Those eigenvalues are the banners β, and the geometric multiplicity of each β is the worldwide total population with banner β. Thus, to prove the lemma we have to show that banner 1 has biggest worldwide population.

Let β be a banner. Then, using Lemma 4.13,

ÿ C is a city with banner β pop C ď 1 2 ÿ C is a city with banner β pop π r pCq `1 2 ÿ C is a city with banner β pop π c pCq .
Since no two cities in the same row (resp. column) can have the same banner, the restriction of π r (resp. π c ) to the set of cities with banner β is a one-to-one map. This allows us to conclude.

Remark 4.16. The Jordan type of a matrix A P Mat dˆd pCq consists on the following data:

1. The number of different eigenvalues.

2. For each eigenvalue, the number of Jordan blocks and their sizes. It follows from Lemma 4.15 that these data is sufficient to determine acyc AdA. (Of course, one can easily write down a formula; see e.g. [START_REF] Gantmacher | The theory of matrices[END_REF]p. 222] or [START_REF] Arnold | Geometrical methods in the theory of ordinary differential equations[END_REF]p. 241].) 4.6. Rigidity estimate for islands. Lemma 4.17. For any island I,

rig `pAd A |I ˝q ď pop 1 π r pIq `pop 1 π c pIq 2 .
In order to prove this lemma, it is convenient to consider separately the cases of non-equatorial and equatorial islands.

Proof of Lemma 4.17 when I is non-equatorial. For each banner β in I, let n β (resp. s β ) be the maximum of rig `pAd A |C ˝q over the northern (resp. southern) cities C in I with banner β. For each city C with banner β, choose matrices X C,1 , . . . , X C,n β `sβ P C ˝such that:

' Λ C :" sorb Ad A pX C,1 , . . . , X C,m q is a transitive subspace of C ˝; ' if C is southern then X 1 " X 2 " ¨¨¨" X n β " 0; ' if C is northern then X n β `1 " ¨¨¨" X n β `sβ " 0. Also, let X C,j " 0 for j ą n β `sβ . Next, define (4.7) Y β,j " ÿ C is a city of I with banner β X C,j and (4.8) Z j " ÿ β banner on I Y β,j
Consider the space ∆ " sorb Ad A pZ 1 , . . . , Z m q, where m " max

β banner on I pn β `sβ q It follows from Lemma 3.2 that ∆ " sorb Ad A Y β,j ; β is a banner, 1 ď j ď n β `sβ ( .
Recall notation (3.4). We claim that (4.9) Λ C Ă ∆ rCs .

Indeed, given M P Λ C , write M " ř j f j pAd A qX C,j , where the f j 's are polynomials and f j " 0 whenever X C,j " 0. Consider N " ř j f j pAd A qY β,j , where β is the banner of C. Then it follows from Lemma 4.2 (part 2) that N P ∆ rCs . This shows (4.9). So, by Lemma 3.11, ∆ is a transitive subspace of I ˝, showing that rig `pAd A |I ˝q ď m.

To complete the proof of the lemma in the non-equatorial case, we will show that (4.10) m ď pop 1 π r pIq `pop 1 π c pIq 2 .

Let β be the banner for which n β `sβ attains the maximum m. If n β ą 0, let C N be a northern city within I with banner β and rig `pAd A |C N q " n β . If s β ą 0, let C S be a southern city within I with banner β and rig `pAd A |C S q " s β . Assume for the moment that both cities exist. Let C 1 , C 2 , C 3 , C 4 be projected equatorial cities as in Fig. 3.

W I 1 I 2 I C 1 C 2 C 3 C 4 C S C N Figure 3. C 1 " πrpC N q, C 2 " πrpC S q, C 3 " πcpC S q, C 4 " πcpC N q. Then m " rig `pAd A |C N q `rig `pAd A |C S q (i) ď pop C N `pop C S (ii) ď 1 2 `pop C 1 `¨¨¨`pop C 4 ˘ď 1 2 `pop 1 I 1 `pop 1 I 2 ˘,
where (i) and (ii) follow respectively from Lemmas 4.12 and 4.13. This proves (4.10) in this case. If there is no southern city or no northern city within I with banner 1 then the proof of (4.10) is easier. So the lemma is proved for non-equatorial I.

We now consider equatorial islands. There is an exceptional kind of island for which the proof of the rigidity estimate has to follow a different strategy. An island is called exotic if it has only the banners 1 and ´1 (so it is equatorial and has 4 cities), each city has a single district, and all districts have the same population.

Proof of Lemma 4.17 when I is equatorial non-exotic. As in the previous case, let n β (resp. s β ) be the maximum of rig `pAd A |C ˝q over the northern (resp. southern) cities C in I with banner β.

We claim that (4.11) n β `sβ ă pop 1 I for all banners β ‰ 1 in I.

Let us postpone the proof of this inequality and see how to conclude. Let M " pop 1 I. In view of Lemma 4.12 and relation (4.11), for each island C we can take matrices X C,1 , . . . , X C,M P C ˝such that:

' Λ C :" sorb Ad A pX C,1 , . . . , X C,M q is a transitive subspace of C ˝; ' X C,M " 0 if C is non-equatorial; ' X C,M is the identity in C ˝if C is equatorial.
Then define matrices Z j as before: by (4.7) and (4.8). Here we have that Z M is the identity matrix in I ˝. As before, sorb Ad A pZ 1 , . . . , Z M q is a transitive subspace of I ˝. Hence rig `pAd A |I ˝q ď M " pop 1 I, as desired. Now let us prove (4.11). Consider a banner β ‰ 1 in I. Let C N (resp. C S ) be a northern (resp. southern) city within I with banner β and of maximal population; assume for the moment that both cities exist. Let C 1 , C 2 , C 3 , C 4 be projected equatorial cities as in Fig. 4.

I C 1 C 2 C 3 C 4 C N C S Figure 4. C 1 " πcpC S q, C 2 " πrpC N q, C 3 " πcpC N q, C 4 " πrpC S q. It is possible that C 1 " C 2 or C 3 " C 4 .
Then n β `sβ " rig `pAd A |C N q `rig `pAd A |C S q ď pop C N `pop C S (4.12) ď 1 2 `pop C 1 `¨¨¨`pop C 4 (4.13) ď pop 1 I. (4.14) Inequality (4.12) follows from Lemma 4.12, inequality (4.13) follows from Lemma 4.13, and inequality (4.14) holds because the cities C 1 , . . . , C 4 are equatorial, and any city can appear at most twice in this list. So (4.15) n β `sβ ď pop 1 I.

In the case that there is no northern city or no southern city with banner β (i.e., n β or s β vanishes), a simpler argument shows that strict inequality holds in (4.15). Now assume by contradiction that (4.11) does not hold. Then we must have equality in (4.15). By what we just saw, both cities C N and C S above exist. Then the inequalities in (4.12)-(4.14) become equalities. Since (4.14) is an equality, there must be exactly two equatorial cities in I. So the non-equatorial banner β satisfies β ´1 " β, that is, β " ´1. Since (4.13) is an equality, it follows from Lemma 4.13 that both non-equatorial cities are district-square. So there is some ℓ such that all four cities in I have ℓ rows of districts and ℓ columns of districts. Since (4.12) is an equality, Lemma 4.12 implies that ℓ " 1. That is, I is a exotic island, a situation which we excluded a priori. This contradiction proves (4.11) and Lemma 4.17 in the present case.

We now come to exotic islands. In all the previous cases, the transitive subspace we found had some vaguely Toeplitz form. For exotic islands, however, this strategy is not efficient. 12 What we are going to do is to find a transitive space of vaguely Hankel form, namely the following:

(4.16) Λ k " "ˆP M M N ˙; M , N , P are k ˆk matrices * .
Notice that Λ k " S k ¨Γk , where

S k " ˆ0 Id Id 0 ˙and Γ k " "ˆM N P M ˙; M , N , P are k ˆk matrices * .
Since Γ k is a generalized Toeplitz space, it follows from Remark 2.3 that Λ k is transitive.

Proof of Lemma 4.17 when I is exotic. If I is exotic then it has size 2k ˆ2k for some k, and the operator Ad A |I ˝is given by X Þ Ñ Ad L pXq, where

L " ˆD 0 0
´D˙, and D " D k is the Jordan block (4.3).

Let V be unique Ad D -invariant subspace of Mat kˆk pCq that has codimension 1 and does not contain the identity matrix (which exists by Lemma 4.3). Take matrices X 1 , . . . , X k P Mat kˆk pCq such that X 1 " Id and V " sorb Ad D pX 2 , . . . , X k q. Define Y 1 , . . . , Y k P Mat 2kˆ2k pCq by

Y 1 " ˆId 0 0 Id ˙, Y j " ˆXj 0 0 0 ˙for 2 ď j ď k, Then sorb Ad L pY 1 , . . . , Y k q " "ˆx Id `K 0 0 xId ˙; x P C, K P V * .
For j " k `1, . . . , 2k, define

Y j " ˆ0 X j´k X j´k X j´k ˙.
Then, by Lemma 3.2, sorb Ad L pY k`1 , . . . , Y 2k q " "ˆ0 M M N ˙; M, N P Mat kˆk pCq * .

Therefore sorb Ad L pY 1 , . . . , Y 2k q is the transitive space given by (4.16). Since Y 1 is the identity on I, this shows that rig `pAd A |I ˝q ď 2k " pop 1 I, concluding the proof of Lemma 4.17.

4.7.

The final rigidity estimate. Let c " cpAq be the number of equivalence classes mod T of eigenvalues of A.

Lemma 4.18. If c ă d then

rig `Ad A ď pop 1 W ´c `1 . Proof. Let m " pop 1 W ´c `1. For each island I, let rpIq " X 1 2 ppop 1 π r pIq `pop 1 π c pIqq \ .
We claim that (4.17)

rpIq ď # m if I is an equatorial island, m ´1 if I is a non-equatorial island.
Let us postpone the proof of this and see how to conclude the lemma.

In view of Lemma 4.17 and relation (4.17), for each island I we can take matrices X I,1 , . . . , X I,m P I ˝such that:

12 For those who have read Appendix A, notice that the simplest exotic island appears when A has a type 3 constraint; we have dealt with them in the proof of Proposition A.2.

' Λ I :" sorb Ad A pX I,1 , . . . , X I,m q is a transitive subspace of I ˝; ' X I,m " 0 if I is non-equatorial; ' X I,m is the identity in I ˝if I is equatorial.

Define matrices:

Y α,j " ÿ I is an island with banner class α X I,j pα is a banner class, 1 ď j ď mq,

Z j " ÿ α is a banner class Y α,j p1 ď j ď mq.
So Z m is the d ˆd identity matrix. Consider the space ∆ " sorb Ad A pZ 1 , . . . , Z m q.

It follows from Lemma 3.2 that ∆ " sorb Ad A Y α,j ; α is a banner class, 1 ď j ď m ( .

We claim that every island I,

(4.18) Λ I Ă ∆ rIs .
Indeed, if M P I then we can write M " ř j f j pAd A qX I,j , where the f j 's are polynomials. Consider N " ř j f j pAd A qY α,j , where α is the banner class of I. It follows Lemma 4.2 (part 1) that N P ∆ rIs . This proves (4.18). So, by Lemma 3.11, ∆ is a transitive subspace of Mat dˆd pCq, showing that rig `Ad A ď m.

To conclude the proof we have to show estimate (4.17). First consider a equatorial island I. Since there are c equatorial islands, and each of them has a positive banner 1 population, we conclude that rpIq ď m, as claimed. Now take a non-equatorial I. Applying what we just proved for the equatorial islands π r pIq and π c pIq, we conclude that rpIq ď m. Now assume that (4.17) does not hold for I, that is, rpIq " m. Then pop 1 π r pIq " pop 1 π c pIq " m " pop 1 W ´c `1.

Since pop 1 W ě pop 1 π r pIq `pop 1 π c pIq `c ´2, we have m " 1 and pop 1 W " c. This means that pop 1 Ĩ " 1 for all equatorial islands Ĩ, which is only possible if c " d. However, this case was excluded by hypothesis.

This proves (4.17) and hence Lemma 4.18. Proof of part 2 of Theorem 3.7. Apply Lemmas 4.15 and 4.18.

Proof of the hard part of the codimension m theorem

We showed in Proposition 2.11 that codim P pKq m ď m. In this section, we will prove the reverse inequalities. More precisely, we will first prove Theorem 1.9 and then deduce Theorem 1.8 from it.

5.1. Preliminaries on elementary algebraic geometry.

5.1.1. Quasiprojective varieties. An algebraic subset of C n is also called an affine variety. A projective variety is a subset of CP n that can be expressed as the zero set of a family of homogeneous polynomials in n `1 variables. The Zariski topology on an (affine or projective) variety X is the topology whose closed sets are the (affine or projective) subvarieties of X.

An open subset U of a projective variety X is called a quasiprojective variety. We consider in U the induced Zariski topology. The affine space C n can be identified with a quasiprojective variety. namely its image under the embedding pz 1 , . . . , z n q Þ Ñ p1 : z 1 : ¨¨¨: z n q.

If X and Y are quasi-projective varieties then the product X ˆY can be identified with a quasiprojective variety, namely its image under the Segre embedding; see [START_REF] Shafarevich | Basic Algebraic Geometry[END_REF]§ 5.1].

The following is an important and very useful property of projective varieties. (See [START_REF] Shafarevich | Basic Algebraic Geometry[END_REF]p. 58] for a proof).

Proposition 5.1. If X is a projective variety and Y is a quasiprojective variety then the projection p : X ˆY Ñ Y takes Zariski closed sets to Zariski closed sets.

A quasiprojective variety is called irreducible if it cannot be written as a nontrivial union of two quasiprojective varieties (that is, none contains the other). 5.1.2. Dimension. The dimension dim X of an irreducible quasiprojective variety X may be defined in various equivalent ways (see for instance [START_REF] Harris | Algebraic geometry: a first course[END_REF]p. 133ff]). It will be sufficient for us to know that there exists an (intrinsically defined) subvariety Y of the singular points of X such that in a neighborhood of each point of X Y , the set X is a complex submanifold of dimension (in the classical sense of differential geometry) dim X; moreover, each irreducible component of Y has dimension strictly less than dim X.

The dimension of a general quasiprojective variety is by definition the maximum of the dimensions of the irreducible components.

Remark 5.2. The dimension of a quasiprojective variety U Ă CP n coincides with the dimension of its Zariski-closure in CP n (see [START_REF] Harris | Algebraic geometry: a first course[END_REF]p. 135]).

The following lemma is useful to estimate the codimension of an algebraic set X from information about the fibers of a certain projection π : X Ñ Y .13 Lemma 5.3. Let Y be a quasiprojective variety. Let X Ă Y ˆCP n be a nonempty algebraically closed set. Let π : X Ñ Y be the projection along CP n . Then:

1. For each j ě 0, the set

C j " ty P Y ; codim π ´1pyq ď ju is algebraically closed in Y . 2.
The dimension of X is given in terms of the dimensions of the C j 's by:

(5.1) codim X " min j; Cj ‰∅ `j `codim C j ˘.
The lemma is a consequence of standard theorems in algebraic geometry but for the reader's convenience let us spell out the details.

Proof of Lemma 5.3. In what follows, all topologies are of course Zariski. We will prove the equivalent "dual form" of the lemma, namely, that the sets Y k " y P πpXq; dim π ´1pyq ě k ( are algebraically closed in Y , and

(5.2) dim X " max k; Y k ‰∅ `k `dim Y k ˘.
First, the sets X k " tx P X; dim π ´1pπpxqq ě ku are closed. (see [START_REF] Harris | Algebraic geometry: a first course[END_REF]Thrm. 11.12]). So, by Proposition 5.1, Y k " πpX k q is closed.

For each k with

X k ‰ ∅, let X k,i indicate the irreducible components of X k . Let µpk, iq " min xPX k,i dim π ´1pπpxqq .
Then, by [START_REF] Harris | Algebraic geometry: a first course[END_REF]Thrm. 11.12] (and Remark 5.2), dim X k,i " µpk, iq `dim πpX k,i q .

By definition, µpk, iq ě k; moreover equality holds unless

X k,i Ă X k`1 . So X k,i Ć X k`1 ñ dim X k,i " k `dim πpX k,i q ď k `dim Y k . Since X " Ť X k,i ĆX k`1 X k,i
, this proves the ď inequality in (5.2). To prove the converse inequality, fix any

k with Y k ‰ ∅. Find i such that dim πpX k,i q " dim Y k . Then dim X ě dim X k,i " µpk, iq `dim Y k ě k `dim Y k .
This proves (5.2) and hence the lemma.

Remark 5.4. Lemma 5.3 works with the same statement if CP n is replaced by C n`1 , provided one assumes that X Ă Y ˆCn`1 is homogeneous in the second factor (i.e., py, zq P X implies py, tzq P X for every t P C). Indeed, this follows from the fact that the projection C n`1 t0u Ñ CP n preserves codimension of homogeneous sets.

Dimension estimates for sets of vector subspaces. If

M P Mat nˆm pKq, let col M Ă K n denote the column space of M . A set X Ă Mat nˆm pKq is called column-invariant if M P X N P Mat nˆm pKq col M " col N , .
ñ N P X.

So a column-invariant set X is characterized by its set of column spaces. We enlarge the latter set by including also subspaces, thus defining:

(5.3) vXw :" E subspace of K n ; E Ă col M for some M P X ( .

In Appendix D we prove:

Theorem D.1. Let X Ă Mat nˆm pCq be an algebraically closed, column-invariant set. Suppose E is a vector subspace of C n that does not belong to vXw. Then codim X ě m `1 ´dim E .

5.1.4.

The real part of an algebraic set. Let X be an algebraically closed subset of C n . The real part of X is defined as X X R n . This is an algebraically closed subset of R n . Indeed, generators of the corresponding ideal f 1 , . . . , f k in CrT 1 , . . . , T n s can be replaced by the corresponding real and imaginary parts polynomials.

As in the complex case, there are many equivalent algebraic-geometric definitions of dimensions of real algebraic or semialgebraic sets. We just point out that a real algebraic or semialgebraic set admits a stratification into real manifolds such that the maximal differential-geometric dimension of the strata coincides with the algebraic-geometric dimension (see [START_REF] Bochnak | Real algebraic geometry[END_REF]p. 50]).

Proposition 5.5. If X is an algebraically closed subset of C n then dim R pX XR n q ď dim C X.
If V is a real (resp. complex) variety V and p P V then let rnk p pV q denote the real (resp. complex) rank of V at p, as defined by Whitney [Wh]. In that paper, he also shows: ' For any (real or complex) variety V , for any point p P V the rank rnk p pV q is greater than the codimension of V . ' If V is real (resp. complex) there is a point p P V such that the real (resp. complex) rank satisfies rnk p pV q " codim R pV q (resp. rnk p pV q " codim C pV q). ' Given a real variety V Ă R n , there is a unique smallest complex variety V ˚Ă C n containing V (in particular, V is the real part of V ˚). Then we have rnk p pV ˚q " rnk p pV q.

Proof of Proposition 5.5. Let V be the real variety X X R n . Let p P V such that rnk p pV q " codim R pV q. Consider the unique smallest complex variety then rnk p pV ˚q " rnk p pV q. In particular codim R pV ˚q ě codim C pV ˚q. Since V ˚Ă X, the proposition follows.

5.2. Rigidity and the dimension of the poor fibers. For simplicity of notation, let us write P m " P pCq m . Also, for A P GLpd, Cq, write: rpAq :" rig `Ad A ´1 .

We decompose the set P m of poor data in fibers:

(5.4) P m " ď

APGLpd,Cq tAu ˆPm pAq, where P m pAq Ă glpd, Cq m .

Lemma 5.6. For any A P GLpd, Cq, the codimension of P m pAq in glpd, Cq m is at least m `1 ´rpAq.

The lemma follows easily from Theorem D.1 above:

Proof. Fix A P GLpd, Cq, and write r " rpAq. We can assume that r ď m, otherwise there is nothing to prove. By definition, there exists a r-dimensional subspace E Ă glpd, Cq m such that sorb Ad A pId _ Eq is transitive. Identify glpd, Cq with C d 2 and thus regard P m pAq as a subset of Mat d 2 ˆmpCq. Since the set P m is algebraically closed and saturated (recall § 2.3), the fiber P m pAq is algebraically closed and column-invariant, as required by Theorem D.1. In the notation (5.3), we have E R vP m pAqw. So applying Theorem D.1, the lemma is proved.

5.3. How rare is high rigidity? For simplicity of notation, let us write:

apAq :" acyc Ad A for A P GLpd, Cq.

So Theorem 3.7 says that rpAq ď apAq ´cpAq provided cpAq ă d.

Lemma 5.7. For any integer k ě 1, the set

M k " A P GLpd, Cq; rpAq ě k ( ; is algebraically closed in GLpd, Cq; moreover if M k ‰ ∅ then codim M k # " 0 if k " 1, ě k if k ě 2.
Lemma 5.7 is basically a consequence of Theorem 3.7, using the following construction:

Lemma 5.8. There is a family GpAq of subsets of GLpd, Cq, indexed by A P GLpd, Cq, such that the following properties hold:

' Each GpAq contains A. ' Each GpAq is an immersed manifold of codimension apAq ´cpAq. ' There are only countably many different sets GpAq.

The informal proof of the lemma goes as follows: For each A P GLpd, Cq, let GpAq be the set of matrices that have the same Jordan type as A (as defined in Remark 4.16), and (at least) the same mod T relations between the eigenvalues. Then GpAq contains the conjugacy class of A, which by Remark 3.4 has codimension apAq. We can also move the eigenvalues (keeping the mod T relations); this gives cpAq extra degrees of freedom, so the codimension of GpAq is apAq ´cpAq. Since there are only finitely many Jordan types of d ˆd matrices, and only countably many mod T relations, there are only countably many different sets GpAq. A formal proof of Lemma 5.8 follows:

Proof. First suppose that A P GLpd, Cq is a matrix in Jordan form:

A " ¨Bt1 pλ 1 q . . .

B tn pλ n q ‹ ', where B t pλq :" ¨λ 1 1 λ ‹ ‹ ' P Mat tˆt pCq.
Let c " cpAq; by the definition (3.2), we can choose numbers µ 1 , . . . , µ c P C ˚, θ 1 , . . . , θ n P T , k 1 , . . . , k n P t1, . . . , cu such that λ i " θ i µ ki for each i " 1, . . . , n. Let U be the subset of py 1 , . . . , y c q P C c such that

y k ‰ 0 for each k, (5.5) i ‰ j ñ θ i y ki ‰ θ j y kj .
(5.6) Define a map Φ : U Ñ GLpd, Cq by: Φpy 1 , . . . , y c q " ¨Bn1 pθ 1 y k1 q . . .

B n k pθ n y kn q ‹ ' .
For every y P U , condition (5.6) assures that Φpyq has the same Jordan type as A, and therefore, by Remark 4.16, apΦpyqq " apAq.

We define the set GpAq as the image of the map Ψ " Ψ A : GLpd, Cq ˆU Ñ GLpd, Cq given by ΨpX, yq " Ad X pΦpyqq.

Let us check that property 5.8 holds. Let B 1 Ψ and B 2 Ψ denote the partial derivatives with respect to X and y, respectively. As we have seen in Remark 3.4, the rank of B 1 ΨpX, yq is equal to d 2 ´apΦpyqq " d 2 ´apAq for every pX, yq. We claim that (5.7) pB 2 ΨpX, yqq ´1pimage of B 1 ΨpX, yqq " t0u;

To see this, consider the map Γ : Mat dˆd pCq Ñ C d that associates to each matrix the coefficients of its characteristic polynomial. Then B 1 pΓ ˝ΨqpX, yq " 0, while B 2 pΓ ˝Ψqp0, 0q is one-to-one. So (5.7) follows. As a result, the rank of the derivative of Ψ is equal to d 2 ´apAq `cpAq at every point. Therefore, by the Rank Theorem, the image of Ψ is an immersed manifold of codimension apAq ´cpAq.

For arbitrary A P GLpd, Cq, we define GpAq " GpA 0 q, where A 0 is the Jordan form of A. Each set GpAq depends only on the data n and pt i , θ i , k i q i"1,...,n ; therefore there are only countably many different sets GpAq.

Remark 5.9. It is not difficult to show that each GpAq is a actually a submanifold of GLpd, Cq, but we won't need this.

Proof of Lemma 5.7. If k " 1 then M 1 " GLpd, Cq (since d ě 2), so there is nothing to prove. Consider k ě 2. We have already shown in § 2.3 that P k is algebraic. Since M k " tA P GLpd, Cq; @ X P glpd, Cq k , pA, Xq P P k u, it is evident that M k is algebraically closed as well. We are left to estimate its dimension.

Take a nonsingular point A 0 of M k where the local dimension is maximal. Let D be the intersection of M k with a small neighborhood of A 0 ; it is an embedded disk. Each A P D has rpAq ě 2; therefore by (both parts of) Theorem 3.7, we have apAq ´cpAq ě rpAq ě k. So, in terms of the sets from Lemma 5.8,

D Ă ď A s.t. apAq´cpAqěk
GpAq.

The right hand side is a countable union of immersed manifolds of codimension at least k. It follows (e.g. by Baire Theorem) that D (and hence M k ) has codimension at least k.

5.4. Proof of Theorem 1.9. Now we apply Lemmas 5.6 and 5.7 to prove one of our major results:

Proof of Theorem 1.9. The set P m Ă GLpd, Cq ˆrglpd, Cqs m is homogeneous in the second factor. Using Lemma 5.3 together with Remark 5.4, we obtain that the sets (5.8) C j " A P GLpd, Cq; codim P m pAq ď j ( are algebraically closed in GLpd, Cq, and codim P m " min j; Cj ‰∅ `j `codim C j ˘.

By Lemma 5.6, we have C j Ă M m`1´j . Therefore, by Lemma 5.7,

(5.9)

C j ‰ ∅ ñ codim C j # ě 0 if j " m, ě m ´j `1 if j ď m ´1.
So codim P m ě m, as we wanted to show.

The proof above only used that codim C j ě m ´j. On the other hand, using the full power of (5.9) we obtain: Scholium 5.10. The set of poor data in "fat fibers", namely F m :" pA, B 1 , . . . , B m q P P pCq m ; codim P m pAq ď m ´1( , has codimension at least m `1 in GLpd, Cq ˆrglpd, Cqs m .

Proof. The projection of F m on GLpd, Cq is C m´1 . Use Lemma 5.3 (together with Remark 5.4) and (5.9).

The real case.

Proof of Theorem 1.8. The real part of P pCq m is a real algebraic set which, in view of Proposition 5.5, has codimension at least m. Recall from § 2.3 that this set contains the semialgebraic set P pRq m , which therefore has codimension at least m. Since we already knew from Proposition 2.11 that codim P pRq m ď m, the theorem is proved.

5.6. Additional information. Let us improve upon Scholium 5.10 and so prepare the ground for the proof of Theorem 1.2. This part is not necessary for the proof of Theorem 1.1.

Recall from § 2.3 the definition of saturated set.

Lemma 5.11. There exists a saturated algebraically closed set S m Ă GLpd, Cq rMat dˆd pCqs m of codimension at least m `1 such that for all pA, B 1 , . . . , B m q P P m S m , the following properties hold:

1. A is unconstrained;

2. if P P GLpd, Cq is such that P ´1AP is a diagonal matrix then there are indices i 0 , j 0 P t1, . . . , du with i 0 ‰ j 0 such that for each k P t1, . . . , mu, the pi 0 , j 0 q entry of the matrix P ´1B k P vanishes; 3. for each choice of P above, the off-diagonal vanishing entry position pi 0 , j 0 q is unique.

Notice that each data in P m S m , after a change of basis, satisfies precisely the hypotheses of Lemma 2.14.

In order to prove the lemma, we begin by checking algebraicity of the constraints:

Lemma 5.12. The set K Ă GLpd, Cq of constrained matrices is an algebraically closed subset of codimension 1.

Proof. Multiply all constraints, obtaining a polynomial in the variables λ 1 , . . . , λ d . This polynomial is symmetric, and therefore (see e.g. [START_REF] Lang | [END_REF]Thrm. IV.6.1]) can be written as a polynomial function of the elementary symmetric polynomials in the variables λ 1 , . . . , λ d . Now substitute each elementary symmetric polynomial in this expression by the corresponding coefficient of the characteristic polynomial of the matrix A. This gives a polynomial function on the entries of the matrix A that vanishes if and only if A is constrained. It is obvious that the corresponding algebraic set K has codimension 1.

Now we check algebraicity of double vanishing:

Lemma 5.13. There exists a saturated algebraically closed subset D of GLpd, Cq rMat dˆd pCqs m such that if pA, B 1 , . . . , B m q P D and A has simple spectrum then property 2 from Lemma 5.11 is satisfied, but property 3 is not.

Proof. First, consider the subset X Ă rMat dˆd pCqs 1`m ˆpCP d´1 q 2 formed by tuples pA, B 1 , . . . , B m , rvs, rwsq such that rAvs " rvs, rA ˚ws " rws, w ˚v " 0, w ˚Bk v " 0 for each k " 1, . . . , m, where v and w are regarded as column-vectors and the star denotes transposition. The set X is obviously algebraic; thus, by Proposition 5.1, so is its projection Y on rMat dˆd pCqs 1`m .

Let A be a matrix with simple spectrum. Then pA, B 1 , . . . , B m q belongs to Y if and only if property 2 from Lemma 5.11 is satisfied. In particular, the fiber of Y over A is a union of affine subspaces of rMat dˆd pCqs m . Intersections of those affine spaces correspond to points where the uniqueness property 3 is not satisfied. These points of intersection are singular points of Y . Conversely, it is clear that the variety Y is smooth at the points on the fiber over A where property 3 is satisfied.

So let Z be the (algebraically closed) set of singular points of Y . It is straightforward to see that the set Y is saturated. Recalling Remark 2.8 (part 1) and the fact that a group acting on a variety preserves singular points, we see that the set Z is saturated as well.

We define D as the set Z minus the tuples pA, B 1 , . . . , B m q with det A " 0. Then D has all the required properties.

Proof of Lemma 5.11. For simplicity of writing we will omit the m subscripts.

Let π : P Ñ GLpd, Cq be the projection on the first matrix. Define

S " π ´1pK q Y pD X Pq,
where K and D come respectively from Lemmas 5.12 and 5.13. Then S is a saturated algebraically closed subset of P. If A " pA, B 1 , . . . , B m q P P S then: ' A R K, which is property 1;

' since A P P, it follows from Lemma 2.13 that A is conspicuously poor, and so property 2 holds; ' since A R D, property 3 also holds.

To complete the proof of the lemma, we need to show that codim S ě m `1. We will use the following inclusion:

(5.10)

S Ă F Y `π´1 pKq F loooooooomoooooooon F 1 Y `pD X Pq π ´1pK q loooooooooooomoooooooooooon F 2 .
where F comes from Scholium 5.10. Recall that F equals π ´1pC m´1 q, where C j is given by (5.8), and it has codimension at least m `1.

We apply Lemma 5.3 and Remark 5.4 to the set F 1 Ă Y 1 ˆrglpd, Cqs m , where Y 1 " GLpd, Cq C m´1 . Since K has codimension at least 1 in Y 1 , and the fibers of F 1 all have codimension at least m, we conclude that that codim F 1 ě m `1.

Next, we want to apply Lemma 5.3 and Remark 5.4 to the set F 2 Ă Y 2 rglpd, Cqs m , where Y 2 " GLpd, Cq K. For each A P Y 2 , it follows from Lemma 5.13 that the fiber of F 2 over A (which is the same as the fiber of D over A) has codimension 2m in rglpd, Cqs m , corresponding to the 2m different matrix entries that must vanish. We conclude that codim F 2 ě 2m.

We have seen that each of the three sets on the right-hand side of (5.10) has codimension at least m `1. So the same is true for S, as we wanted to prove.

Proof of the main results

6.1. Stratifications. We first recall a few notions about stratifications. We refer the reader to [GWPL, Ma] for details and proofs.

Let Σ be a closed subset of a smooth (i.e., C 8 ) manifold X. A smooth stratification of Σ is a filtration by closed subsets Σ " Σ n Ą Σ n´1 Ą ¨¨¨Ą Σ 0 such that and for each i, the set X i " Σ i Σ i´1 (where Σ ´1 :" ∅) either is a smooth submanifold of M without boundary and of dimension i, or is empty. Each connected component of X i is called a stratum. The codimension of a stratified space is the lowest codimension of strata. This does not depend on the choice of the stratification.

Note that, apart for discrete subsets Σ Ă X, if there is one smooth stratification, then there are infinitely many others. However, the subsets that we will be dealing with will be endowed with certain canonical stratifications: Theorem 6.1 (Existence of canonical stratifications). Any algebraic set Σ Ă C N admits a canonical smooth stratification, whose strata are complex submanifolds of C N . Any closed semialgebraic set Σ Ă R N admits a canonical smooth stratification, whose strata are semialgebraic submanifolds of R N .

In the case of an irreducible algebraic set Σ Ă C n , the canonical stratification can be obtained as follows: The connected components of the set of regular (i.e., non-singular) points form the higher-dimensional strata; then one decomposes the set of singular points of Σ into irreducible components and proceeds by induction.

In any case, those canonical stratifications are uniquely characterized by a certain minimality property. In particular, the canonical stratifications are equivariant under polynomial automorphisms of the ambient space.

Another important property of the canonical stratifications is that they satisfy the so-called Whitney conditions. We will not recall here those conditions, which would be rather technical; we will only write down some of their properties.

A smooth stratification that satisfies the Whitney conditions is called a Whitney stratification. Proposition 6.2 (Basic properties of Whitney stratifications). Let X, Y be smooth manifolds. Let (6.1)

Σ n Ą ¨¨¨Ą Σ 0 be a filtration of a set Σ Ă X. Then:

1. Being a Whitney stratification is a local property of a filtration: So if (6.1)

is a Whitney stratification of Σ then Σ n X U Ą ¨¨¨Ą Σ 0 X U is a Whitney stratification of Σ X U , and conversely if each point in Σ has an open neigh- borhood U Ă X such that Σ n X U Ą ¨¨¨Ą Σ 0 X U is a Whitney stratification of Σ X U then (6.1) is a Whitney stratification of Σ. 2. If (6.1) is a Whitney stratification of Σ then Σ n ˆY Ą ¨¨¨Ą Σ 0 ˆY is is a Whitney stratification of Σ ˆY Ă X ˆY . 3. If (6.1) is a Whitney stratification of Σ and f : X Ñ Y is a smooth diffeo- morphism then f pΣ n q Ą ¨¨¨Ą f pΣ 0 q is a Whitney stratification of f pΣq Ă Y .
Let us now discuss how stratifications behave with respect to transversality. Let f : X Ñ Y be a C 1 map. Let Σ " Σ d Ą ¨¨¨Ą Σ 0 be a stratification of a closed subset Σ of Y . One says that f is transverse to that stratification (in symbols, f J X Σ) if it is transverse to each of its strata. Transversality to a general stratification is not an open condition. However, we obtain openness if the stratification is Whitney:

Proposition 6.3 (Transversality is open). Let X, Y be C 8 manifolds without boundary. Let Σ " Σ d Ą ¨¨¨Ą Σ 0 be a Whitney stratification of a closed subset of Y . Then the set O " tf P C 1 pX, Y q; f J X Σu is open in C 1 pX, Y q (with
respect to the strong topology).

Actually, only the first of the Whitney conditions is necessary here (use the (1)ñ(3) implication of Trotman's theorem [Tr]). 6.2. Jets and jet transversality. We recall the basic notions on jets and state the transversality theorems we will need; see [Hi] for details.

Let X, Y be smooth manifolds without boundary. If 1 ď r ă 8, an r-jet from X to Y is an equivalence class of pairs px, f q, where x P X, f is a C r map from a neighborhood of x to Y , and where px, f q is equivalent to px 1 , f 1 q if x " x 1 and f and f 1 have same derivatives at x up to order r. We denote by J r pX, Y q the space of r-jets from X to Y . It is a smooth manifold.

For all 1 ď s ď 8, we denote by C s pX, Y q the space of C s -maps from X to Y , endowed with the strong topology.

Given 1 ď r ă s ď 8 and a map g P C s pX, Y q, the r-jet extension is the map j r g : X Ñ J r pX, Y q that sends x to the equivalence class j r gpxq of px, gq. Then the mapping j r : C s pX, Y q Ñ C s´r pX, J r pX, Y qq is continuous. Theorem 6.4 (Jet transversality). Let 1 ď r ă s ď 8. Let X and Y be C 8 manifolds without boundary. Let W Ă J r pX, Y q be a C 8 submanifold without boundary. Then the C s -maps g : X Ñ Y for which the r-jet extension j r g is transverse to W form a residual subset of C s pX, Y q.

Let us now show the following: Proposition 6.5. Let X, Y be C 8 -manifolds without boundary. Let Σ Ă J 1 pX, Y q be a Whitney stratified closed subset.

Then tf P C 2 pX, Y q; j 1 f J X Σu is C 2 -open and C 8 -dense in C 2 pX, Y q.
Here, as in the introduction, we say that a subset of C 2 pX, Y q is C 8 -dense if its intersection with C r pX, Y q is C r -dense, for every r ě 2.

Proof of Proposition 6.5. By Proposition 6.3, the set tF :

X Ñ j 1 pX, Y q; F J X Σu is open in C 1 `X, J 1 pX, Y q ˘. Hence the set O :" tf : X Ñ Y ; j 1 f J X Σu is open in C 2 pX, Y q.
Fix r ě 2. Given a Whitney stratification Σ n Ą ¨¨¨Ą Σ 0 of Σ, let Z i " Σ i Σ i´1 be the corresponding decomposition into smooth submanifolds. By the jet transversality theorem (Theorem 6.4), each set

R i " tf P C r pX, Y q; j 1 f J X Z i u is residual. Thus O X C r pX, Y q " Ş i R i is C r -dense.
This concludes the proof. 6.3. Proof of the main result. We now use Theorem 1.8 and the tools explained above to prove our main result. Before going into the proof itself, let us deal with a technical detail.

By Theorem 1.8, P pRq m is a closed semialgebraic subset of GLpd, Rq ˆglpd, Rq m . Since Theorem 6.1 concerns semialgebraic subsets of affine space, we proceed as follows. First, enlarge P pRq m by including all pA, B 1 , . . . , B m q with det A " 0, thus obtaining a subset Γ of rMat dˆd pRqs 1`m which is also closed and semialgebraic. By Theorem 6.1, the set Γ admits a canonical Whitney stratification Γ " Γn Ą ¨¨¨Ą Γ0 . Now we remove all pA, B 1 , . . . , B m q with det A " 0 from each Γi , thus (by locality property 1 in Proposition 6.2) obtaining a Whitney stratification of codimension m: (6.2) P pRq m " Γ n Ą ¨¨¨Ą Γ 0 . (We may have Γ n " Γ n´1 .) Since the stratification of Γ is canonical, the stratification (6.2) is invariant under polynomial automorphisms of the set GLpd, Rq ĝlpd, Rq m that preserve P pRq m .

Proof of Theorem 1.1. Let U be a smooth manifold without boundary and of dimension m. Given local coordinates on an open set U Ă U , the set of 1-jets from U to GLpd, Rq may be identified with the set U ˆGLpd, Rq ˆglpd, Rq m . Indeed, a jet J represented by a pair pu, Aq can be identified with the point pu, Apuq, B 1 , . . . , B m q P U ˆGLpd, Rq ˆglpd, Rq m , where B i P Mat dˆd pRq is the normalized derivative of A at u, along the i th coordinate. Let us say that the 1-jet J is rich if the data A " pApuq, B 1 , . . . , B m q is rich, or equivalently, if for sufficiently large N , the input pu, . . . , uq P U N is universally regular for the system (1.4). If the jet is not rich then it is called poor.

Define a filtration (6.3) Σ n Ą ¨¨¨Ą Σ 0 of the set of poor jets from U to GLpd, Rq as follows: a jet J represented as above in local coordinates by pu, Apuq, B 1 , . . . , B m q belongs to Σ i if and only if pApuq, B 1 , . . . , B m q belongs to the set Γ i in (6.2). We need to check that this definition does not depend on the choice of the local coordinates. Indeed, this follows from the fact that P pRq m is a saturated set (see § 2.3) using the invariance property of the stratification (6.2) explained above.

We claim that the filtration (6.3) is a Whitney stratification of codimension m. Indeed, the intersection of the filtration with the open subset J 1 pU, GLpd, Rqq of J 1 pU , GLpd, Rqq is identified (through a smooth diffeomorphism) with the filtration U ˆΓn Ą ¨¨¨Ą U ˆΓ0 .

So the claim follows from Proposition 6.2.

Applying Proposition 6.5, we obtain a C 2 -open C 8 -dense set O Ă C 2 pU , GLpd, Cqq formed by maps A that are transverse to the stratification (6.3) of the set of poor jets. Since the codimension of the stratification equals the dimension of the manifold U , if A P O then the points u for which j 1 Apuq is poor form a 0-dimensional set. This proves Theorem 1.1.

Remark 6.6. In the proof above, instead of working with the semialgebraic set P be its real part. This is an algebraically closed saturated subset of GLpd, Rq rglpd, Rqs m which, by Proposition 5.5, has codimension at least m `1. Consider the set Γ of 1-jets J P J 1 pU , GLpd, Cqq that have a local expression pu, Apuq, B 1 , . . . , B m q with pApuq, B 1 , . . . , B m q P S pRq m . This does not depend on the choice of the local coordinates, because S pRq m is saturated. By the same arguments as in the proof of Theorem 1.1, the set Γ admits a Whitney stratification. Its codimension is at least m `1. Applying Proposition 6.5, we obtain a C 2 -open C 8 -dense set Õ Ă C 2 pU , GLpd, Cqq formed by maps A that are transverse to the stratification.

Let O be the set provided by Theorem 1.1. and consider a map A P O X Õ. Then whenever a jet j 1 Apuq is poor, it does not belong to Γ. Recalling Lemma 5.11, we see that the local expression of j 1 Apuq satisfies (after a change of basis) the hypotheses of Lemma 2.14. Therefore parts 1 and 2 of the theorem follow respectively from conclusions 1 and 2 of the lemma.

Remark 6.7. The proof of Theorem 1.2 also gives more information about the 1-jets that appear generically for singular constant inputs pu, . . . , uq: the associated matrix data is conspicuously poor (see § 2.4), and the matrix Apuq is unconstrained (see § 2.5). Remark 6.8. Properties 1 and 2 in Theorem 1.2 are in fact dual to each other. If A is the data representing the 1-jet of A at u, and Λ " ΛpAq, then property 1 means that there is an unique direction rvs P RP d´1 such that Λ ¨v ‰ C d . Then property 2 means that there is an unique direction rws P RP d´1 such that Λ ˚¨w ‰ C d , where Λ is the set of the transposes of the matrices in Λ. This fact can be proved easily using the dual characterization of Lemma 3.12.

Recall from § 2.5 that an elementary constraint between variables λ 1 , . . . , λ d is a relation that can be reduced to one of the four canonical constraints after a change of indices. Each constraint has a unique type.

Let us say that a matrix A P GLpd, Rq is piq-constrained, for 1 ď i ď 4 if: ' its eigenvalues, counted with multiplicity, satisfy exactly one elementary constraint, which is a type i constraint, ' if there is a type 4 constraint between the eigenvalues, then the matrix A is not diagonalizable. Hence if a matrix A is not piq-constrained for any 0 ď i ď 4, then ' either A is unconstrained, i.e., its eigenvalues (with multiplicity) satisfy no constraint; ' or the eigenvalues of A satisfy at least two constraints; ' or A has a (multiple) eigenvalue corresponding to at least two Jordan blocks. If either of the last two cases hold, we say that A is multiconstrained.

Proposition A.1.

1. The complement of the set of unconstrained matrices has codimension 1 in GLpd, Rq. 2. The set of multiconstrained matrices has codimension 2 in GLpd, Rq.

Informal proof. Matrices that are not unconstrained have at least one constraint on their eigenvalues, so the corresponding set has codimension 1.

Matrices that are very constrained either have at least two constraints on their eigenvalues, or have an eigenvalue of multiplicity 2 and are diagonalizable. In both cases, the corresponding set has codimension 2.

Let us define adapted bases for matrices A that are not multiconstrained:

' If A is unconstrained then an adapted basis is a basis of eigenvectors. ' If A is piq-constrained, for i " 1, 2, or 3 then an adapted basis is an (ordered) basis of eigenvectors such that the corresponding eigenvectors λ 1 , . . . λ d satisfy the canonical type i constraint. ' If A is p4q-constrained then an adapted basis for A is a basis in which A is written in the following modified Jordan form 14 :

¨λ1 λ 1 0 λ 1 λ 3 . . . λ d ‹ ‹ ‹ ‹ ‹ '
.

Obviously, such adapted bases always exist. If a matrix A is piq-constrained then we say that a dˆd matrix B is a good match for A, if there is an adapted basis for A in which it writes as B " pb ij q, where all nondiagonal entries b ij are nonzero and if b 11 ‰ b 22 , in the particular case where A is 3-constrained.

The usefulness of this definition is explained by the following Propositions A.2 and A.3 15 : Proposition A.2. If A is not multiconstrained and B is a good match for A then the pair pA, Bq is rich.

14 The reason for using a modified Jordan form is that it makes the expression of Ad A simpler, as we will see later.

15 Actually, the definition of a good match matrix is stronger than necessary for Proposition A.2 to be true. But in order to avoid complications, we chose a condition that works for all types of constraints.

This is not a generalized Toeplitz space. However, consider the linear automorphism S that swaps the first two elements of the canonical basis of C n , and fixes the others. Then S ¨Γ " pz ij q P glpd, Cq; z 33 " ¨¨¨" z dd , b

‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ ‹ '
where the block C 22 is a 2 ˆ2 matrix, the blocks C 2j are 2 ˆ1, the blocks C i2 are 1 ˆ2 and the others are 1 ˆ1. Then, the operator Ad A leaves invariant the space Γ ij of matrices whose nonzero coefficients lie inside the block C ij . Moreover, it is easily computed that the operator Ad A has the following properties:

' restricting to the space Γ 22 , which we canonically identify to glp2, Cq, one has:

Ad A ˆ0 0 1 0 ˙" ˆ1 ´1 1 ´1 ˙; Ad A ˆ0 0 0 1 ˙" ˆ0 1 0 1 Ȧd A ˆ1 0 0 0 ˙" ˆ1 ´1 0 0 ˙; Ad A ˆ0 1 0 0 ˙" ˆ0 1 0 0
Ȯne then easily computes that, in the ordered basis formed by vectors

J 1 " ˆ0 ´2 0 0 ˙; J 2 " ˆ1 ´1 0 ´1 ˙; J 3 " ˆ0 0 1 0 ˙; J 4 " ˆ1 0 0 1 ˙, the matrix of Ad A |Γ 11 is ¨1 1 1 1 1 1 ‹ ‹ ' .
' For any j ě 3, identifying Γ 2j to the space of 2 ˆ1 matrices, the matrix of

Ad A |Γ 2j is ˆλ2 λ ´1 j 1 0 λ 2 λ ´1 j ˙in the basis formed by matrices λ 2 λ ´1 j E 1,j " ˆλ2 λ ´1 j 0 ˙and E 2,j " ˆ0 1
˙, where we use the notation E i,j from (2.4).

' For any i ě 3, identifying Γ i,2 to the space of 1 ˆ2 matrices, the matrix of

Ad A |Γ i2 is ˆλi λ ´1 2 1 0 λ i λ ´1 2
˙in the basis formed by matrices ´λi λ ´1 2 E i,1 " `0 ´λi λ ´1 2 ˘and E i2 " `1 0 ˘. ' for 3 ď i, j ď d, pE ij q is a basis of Γ ij ; it is an eigenvector with eigenvalue λ i λ ´1 j .

' The spaces Γ ij , for 2 ď i, j ď d have respective spectra tλ i λ ´1 j u, which for i ‰ j are pairwise disjoint and different from t1u. The concatenation of the bases described above gives a Jordan basis for Ad A . Now take a matrix B that is a good match for A, and consider its expression as a linear combination of the elements of that Jordan basis.

Claim A.4. All coefficients in this linear combination are nonzero, except possibly the coefficients of the vectors J 1 , J 2 , J 4 and the vectors E ii , for all 3 ď i ď d.

The verification is direct. Consider now the splitting Mat dˆd pCq " V ' ∆, where ∆ is the subspace CJ 4 ' E 33 ' . . . ' E dd of the space of diagonal matrices, and V is the space spanned by all other elements of the above Jordan basis. Note that

V " pCJ 1 `CJ 2 `CJ 3 q ' ¨à 2ďi,jďd i‰j Γ ij
' is a decomposition of V into Ad A -invariant subspaces with pairwise disjoint spectra.

Let π be the projection onto V along ∆. It follows from the claim and Lemmas 3.1 and 3.2 that πpBq is a cyclic vector for Ad A |V . So, using the Ad A -invariance of the spaces V and ∆, we have πpΓq " π `sorb Ad A pBq ˘" sorb Ad A pπpBqq " V.

Note that V contains the matrices E ij , for all i ‰ j, hence tIdu _ V is a generalized Toeplitz space. As π projects along a subspace of diagonal matrices, tIdu _ Γ is again a generalized Toeplitz space and in particular is a transitive space.

We have considered the four types, and Proposition A.2 is proved.

Appendix B. Complementary facts about singular constant inputs of generic type

In this appendix we give grounds for Remark 1.3. We also discuss other controltheoretic properties of generic semilinear systems, related to universal regularity. B.1. Local persistence of singular inputs. Let A P C r pU , GLpd, Rqq, r ě 1. We will work upon Lemma 2.9 in order to obtain a more practical way to detect that the 1-jet of A at a point corresponds to conspicuously poor data. (Recall from Remark 6.7 that this is the only type of poor data that appears generically.) For example, in the m " 1, d " 2 case, we will see that conspicuous poorness means that the angular velocity of one of the eigendirections vanishes (see Remark B.1 below).

Suppose that u 0 P U is such that the matrix Apu 0 q is diagonalizable over R and with simple eigenvalues only. By Proposition 2.10, there is a neighborhood U 0 of u 0 and C r -maps λ 1 , . . . , λ d : U 0 Ñ C such that for all u P U 0 , the complex numbers λ i puq are all distinct, and form the spectrum of Apuq; moreover there exist a C r map P : U 0 Ñ GLpd, Rq such that for all u P U 0 , (B.1)

Apuq " P puq ∆puq P ´1puq , where ∆puq " Diagpλ 1 puq, . . . , λ d puqq.

For simplicity, let us consider first case where U is an interval in R (in particular m " 1). Then the normalized derivative of A at a point u can be identified with N puq :" A 1 puq A ´1puq. Consider the expression of N puq in the basis that diagonalizes Apuq, that is, Bpuq :" P ´1puq N puq P puq. Since d du P ´1puq " ´P ´1puq P 1 puq P ´1puq, we compute that Bpuq " ∆ 1 puq ∆ ´1puq `Qpuq ´∆puq Qpuq ∆ ´1puq , where Qpuq :" P ´1puq P 1 puq .

So the off-diagonal entries of the matrices Bpuq and Qpuq are related by b ij puq " `1 ´λi puq{λ j puq ˘qij puq pi ‰ jq.

In view of Lemma 2.9, we conclude the following: if for some u ˚P U 0 (B.2) there is an off-diagonal entry position pi, jq such that q ij pu ˚q " 0 then the 1-jet j 1 Apu ˚q is poor.

Remark B.1. Let us give a geometrical interpretation of condition (B.2). The columns of P form a basis pv1, . . . , v d q of eigenvectors of A, and the rows of P ´1 form a basis pf1, . . . , f d q of eigenfunctionals of A (in the sense that fi ˝A " λifi); these two bases are related by fipvjq " δij. So qij " fi ´dv j du ¯is the component of the velocity of vj in the direction of vi. For example, for d " 2, condition (B.2) means that one of the eigendirections of A has zero angular speed at instant u " u˚.

It is trivial to adapt the previous calculations to the higher dimensional case and then conclude the following: Proposition B.2. Let pu 1 , . . . , u m q be coordinates in a chart domain U 0 Ă U where expression (B.1) holds. Consider matrices

(B.3) Q k puq :" P ´1puq BP Bu k puq .
If for some u ˚P U 0 there is an off-diagonal entry position pi, jq such that (B.4) for each k " 1, . . . , m, the pi, jq-entry of the matrix Q k pu ˚q vanishes then the 1-jet j 1 Apu ˚q is poor, that is, the constant input pu ˚, . . . , u ˚q (of any length) is singular.

In the situation of Proposition B.2, assume additionally that the map (B.5) Φ :

# U 0 Ñ Im Φ Ă K m u Þ Ñ rthe pi, jq-entry of Q k puqs 1ďkďm is a diffeomorphism.
In that case, the existence of a poor jet is persistent in the following way: If à is sufficiently C 2 -close to A then by Proposition 2.10 we can express Ãpuq " P puq ∆puq P ´1puq for u close to u ˚, where P and ∆ are C 2 -close to P and ∆ respectively, and ∆ is diagonal. The corresponding matrices Qk "

P ´1 B P Bu k are C 1 -close to Q k and the map Φ : u Þ Ñ " the pi, jq-entry of Qk puq ı 1ďkďm
is C 1 -close to Φ. By (B.5) the fact that Φpu ˚q " p0, ..., 0q, there is ũ close to u such that Φpuq " p0, ..., 0q. In particular the 1-jet j 1 Ãpũq is poor. Now, concerning existence: It is evident that a domain U 0 and 2-jets j 2 P pu ˚q satisfying conditions (B.4) and (B.5) actually exist; moreover we can always find a map P : U Ñ GLpd, Rq with a prescribed 2-jet at a point u ˚. In view of the discussion above, we conclude the following: Proposition B.3 (Persistence of singular inputs). For any d ě 1 and any ddimensional smooth manifold U , there exists a C 2 -open nonempty subset of maps A P C 2 pU , GLpd, Rqq such that the following holds: there exists u P U such that the constant inputs pu, . . . , uq of any length are all singular for the system (1.4).

That is, one cannot improve Theorem 1.1 replacing "discrete set" by "empty set".

We can also see why the statement of Theorem 1.1 with "C 2 -open" replaced by "C 1 -open" is not true: Given any map A such that (B.4) holds at some point, we can C 1 -perturb A (by C 0 -perturbing P ) in a way such that (B.4) now holds for a non-discrete set of points.16 B.2. Other control-theoretic properties. We now introduce a few controltheoretic notions related to accessibility and regularity, and discuss the validity of statements similar to Theorem 1.1 for these notions.

Consider a general control system (1.1). Fix a time length N , and let φ N denote the response map as in (1.2). We say that a trajectory determined by px 0 ; u 0 , . . . , u N ´1q is:

' locally accessible 17 if for every neighborhood V of pu 0 , . . . , u N ´1q in U N , the set φ N ptx 0 u ˆV q has nonempty interior. ' strongly locally accessible if for every neighborhood V of pu 0 , . . . , u N ´1q in U N , the set φ N ptx 0 uˆV q contains in its interior the final state φ N px 0 ; u 0 , . . . , u N ´1q.

The following implications are immediate: regular ñ strongly locally accessible ñ locally accessible.

We say that an input pu 0 , . . . , u N ´1q is universally locally accessible (resp. universally strongly locally accessible) if the trajectory determined by px 0 ; u 0 , . . . , u N ´1q is locally accessible (resp. strongly locally accessible). Now we come back to the context of projective semilinear control systems (1.4). A (relatively weak) corollary of Theorem 1.1 is that for generic maps A, universal local accessibility holds at all constant inputs: Proposition B.4. Let N P N and O Ă C 2 pU , GLpd, Rqq be as in Theorem 1.1. For any A P O, every constant input sequence of length N is universally locally accessible.

Proof. If A P O then for every constant input sequence of length N we can find a regular input sequence nearby.

As we have shown in Proposition B.3, it is not possible to improve Proposition B.4 by replacing "local accessibility" by "regularity". Neither it is possible to replace "local accessibility" by "strong local accessibility", as the following simple example (in m " 1, d " 2) shows:

Example B.5. For u P R, define

P puq " ˆ1 u u 2 1 ˙, ∆puq " Diagp2, 1q.
Let U be an small open interval containing 0, and define A : U Ñ GLp2, Rq by (B.1). Let ξ0 P RP 1 correspond to the direction of the vector p1, 0q. Then for any subinterval V Q 0, and any N ą 0, the set φN ptξ0u ˆV N q " Apun´1q ¨¨¨Apu0q ¨ξ0 ui P V ( is an "interval" of RP 1 containing ξ0 " φN pξ0; 0, . . . , 0q in its boundary. Therefore the input p0, . . . , 0q is not universally strongly locally accessible. A similar situation occurs for any C 2 -perturbation of A.

:" R k R k´1 .
We define a map π k : Rk Ñ G k pC n q by A Þ Ñ col A.

Lemma D.3. If X is an algebraically closed column-invariant subset of Rk then Y " π k pXq is algebraically closed subset of G k pC n q, and the codimension of Y inside G k pC n q is the same as the codimension of X inside Rk .

Proof. First, let us see that π k : Rk Ñ G k pC n q is a regular map. We identify G k pC n q with the image of the Plücker embedding. In a Zariski neighborhood of each matrix A P Rk , the map π k can be defined as A Þ Ñ ra j1 ^¨¨¨^a j k s for some j 1 ă ¨¨¨ă j k , where a j is the j th column of A. This shows regularity.

Next, let us see that Y " π k pXq is closed with respect to the classical (not Zariski) topology. Consider the subset K of X formed by the matrices A P Rk whose first k columns form an orthonormal set, and whose m´k remaining columns are zero. Then K is compact (in the classical sense), and thus so is π k pKq. But column-invariance of X implies that π k pKq " Y , so Y is closed (in the classical sense).

It follows (see e.g. [START_REF] Harris | Algebraic geometry: a first course[END_REF]p.39]) from regularity of π k is regular that the set Y is constructible, i.e., it can be written as

Y " p ď i"1 Z i W i ,
where Z i Ń W i are algebraically closed subsets of G k pC n q. We can assume that each Z i is irreducible. It follows from [START_REF] Mumford | Algebraic geometry. I. Complex projective varieties[END_REF]Thrm. 2.33] that Z i W i " Z i , where the bar denotes closure in the classical sense. In particular, Y " Y " Ť p i"1 Z i , showing that Y is algebraically closed.

We are left to show the equality between codimensions. Since the codimension of an algebraically closed set equals the minimum of the codimensions of its components, we can assume that X is irreducible.

By column-invariance of X, for each y P Y , the whole fiber π ´1pyq is contained in X. All those fibers have the same dimension µ " km. By [START_REF] Harris | Algebraic geometry: a first course[END_REF]Thrm. 11.12], dim X " dim Y `km. By (D.2) and (D.3), we have dim Rk ´dim G k " km, so the claim about codimensions follows.

Proof of Theorem D.1. Let X Ă Mat nˆm pCq be a nonempty algebraically closed, column-invariant set. Suppose E is a vector subspace of C n that does not belong to vXw. Let e " dim E. We can assume e ą 0 (otherwise the result is vacuously true), and e ă n (because the case e " n was already considered in § D.2).

Notice that X Ă R n´1 . Let X k :" X X Rk and Y k :" π k pX k q, for 0 ď k ď minpm, n ´1q.

For every k with e ď k ă n, the set Y k is disjoint from the set S k pEq defined by (D.4). In view of Lemma D.3 and Theorem D.2, we have codim Rk X k " codim Y k ě k `1 ´e .

So the codimension of X k as a subset of Mat nˆm pCq is codim X k " codim Rk `codim Rk X k ě pm ´kqpn ´kq `k `1 ´e ": f pkq .

The function f pkq is decreasing on the interval 0 ď k ď minpm, n ´1q. Therefore: codim X " min The proof of Theorem D.2 will be given in § D.6, after we explain the necessary tools in § § D.4, D.5. D.4. Schubert calculus. Here we will outline some facts about the intersection of Schubert varieties. The readable expositions [Bl, Va] contain more information. A (complete) flag in C n is a sequence of subspaces F 0 Ă F 1 Ă ¨¨¨Ă F n with dim F j " j. We denote F ' " tF i u.

Given V P G k pC n q, its rank table (with respect to the flag F ' ) is the data dimpV X F j q, j " 0, . . . , n. The jumping numbers are the indexes j P t1, . . . , nu such that dimpV X F j q ´dimpV X F j´1 q is positive (and thus equal to 1). Of course, if one knows the jumping numbers, one know the rank table and vice-versa. Let us define a third way to encode this information: Consider a rectangle of height m and width n ´m, divided in 1 ˆ1 squares. We form a path of square edges: Start in the northeast corner of the rectangle. In the j th step (1 ď j ď n), if j is a jumping number then we move one unit in the south direction, otherwise we move one unit in the west direction. Since there are exactly k jumping numbers, the path ends at the southwest corner of the rectangle. The Young diagram of V with respect to the flag F ' is the set of squares in the rectangle that lie northwest of the path. We denote a Young diagram by λ " pλ 1 , λ 2 , . . . , λ k q, where λ i is the number of squares in the i th row (from north to south). Its area λ 1 `¨¨¨`λ k is denoted by |λ|.

Example D.4. Here is a possible rank table with k " 5, n " 12; the jumping numbers are underlined: j " 0 1 2 3 4 5 6 7 8 9 10 11 12 dimpW X Fjq " 0 0 0 1 1 1 2 2 3 4 4 5 5 The associated path in the rectangle is:

✛ ✛ ❄ ✛ ✛ ❄ ✛ ❄ ❄ ✛ ❄ ✛
and so the Young diagram is λ " " p5, 3, 2, 2, 1q.

In general, we have: ' λ " pλ 1 , . . . , λ k q is a possible Young diagram if and only if n ´k ě λ 1 ě ¨¨¨ě λ k ě 0. ' If j 1 ă ¨¨¨ă j k are the jumping numbers then λ i " n ´k ´ji `i. The set of V P G k pC n q that have a given Young diagram λ is called a Schubert cell, denoted by Ωpλq or Ωpλ, F ' q. Each Schubert cell is a topological disk of real codimension 2|λ|. The Schubert cells (for a fixed flag) give a CW decomposition of the space G k pC n q. The closure of Ωpλq (in either classical or Zariski topologies) is the set of V P G k pC n q such that dimpV X F ji q ě i for each i " 1, . . . , n (where j 1 ă ¨¨¨ă j k are the jumping numbers associated to λ). These sets are closed irreducible varieties, called Schubert varieties. (See e.g. [START_REF] Fulton | With applications to representation theory and geometry[END_REF]§9.4].) Let A ˚pk, nq denote the set of formal linear combinations with integer coefficients of Young diagrams in the k ˆpn ´kq rectangle. This is by definition an abelian group.

Proposition D.6. There is a second binary operation called the cup product and denoted by the symbol that makes A ˚pk, nq a commutative ring, and is characterized by the following properties:

If λ and µ are Young diagrams with respective areas r and s then their cup product is of the form: λ µ " ν 1 `¨¨¨`ν N . where ν 1 , . . . , ν N are Young diagrams with area r `s (possibly with repetitions, possibly N " 0). Moreover, there are flags F ' , G ' , H piq ' such that the manifolds Ωpλ, F ' q and Ωpµ, G ' q are transverse and their intersection is Ť Ωpν i , H piq ' q.

Example D.7. Working in A ˚p2, 4q, let us compute the products of the Young diagrams λ " and µ " . Fix a flag F'. Then Ωpλ, F'q is the set of W P G2pC 4 q that contain F1, and Ωpµ, F'q is the set of W P G2pC 4 q that are contained in F3. Take another flag G' which is in general position with respect to F', that is Fi X G4´i " t0u. Then: ' The set Ωpλ, F'q X Ωpλ, G'q contains a single element, namely F1 ' G1, and thus equals Ωpp2, 2q, H'q " tH2u for an appropriate flag H'. This shows that λ λ " . ' The space F3 X G3 is 2-dimensional and thus is the single element of Ωpµ, F'q X Ωpµ, G'q. So µ µ " . ' The set Ωpλ, F'q X Ωpµ, G'q is empty, thus λ µ " 0.

However, if we work in A ˚p4, 8q then it can be shown that: " ``, " ``, " `.

If we drop the terms that do not fit in a 2ˆ2 rectangle, we reobtain the results for G2pC 4 q.

The general computation of the product λ µ is not simple and can be done in various ways -see e.g. [Va, Fu]. 18 For our purposes, however, it will be sufficient to know when the product is zero or not. The answer is provided by the following simple lemma 19 : Lemma D.8 ( [START_REF] Fulton | With applications to representation theory and geometry[END_REF]. Let λ and µ be Young diagrams in the k ˆpn ´kq rectangle. The following two conditions are equivalent:

1. λ µ ‰ 0. 2. If one draws inside the k ˆpn ´kq rectangle the Young diagrams of λ and µ, being the later rotated by 180 ˝and put in the southeast corner, then the two figures do not overlap (see Fig. 5). Equivalently, λ i `µk`1´i ď n ´k for every i " 1, . . . , n. 18 Here is an online calculator: young.sp2mi.univ-poitiers.fr/ cgi-bin/ form-prep/ marc/ LiE form.act?action=LRR 19 In [Va] condition 2 of the lemma is expressed as "the white checkers are happy". The picture shows that the non-overlap condition (2) from Lemma D.8 is satisfied, and in particular λ µ ‰ 0. (This example is reproduced from [START_REF] Fulton | With applications to representation theory and geometry[END_REF]p. 150].) D.5. Intersection of subvarieties of the grassmannian. Next we explain how the Schubert calculus sketched above can be used to obtain information about intersection of general subvarieties of the Grassmannian, by means of cohomology and Poincaré duality. Our primary source is [Fu, Appendix B]; also, [Hu] is a very readable account about the geometric interpretation of the cup product in cohomology.

Any topological space X has singular homology groups H i X and cohomology groups H i X (here taken always with integer coefficients). With the cup product H i X ˆHj X Ñ H i`j X, the cohomology H ˚X " À H i X has a ring structure. If X is a real compact oriented manifold of dimension d then the homology group H d X is canonically isomorphic to Z, with a generator rXs called the fundamental class of X. In addition, there is Poincaré duality isomorphism H i X Ñ H d´i X, which is given by α Þ Ñ α rXs (taking the cap product with the fundamental class). Let us denote by ω Þ Ñ ω ˚the inverse isomorphism.

Next suppose Y and Z are compact oriented submanifolds of X, of codimensions i and j respectively. Also suppose that Y and Z have transverse intersection Y XZ, which therefore is either empty or a compact submanifold of codimension i`j, which is oriented in a canonical way. The images of the fundamental classes of Y , Z, and Y X Z under the inclusions into X define homology classes that we denote (with a slight abuse of notation) by rY s P H d´i X, rZs P H d´j X, rY X Zs P H d´i´j X.

Then their Poincaré duals rY s ˚P H i X, rZs ˚P H j X, and rY X Zs ˚P H i`j X are related by: rY s ˚ rZs ˚" rY X Zs ˚.

That is, cup product is Poincaré dual to intersection. Now consider the case where X is a projective nonsingular (i.e., smooth) complex variety, and Y and Z are irreducible subvarieties of X. Obviously, the fundamental class rXs makes sense, because X is a compact manifold with a canonical orientation induced from the complex structure. A deeper fact (see [Fu, Appendix B]) is that fundamental classes rY s and rZs can also be canonically associated to the (possibly singular) subvarieties Y and Z, and the Poincaré duality between cup product and intersection works in this situation. More precisely, suppose that Y and Z are transverse in the algebraic sense: Y X Z is a union of subvarieties W 1 , . . . , W ℓ whose codimensions are the sum of the codimensions of Y and Z, and for each i " 1, . . . , ℓ, the tangent spaces T w Y and T w Z are transverse for all w in a Zariskiopen subset of W i . Then each W i has its canonical fundamental class, and the following duality formula holds: rY s ˚ rZs ˚" rW 1 s ˚`¨¨¨`rW ℓ s ˚.

In our application of this machinery, X will be the grassmannian G k pC n q. In this case:

' The fundamental classes of the Schubert varieties r Ωpλ, F ' qs do not depend on the flag F ' . ' Let σ λ denote the Poincaré dual of r Ωpλ, F ' qs. Then H 2r G k pC n q is a free abelian group and the elements σ λ with |λ| " r form a set of generators.

(The cohomology groups of odd codimension are zero.) ' The cup product on cohomology agrees with the "cup" product of Young diagrams explained in the previous section.

D.6. End of the proof. We are now able to give to prove Theorem D.2.20

Proof of Theorem D.2. Let 1 ď e ď k ă n. Let E Ă C n be a subspace of dimension e, and consider the set S k pEq defined by (D.4). Recall from Example D.5 that this is the Schubert variety for the Young diagram λ given by (D.5). Now consider a (nonempty) subvariety Y Ă G k pC n q that is disjoint from S k pEq. We want to give a lower bound for the codimension c of Y . We can of course assume that Y is irreducible.

Let rY s ˚be the dual of fundamental class of Y . This is a nonzero element of H 2c G k pC n q. It can be expressed as ř n i σ µi , where µ i are Young diagrams with area |µ i | " c, and n i are nonzero integers. In fact we have n i ą 0, because of the canonical orientations induced by complex structure.

Since the intersection between S k pEq and Y is empty (and in particular transverse), Poincaré duality gives rS k pEqs ˚ rY s ˚" 0. Therefore we have σ λ σ µi " 0 for each i.

By Lemma D.8, if we draw the Young diagram of µ i rotated by 180 ˝and put in the southeast corner of the k ˆpn ´kq rectangle, then it overlaps the Young diagram λ pictured in (D.5). This is only possible if c ě k ´e `1; indeed the Young diagram µ with least area such that λ µ ‰ 0 is µ " `1, . . . , 1 loomoon k´e`1 times , 0, . . . , 0 loomoon e´1 times

˘,

for which the overlapping picture becomes:

This concludes the proof of Theorem D.2.

As explained in § D.3.2, Theorem D.1 follows.

Figure 1 .

 1 Figure 1. The geography corresponding to Example 4.1.Thick (resp., thin, dashed) lines represent island (resp., city, district) borders. Population and latitude of each district inside a selected city are indicated. The population of each city is recorded in its upper left corner, along with a symbolic representation of its banner. There are three banner classes (' " r1s, ó " r2s and ò " r1{2s), each of them with 3 different banners. Southern cities are marked with S.

2 .

 2 Lemma 4.2. Let C be a city in an island I. Consider the divisions of the world W and the island I as in Fig.2. The divisions of W and I in Lemma 4.2.

  Lemma 4.10. For any city C, rig `pAd A |C ˝q ď ÿ ℓ latitude max D is a district of C with latitude ℓ rig `pAd A |D ˝q .

  worked equally well with the real part of P pCq m , since it is an algebraic set containing P pRq m and has the same codimension. 6.4. Proof of the addendum. Proof of Theorem 1.2. Consider the set S pCq m given by Lemma 5.11, and let S pRq m

  , n ´1qq " m `1 ´e, as claimed. This proves Theorem D.1 modulo Theorem D.2.

  Example D.5. If E Ă C n is a subspace with dim E " e ď k then the set S k pEq defined by (D.4) is a Schubert variety Ωpλ, F'q, where F' is any flag with Fe " E and (D.5)λ " `n ´k, . . . , n ´k looooooooomooooooooon

Figure 5 .

 5 Figure 5. Consider k" 5, n " 12, λ " p5, 3, 2, 2, 1q, and µ " p5, 5, 4, 2, 0q.

  Example 2.1. Recall that a Toeplitz matrix, resp. a Hankel matrix, is a matrix of the

	form
	¨t0	t1 ¨¨¨t d´1
	t´1	. . .
	. . .	t1
	t ´d`1 ¨¨¨t´1 t0

  The sets of poor data. For emphasis, we repeat the definition already gave at the introduction: The data A " pA, B 1 , . . . , B m q P GLpd, Kq ˆrglpd, Kqs m is rich

	if the space ΛpAq defined by (2.2) is transitive, and poor otherwise. The concept in
	fact depends on the field under consideration. The set of such poor data is denoted
	by P	pKq m,d .
	It follows immediately from Proposition 2.4 that P	pRq m,d is a closed and semialge-
	braic subset of GLpd, Rq ˆrglpd, Rqs m and P Cqs m . This proves part of Theorems 1.8 and 1.9. pCq m,d is an algebraic subset of GLpd, Cq	rglpd,
	Also, by Proposition 2.5 the real poor data are contained in the real part of the
	complex poor data, i.e.,
	(2.3)	P	pRq m,d X	"	GLpd, Kq ˆrglpd, Kqs m ‰	Ă P	pCq m,d .

  Example 4.19. If A is the matrix of Example 4.1 then Lemma 4.18 gives the estimate rig `AdA ď 28. A more careful analysis (going through the proofs of the lemmas) would give rig `AdA ď 7 (see Example 4.11).

  ´1 12 z 22 " b ´1 21 z 11 ( is a generalized Toeplitz space! By Remark 2.3, the space S ¨Γ is transitive, and so are Γ and ΛpA, Bq. p4q-constrained case: This case is more involved because the operator Ad A is not diagonalizable. We will explain its Jordan form. Let us explain visually how Ad A acts: given any matrix, decompose it into blocks C ij as in the following picture

	¨C22	C 23 C 24	. . .	C 2d
	C 32	C 33		. . .
	C 42		C 44	. . .
	. . .	. . .	. . .	. . .
	C d2			. . .	C dd

  D.3.2. Proof of Theorem D.1 assuming Theorem D.2. Assuming Theorem D.2 for the while, let us see how it yields Theorem D.1.

	Recalling notation (D.1), define the quasiprojective variety
	Rk

The corank of a linear map L : V Ñ W is the number dim W ´dim LpV q.

In other words, if you're old enough and still poor then you'll never get rich.

A slightly similar result is[START_REF] Sontag | Remarks on universal nonsingular controls for discrete-time systems[END_REF] Prop. 16].

Using this idea and Baire's theorem, one can also show that the conclusion of Theorem 1.1 is not true for C 1 -generic maps A; actually for C 1 -generic A, the points u P U corresponding to singular constant controls form a perfect set.

Probably the result could also be proved using the Chow ring, but we feel more comfortable with singular cohomology.

Acknowledgements. We are grateful for the hospitality of Institute Mittag-Leffler, where this work begun to take form. We thank R. Potrie, L. San Martin, S. Tikhomirov, and C. Tomei for valuable discussions.

was partially supported by CNPq, Université Bordeaux I, Rede Franco-Brasileira em Matemática, and FAPERJ. N.G. was partially supported by FAPERJ..

Appendix A. The case of one-dimensional input As we explained in § 1.4, this appendix contains a basically independent discussion of the case dim U " 1. The prerequisites are all contained in Section 2 and § 3.1. In order to avoid technicalities at this point, we will be sometimes informal, especially regarding questions of transversality.

Let us define the canonical constraints respectively of type 1, 2, 3, 4 as the following relations:

In other words, P pCq 1 is contained in the following set:

(A.2) E :" pA, Bq P GLpd, Cq ˆglpd, Cq; either A is multiconstrained or A is not multiconstrained but B is not a good match for A ( .

Proposition A.3.

1.

The set E has codimension 1. 2. The set tpA, Bq P E; A is not unconstrainedu has codimension 2.

Informal proof. Proposition A.3 follows from Proposition A.1 and from the fact that for each matrix A that is not multiconstrained, the set of B's that are not good matches for A has positive codimension in glpd, Cq.

Theorem 1.9 in the case m " 1 follows from the propositions above. Therefore the other main results (Theorems 1.1, 1.2, 1.8 and C.1) in the m " 1 case also follow from the propositions. For any of these results, the propositions give extra information of practical value: with the explicit definition of the set E in (A.2), we know which 1-jets should be avoided in Theorem 1.1, for example. The discussion given in Appendix B also applies; it gives explicit conditions on the 2-jet extension of the map A : U Ñ GLpd, Rq that ensure that A satisfies the conclusions of Theorems 1.1 and 1.2.

Proof of Proposition A.2. Let A and B satisfy the hypotheses. We need to show that the space ΛpA, Bq defined by (2.2) is a transitive subspace of glpd, Cq. Let Γ :" sorb Ad A pBq, so that ΛpA, Bq " tIdu _ Γ.

The matrix A is not multiconstrined and so has an adapted basis as above. We change the basis so that A and B are "canonical".

The proof is divided in cases according to the type of constraint. Except for the p4q-constrained case, the matrix A is diagonal, and so the space Γ is described by (2.6).

Unconstrained case: It follows from Lemma 2.13 that if A is unconstrained and diagonal then the only way for the pair pA, Bq to be poor is that B has an offdiagonal zero entry. (The reader should review the proof of Lemma 2.13.) p1q-constrained case: We see that the adjoint Ad A has two eigenvalues (different from 1) of multiplicity 2, namely λ 1 λ ´1 2 " λ 2 λ ´1 3 and λ 2 λ ´1 1 " λ 3 λ ´1 2 . By the same reasoning as in the unconstrained case, it follows that tIdu _ Γ contains the space py ij q P glpd, Cq; y 11 " ¨¨¨" y dd , b ´1 12 y 12 " b ´1 23 y 23 , b ´1 21 y 21 " b ´1 32 y 32 ( . This is a generalized Toeplitz space, and so by Example 2.2 it is transitive.

p2q-constrained case: The reasoning is very similar to that of the p1q-constrained case, but now the adjoint has four eigenvalues (different from 1) of multiplicity 2. The space ΛpA, Bq contains the following subspace:

Again, this is a generalized Toeplitz space, and so it is transitive.

p3q-constrained case: This case is a little different from the two previous ones.

The adjoint has an eigenvalue ´1 of multiplicity 2. Recalling that b 11 and b 22 are different, and making use of the identity matrix, we see that ΛpA, Bq contains the following subspace:

Γ " py ij q P glpd, Cq; y 33 " ¨¨¨" y dd , b ´1 12 y 12 " b ´1 21 y 21 ( .

Appendix C. Proof of a complex version of Theorem 1.1

In the complex setting we consider instead holomorphic mappings A : U Ñ GLpd, Cq.

More precisely, given an open subset U Ă C m , we denote by HpU , GLpd, Cqq the set of holomorphic mappings A : U Ñ GLpd, Cq endowed with the usual topology of uniform convergence on compact sets.

Theorem C.1. Given integers d ě 2 and m ě 1, there exists an integer N ě 1 with the following properties. Let U Ă C m be open, and let K Ă U be compact. Then there exists an open and dense subset O of HpU , GLpd, Cqq such that for any A P O the constant inputs in K N are all universally regular for the system (1.4), except for a finite subset.

We have the straightforward corollary:

Corollary C.2. Given integers d ě 2 and m ě 1, there exists an integer N ě 1 with the following properties. Let U Ă C m be an open subset. There exists a residual subset R of HpU , GLpd, Cqq such that for any A P R the constant inputs in U N are all universally regular for the system (1.4), except for a discrete subset.

These results could probably be obtained in certain more general complex manifolds. But in order to avoid technicalities, we consider only open subsets of C m . Also, we use only elementary real transversality tools. As we did in Section 6, and using Theorem 1.9 instead of Theorem 1.8, we obtain that the set of poor 1-jets from U to GLpd, Cq is the algebraic subset U ˆPpCq m of the space of 1-jets. Hence it admits a stratification

Write U ˆPpCq m as the disjoint union Ů 0ďiďn X i where each X i is a smooth submanifold of dimension i in the jet space J 1 pU , GLpd, Cqq, and X n has codimension m.

Fix now a map A P HpU , GLpd, Cqq. For all v " pa, b 1 , . . . b m q P C m`1 and u " pu 1 , . . . , u m q P C m , write

For all v " pv i,j q 1ďi,jďd P `Cm`1 ˘d2 , write P v " " P vi,j ‰ 1ďi,jďd and define the map Φ v " A `Pv . One can write the 1-jet extension j 1 A at the point u P U as j 1 Apuq " ru, Apuq, B 1 , . . . , B m s P U ˆGLpd, Cq ˆrMat dˆd pCqs m .

The same way, if we put v i,j " pa i,j , b 1,i,j , . . . , b m,i,j q, we have j 1 P v puq " ru, P v puq, pb 1,i,j q 1ďi,jďd , . . . , pb m,i,j q 1ďi,jďd s .

Define the map

The evaluation map of F is:

Hence, F ev pv, uq " j 1 pA `Pv q " " u, pA `Pv q puq, pb 1,i,j q 1ďi,jďd , . . . , pb m,i,j q 1ďi,jďd ı Claim C.3. For all u, the map F ev restricts to a submersion from the p¨, uq-fiber to the ru, ¨s-fiber.

Proof. We want to prove that v Þ Ñ " pA `Pv qpuq, pb 1,i,j q 1ďi,jďd , . . . , pb m,i,j q 1ďi,jďd ı is a submersion, or equivalently that v Þ Ñ " P v puq, pb 1,i,j q 1ďi,jďd , . . . , pb m,i,j q 1ďi,jďd ı is a submersion. Noting that v " pa i,j , b k,i,j q 1ďi,jďd 1ďkďm

, this comes easily from the fact that pa i,j q Þ Ñ P v puq is a submersion, for any fixed set of coefficients pb k,i,j q 1ďi,jďd 1ďkďm .

That claim immediately implies that F ev is a submersion. In particular it is transverse to each X i . By the parametric transversality theorem (see [START_REF] Hirsch | Differential Topology[END_REF]p. 79]), there is a residual subset of parameters v in `Cm`1 ˘d2 such that F v " j 1 Φ v is transverse to X i , for all i.

When v goes to 0, Φ v tends to A in H pU , GLpd, Cqq. Hence, the denseness in H pU , GLpd, Cqq of the maps  such that j 1  is transverse to X i , for all i. Take such a map Â: for all i, the image of j 1  does not intersect X 0 \ ¨¨¨\ X n´1 and intersects X n (which has codimension m) only in a discrete subset.

Fix K 1 Ă U a compact set that contains K in its interior. The image j 1  restricted to K 1 can only intersect X n in a finite set Γ: indeed, any accumulation point of that intersection set would have to be in X 0 \ ¨¨¨\ X n´1 , since X 0 \ . . . \ X n is closed, and this would contradict the fact that j 1  does not intersect X 0 \ ¨¨¨\ X n´1 .

By the choice of our topology, a small perturbation à of  is C 0 close to  by restriction to K 1 . By Cauchy's formula, the map à is C 2 close to  over the set K. Hence, the (compact) image of j 1 à restricted to K is still far from X 0 \ ¨¨¨\ X n´1 , and intersects X n transversally in some ǫ-neighborhood of Γ inside X n . Thus it also has to intersect X n only on a finite set.

So we have found an open and dense subset of holomorphic maps whose 1-jets above K intersect the set of N -poor jets only on a finite number of points. As a consequence, for such maps, there are only finitely many constant singular inputs in K N for the system 1.4. This concludes the proof of Theorem C.1.

Appendix D. Dimension of certain algebraic sets of matrices

In this appendix, which is independent from the rest of the paper, we prove Theorem D.1, which was used in Section 5. This result is also used in [START_REF] Bochi | Transitivity of spaces of matrices[END_REF].

ñ N P X.

So a column-invariant set X is characterized by its set of column spaces. We enlarge the latter set by including also subspaces, thus defining:

vXw :" E subspace of C n ; E Ă col M for some M P X ( .

Then we have:

Theorem D.1. Let X Ă Mat nˆm pCq be a nonempty algebraically closed, columninvariant set. Suppose E is a vector subspace of C n that does not belong to vXw. Then codim X ě m `1 ´dim E .

It is obvious that the algebraicity hypothesis is indispensable.

Theorem D.1 follows without difficulty from intersection theory of the grassmannians ("Schubert calculus"). We tried to make the exposition the least technical as possible, to make it accessible to non-experts (like ourselves). D.2. A particular case. Define (D.1) R k :" A P Mat nˆm pCq; rank A ď k ( .

We recall (see [START_REF] Harris | Algebraic geometry: a first course[END_REF]Prop. 12.2]) that this is an irreducible algebraically closed set of codimension

We can assume that n ´1 ď m, otherwise the conclusion of the theorem is vacuous. Thus codim X ě codim R n´1 " m `1 ´n, as we wanted to show. D.3. Reduction to a property of grassmannians. As we will see, to prove Theorem D.1 it is sufficient to prove a dimension estimate (Theorem D.2 below) for certain subvarieties of a grassmaniann. D.3.1. Grassmannians. Given integers n ą k ě 1, the grassmanniann G k pC n q is the set of the vector subspaces of C n of dimension k.

The grassmannian can be interpreted as a subvariety of a higher dimensional complex projective space using the Plücker embedding G k pC n q Ñ P p Ź k C n q, which maps each V P G k pC n q to rv 1 ^¨¨¨^v k s, where tv 1 , . . . , v k u is any basis of V / This is clearly an one-to-one map. It can be shown (see e.g. [START_REF] Harris | Algebraic geometry: a first course[END_REF]p. 61ff]) that the image is an algebraically closed subset of P p Ź k C n q. Its dimension is (D.3) dim G k pC n q " kpn ´kq.

If E Ă C n is a vector space with dim E " e ď k then we consider the following subset of G k pC n q: (D.4) S k pEq :" V P G k pC n q; V Ą E ( .

(This is a Schubert variety of a special type, as we will see later.) Since any V P S k pEq can be written as E ' W for some V Ă W K , we see that S k pEq is homeomorphic to G k´e pC n´e q.

We will show that an algebraic set that avoids S k pEq cannot be too large:

Theorem D.2. Fix integers 1 ď e ď k ă n. Suppose that Y is an algebraically closed subset of G k pC n q that is disjoint from S k pEq, for some e-dimensional subspace E Ă C n . Then codim Y ě k `1 ´e.