Evelyne Hubert
email: evelyne.hubert@inria.fr

George Labahn
email: glabahn@uwaterloo.ca

Scaling Invariants and Symmetry Reduction of Dynamical Systems

Keywords: Group actions, Rational invariants, Matrix normal form, Model reduction, Dimensional analysis, Symmetry reduction, Equivariant moving frame AMS Classification: 08-04, 12-04, 14L30, 15-04

Scalings form a class of group actions that have theoretical and practical importance. A scaling is accurately described by a matrix of integers. Tools from linear algebra over the integers are exploited to compute their invariants, rational sections (a.k.a. global cross-sections), and offer an algorithmic scheme for the symmetry reduction of dynamical systems. A special case of the symmetry reduction algorithm applies to reduce the number of parameters in physical, chemical or biological models.

Introduction

Consider the following predator-prey model

dn dt = n r 1- n K -k p n + d , dp dt = s p 1-h p n
which has six parameters, r, K, k, s, h, d, and s. Following [START_REF] Murray | [END_REF]Section 3.4] one introduces nondimensional variables

s = s r , k = k rh , d = d K , t = r t, and n = n K , p = h K p (1)
so as to simplify the system into

dn dt = n (1 -n) -k n p n + d , dp dt = s p 1 - p n
where there are only three parameters left, s, h, k.

The original motivation for the present article is to determine this reduced system algorithmically. For that we first need to understand what are the new variables, and how they can be found from the dynamical system at hand. Here, the original dynamical system admits a scaling symmetry: it is invariant under any of the following change of parameterized variables (η, µ, ν):

r → η -1 r, h → µ ν -1 h, K → µ K, s → η -1 s, k → η -1 µν -1 k, d → µ d, t → η t, n → µ n, p → ν p. (2)
The new variables [START_REF] Anderson | Exterior differential systems with symmetry[END_REF] are some specific invariants of the above transformations. We shall prove that they have the rather strong property that any dynamical system that is invariant under the transformations (2) can be written in terms of the variables [START_REF] Anderson | Exterior differential systems with symmetry[END_REF] with the following substitution:

r → 1, h → 1, K → 1, s → s, k → k, d → d, t → t, n → n, p → p. (3)
In this paper we propose algorithms to compute the scaling symmetry of a dynamical system and determine a set of invariants together with a rewriting mechanism to obtain the reduced system. Furthermore we shall show how to retrieve the solutions of the original system from the solutions of the reduced system.

In the above example, if (n(t), p(t)) is a solution of the reduced system for the parameters (s, h, k) then, for any constant (r, h, K), we obtain a solution of the original system with parameter (r, h, K, s, k, d) by forming the following combinations:

s = r s, k = r h k, d = K d, n(t) = K n(rt), p(t) = K h p(rt). (4)
Note that the relationships (1-4) are all given by monomial maps, where negative powers were allowed. As such they are appropriately described by matrices of integers. For instance the transformations (2) is described by a 3 × 9 matrix. If we use the order (η, µ, ν) for the parameters of the transformations and (r, h, K, s, k, d, t, n, p) for the variables of the system then this matrix is

A =   -1 0 0 -1 -1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 -1 0 0 -1 0 0 0 1   .
In this paper we show how parameter reduction, as in the above example, can be algorithmically performed with linear algebra over the integers. This applies to a great number of models from mathematical biology.

Parameter reduction is actually a particular case of a more general problem to which we give a complete solution. We provide an algorithmic solution to scaling symmetry reduction of a dynamical system: determine a maximal scaling symmetry without isotropy, compute a generating set of rational invariants that act as new variables, obtain the dynamics on those new variables and finally establish the correspondence between the solutions of the reduced system and the original system. All those steps, except actually solving the differential systems, are algorithmic and rely solely on linear algebra over the integers.

Scalings form a class of group actions. They describe transformations like (2) that rescales each individual variable. On the theoretical front, scalings are known as torus actions and play a major role in algebraic geometry and combinatorics. Scalings also underlie what is known as dimensional analysis with the invariants giving the dimensionless quantities needed to derive physical laws [START_REF] Birkhoff | Hydrodynamics: A study in logic, fact and similitude[END_REF][START_REF] Bridgman | Dimensional Analysis[END_REF][START_REF] Huntley | Dimensional Analysis[END_REF]. Dimensional analysis has been automated in the works [START_REF] Ishida | Formula processing on physical systems[END_REF] and [START_REF] Khanin | Dimensional analysis in computer algebra[END_REF]. Central to this is the Buckingham-π-theorem. A reinterpretation of this theorem states that a fundamental set of invariants is obtained from the basis of the nullspace of the matrix of exponents of the scaling [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]Section 3.4]. As illustrated in the above example scalings also give mathematical sense to rules of thumb applied to reduce the number of parameters in biological and physical models [START_REF] Murray | [END_REF][START_REF] Lin | Mathematics applied to deterministic problems in the natural sciences[END_REF]. In this context, reduction by a scaling symmetry of a dynamical was previously studied with an algorithmic point of view in [START_REF] Hubert | Polynomial Time Nondimensionalisation of Ordinary Differential Equations via their Lie Point Symmetries[END_REF][START_REF] Lemaire | A method for semi-rectifying algebraic and differential systems using scaling type Lie point symmetries with linear algebra[END_REF][START_REF] Sedoglavic | Reduction of algebraic parametric systems by rectification of their affine expanded lie symmetries[END_REF]. In this paper we go further in this direction than handled in the previous cited works.

Determining symmetries of differential equations has had many applications [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF][START_REF] Anderson | CRC handbook of Lie group analysis of differential equations[END_REF]. One usually resorts to infinitesimal methods and obtain local symmetries. When dealing with a dynamical system given in terms of rational functions, we determine the maximal scaling symmetry as a lattice kernel of an integer matrix. The group action thus determined is rational but retains trivial isotropy.

Computing a generating set of rational invariants and rewrite rules for the general class of rational actions of an algebraic group typically require Gröbner bases computations [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Kemper | The computation of invariant fields and a new proof of a theorem by Rosenlicht[END_REF][START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF]. A rewriting substitution can be achieved provided we allow algebraic functions [START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. Gröbner bases are unnecessary for scalings; linear algebra over the integers provides more information. The key is to compute a Hermite normal form of the matrix describing the scaling. The information is then read from the associated unimodular multiplier giving the Hermite normal form, and its inverse. The unimodular multiplier provides a minimal generating set of rational invariants and the equations of a rational section. Its inverse provides the substitution to be performed to rewrite any invariant in terms of the exhibited generating set. When comparing to [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF][START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF][START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF] where the local crosssection has to be part of the input, an important point here is that a rational section, that is, a global cross-section, is actually a side-product of the algorithm.

As illustrated earlier, invariants can be used as new variables to simplify dynamical systems with a symmetry. When this symmetry is a scaling we show that the reduced dynamical system can be directly determined from the unimodular multiplier and its inverse. The relationship between the solutions of the reduced system and the original system can also be written down explicitly from those two matrices. The solutions of the original system are obtained from the solutions of the reduced system by additional mutually independent quadratures. This is to be compared and contrasted with the general methods of symmetry reduction proposed in [START_REF] Anderson | Exterior differential systems with symmetry[END_REF][START_REF] Fels | Integrating scalar ordinary differential equations with symmetry revisited[END_REF] and [START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF]Section 6] and can be related to the analysis of equivariant evolution equations [START_REF] Chossat | Methods in equivariant bifurcations and dynamical systems[END_REF][START_REF] Gatermann | Computer algebra methods for equivariant dynamical systems[END_REF].

The unimodular multiplier for the Hermite normal form of a scaling matrix is not unique. We propose a normal form that exhibits further properties of the scaling. In particular, this normal form discriminates the cases where the scaling symmetry can be fully used to reduce the number of parameters in a dynamical system. The solutions of the original system are then obtained from the solution of the reduced system with just some additional constants. We also show that the normal form allows us to decide when a natural local cross-section is actually a global cross-section (Theorem 4.10).

The remainder of the paper is organized as follows. Section 2 presents the needed material on integer matrices and the Hermite normal form, along with the normalization of its unimodular multipliers. Section 3 presents scalings together with the matrix notations for monomial maps. Section 4 shows how to produce the generating invariants, rewrite rules and a rational section for a scaling. Section 5 provides an algorithm to compute the maximal scaling that leaves a given set of rational function invariants. The determination of the maximal scaling symmetry of a dynamical system is reduced to this problem. The scaling symmetry reduction of dynamical systems is discussed in Section 6. Section 7 shows how this can be specialized to explicitly reduce the number of parameters in dynamical systems, as mentioned earlier in the introduction.

Integer Matrix Normal Forms

When dealing with matrices of integers such basic operations as Gaussian elimination or finding a row echelon form are no longer ideal since these involve working over the field of rational numbers.

October 2012

In this section we provide the basic information about the Hermite normal form of a matrix of integers, a type of triangularization for integer matrices. Here row and column operations are represented by unimodular matrices, which are invertible integer matrices whose inverses are also integer matrices. The unimodular multiplier to obtain the Hermite normal form of an integer matrix is not necessarily unique. We propose a normal form for such a multiplier, a form particularly relevant for our applications.

Hermite Normal Forms

Definition 2.1 An m × n integer matrix H = [h ij ] is in column Hermite Normal Form if there exists an integer r and a strictly increasing sequence

i 1 < i 2 < • • • < i r of pivot rows such that (i) The first r columns are nonzero; (ii) h k,j = 0 for k > i j ; (iii) 0 ≤ h ij ,k < h ij ,j when j < k.
Thus a matrix is in column Hermite normal form if the submatrix formed by the pivot rows i 1 , • • • , i r and the first r columns is upper triangular and that all nonzero elements of the pivot rows are positive and less than the corresponding (positive) diagonal entry. The integer r is the rank of the matrix. By changing column to row and row and column indices in (ii) and (iii) one obtains the row Hermite Normal Form of a matrix of integers.

Every integer matrix can be transformed via integer column operations to obtain a unique column Hermite form. The column operations are encoded in unimodular matrices, that is, invertible integer matrices whose inverses are also integer matrices. Thus for each A there exists a unimodular matrix V such that A • V is in Hermite normal form. This unimodular matrix is central in the construction of the invariants and the symmetry reduction scheme of dynamical system. It actually has a more prominent role than the Hermite form. In order to simplify the wording we shall call Hermite multiplier of A any unimodular matrix V such that A • V is in Hermite normal form.

Similar statements also holds for the row Hermite normal form. We refer the reader to [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] for more information on such forms.

When A ∈ Z r×n , with r ≤ n, has full row rank r then there exists a unimodular matrix V such that

A • V = [H, 0] with H ∈ Z r×r of full rank. (5)
If W ∈ Z n×n is the inverse of V then we can partition V and W as

V = [V i , V n ] with V i ∈ Z n×r and V n ∈ Z n×(n-r) (6)
and

W = W u W d with W u ∈ Z r×n and W d ∈ Z (n-r)×n . (7)
We then have

I n = W V = W u V i W u V n W d V i W d V n I n = V W = V i W u + V n W d . (8)
Note that the blocks of V provide the column Hermite normal forms of the blocks of W since from [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF] we have

W u • [V i , V n ] = [I r , 0] and W d • [V n , V i ] = [I n-r , 0].
We state a known property of Hermite normal forms [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] in a way that is needed later in the paper.

Lemma 2.2 Let A ∈ Z r×n be a full row rank matrix and V ∈ Z n×n a Hermite multiplier, i.e. V is a unimodular matrix AV is in Hermite normal form. Assume that A

• V = [ H, 0], with H ∈ Z r×r . If V = [V i , V n ]
is partitioned accordingly, with V i ∈ Z n×r , then the columns of V n form a basis for the integer lattice defined by the kernel of A.

Normal Hermite multiplier

For the problem of interest in this paper the number of columns is larger than the rank. In this case the Hermite multiplier is not unique. Indeed, with the partition V = [V i , V n ] as in [START_REF] Chossat | Methods in equivariant bifurcations and dynamical systems[END_REF], column operations using the columns of V n do not affect the Hermite form H and hence result in different Hermite multipliers V . In this subsection we describe a normalization of the Hermite multiplier V which is both simple and unique.

Previous work on determining unique Hermite multipliers includes that of [START_REF] Havas | Extended gcd and Hermite normal form algorithms via lattice basis reduction[END_REF] for integer matrices where the Hermite multiplier is reduced via lattice reduction. We favor the component V n to be in Hermite normal form, as in [START_REF] Beckermann | Normal forms for general polynomial matrices[END_REF], which deals with polynomial matrices. The resulting triangular form exhibits the preferred rational sections (Theorem 4.10) and allows for a parameter reduction scheme for dynamical systems (Section 6).

Proposition 2.3 Let A ∈ Z r×n be a full row rank matrix and V ∈ Z n×n a Hermite multiplier such that A V = [ H, 0] with H ∈ Z r×r .

(i) A Hermite multiplier V is unique up to multiplication on the right by matrices of the form

I r 0 M U , with U ∈ Z (n-r)×(n-r) unimodular .
(ii) There exists a unique Hermite multiplier

V = [V i , V n ] with (a) A • V = [H, 0] with H ∈ Z r×r in column Hermite normal form, (b) V = [V i , V n ] with V n ∈ Z n×(n-r) in column Hermite normal form, (c) If i 1 < i 2 < • • • < i n-r
are the pivot rows for V n then for each 1 ≤ j ≤ n -r :

0 ≤ [V i ] ij ,k < [V n ] ij ,j for all 1 ≤ k ≤ r.
Thus V i is reduced with respect to the pivot rows of V n .

The Hermite multiplier satisfying (a-c) is the normal Hermite multiplier.

proof: Suppose that

V (1) = [V (1)
i , V

n ] and

V (2) = [V (2)
i , V

n ] are two Hermite multipliers both partitioned in the usual way. Then V (1) n and V

(2) n are two bases for the nullspace of A as a module over Z. Thus there exists a unimodular matrix U ∈ Z (n-r)×(n-r) which makes these matrices column equivalent, that is, V

(1) n = V (2)
n U . Also, by the uniqueness of H, the columns of

V (1) i -V (2) i
are in the nullspace of A and hence there exists a matrix M ∈ Z (n-r)×r such that

V (1) i -V (2) i = V (2)
n M . This gives the general form of the multipliers in (i). In order to prove part (ii), let V * ∈ Z n×n be a unimodular matrix such that

H * = I n A • V * is in column Hermite normal form. Partition V * = [V * 1 , V * 2 ] with V * 2 having r columns and set V = [V * 2 , V * 1 ]
. We claim that V is the sought normal Hermite multiplier, that is,

V * 1 = V n and V * 2 = V i .
October 2012

Notice first that V is unimodular since this matrix is simply a reordering of the columns of the unimodular matrix V * . In addition, since A • V * is equal to the last r rows of H * , which is in column Hermite form, and A has full row rank, we have that A • V * = [0, H + ] with H + in Hermite normal form. Therefore A • V = [H + , 0] is in column Hermite form with V unimodular and so, by uniqueness, we have H + = H. This gives part (a). Parts (b) and (c) follow from the fact that V * is also equal to the first n rows of H * , which is in column Hermite normal form. Finally, the uniqueness of V follows from the uniqueness of Hermite normal forms.

The proof of Proposition 2.3, Part (ii), provides a computational method for determining both the Hermite form H and the normal Hermite multiplier V = [V i , V n ]. Indeed one has

I n A • [V n , V i ] = V n V i 0 H ,
with the right hand side in column Hermite form. The complexity of such a computation is therefore the cost of finding a column Hermite form of an (r + n) × n integer matrix. This can be done using the methods of [START_REF] Storjohann | Algorithms for Matrix Canonical Forms[END_REF][START_REF] Storjohann | Asymptotically fast computation of Hermite Normal Forms of integer matrices[END_REF]

V =       -1 -2 -2 -2 -1 -3 -14 -7 -13 -7 1 1 2 1 0 0 2 0 3 0 0 1 0 0 2       .

Scalings

Scalings can be described through the matrix of exponents of the group parameters as they act on each component. Similar descriptions are used for the parameterization of toric varieties [START_REF] Sturmfels | Gröbner Bases and Convex Polytopes[END_REF]. In this section we describe the matrix forms and properties that are useful when representing scalings and computing their invariants. We consider an algebraically closed field K of characteristic zero, the multiplicative group of which is K * .

Matrix notations for monomial maps

If a = [a 1 , . . . , a r ] T is a column vector of integers and λ = [λ 1 , . . . , λ r ] is a row vector with entries in K * , then λ a denotes the scalar

λ a = λ a1 1 • • • λ ar r .
If λ = [λ 1 , . . . , λ r ] is a row vector of r indeterminates, then λ a can be understood as a monomial in the Laurent polynomial ring K[λ, λ -1 ], a domain isomorphic to K[λ, µ]/(λ 1 µ 1 -1, . . . , λ r µ r -1). We extend this notation to matrices: If A is an r × n matrix then λ A is the row vector

λ A = [λ A•,1 , • • • , λ A•,n ]
where A •,1 , . . . , A •,n are the n columns of A.

In some cases it is important to keep track of those exponents which are nonnegative (and hence describe numerators) and those which are negative (and hence describe denominators). To this end the following notation becomes useful. Every vector a ∈ Z r can be uniquely written as a = a + -a - where a + and a -are nonnegative and have disjoint support. Their components are:

[a + ] i = a i if a i ≥ 0 0 otherwise and [a -] i = a i if a i ≤ 0 0 otherwise.
This can be extended to r × n matrices by

A + = [(A .,1 ) + , • • • , (A .,n ) + ] and A -= [(A .,1 ) -, • • • , (A .,n ) -]. If x = [x 1 , . . . ,
x n ] and y = [y 1 , . . . , y n ] are two row vectors, we write x ⋆ y for the row vector obtained by component wise multiplication:

x ⋆ y = [x 1 y 1 , . . . , x n y n ] .
Proposition 3.1 Suppose A and B are matrices of size r × n and n × n, respectively, and that λ is a row vector with r components. Then

(a) If A = [A i , A n ] is a partition of the columns of A, then λ A = [λ A i , λ An ], (b) λ AB = (λ A ) B ,
Suppose A and B are matrices of size r × n and λ and µ are row vectors with r components. Then

(c) (λ ⋆ µ) A = λ A ⋆ µ A . (d) λ A+B = λ A ⋆ λ B
proof: Part (a) follows directly from the definition of λ A . For part (b) we have for each component j, 1 ≤ j ≤ t:

[(λ A ) B ] j = n i=1 [λ A ] bij i = n i=1 ( r ℓ=1 λ a ℓi ℓ ) bij = r ℓ=1 ( n i=1 λ a ℓi bij ℓ ) = r ℓ=1 ( λ n i=1 a ℓi bij ℓ ) = [λ AB ] j .
For part (c) one simply notices that for each j we have

[(λ ⋆ µ) A ] j = r i [λ ⋆ µ] ai,j i = r i λ ai,j i • µ ai,j i = [λ A ] j [µ A ] j = [λ A ⋆ µ A ] j .
The proof of (d) follows along the same lines. October 2012

Scalings in matrix notation

The r-dimensional torus is the Abelian group (K * ) r . Its identity is 1 r = (1, . . . , 1) and the group operation is component-wise multiplication, which we denoted ⋆. Definition 3.2 Let A be a r × n integer matrix: A ∈ Z r×n . The associated scaling is the linear action of (K * ) r on the affine space K n given by

(K * ) r × K n → K n (λ , z) → λ A ⋆ z. (9)
With the notations introduced above we have that

λ A ⋆ z = [λ A•,1 z 1 , . . . , λ A•,n z n ]
with A •,1 , . . . , A •,n being the n columns of A. Thus for each j = 1, . . . , n the action scales the j th component z j by the power product λ a1,j 1

• • • λ ar,j
r . The axioms for a group action are satisfied thanks to Proposition 3.1:

1 r ⋆ z = z and (λ ⋆ µ) A ⋆ z = λ A ⋆ (µ A ⋆ z).
Example 3.3 Consider the 1 × 2 integer matrix A = 2 3 . It defines a scaling on the plane. The scaling is the group action given by

K * × K 2 → K 2 (λ, (z 1 , z 2 )) → λ 2 z 1 , λ 3 z 2 .
The orbits are easily visualized: They lie on the algebraic curves

z 3 1 = c z 2 2 .
Example 3.4 Consider the 2 × 5 matrix A given by

A = 6 0 -4 1 3 0 3 1 -4 3 .
If λ = (µ, ν) and z = (z 1 , z 2 , z 3 , z 4 , z 5 ) then the group action defined by A is given by

λ A ⋆ z = ( µ 6 z 1 , ν 3 z 2 , ν µ 4 z 3 , µ ν 4 z 4 , µ 3 ν 3 z 5 ).
There is no loss of generality in assuming that A has full row rank. Indeed, we can view the scaling defined by A as a diagonal representation of (K * ) r on the n dimensional space K n :

(K * ) r → D n (λ 1 , . . . , λ r ) → diag(λ A )
where D n is the group of invertible diagonal matrices. This in turn can be factored by the group morphism from (K * ) r to (K * ) n defined by A. This is given explicitly by:

ρ(A) : (K * ) r → (K * ) n (λ 1 , . . . , λ r ) → λ A . Suppose now that U A = B 0 is in row Hermite normal form 1 , with unimodular row multiplier U . Consider the splitting U = U 1 U 2 , where U 1 A = B is of row dimension d and U 2 A = 0. Then (K * ) d × (K * ) r-d U -→ (K * ) r A -→ (K * ) n (µ 1 , µ 2 ) → µ U1 1 ⋆ µ U2 2 → (µ U1 1 ⋆ µ U2 2 ) A = µ B 1 .
1 Or any row rank revealing form.

8 http://hal.inria.fr/hal-00668882

Since U is unimodular, ρ(U ) is an isomorphism of groups and the image of (K * ) r by ρ(A) is equal to the image of (K * ) d by ρ(B).

Proposition 3.5 Let A be a full row rank matrix in Z r×n . The isotropy groups for the scaling defined by A on (K * ) n are trivial if and only if the column Hermite normal form of A is [I r , 0].

proof: Assume V = [V i , V n ] is a Hermite multiplier: A • V is in Hermite normal form [H, 0]. Take z ∈ (K * ) n so that there exists λ ∈ (K * ) r such that λ A ⋆ z = z. This is equivalent to [λ H ⋆ z V i , z Vn ] = z V
and therefore to λ H = 1 r . Since H is triangular with positive integer entries on the diagonal, the set of equations λ H = 1 r has r i=1 h i distinct solutions, where (h i ) are the diagonal entries. In all cases, λ = 1 r is a solution. It is the only solution if and only if H = I r .

Rational invariants of scaling

Consider a full row rank matrix A ∈ Z r×n which defines a scaling, that is an action of the torus

(K * ) r on K n . A rational invariant is an element f of K(z) such that f (λ A ⋆ z) = f (z). Rational invariants form the subfield K(z) A of K(z).
In this section we show how a Hermite multiplier of A provides us with a complete description of the subfield of rational invariants. From V , and its inverse, we shall extract

• n -r generating rational invariants that are algebraically (and functionally) independent

• a simple rewriting of any (rational) invariant in terms of this generating set,

• a rational section to the orbits of the scaling.

We thus go much further than the group action transcription of the Buckingham π-theorem of dimensional analysis [START_REF] Birkhoff | Hydrodynamics: A study in logic, fact and similitude[END_REF][START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]. This latter takes any basis of the nullspace of the matrix A and provides a set of functionally generating invariants, some of which could involve fractional powers. In the present approach, only integer powers are involved. This spares us the determination of proper domains of definition. Furthermore, the Buckingham π-theorem gives no indication on how to rewrite an invariant in terms of the generators produced. The rewriting we propose is a simple substitution. This is reminiscent of the normalized invariants appearing in [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF][START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF] (or replacement invariants in [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF]). Using the terminology of those articles, we are in a position to exhibit a global cross-section (or cross-section of degree one) to the orbits of the scaling. Note though that the substitution is again rational: we do not introduce any algebraic functions as would generally be the case when choosing a local cross-section arbitrarily.

Generating and replacement invariants

A Laurent monomial z v is a rational invariant if (λ A ⋆ z) v = z v
and therefore if and only if Av = 0. The following lemma shows that rational invariants of a scaling can be written as a rational function of Laurent monomials that are invariants.

Lemma 4.1 Suppose p q ∈ K(z) A , with p, q ∈ K[z] relatively prime. Then there exists u ∈ Z n such that p(z) = v ∈ kerA ∩ Z n a v z u+v and q(z) = v ∈ kerA ∩ Z n b v z u+v
where the families of coefficients, (a v ) v and (b v ) v , have finite support. proof: We take advantage of the more general fact that rational invariants of a linear action on K n are quotients of semi-invariants (see for instance [START_REF] Popov | Invariant Theory[END_REF]Theorem 3.3]). Indeed, if p/q is a rational invariant, then we have

p(z) q(λ A ⋆ z) = p(λ A ⋆ z) q(z) in K(λ)[z].
As p and q are relatively prime, p(z) divides p(λ A ⋆ z) and, since these two polynomials have the same degree, there exists χ(λ) ∈ K(λ) such that p(λ A ⋆ z) = χ(λ) p(z). It then also follows that q(λ A ⋆ z) = χ(λ) q(z).

Let us now look at the specific case of a scaling. Then

p(z) = w ∈ Z n a w z w ⇒ p(λ A ⋆ z) = w ∈ Z n a w λ Aw z w .
For p(λ A ⋆ z) to factor as χ(λ) p(z) we must have A w = A u for any two vectors u, w ∈ Z n with a v and a u in the support of p. Let us fix u. Then w -u ∈ ker A and χ(λ) = λ Au . From the previous paragraph we have

w ∈ Z n b w λ Aw z w = q(λ A ⋆ z) = λ Au q(z) = λ Au w ∈ Z n b w z w .
Thus Au = Aw and therefore there exists v ∈ ker A ∩ Z n such that w = u + v for all w with b w in the support of q.

The set of rational functions on K n that are invariant under a group action form a subfield of K(z) and, as such, it is a finitely generated field. In the case of a scaling the generators of this field can be constructed making use only of linear algebra and the representation of rational invariants given in Lemma 4.1. proof: Observe first that the components of g are invariants. Indeed the columns of V n span kerA and so λ A ⋆ z Vn = λ AVn ⋆ z Vn = z Vn . We shall prove that any rational invariant can be rewritten in terms of these components.

Theorem 4.2 Let V = [ V i , V n ]
Since V and W are inverses of each other we have

I n = V i W u + V n W d . Thus z = z V i Wu+VnWd
, where z = [z 1 , . . . , z n ] T , the vector of degree 1 monomials. More generally, for any v ∈ Z n ,

z v = z (V i Wu+VnWd)v . If now v ∈ kerA ∩ Z n then z v = z VnWdv = g Wdv since ker A ⊂ ker W u .
The representation given in Lemma 4.1 implies that any p q ∈ K(z) T , with p, q ∈ K[z] relatively prime, has the form

p(z) = v ∈ kerA ∩ Z n a v z u+v and q(z) = v ∈ kerA ∩ Z n b v z u+v
for some u ∈ Z n . As elements of K(z), we can rewrite these as

p(z) = z u v∈kerA ∩ Z n a v z VnWd v and q(z) = z u v ∈ kerA ∩ Z n b v z VnWd v and so p(z) q(z) = p z VnWd q (z VnWd ) = p g Wd q (g Wd ) .
Both V and W are needed for computing invariants and rewrite rules. The method found in [START_REF] Storjohann | Algorithms for Matrix Canonical Forms[END_REF][START_REF] Storjohann | Asymptotically fast computation of Hermite Normal Forms of integer matrices[END_REF] is able to find both V and its inverse W with the same complexity.

V = -1 3 1 -2 with inverse W = 2 3 1 1 . It follows that g = z 3 1 z 2 2
is a generating invariant. Any other rational invariant can be written in terms of g with the substitution z 1 → g, z 2 → g.

V =       1 1 2 1 0 1 0 -1 2 0 1 1 3 2 1 1 0 0 2 1 0 0 0 0 1       and W=       2 -2 -2 3 -1 0 3 1 -4 3 0 -1 0 1 -1 -1 1 1 -1 0 0 0 0 0 1       . With z = (z 1 , z 2 , z 3 , z 4 , z 5
) a generating set of invariants is given by the components

(g 1 , g 2 , g 3 ) = z Vn = z 2 1 z 2 z 3 3 , z 1 z 2 2 z 2 3 z 2 4 , z 3 z 4 z 5
while the rewrite rules are given by

(z 1 , z 2 , z 3 , z 4 , z 5 ) → g Wd = 1 g 2 , g 2 g 1 , g 2 , g 1 g 2 , g 3 g 1 .

Rational section to the orbits

The fact that we can rewrite any invariant in terms of the exhibited generating set by a simple substitution actually reflects the existence and intrinsic use of a rational section [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. Indeed, any unimodular multiplier for the Hermite normal form provides a rational section.

An irreducible variety P ⊂ K n is a rational section for the rational action of an affine algebraic group if there exists a nonempty Zariski open subset Z ⊂ K n such that any orbit of the induced action on Z intersects P at exactly one point [27, Section 2.5].

Theorem 4.5 With the hypotheses of Theorem 4.2, the variety P of (z

V + i -z V - i ) :
z ∞ is a rational section for the scaling defined by A. The intersection of the orbit of a point z ∈ (K * ) n with this section is the point z VnWd . proof: The matrix W d is full row rank and

W d •[V n , V i ] = [I n-r , 0]. By Lemma 2.2 the columns of V i span the lattice kernel of W d . Thus the kernel of K[z] → K[x, x -1 ] z → x Wd .
October 2012 is the prime (toric) ideal Assume z ∈ (K * ) n . For z = λ A ⋆z to be on the variety P of P the components of zV i need to all be equal to 1. Thus λ AV i = z -V i , that is, λ H = z -V i . Because of the triangular structure of H we can always find λ ∈ (K * ) r satisfying this equation. For any such λ we then have z = λ A ⋆ z

P = z V + i -z V - i : (z 1 . . . z n ) ∞ of dimension
V i Wu+VnWd since V i W u + V n W d = I n and so z = λ HWu ⋆ z V i Wu+VnWd = z -V i Wu ⋆ z V i Wu+VnWd = z VnWd by Proposition 3.1.
Thus the intersection of the orbit of z with the variety of P exists, is unique and equal to z VnWd .

From this description we deduce that the invariants z VnWd are actually the normalized invariants as defined in [START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF]. As such the rewriting of Theorem 4.2 applies to the more general class of smooth invariants. Furthermore, if the Hermite form of A is I r there is a global moving frame for the group action, namely the equivariant map ρ : (K * ) n → (K * ) r given by ρ(z) = z -V i . The components z VnWd = ρ(z) A ⋆ z correspond then to the normalized invariants as originally defined in [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF]. The Hermite multiplier exhibited indicates that z 1 = z 2 is the equation of a rational section of the orbits. The intersection of the orbit of a point (z 1 , z 2 ) ∈ (K * ) 2 with this rational section is read from the Hermite multiplier of A and its inverse. It is

z 3 1 z 2 2 , z 3 1 z 2 2 .
Example 4.7 Consider the scaling given by

(z 1 , z 2 , z 3 , z 4 , z 5 ) → ( η ν 3 z 1 , η µ z 2 , ηz 3 , ν ηµ z 4 , ην µ z 5 )
an example used to illustrate dimensional analysis in [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]. In this case the matrix of exponents is

A =   -3 1 1 -1 1 0 -1 0 -1 -2 1 0 0 1 1  
which has a trivial Hermite form [I 3 , 0]. The normal Hermite multiplier and its inverse are given by

V =       0 0 1 -1 -1 0 -1 0 -1 -2 1 1 3 -1 -2 0 0 0 1 0 0 0 0 0 1       and W =       -3 1 1 -1 1 0 -1 0 -1 -2 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1       .
Thus the rewrite rules are simply z → g Wd = (1, 1, 1, g 1 , g 2 ). By Theorem 4.5 the associated rational section is the variety (z 3 -1, z 3 -z 2 , z 3 3 -z 1 ) : z ∞ . Combinations of the ideal generators show that this ideal is simply (z 1 -1, z 2 -1, z 3 -1). This favorable situation comes from the fact that the normal unimodular multiplier and its inverse have a (n -r) × r block of zeros at the bottom left.

The simplest case for the normalization of the Hermite multiplier V occurs when the pivot rows of V n are the rows of an (n -r)-identity matrix. Assuming that the pivot rows appear at the end, a situation that can be arranged by permuting the columns of A and therefore the order of the original variables, then the normal Hermite multiplier and its inverse are

V = V * i V * n 0 I n-r and W = V * i -1 -V * i -1 V * n 0 I n-r .
The rewrite rules are then: z → g Wd = (1, . . . , 1, g 1 , . . . , g n-r ) which indicates that the equations for the section can be made simpler than in Theorem 4.5. This is explored in next section.

Simple rational sections

A rational section is defined by r monomial identities involving the original variables. The simplest identity is an assignment of values to particular variables. In the framework of [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF][START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF] or [START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Hubert | Smooth and algebraic invariants of a group action. Local and global constructions[END_REF], the most natural equations to consider for a cross-section are z 1 = 1, . . . , z r = 1. With an appropriate re-ordering of the variables, such equations always define a local cross-section. In Theorem 4.10 we give a necessary and sufficient condition for such equations to in fact define a global cross-section (i.e. a rational section). The criterion is read from the normal Hermite multiplier defined by Theorem 2.3. We isolate two facts for the proof as lemmas before proceeding with the theorem. proof: The proof boils down to a simple factorization rule. Suppose x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ) and let I = (x 1 -y 1 , . . . , x n -y n ) denote the ideal generated by the components of x -y. It is enough to show that x a -y a ∈ I for any vector a = (a 1 , . . . , a r ) T representing an arbitrary column of A. Then

x a -y a = x a1 1 • • • x ar r -y a1 1 • • • y ar r .
If for all j, a j = 0 then x a -y a = 0 ∈ I. If there is a j such that a j > 0 then

x aj j -y aj j = (x j -y j ) aj -1 b=0 x b j y aj -1-b j ∈ I
so that x aj j ≡ y aj j mod I and therefore x a ≡ y a mod I, hence x a -y a ∈ I. Otherwise note that x -1 i -y -1 j = x -1 j y -1 j (x j -y j ) ∈ I so that the previous argument can be adapted when a has only negative components. Lemma 4.9 Let V n be an integer matrix with n rows. The components of z Vn form a generating set of rational invariants if and only if V n is a basis of the lattice kernel of A.

proof: By Lemma 4.1 it is sufficient to prove the result for invariant Laurent monomials. A Laurent monomial z v is invariant if and only if v ∈ ker A.

Theorem 4.10 The variety of the ideal (z 1 -1, . . . , z r -1) is a rational section to the scaling defined by A if and only if the normal Hermite multiplier V of A is of the form

V = V * i V * n 0 I n-r . ( 10
)
The equations z 1 = 1, . . . , z r = 1 for a local cross section in a moving frame construction is a very natural choice [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF][START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF] . The previous theorem shows when such a choice is a global section.

The generating invariants are therefore g i = (z 1 , . . . , z r ) V * n z r+i for 1 ≤ i ≤ n -r. In addition, any other rational invariants can be written in terms of these g i with the substitution (z 1 , . . . , z r , z r+1 , . . . , z n ) → (1, . . . , 1, g 1 , . . . , g n-r ).

Note that the form [START_REF] Gatermann | Computer algebra methods for equivariant dynamical systems[END_REF] is the only possibility for the n -r bottom rows of V i to be zero. As mentioned at the end of Subsection 2.2, the rows of V i being zero implies that the n -r bottom rows of V n form a unimodular matrix. Such a block in Hermite normal form can only be the identity matrix.

October 2012 proof: We first prove that if the normal Hermite form multiplier is as described then (z

V + i - z V - i ) : z ∞ = (z 1 -1, . . . , z r -1). As (z V + i -z V - i ) : z ∞ = P ∩ K[z]
, where P is the ideal generated by the components of (z V i -1) in K[z, z -1 ], it is sufficient to prove that P = (z 1 -1, . . . , z r -1).

Let z = (z 1 , . . . , z r ). Due to the special structure of V i we have z V i = zV * i where V * i is unimodular. From zV * i ≡ 1 r mod P we infer z = zV

* i V * i -1
≡ 1 r mod P thanks to Lemma 4.8. Thus (z 1 -1, . . . , z r -1) ⊂ P . Conversely, by Lemma 4.8 the components of (z V * i -1 r ) belong to the ideal (z 1 -1, . . . , z r -1) hence P = (z 1 -1, . . . , z r -1).

We now prove that if (z 1 -1, . . . , z r -1) is the ideal of a rational section then the normal Hermite multiplier is of the shape indicated in the Theorem.

An irreducible variety P is a rational section if the ideal I ⊂ K(y)[z] of the intersection of P with a generic orbit O y consists of a single point. Then the reduced Gröbner basis G of I, for any term order, is given by {z 1 -q 1 (y), . . . , z n -q n (y)}, where the q i are rational functions in K(y). According to [13, Theorem 3.7], {q i | 1 ≤ i ≤ n} form a generating set of rational invariants and any invariant rational function R can be rewritten in terms of these by substitution: R(z 1 , . . . , z n ) = R (q 1 (z), . . . , q n (z)) .

Assuming (z 1 -1, . . . , z r -1) is the ideal of a rational section to the scaling action determined by A, the ideal I is

(z 1 -1, . . . , z r -1, λ A - 1 z 1 -λ A + 1 y 1 , . . . , λ A - 1 z n -λ A + n y n ) : λ ∞ ∩ K(y)[z].
This is a binomial ideal ideal with its reduced Gröbner basis consisting of binomials: the rational functions q i are Laurent monomials. Collecting their powers into an integer matrix U ∈ Z n×(n-r) , we can write the reduced Gröbner basis as: G = z 1 -1, . . . , z r -1, z r+1 -y U1 , . . . , z n -y Un-r . The components of y U thus form a generating set of rational invariants and for any rational invariant R we have R(z 1 , . . . , z n ) = R 1, . . . , 1, z U1 , . . . , z Un-r .

Take V = V i V n a Hermite multiplier for A and write

U = U * U † and V n = V * n V † n
where U * and V * n are of size (n -r) × r while U † and V † n are of size (n -r) × (n -r). Since z Vn is a vector of invariants we have

z Vn = z 0 U Vn . Thus V n = U V † n and hence V † n = U † V † n . Since V n has full column rank n -r, we deduce from V n = U V † n that V † n is non singular. Hence V † n = U † V † n implies that U † = I n-r
. By Lemma 4.9, the columns of U form a lattice basis of the kernel of A. Hence Ṽ = V i U is a Hermite multiplier of A. Further reductions of the columns of V i with respect to the columns of U brings the desired normal Hermite multiplier.

Determining scaling symmetries

In the previous section we assumed that a scaling matrix is provided and we computed its rational invariants. In this section we consider a the reverse problem. That is, we are given a finite set of rational functions and look for a maximal scaling matrix A ∈ Z r×n that leaves these functions invariant. This allows us to determine all the scaling symmetries of the dynamical systems studied in Sections 6 and 7.

Symmetries of differential systems are often determined through infinitesimal methods [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]. If we make the infinitesimal method specific to scaling symmetries, a solution can be achieved by computing the nullspace of a matrix [START_REF] Hubert | Polynomial Time Nondimensionalisation of Ordinary Differential Equations via their Lie Point Symmetries[END_REF]. However in that case we only have a local symmetry. In the case of a scaling symmetry of a dynamical system given by rational functions we can have a global picture. Consider f = p q ∈ K(z), where p, q ∈ K[z] are relatively prime, and pick w in the support of p or q. By Lemma 4.1, A • (v -w) = 0 for all v in the support of p and q. Let K f be the matrix whose columns consist of the vectors v -w for all v in the support of p and q (with v = w). Then f = p q is invariant for the scaling determined by A if and only if A • K f = 0. When f is already a Laurent polynomial one should simply take K f to be the matrix of exponents of f -thus considering w = 0, the exponent of the denominator.

The condition on the above scaling matrix A is independent of the choice of w in the support of p or q. Indeed suppose α 1 , . . . , α ℓ are the integer vectors of the form v -w for all v = w in the support of p and q and β 1 , . . . , β ℓ are the integer vectors of the form v -u with v = u in the support and w and u distinct. Then there exists an index k such that β j = α j -α k for all j. Then A • α j = 0 for all j implies A • β j = 0 for all j (and conversely).

Consider a vector of rational functions F (z) = [f 1 (z), . . . , f m (z)]. To each component f i we can associate a matrix K i as previously described. Let K = [K 1 , . . . , K m ]. Then the necessary and sufficient condition for F to be an invariant map for the scaling defined by A is that A • K = 0. For this we have the following, which is a simple variation of a proposition found in [7, page 72].

Proposition 5.1 Suppose K ∈ Z n×m is a matrix of integers and that U ∈ Z n×n is a unimodular matrix such that U • K is in row Hermite normal form

U • K = K 1 0 (11)
having exactly r zero rows. Let A be the last r rows of U . Then proof: Let V be the inverse of U . Then A • V = [0, I r ] and so permuting the columns of V gives a unimodular multiplier having trivial Hermite normal form. This gives (i). Property (ii) follows from the fact that A is a basis for the integer lattice given by left kernel of K.

The first property implies in particular that A is of full row rank. It furthermore defines a scaling without isotropy (cf. Proposition 3.5).

The second property shows the maximality of the scaling found. If A * is another matrix with the same property then there is a unimodular matrix U * such that A * = U * • A. Otherwise B = M • A has either lower rank or has a nontrivial Hermite normal form.

Example 5.2 In order to find the scaling symmetry of the prey-predator model presented in the introduction we need to determine the scalings that leave invariant the two rational functions which are the components of

F = t r 1- n K -k p n + d , s t 1-h p n .
The first step is to normalize one of the terms of the denominators. For instance we consider:

F = rt + dtn -1 -rK -1 tn -rK -1 dt -ktn -1 p 1 + dn -1 , s t -h n -1 s t p 1 .

October 2012

We can then form the matrix K with the non trivial exponents. With variable order (r, h, K, s, k, d, s, t, n, p) this matrix is:

K =               0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 -1 0 -1 1 0 -1 0 -1 0 0 0 0 0 1 0 1              
.

Here the first 6 columns of K are determined from the exponents of the first component of F and the last 2 columns are determined from the second component.

Applying Proposition 5.1 we determine a 9 × 9 unimodular matrix U such that U • K is in row Hermite normal form. The row Hermite normal form here has 3 zero rows at the end. We thus retain from U the bottom three rows. The maximal scaling leaving F invariant is thus given by the matrix

A =   -1 0 0 -1 -1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 -1 0 0 -1 0 0 0 1   .

Dynamical Systems

In this section we consider dynamical systems of the form

dz dt = G(t, z), (12)
where z = (z 1 , . . . , z n ) is a vector of variables dependent on t and G is a rational map R × R n → R n . We examine the simplification that can be obtained when such a system has a scaling symmetry.

The symmetry of a differential system is a group of transformations that leaves the solution set invariant [START_REF] Olver | Applications of Lie Groups to Differential Equations[END_REF]. There is a common understanding that a differential system with symmetry can be reduced. For equivariant dynamical systems the reduction has clear meaning [START_REF] Chossat | Methods in equivariant bifurcations and dynamical systems[END_REF][START_REF] Gatermann | Computer algebra methods for equivariant dynamical systems[END_REF]. The symmetry is given by a locally free linear action on the space of variables. The reduced system is then the dynamical system induced on the invariants of this action. Yet obtaining the invariants and the reduced system is only the first issue. A second issue is to recover the solutions of the original system from the solutions of the reduced system.

We first study the case where the symmetry is a scaling that acts only on the z variables. We then consider the more general case where the scaling acts on t as well as on z. We show how to obtain directly a reduced system and how the solution of the original system can be deduced from the solution of the reduced system with some additional quadratures. The reduced system and the quadratures are simply constructed from a Hermite multiplier of the scaling matrix, and its inverse.

Our results corroborate the results in [START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF] and [START_REF] Anderson | Exterior differential systems with symmetry[END_REF] without being direct applications. On one hand [START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF]Section 6] suggests how to apply the ingredients of the moving frame [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF] in order to reduce a differential system by its symmetry. This method requires a (local) cross-section as input and a companion equation. The differential equations are then rewritten in terms of the so-called normalized invariants and one needs to spot a differentially generating subset among these, with the possibility of requiring syzygies. The solutions of the original equations are then obtained thanks to the solutions of the differential system bearing on the moving frame 3 that can be written in terms of the curvature matrices.

On the other hand the symmetry reduction scheme in [START_REF] Anderson | Exterior differential systems with symmetry[END_REF] applies to exterior differential systems. It naturally requires the infinitesimal generators of the symmetry group but also a quotient map and a cross-section. The key to obtaining the reduced system lies in the semi-basic forms. Computing these essentially resorts to solving a linear system with functional coefficients. The solutions of the original system are then recovered by determining and solving equations of Lie type. When the symmetry group is solvable, these equations can be solved by quadratures. In the case of scaling symmetries a quotient map and a (global) cross-section are provided in Section 4: they are given by the monomial maps defined by V i and W d respectively. Therefore the scaling symmetry reduction of any exterior differential system can be carried out essentially algorithmically. We shall point out in the text what the semi-basic forms are in the case of a dynamical systems. Indeed, we do not need to determine those then.

In what follows, we show how to read the reduced system and the quadratures directly on the Hermite multiplier of the matrix defining the scaling, and its inverse.

Symmetry on the dependent variables

Consider a scaling on K n defined by A ∈ Z r×n . The condition for the scaling defined by A to be a symmetry of the differential system ( 12) is that G be equivariant with respect to z, that is,

G(t, λ A ⋆ x) = λ A ⋆ G(t, z). In this case, if z(t) is a solution of (12) then, for any λ ∈ (R * ) r , λ A ⋆ z(t) is also a solution.
For the rest of this subsection we simply write G(z), omitting t, even though we do not assume that G is independent of t. The notation should only suggest that the scaling acts trivially on t. With the notation

z -1 = z -1 1 , . . . , z -1 n
we have that z -1 ⋆ G(z) is an invariant map so that there is no loss of generality in considering the dynamical system dz dt = z ⋆ F (z) where

F (λ A ⋆ z) = F (z). ( 13
) Let V = [V i , V n ]
be a Hermite multiplier of A and W = W u W d its inverse. We consider the new variables x = z V i and y = z Vn . The variables y stand for the invariants of the scaling, while the auxiliary variables x stand for a moving frame, up to isotropy (Theorems 4.2 and 4.5). The dynamics for x and y are obtained by application of the following useful lemma. Lemma 6.1 Suppose z = [z 1 , . . . , z n ] is a vector of functions of time t and B ∈ Z n×k is a matrix of integers. Then

d dt z B = z B ⋆ z -1 ⋆ dz dt • B . (14)
proof: Suppose first that b = [b 1 , . . . , b n ] T is an arbitrary column vector of integers. Then

z b = z b1 1 • • • z bn n and so d dt (z b ) = b 1 z b z 1 • dz 1 dt + • • • + b n z b z n • dz 1 dt = z b b 1 z 1 • dz 1 dt + • • • + b n z n • dz 1 dt = z b z -1 ⋆ dz dt • b . (15)
October 2012

Example 6.4 Consider the dynamical system

dz 1 dt = z 1 (1 + z 1 z 2 ), dz 2 dt = z 2 1 t -z 1 z 2
Then A, V and W defined by

A = 1 -1 , V = 1 1 0 1 , W = 1 -1 0 1 .
define a scaling symmetry, its normal Hermite multiplier, and its inverse.

We introduce, as new variables, the invariant of the scaling y = z Vn = z 1 z 2 and the auxiliary variable x = z V i = z 1 . The induced dynamical system for those variables are, on one hand, the reduced system -consisting of a single equation -and a quadrature:

dy dt = y 1 + 1 t , 1 x dx dt = 1 + y.
It is reasonably easy to write the solution of this linear differential system:

y(t) = c 1 t e t , x(t) = c 2 exp t + c 1 (t -1)e 2t .
We can thus provide the solutions of the original system as

[z 1 (t), z 2 (t)] = [x(t), y(t)] W , which is z 1 (t) = x(t) = c 2 exp t + c 1 (t -1) e t , z 2 (t) = y(t) x(t) = c 1 c 2 t exp c 1 (t -1) e t .

General case

Consider a scaling on K n+1 defined by Ā ∈ Z r×(n+1) . The condition for the scaling defined by Ā to be a symmetry of the differential system [START_REF] Hubert | Generation properties of Maurer-Cartan invariants[END_REF] is that F (t, z) = t z -1 ⋆ G(t, z) is an invariant map for the scaling. Without loss of generality we therefore write our dynamical system in the form

t dz dt = z ⋆ F (t, z) (19)
where F : R × R n → R n is an invariant map for the scaling defined by Ā ∈ Z r×(n+1) .

We write Ā = [A 0 , A] = [A 0 , A 1 , . . . , A n ] so that the scaling is given by

λ Ā ⋆ [t, z] = λ A0 t, λ A z = λ A0 t, λ A1 z 1 , . . . , λ An z n .
It is actually convenient to introduce an additional dependent variable z 0 , add an equation for it, and keep time invariant in a first step. We set F = [1, F ] and z = (z 0 , z 1 , . . . , z n ) and consider the dynamical system:

t dz dt = z ⋆ F (z). (20)
The first equation of this system is t dz

0 dt = z 0 so that t -1 z 0 is constant. If z(t) = [z 0 (t), z1 (t), . . . , zn (t)]
is a solution of (20) and the constant c = t -1 z0 (t) is not zero, then

z(t) = z1 t c , . . . , zn t c
is a solution of [START_REF] Kemper | The computation of invariant fields and a new proof of a theorem by Rosenlicht[END_REF]. Conversely, if z(t) = [z 1 (t), . . . , z n (t)] is a solution of ( 19) then [t, z 1 (t), . . . , z n (t)] is a solution of [START_REF] Khanin | Dimensional analysis in computer algebra[END_REF]. If we set s = ln(t) then system (20) can be rewritten as dz ds = z ⋆ F (z). We can then apply the reduction of Theorem 6.3. We can also keep t as the independent variable. The statement and the proof are completely analogous.

Using Maple one obtains closed form solutions for these equations, solving first for y 2 , then y 1 and x:

y 2 (t) = t c 1 -t y 1 (t) = c 1 t (ln(t -c 1 ) -ln(t) + c 2 ) x(t) = c 3 t 1/3 (ln(t -c 1 ) -ln(t) + c 2 ) 2/3
with c 1 , c 2 , c 3 arbitrary constants. A solution to the original dynamical system is therefore given by

(z 0 (t), z 1 (t), z 2 (t)) = (x(t), y(t)) W = x(t) 3 y 1 (t) 2 , y 1 (t) x(t) , x(t) 5 y 2 (t) y 1 (t) 4 = c 3 3 c 2 1 t, c 1 c 3 t 2/3 (ln(t -c 1 ) -ln(t) + c 2 ) 1/3 , c 5 3 t 10/3 (ln(t -c 1 ) -ln(t) + c 2 ) 2/3 c 4 1 (-t + c 1 )
.

Substituting t → t/c with c = c 3 3 c 2 1
, simplifying and renaming the constants gives the solution of the original system as

z 1 (t) = a 1/3 t 2/3 (ln(t -a) -ln(t) + b) 1/3 , z 2 (t) = t 10/3 (ln(t -a) -ln(t) + b) 2/3 a 2/3 (a -t)
with a, b arbitrary constants. We note that this solution is considerably simpler than that produced by Maple.

Models with parameters

Dynamical systems are a standard tool in modeling. The model bears on some state variables z 1 , . . . , z q that evolve with time t and the equations are written with some constant parameters c 1 , . . . , c p that describe the media. The parameterized dynamical system can be written

dz dt = G(c, t, z). (23)
Biological models typically come with more parameters than are relevant for a qualitative analysis: there is often a way to group parameters without qualitative change to the solution [START_REF] Murray | [END_REF]. The rule of thumb used in these problems can often be explained by a scaling symmetry. This was the case, for example, in the predator-prey model in the introduction.

In this section we apply the results of the previous section to reduce the number of parameters in the presence of a scaling symmetry. With a series of classical models we demonstrate our algorithmic approach to the reduction of parameters: first compute the scaling symmetry, then produce the reduced system and the correspondence with the solution of the original system. Each example illustrates a different aspect of the particular reduction.

Symmetry reduction of the number of parameters

Note that (23) can be recast into (12) by extending the system with the equations dc dt = 0. The matrix A ∈ Z r×n , n = p + q + 1, defines a scaling symmetry of [START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF] if the map F (c, t, z) = t z -1 ⋆ G(c, t, z) is an invariant, that is, F (λ A ⋆ (c, t, z)) = F (c, t, z). The scaling matrix A is determined by the method given in Section 5.

Let us assume that the normal Hermiter multiplier of A has the form4 :

V = Ṽ V 0 I q+1 . with inverse W = W Ŵ 0 I q+1 . ( 24
)
Then Ṽ is a unimodular matrix in Z p×p . Also r ≤ p and so we can reduce the number of parameters by r. The appropriate recombinations of parameters to consider are read from V . Consider the partition Ṽ and V as Ṽ = [ Ṽi , Ṽn ] and V = [ Vt , Vz ] (

where Ṽn and Vz have p -r and q columns, respectively. From Theorem 6.5 we know the invariants of the scaling are given by

c = (c 1 , . . . , c p-r ) = (c 1 , . . . , c p ) Ṽn , t = (c 1 , . . . , c p ) Vt • t, z = (z 1 , . . . , z q ) = (c 1 , . . . , c p ) Vz ⋆ (z 1 , . . . , z q ). ( 26
)
The algebraic manipulations on the variables (c, t, z) in this case bear essentially on the variables c. Indeed if A is the original scaling matrix and we use the partition A = [ Ã, Â], with à having p columns, then we see that

à • Ṽ = à • [ Ṽi , Ṽn ] = [ H, 0 ]
where H is the column Hermite form for à (and A). It is not difficult to see that Ṽ is in fact the normal Hermite multiplier of à in this case with W its inverse.

The reduced system of the dynamical system is obtained from W d , the bottom p -r + q + 1 rows of the inverse of V . In this case we can partition these rows as

W d =   W c W t W z 0 1 0 0 0 I q   . ( 27
)
The reduced system is then determined with the subsitution

c → c Wc , t → c Wt t, z → c Wz ⋆ z giving dz dt = c Wt c -Wz ⋆ G c Wc , c Wt t, c Wz ⋆ z . (28)
The reduced system has p -r parameters, c, and q state variables, z.

If (c, z(t)) is a solution of ( 23), with no vanishing component, then c Ṽn , c Vz z(c -Vt t) is a solution of [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF]. Conversely if (c, z(t)) is a solution of [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF], with no vanishing component, then

d Wu ⋆ c Wc , c Wz ⋆ z(c -Wt t)
dn dt = r n 1 - n k .
The scaling symmetries of this system are the scalings that leave the Laurent polynomial r 1 k 0 t 1 n 0r 1 k -1 t 1 n 1 invariant. Following Section 5 we form the matrix K of its exponents:

K =     1 1 0 -1 1 1 0 1     .
Applying Proposition 5.1 one determines the matrix A that describes the scaling symmetry for this system, A = -1 0 1 0 0 1 0 1 .

One can indeed see that the system is invariant if we make any of the following change of variables parameterized by (µ, ν)

r → µ -1 r, k → ν k, t → µ t, n → ν n.
The normal Hermite multiplier of A, and its inverse, are given by

V =     -1 0 1 0 0 1 0 -1 0 0 1 0 0 0 0 1     and W =     -1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1     .
With the substitution read from W d , r → 1, k → 1, t → t, n → n, we obtain the reduced system:

dn dt = n (1 -n).
We can combine the general solution n(t) = (1 + c e -t ) -1 of the reduced system and two constants (r, k) into the general solution of the original system as follows from W :

r = 1 r , k = k, n(t) = k n t r = k 1 + c e -t r -1
.

Conversely any solution of the original system n(t) = k (1 + c e -rt ) -1 provides a solution of the reduced system by taking n(t) = 1 k n( t r ) as dictated by V .

Lotka-Volterra equations

The scaling symmetry reduction of a given dynamical system is not unique. For example, the dynamical system governing a reaction kinetics described in [START_REF] Murray | [END_REF]Section 6.6]

dx dt = k 1 ax -k 2 xy, dy dt = k 2 xy -k 3 y
has parameters (a, k 1 , k 2 , k 3 ) and variables (x, y). In [START_REF] Murray | [END_REF]Section 6.6] it is reduced to the Lotka-Volterra equations

du dτ = u (1 -v), dv dτ = α v (u -1)
using the variables

α = k 3 k 1 a , τ = ak 1 t, u = k 2 k 3 x, v = k 2 k 1 a y. (29)
October 2012

This change of variables can be obtained through the general scheme we described in Section 6.

When we see it this way we have a simple way of rewriting the system in terms of these new variables. It is given by an explicit substitution:

a → 1, k 1 → 1, k 2 → 1, k 3 → α, t → τ, x → α u, y → v.
The first step of our algorithm is to determine the scaling symmetry of the dynamical system: these are the scalings that leave the components of [t (k 1 a -k 2 y), t (k 2 x -k 3 )] invariant. To determine these we form the matrix K of the exponents:

K =           1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0          
with a basis of the lattice left kernel of K providing the maximal scaling symmetry of the system (Section 5). This scaling symmetry is given by the matrix

A =   0 -1 -1 -1 1 0 0 -1 1 0 0 0 0 0 2 -2 -1 0 0 1 1   .
By Theorem 4.2 a minimal set of generating invariants for this scaling is given by any Hermite multiplier V of A. The Hermite multiplier underlying the choice of new variables in [START_REF] Sedoglavic | Reduction of algebraic parametric systems by rectification of their affine expanded lie symmetries[END_REF] and its inverse are given by

V =           -1 1 1 -1 1 0 -1 -1 2 1 -1 1 0 -1 0 -2 -1 0 0 1 1 0 0 0 1 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1           and W =           0 -1 -1 -1 1 0 0 -1 1 0 0 0 0 0 2 -2 -1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1           .
This Hermite multiplier has the required shape [START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF] to apply the parameter reduction scheme of Section 7.1. The reduced system, with three fewer parameters, is obtained by applying the substitution read from the inverse W while the new variables are read from the Hermite multiplier V itself.

In the above example V is not the normal Hermite multiplier since the kernel V n is not in column Hermite form. In this case the normal Hermite multiplier and its inverse are given by

V =           -1 1 1 -1 1 -1 -1 -1 2 1 -1 1 -1 -1 0 -2 -1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1           and W =           0 -1 -1 -1 1 0 0 -1 1 0 0 0 0 0 2 -2 -1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1           .
This normal Hermite multiplier is obtained from the previous Hermite multiplier simply by adding column 4 to column 6. Using the normal Hermite multiplier leads to the reduced system

du dτ = u (1 -v), dv dτ = v (u -α)
with the substitution, which can be read from W ,

a → 1, k 1 → 1, k 2 → 1, k 3 → α, t → τ, x → u, y → v
and with the new variables, which are read from V ,

α = k 3 ak 1 , τ = ak 1 t, u = k 2 ak 1 x, v = k 2 ak 1 y.
This example illustrates how the choice of a Hermite multiplier affects the new variables and the reduced system. We do not claim that the normalization of the Hermite multiplier we offered is always the best choice. Yet this is a choice that detects when the scaling symmetry can be fully used to reduce the number of parameters. The scheme proposed in Section 7.1, or even of Section 6, can nevertheless be put into action with other choices of Hermite multiplier. Also, one should remark that the normalization of the Hermite multiplier, and hence the invariants we use as new variables, depends on the order of the parameters and variables. As a practical tip, one should choose an order where the parameters that we want to be substituted by 1 come first.

Schackenberg model for a simple chemical reaction with limit cycle

Consider the following dynamical system which models a plausible chemical reaction [START_REF] Murray | [END_REF]Section 7.4] . The parameters are c = (a, b, k, h).

dx dt = a -k x + h x 2 y, dy dt = b -h x 2 y.
The scaling symmetries of this system are the scalings that leave a t x -1 -k t + h t x y, b t y -1 -h t x 2 invariant. Following Section 5 we form the matrix K of the exponents appearing in those Laurent polynomials:

K =           0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 1 1 -1 0 1 0 2 0 0 1 -1 0           .
Applying Proposition 5.1 one then determines the matrix A that describes the scaling symmetries for this system:

A = 1 1 1 1 -1 0 0 0 0 -1 -3 1 1 1 .
The normal Hermite multiplier V of A has the particular simple form [START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF]. Together with its inverse W , they are given by:

V =           1 1 -1 2 0 -1 -1 0 0 1 0 0 0 0 0 -1 0 -3 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1           , W =           1 1 -1 1 -1 0 0 0 0 -1 -3 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1           .
October 2012

The reduced model therefore has two parameters (b, h) and two state variables (x, y):

dx dt = 1 -x + h x 2 y dy dt = b -h x 2 y
with the new model obtained by the substitution

a → 1, b → b, k → 1, h → h, t → t, x → x, y → y.
If (b, h, x(t), y(t)) is a solution of this reduced system and (a, k) is any pair of constants then a, ak,

1 ab , ah b 3 , bx a b t , by a b t
is a solution of the original system. We have intrinsically considered the invariant variables:

(b, h) = c = b a , a 2 h k 3 , t = k t, and (x, y) = z = k a , k a ⋆ (x, y).
This example raises two remarks. First, had we chosen to order the parameters as c = (a, k, b, h), the normal Hermite multiplier would be of the form [START_REF] Gatermann | Computer algebra methods for equivariant dynamical systems[END_REF]. Nonetheless, with the slightly more general form [START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF] we do obtain a model reduction as expected, without having to fiddle with the parameter order.

Secondly, the nondimensional model used in [START_REF] Murray | [END_REF]Section 7.4] is

dx dt = a -x + x 2 y, dy dt = b -x 2 y
and is obtained with the non dimensional variables a = h

1 2 k 3 2 a, b = h 1 2 k 3 2 b, t = k t, x = h 1 2 k 1 2
x, y = h

1 2 k 1 2
y.

To cast this in the context of symmetry reduction, we can resort to the general approach of [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF][START_REF] Hubert | Rational invariants of a group action. Construction and rewriting[END_REF][START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF]. The variety of (h -1, k -1) is a quasi-section: it has two points of intersection with a generic orbit. The related replacement invariants are thus algebraic functions of degree 2 and hence the appearance of square roots. Here, the state variables x and y are molecular concentrations of reactants that evolve with time, while a and b reflect constant supply of some of the reactants. The parameters k and h are stochiometric coefficients. As such, they are positive and the use of square roots is well defined. The reductions obtained with the approach proposed in this paper are always rational. We therefore do not need to argue about the sign of the parameters or of the state variables.

Prey-predator model

Consider the predator-prey model given by the dynamical system

dn dt = n r 1- n K -k p n + d , dp dt = s p 1- hp n
which appears in the introduction. The parameters are c = (r, h, K, s, k, d) and the state variables are z = (n, p).

The scaling symmetry of this system was determined in Example 5.2 and is given by

A =   -1 0 0 -1 -1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 -1 0 0 -1 0 0 0 1   .
The normal Hermite multiplier V of A has the particular simple form [START_REF] Müller-Quade | Calculating generators for invariant fields of linear algebraic groups[END_REF]. Together with its inverse W , they are given by:

V =               -1 0 0 -1 -1 0 1 0 0 0 0 -1 0 -1 0 0 0 1 0 1 1 0 0 -1 0 -1 -1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1               , W =              
-1 0 0 -1 -1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 -1 0 0 -1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1

             
.

The reduced system

dn dt = n (1 -n) -k p n + d , dp dt = s p 1 - p n .
is then obtained by the substitution:

r → 1, h → 1, K → 1, s → s, k → k, d → d, t → t, n → n, p → p.

Reaction kinetics

The previous examples all had, at least up to parameter ordering, simple rational sections. Consider now the following example of reaction kinetics from Murray [START_REF] Murray | [END_REF]Pg 216] given by

dx dt = k 1 y 2 k + y 2 -k 2 x dy dt = h 1 x 2 h + x 2 -h 2 y.
In this case we have two state variables x, y and parameters k, h, k 1 , h invariant. Following Section 5 we normalize these rational functions and then form the matrix K of the exponents:

K =              
-1 -1 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1

1 0 1 1 1 0 1 1 1 0 -1 0 0 2 1 0 2 2 2 0 2 0 -1 0 0              
.

The resulting symmetry matrix is given by

A =   0 0 -1 -1 -1 -1 1 0 0 0 2 1 1 0 0 0 1 0 2 0 0 1 0 0 0 0 1  
which implies that one can reduce the system by 3 variables. The normal Hermite multiplier V and its inverse W are given by In this case the rational section is not as simple as in the previous cases. it is given by hk 2 = k 2 1 , hk 2 = k 1 and h 1 = k 1 , or equivalently by k 1 = h 1 = 1 and h • k 2 = 1.

V =               0 0 0 -1 0 0 0 0 -1 1 1 0 0 1 1 0 0 0 -2 -1 -1 -2 -2 -2 0 -1 -1 0 0 1 2 0 0 0 0 1 1 1 0 0 2 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1               , W =               0 0 -1 -1 -1 -1 1

Conclusion and prospects

In this paper we have showed how a scaling symmetry can be determined and used algorithmically to reduce dynamical systems rationally. We have demonstrated how this in particular applies to the reduction of the number of parameters in models of mathematical biology. Previously we had given a scaling symmetry reduction scheme for polynomial systems [START_REF] Hubert | Rational invariants of scalings from Hermite normal forms[END_REF]. The main tool used is the Hermite normal form of the matrix of exponents along with its unimodular multiplier. All the algorithms in this paper have been implemented in the computer algebra system Maple with the code available from the authors.

There are a number of research topics that emerge from this work. We have used the Hermite normal form and a normalized unimodular multiplier as the basic algorithmic tools for computing scaling symmetries, rational invariants and reductions. However other normal forms and normalizations for the unimodular multiplier can also be appropriate for such computations. It nonetheless remains an open question as to which rank revealing normal form and unimodular multiplier normalization are in fact best for a given application.

Scaling symmetry reductions for more general differential systems are also of interest. In this paper we have treated the simplest case of evolution equations, one with a single independent variable. However evolution equations in terms of partial differential equations are also common in physics and mathematical biology. One can inquire how to obtain an algorithmic parameter reduction technique as explicit as that presented in Section 7 for such situations. A general scheme of scaling symmetry reduction of higher order (partial) differential systems as explicit as found for dynamical system in Section 6 is a challenge.

2

 2

  be a Hermite multiplier of A and W = W u W d its inverse. Then the scaling defined by A has the following properties: (a) The n -r components of g = [z 1 , . . . , z n ] Vn form a generating set of rational invariants; (b) Any rational invariant can be written in terms of the components of g by substituting z = [z 1 , . . . , z n ] by the respective components of g Wd .

Example 4 . 3

 43 Continuing with Example 3.3 where we considered the scaling defined by A = 2 3 we have that the Hermite multiplier of A is

Example 4 . 4 3

 443 Continuing with Example 3.4 where the scaling was defined by the 2 × 5 matrix the column Hermite normal form for A is given by [ H, 0 ] = 3 2 0 0 0 0 1 0 0 0 and the normal Hermite multiplier and its inverse are

Example 4 . 6

 46 In Example 4.3 we considered the scaling on the plane defined by A = 2 3 .

Lemma 4 . 8

 48 If A ∈ Z r×n then the components of x A -y A belong to the ideal generated by the components of x -y in the ring of Laurent polynomials K[x, y, x -1 , y-1 ].

( i )

 i The column Hermite normal form of A is [I r , 0]. (ii) An integer matrix B satisfies B•K = 0 iff there exists an integer matrix M such that B = M •A.

  is a solution of[START_REF] Mansfield | A Practical Guide to the Invariant Calculus[END_REF], for any constants d = (d 1 , . . . , d r ), with no vanishing component. Here W u denotes the first r rows of the inverse W .

7. 2

 2 Verhulst model of logistic growthConsider first the Verhulst model of logistic growth[START_REF] Murray | [END_REF] Section 1.1]

  If (s, k, d, n(t), p(t)) is a solution of this reduced system and (a, b, c) is any triplet of constants then of the original system. The reduced system is actually the dynamics for the invariant variables:(s, k, d) = c = r t, and (n, p) = z = 1

1 , hk 2 h 2 k 2 1 ,

 11 the substitution k = 1 s , h = 1 r , k 1 = 1, h 1 = 1, k 2 = k, h 2 = h, t = t r , x = x r , y = y s . If (s, r, h, x(t), y(t)) is a solution of this reduced system and (a, b, c) is any triplet of constants then , b x (rt ) , c y (rt) is a solution of the original system. The reduced system is actually the dynamics for the invariant variables:(s, r, h) = c = t = k 2 t, and (x, y) = z =

  with a cost of O ∼ n ω+1 d bit operations. Here O ∼ is the same as Big-O but without log factors, ω is the power of fast matrix multiplication and d is the maximal integer exponent of the scaling matrix A.

	Example 2.4 Consider
		A =	8 2 15 9 11 6 0 6 2 3
	which has Hermite normal form [I 2 , 0]. The reduction performed by Maple results in the Hermite
	multiplier
			-49 -1 -57 -13 -28	
			-36 -1 -42 -10 -21	
	V ′ =	 	79	2	92	21	45	 
		 	-36 -1 -42 -9 -21	 
			-36 -1 -42 -10 -20
	while the normal Hermite multiplier is

  r [32, Lemma 4.1, 4.2 and 12.2].

  1 , k 2 , h 2 . The scaling symmetries are those leaving the components of k 1 ty 2 -kk 2 tx -k 2 txy 2 kx + xy 2 , h 1 tx 2 -hh 2 ty -h 2 tx 2 y hy + x 2 y

	October 2012

http://hal.inria.fr/hal-00668882

In particular av = 0 (respectively bv = 0) when u + v / ∈ N n .October 2012

It is actually a differential system of Lie type: the entries of the Maurer-Cartan matrix[START_REF] Hubert | Generation properties of Maurer-Cartan invariants[END_REF] are the coefficients of the Lie algebra basis .

October 2012

This was the case in the many (> 40) models from mathematical biology we examined.

The result then follows by applying [START_REF] Hubert | Rational invariants of scalings from Hermite normal forms[END_REF] to each column of B. Proposition 6.2 Consider a map F : R n → R n that is invariant under the scaling defined by

where none of the components vanish then [x(t), y(t)] = z(t) V i , z(t) Vn is a solution of the dynamical system:

proof: From Lemma 6.1 we have that

The same argument gives equation [START_REF] Huntley | Dimensional Analysis[END_REF]. System ( 16) is the reduced system: it is the dynamical system bearing on the n -r variables which are intrinsically generating invariants of the scaling. System ( 17) is an auxiliary system providing the dynamic system of the moving frame as defined in [START_REF] Fels | Moving coframes. ii. Regularization and theoretical foundations[END_REF], up to isotropy. It is actually a quadrature. For a given solution to the system [START_REF] Hubert | Polynomial Time Nondimensionalisation of Ordinary Differential Equations via their Lie Point Symmetries[END_REF], a solution to [START_REF] Huntley | Dimensional Analysis[END_REF] is obtained by integration:

The coupled system (16 -17) thus lends itself better to solving or to analysis. The next result shows how we can recover the solutions of the original system from the solutions of the reduced system with the help of the auxiliary system.

In order to make the link with [START_REF] Anderson | Exterior differential systems with symmetry[END_REF], one can check that (z -1 ⋆ dz -F (z)dt) • V n forms a basis for the semi-basic forms when considering the exterior differential system z -1 ⋆ dz -F (z)dt. The section σ : y → y Wd would bring the reduced exterior differential system y -1 ⋆ dy -F (y Wd ) • V n dt. Theorem 6.3 Consider a map F : R n → R n that is invariant under the scaling defined by A ∈

where none of the components vanish, then

proof: By Lemma 6.1 we have

we have z(t) Vn = [x(t), y(t)] W •Vn = y(t), and so, by Theorem 4.2, F (y(t) Wd ) = F (z(t)) since F is an invariant. Theorem 6.5 Consider a map F : R × R n → R n that is invariant under the scaling defined by

y(t) and x(t) are solutions of the dynamical systems

where F = [1, F ], having the property that none of their components vanish. If [z 0 (t), z1 (t) . . . ,

is a solution of the dynamical system

The system ( 21) is the reduced system having n + 1 -r variables, which correspond to the generating set of invariants and can be read from V . The change of time s = ln(t) makes it an autonomous system. In addition, ( 22) is a quadrature. If y(t) is a solution to (21) then the complete solution is obtained by integration:

Example 6.6 Consider the dynamical system given by

This dynamical system is invariant under the scaling defined by the matrix A = [ 3 -1 5 ]. The normal Hermite multiplier and its inverse are given by

) and so