Benaych-Georges Florent

¸ois Chapon
email: francois.chapon@upmc.fr

RANDOM RIGHT EIGENVALUES OF GAUSSIAN QUATERNIONIC MATRICES

Keywords: . 2000 Mathematics Subject Classification. 15A52, 60B15. Key words and phrases. Random matrices, quaternions

We consider a random matrix whose entries are independent Gaussian variables taking values in the field of quaternions with variance 1/n. Using logarithmic potential theory, we prove the almost sure convergence, as the dimension n goes to infinity, of the empirical distribution of the right eigenvalues towards some measure supported on the unit ball of the quaternions field. Some comments on more general Gaussian quaternionic random matrix models are also made.

Introduction

Our motivation for studying quaternionic random matrices comes from the following facts. The projection onto the complex plane of the uniform measure on the unit sphere S 3 of R 4 is the uniform measure on the unit disk D(0, 1) of C, also called the circular law. Furthermore, the projection onto the real axis of the uniform measure on D(0, 1) is the semi-circular law on [-1, 1]. The last two measures play a key role in random matrix theory. Indeed, it is well known since Wigner's paper [START_REF] Wigner | On the distribution of the roots of certain symmetric matrices[END_REF] that as the dimension goes to infinity, the empirical distribution of the eigenvalues of a Gaussian Hermitian random matrix converges to the semi-circular law, and it has also been proved that the empirical distribution of the eigenvalues of a complex Gaussian random matrix converges to the circular law (see e.g. the book of Mehta [START_REF] Mehta | Random matrices[END_REF] or the paper of Tao, Vu and Krishnapur [START_REF] Tao | Krishnapur Random matrices: Universality of ESDs and the circular law[END_REF]). Our initial idea, due to Philippe Biane, was to find a random matrix model such that the empirical spectral measure would converge to the uniform measure on the unit sphere S 3 , and thus, in view of the previous observations, to study quaternionic random matrices, the unit sphere of quaternions being naturally identified with the unit sphere S 3 . The hope was then, after defining properly the eigenvalues of quaternionic random matrices, that the empirical spectral distribution of a quaternionic Gaussian matrix will converge to the uniform distribution on the unit sphere of quaternions. We will see that in fact, this is not the case, and we will prove a convergence result for the empirical spectral distribution towards some measure supported by the unit ball of the quaternions field.

The paper is organized as follows. In Section 1, we recall some basic facts on the quaternions field H and on matrices of quaternions. Note that due to the noncommutativity of H, two notions of eigenvalues cohabit, the left and the right ones, and we will only consider here the right eigenvalues. We will see that we can associate to a quaternionic matrix X(n) a complex matrix whose dimension is doubled which enables to study the complex right eigenvalues of X(n). In Section 2, we state the main results of this paper about the convergence of the empirical distribution of right eigenvalues of quaternionic Gaussian random matrices. The last sections and the appendix are devoted to the proofs of the results and some needed computations.

Acknowledgements. Second author would like to thank Philippe Biane, Léonard Gallardo, Emmanuel Lesigne, Thierry Lévy and Alain Rouault for some useful comments.

1. Basic facts on quaternionic matrices 1.1. Quaternions. We begin with a brief recall of basic facts on quaternions (see [START_REF] Zhang | Quaternions and Matrices of Quaternions[END_REF]). Let us denote by H the noncommutative field of quaternions: as a real linear space, H admits a basis denoted by (1, i, j, k) and its multiplicative structure is defined by the fact that 1 is the neutral element,

i 2 = j 2 = k 2 = -1, ij = -ji = k, jk = -kj = i, ki = -ik = j.
For all q = q 0 + q 1 i + q 2 j + q 3 k ∈ H, one defines q * = q 0 -q 1 i -q 2 j -q 3 k, ℜ(q) = q 0 , ℑ(q) = q 1 i+q 2 j+q 3 k. Then one has qq * = q 2 0 +q 2 1 +q 3 2 +q 2 3 (which proves that any non null quaternion is invertible) and we put |q| := √ qq * . It can be proved that for any q, q ′ ∈ H, |qq ′ | = |q||q ′ |. Note that identifying 1 and i with their usual definitions, one has R ⊂ C ⊂ H (an inclusion which is compatible with the algebraic operations).

Two quaternions x, y are said to be similar if there exists a nonzero quaternion q such that x = qyq -1 . Let S(H) denote the group of quaternions with norm one. Note that x, y are said to be similar if and only if for a certain u ∈ S(H), x = uyu * . The following lemma will be important for the study of right eigenvalues of quaternionic matrices. Lemma 1.1 (Lemma 2.1 of [START_REF] Zhang | Quaternions and Matrices of Quaternions[END_REF]). If q = q 0 + q 1 i + q 2 j + q 3 k ∈ H, then q and ℜ(q) + |ℑ(q)|i are similar.

Right eigenvalues of quaternionic matrices. Let

A ∈ M n (H).
Then λ ∈ H is called a right eigenvalue of A if there exists a non zero vector X ∈ H n such that AX = Xλ. If λ is a right eigenvalue of A, we can easily see that qλq -1 is still a right eigenvalue for all q ∈ H \ {0}. So the right spectrum of A is either infinite or contained in R. Since every quaternion is similar to an unique element of C/(z ∼ z), we can first restrict our attention to complex right eigenvalues. Let A 1 , A 2 ∈ M n (C) be such that A = A 1 + A 2 j (such matrices exist and are unique because q 0 + q 1 i + q 2 j + q 3 i = (q 0 + q 1 i) + (q 2 + q 3 i)j). Then for any λ ∈ C and X = Y + Zj, with Y, Z ∈ C n , we have an equivalence between (i) AX = Xλ,

(ii) A 1 A 2 -A 2 A 1 Y -Z = λ Y -Z , (iii) A 1 A 2 -A 2 A 1 Z Y = λ Z Y .
Hence, the right spectrum of A, when restricted to complex numbers, is finite and is given by the 2n eigenvalues of the complex matrix

A ′ := A 1 A 2 -A 2 A 1 ,
which appear in conjugate pairs. The whole set of right eigenvalues of A is the union of the similitary classes of the complex right eigenvalues of A. Note that when A = X(n) is the Gaussian quaternionic matrix introduced below, A ′ is said to be taken in the Ginibre Symplectic Ensemble.

Main results

2.1. Quaternionic random matrix models. Let X(n) be an n×n quaternionic random matrix with independent identically distributed entries, whose distribution is defined by the fact that X(n) 1,1 = q 0 + q 1 i + q 2 j + q 3 k, where q 0 , q 1 , q 2 , q 3 are independent Gaussian variables with mean 0 and variance 1/(4n), so that

E(X(n) i,j ) = 0 and E |X(n) i,j | 2 = 1 n
, for all i, j = 1, . . . , n.

We can associate to X(n) an 2n × 2n complex random matrix Y (n) as seen above in Section 1.2. We will denote by (z n,i ) 2n i=1 the 2n eigenvalues of Y (n), with the convention

z n,n+i = z n,i , for all i = 1, . . . , n,
because the eigenvalues of Y (n) appear in conjugate pairs. The right eigenvalues of X(n) are then the elements of the similarity classes of the z n,i 's, for i = 1, . . . , n. The distribution of the eigenvalues of Y (n) has been calculated by Ginibre [START_REF] Ginibre | Statistical Ensembles of Complex, Quaternion, and Real Matrices[END_REF] and admits the following density with respect to the Lebesgue measure on C n : for z = (z 1 , . . . , z n ) ∈ C n ,

P n (z) = 1 c n exp -2n n i=1 |z i | 2 1≤i<j≤n |z i -z j | 2 |z i -zj | 2 n i=1 |z i -zi | 2 ,
where c n is a normalization constant. If we write 1≤i =j≤2n

log |z i -z j | = 2 1≤i =j≤n log |z i -z j ||z i -zj | + 2 i=1,...,n log |z i -zi |,
then the density P n can be rewritten as

P n (z) = 1 c n exp   - 1 2 2n 2n i=1 |z i | 2 + 1≤i =j≤2n log |z i -z j | -1 + 2n i=1 log |z i -zi | -1   .
We will embed our considerations in a more general setting, since the density P n can be generalized in the following way. Let V : C → [0, +∞] be a continuous non-negative function, conjugate invariant, and such that there is a constant δ > 0 such that V (z) ≥ (δ +1) log(|z| 2 +1), for |z| large enough. We suppose that the set E 0 = {z ∈ C | V (z) < ∞} has positive capacity, i.e. that there exists at least one probability measure µ with compact support contained in E 0 such that log |x -y| -1 dµ(x)dµ(y) < ∞ (this notion will become apparent in Section 3). For z = (z 1 , . . . , z n ) ∈ C n , set

K n (z) := 1≤i =j≤2n k(z i , z j ) with k(x, y) := log |x-y| -1 + 1 2 (V (x)+V (y)).
Then we have

K n (z) = 1≤i =j≤2n log |z i -z j | -1 + 1≤i =j≤2n V (z i ) = 1≤i =j≤2n log |z i -z j | -1 + (2n -1) i=1,...,2n
V (z i ).

Define the probability density P V n on C n by,

P V n (z) = 1 c V n exp - 1 2 K n (z) + 2n i=1 V (z i ) + 2n i=1 log |z i -zi | -1 ,
where c V n is the normalization constant. One recovers P n for V (x) = |x| 2 . Note also that the matrices having the structure

A 1 A 2 -A 2 A 1 are non nor- mal, so when V (z) is not of the form V (z) = a 1 z 2 + a 2 z2 + a 3 zz, the density P V
n is not the density of the complex eigenvalues of a quaternionic random matrix with distribution ∝ exp(Trace(b

1 A 2 + b 2 A * 2 + b 3 AA * ))dA.
2.2. Convergence of the empirical measure associated to a P V ndistributed sample. The following theorem is proved for any potential V as above.

Theorem 2.1. Let z (n) = (z n,1 , . . . , z n,n ) ∈ C n be distributed according to P V n . Then, the empirical distribution

1 2n i=1 δ z n,i
converges almost surely, as n goes to infinity, towards a compactly supported probability measure µ V , which is the unique minimum, on the set of probability measures on C, of the weighted logarithmic energy, defined by the formula

I(µ) := log |x -y| -1 dµ(x)dµ(y) + V (z)dµ(z),
for µ a probability measure on C.

Taking V (z) = |z| 2 in the last theorem and identifying µ V , we get the following corollary about the convergence of the empirical distribution of the complex right eigenvalues of the Gaussian random quaternionic matrix X(n) introduced in Section 2.1.

Corollary 2.2. Let z n,1 , . . . , z n,2n be the complex right eigenvalues of X(n).

As n tends to infinity, the probability measure

1 2n 2n i=1 δ z n,i
tends almost surely to the uniform law µ on the unit disk of the complex plane.

2.3. Limits of uniformly chosen right eigenvalues of quaternionic random matrices. Theorem 2.3. Let X(n) be as defined in Section 2.1. Let C n,1 , . . . , C n,n be the similarity classes of its right spectrum, and c n,1 , . . . , c n,n be elements taken independently at random, uniformly in respectively C n,1 , . . . , C n,n . Then as n → ∞, the empirical probability measure

1 n n i=1 δ c n,i
tends almost surely to the law on H with density with respect to the Lebesgue measure

(1) ρ(q) = 1 2π 2 |ℑq| 2 ½ |q|≤1 . Remark 2.4 (Alternative formulations of Theorem 2.3). By Lemma 1.1, we have C n,i = {q ∈ H, ℜ(q) = ℜ(c n,i ), |ℑ(q)| = |ℑ(c n,i )|}, hence C n,i is a sphere of an affine three-dimensional subspace, with radius r n,i := |ℑ(c n,i )|.
Let us denote by S C n,i the uniform measure on C n,i , with a normalization inherited from the euclidian structure of H, i.e. with total mass 4πr 2 n,i and set V n := n i=1 4πr 2 n,i to be the total mass of the right spectrum of X(n). It can easily be deduced from the proof of Theorem 2.3 that this theorem is equivalent to its following alternative version: as n goes to infinity, both random probability measures

(2) 1 V n n i=1 4πr 2 n,i δ c n,i and
1 V n n i=1 S C n,i
converge weakly to the uniform probability measure on the unit ball of H. Note that both probability measures of (2) correspond to the picking of random right eigenvalues of X(n) at random, with probabilities proportional to the masses of their similarity classes. The second probability measure of (2) is, in a certain sense, the exact empirical distribution of the right eigenvalues of X(n). As a consequence, an alternative formulation of Theorem 2.3 is the following one: the empirical distribution on the right spectrum of X(n) converges to the uniform probability measure on the unit euclidian ball of H.

We see from Theorem 2.3 that the empirical spectral distribution of X(n) does not tend to the uniform measure on the unit sphere S(H) of H. One can ask if it is possible to find a quaternionic random matrix model for which the empirical distribution of right eigenvalues would converge to the uniform measure on S(H). We next show that it is not possible if one restricts to quadratic potentials, i.e. potentials of the form V (z) = a 1 z 2 + a 2 z2 + a 3 zz corresponding to a more general Gaussian quaternionic random matrix model. Theorem 2.5. There is no quadratic potential V such that for a P V ndistributed random vector (z n,1 , . . . , z n,2n ) and some independent u i 's uniformly distributed on S(H), the random measure 1 2n 2n i=1 δ u i z n,i u * i converges to the uniform measure of S(H).

Note that it remains open whether there are some more general quaternionic random matrix models whose spectral empirical distribution converges towards the uniform distribution.

Proof of Theorem 2.1

The proof is quite classical. The arguments are close to the ones of [START_REF] Ben Arous | Guionnet Large deviations for Wigner's law and Voiculescu's non-commutative entropy[END_REF][START_REF] Ben Arous | Zeitouni Large deviations from the circular law[END_REF][START_REF] Deift | Orthogonal polynomials and random matrices: a Riemann-Hilbert approach[END_REF][START_REF] Johansson | On fluctuations of eigenvalues of random Hermitian matrices[END_REF][START_REF] Anderson | An Introduction to Random Matrices[END_REF] and use logarithmic potential theory.

Firstly, the fact that the functional I admits a minimum achieved at a unique probability measure µ V , which is compactly supported, is the statement of Theorem 1.3 p. 27 of [START_REF] Saff | Logarithmic Potentials with External Fields[END_REF]. This measure is called the equilibrium measure of V . Let us denote by E V the minimum of I, i.e.

E V = I(µ V ). For x ∈ C, let H(x) = V (x) -log(|x| 2 + 1). We remark that k(x, x ′ ) ≥ H(x)+H(x ′ ) 2 , for all x, x ′ ∈ C, since |x -x ′ | 2 ≤ (|x| 2 + 1)(|x ′ | 2 + 1)
. So, k is bounded from below. Let l ≥ 0. For µ a probability measure on C, let us define

k l = k ∧ l, I l (µ) = k l (x, y)dµ(x)dµ(y) and K l n (z) = 1≤i =j≤2n k l (z i , z j ).
Since k l is continuous almost everywhere, by monotone convergence, I l converges to I as l goes to infinity. Notation. For z = (z 1 , . . . , z n ) ∈ C n , we will denote by µ z the empirical distribution of z 1 , . . . , z 2n (with our convention that z n+i = zi , for i = 1, . . . , n), i.e.

µ z := 1 2n 2n i=1 δ z i = 1 2n n i=1 (δ z i + δ zi ).
An immediate calculation gives

(3) I l (µ z ) = 1 4n 2 K l n (z) + l 2n .
The following two facts will be useful for the proof of the convergence of the empirical distribution.

Lemma 3.1.

(i) For all n, consider z (n) ∈ C n such that the sequence

1 4n 2 K n (z (n) ) is bounded. Then the sequence µ z (n) is tight. (ii) Let µ n
be a tight sequence of probability measures on C such that for all l, lim sup

n I l (µ n ) ≤ E V .
Then µ n converge weakly to µ V .

Proof. (i) follows from the facts that H(x) → ∞ as |x| → ∞ and k(x, y) ≥ H(x)+H(y) 2

. (ii) Let σ be an accumulation point of µ n . The functional I l is continuous for the weak convergence because k l is bounded and continuous a.e., so I l (σ) ≤ E V by hypothesis. Letting l → ∞, we get I(σ) ≤ E V . By unicity of the equilibrium measure, the result follows.

From this lemma and Equation (3), we deduce the following proposition.

Proposition 3.2. Let, for all n, x (n) ∈ C n such that lim sup n 1 4n 2 K n (x (n) ) ≤ E V .
Then µ x (n) converges weakly to µ V as n goes to infinity.

We shall now prove a concentration result of 1 4n 2 K n (z), under the distribution P V n , which is the analogue of the same result in the Hermitian case. Firstly, the following lemma gives some estimate on the normalization constant c V n . The proof follows exactly the lines of the analogue result for the Hermitian case, so we refer to [START_REF] Deift | Orthogonal polynomials and random matrices: a Riemann-Hilbert approach[END_REF] or [START_REF] Johansson | On fluctuations of eigenvalues of random Hermitian matrices[END_REF] for the details.

Lemma 3.3. As n goes to infinity, lim sup 1 2n 2 log 1 c V n ≤ E V . The concentration of 1 4n 2 K n (z (n)
) around E V is the content of the next proposition.

Proposition 3.4. Let z (n) be a random vector of C n having density P V n . Then, for all 0 < ε < η, for n large enough,

P 1 4n 2 K n (z (n) ) > E V + η ≤ e -2εn 2 .
Proof.

Set A n := {x ∈ C n 1 4n 2 K n (x) > E V + η}. We have, P z (n) ∈ A n ≤ 1 c V n e -2n 2 (E V +η) e -1 2 2n i=1 V (z i )+ 2n i=1 log |z i -z i | -1 dz 1 • • • dz n = 1 c V n e -2n 2 (E V +η) e -V (x)-log |x-x| -1 dx n
Now, taking the logarithm of the above inequality, we obtain 1 2n

2 log P z (n) ∈ A n ≤ 1 2n 2 log 1 c V n -E V -η + 1 2n log(a),
where a = C e -V (x) |x -x|dx is a finite constant by the hypothesis V (x) ≥ (1 + δ) log(|x| 2 + 1) for |x| large enough. Now, taking the lim sup and using the estimate of c V n given by Lemma 3.3, we obtain lim sup

n 1 2n 2 log P z (n) ∈ A n ≤ E V -E V -η < -ε, so the result follows.
Proof of Theorem 2.1. By Proposition 3.4 and Borel-Cantelli Lemma, we have that almost surely, for all η > 0, and n large enough,

1 4n 2 K n (z (n) ) ≤ E V + η. Hence, almost surely lim sup n 1 4n 2 K n (z (n) ) ≤ E V . By Proposition 3.2, the almost surely convergence of µ z (n) follows. 4. Proof of Corollary 2.2: identification of µ V for V (z) = |z| 2
For σ a probability measure on C and x ∈ C, let

U σ (x) := log |x -y| -1 dσ(y),
be the logarithmic potential of some measure σ ∈ M(C). The equilibrium measure µ V can be characterized by the following theorem, see Remark 1.5 p. 28 and Theorem 3.3 p. 44 of [START_REF] Saff | Logarithmic Potentials with External Fields[END_REF].

Theorem 4.1. Let σ ∈ M(C), be a compactly supported probability measure on C such that I(σ) < ∞. Then we have σ = µ V if and only if there exists a constant l such that

(1) 2U σ (x) + V (x) = l, µ V -a.e. on the support of σ (2) 2U σ (x) + V (x) ≥ l, µ V -a.e.

Let us now apply this theorem to find out the equilibrium measure of the quadratic potential V (z) = |z| 2 is the uniform measure µ on D(0, 1). We have to calculate the logarithmic potential of µ.

Firstly, the mean-value property of harmonic functions implies the following useful classical lemma. A straightforward computation using the above lemma allows one to compute the logarithmic potential of µ given in the next proposition. Proposition 4.3. Let µ be the uniform measure on the unit disk D(0, 1). Let U µ be the logarithmic potential of µ, i.e. U µ (x) = log |x -y| -1 µ(dy) for x ∈ C. Then,

U µ (x) = 1 2 (1 -|x| 2 ), for |x| ≤ 1, -log |x|, for |x| > 1.
Now, as a direct consequence of Theorem 4.1, the equilibrium measure of the weighted logarithmic energy I with potential V (z) = |z| 2 is given by the uniform measure µ on the unit disk of C.

Proof of Theorem 2.3

Before providing a formal proof of Theorem 2.3, let us outline this proof. We will at first consider the random probability measure (4)

1

n n i=1 δ (z n,i ,u i ) ,
where the z n,i 's are the complex right eigenvalues of X(n) with positive imaginary part and the u i 's are i.i.d. variables, independent of the z n,i 's, and whose distribution U S(H) is the uniform law on the sphere S(H). We know, by Corollary 2.2, that 1 n n i=1 δ z n,i converges towards U D + C (0,1) , the uniform distribution on the intersection of the unit circle with the upper half-plane. We also know, by the Law of Large Numbers, that 1 n n i=1 δ u i converges towards U S(H) . Hence by independence and exchangeability of the samples (z n,1 , . . . , z n,n ) and (u 1 , . . . , u n ), the measure of (4) will converge to U D + C (0,1) ⊗ U S(H) (this is the content of Lemma 5.1 below, whose statement seems quite intuitive and well-known, but for which we did not find any reference, hence provide a proof). To conclude the proof, we next have to prove that the push-forward of U D + C (0,1) ⊗ U S(H) by the map (z, u) → uzu * is the measure of (1). This last step relies on the identification of the orbits of the action of S(H) by conjugation on H, which is due to Brenner in [START_REF] Brenner | Matrices of quaternions[END_REF]. A kind of probabilistic version of Brenner's result is given in Proposition 5.2 below.

So first, we state the preliminary results that we need, the first of which is a kind of multidimensional and almost sure reformulation of [4, Th. 1.8, Part 1].

Lemma 5.1. Let p, q be two positive integers and µ, ν be two probability measures on respectively R p , R q . Let, for each n,

x n,1 , . . . , x n,n , y n,1 , . . . , y n,n be random variables, the x n,i 's taking values in R p and the y n,j 's taking values in R q such that (i) for each n, {x n,1 , . . . , x n,n } and {y n,1 , . . . , y n,n } are independent sets of random variables, (ii) for each n, the laws of the random vectors (x n,1 , . . . , x n,n ) and (y n,1 , . . . , y n,n ) are invariant under the actions of the symetric group S n , (iii) the random probability measures

µ n := 1 n n i=1 δ x n,i , ν n := 1 n n i=1 δ y n,i
converge almost surely respectively to µ, ν as n tends to infinity.

Then the random probability measure

ρ n := 1 n n i=1 δ (x n,i ,y n,i )
converges almost surely to µ ⊗ ν as n tends to infinity.

Proof. It suffices to prove that for any compactly supported real valued continuous function f defined on R p+q , f (t)dρ n (t) tends almost surely to f (t)dµ ⊗ ν(t) as n tends to infinity. By Stone-Weierstrass theorem, it suffices to prove it when f = g ⊗ h, with g, h compactly supported real valued continuous functions defined respectively on R p , R q . Moreover, since by (iii), it is obvious when g or h is a constant function, one can suppose that g(t)dµ(t) = h(t)dν(t) = 0.

Thus we have to prove that 1 n n i=1 g(x n,i )h(y n,i ) tends almost surely to 0. Let us define, for all n, for all i = 1, . . . , n,

a n,i = g(x n,i ) - 1 n n j=1 g(x n,j ), b n,i = h(y n,i ) - 1 n n j=1
h(y n,j ).

Since 1 n n j=1 g(x n,j ) and 1 n n j=1 h(y n,j ) converge almost surely to zero and the functions g, h are bounded, it suffices to prove that 1 n n i=1 a n,i b n,i converges almost surely to zero. Note that the advantage of working with the a n,i 's and the b n,i 's instead of working with the g(x n,i )'s and the h(y n,i )'s is that for all n, one has almost surely ( 5)

n i=1 a n,i = n i=1 b n,i = 0.
We claim that the fourth moment of n i=1 a n,i b n,i is O(n 2 ). Let us prove it. We have

(6) E   n i=1 a n,i b n,i 4   = 1≤i,j,k,l≤n E(a n,i a n,j a n,k a n,l )E(b n,i b n,j b n,k b n,l ).
Note that by the hypothesis (ii), each term in the sum of the right hand side of (6) only depends on the partition of {1, 2, 3, 4} defined by (i, j, k, l): let us define α n,1,1,1,1 = E(a n,i a n,j a n,k a n,l ) for i, j, k, l pairwise distinct,

α n,2,1,1 = E(a 2 n,i a n,k a n,l ) for i, k, l pairwise distinct, α n,2,2 = E(a 2 n,i a 2 n,k ) for i = k, α n,3,1 = E(a 3
n,i a n,l ) for i = l, α n,4 = E(a 4 n,i ) for i ∈ {1, . . . , n} and let us define the β n,• 's in the same way with the b n,i 's instead of the a n,i 's. Then by the hypothesis (ii), with the notation

A k n = n(n -1) • • • (n -k + 1) for all k, E   n i=1 a n,i b n,i 4   = A 4 n α n,1,1,1,1 β n,1,1,1,1 + 6A 3 n α n,2,1,1 β n,2,1,1 + 4A 2 n (α n,2,2 β n,2,2 + α n,3,1 β n,3,1 ) + nα n,4 β n,4
. Note that since g and h are bounded, the α n,• 's and the β n,• 's are all O(1). Thus to prove the claim, it suffices to prove that α n,1,1,1,1 = O(n -1 ), α n,2,1,1 = O(n -1 ) and that the same holds for the β's. We shall only treat the case of the α's. Passing (5) to the fourth power and taking the expectation, we get

A 4 n α n,1,1,1,1 + 6A 3 n α n,2,1,1 + 4A 2 n (α n,2,2 + α n,3,1 ) + nα n,4 = 0,
from which it follows that α n,1,1,1,1 = O(n -1 ). In the same way, it follows from (5) that i,j,k pairwise distinct

a 2 n,i a n,j a n,k = i =j a 2 n,i a n,j (-a n,i -a n,j ),
which gets, by integration,

A 3 n α n,2,1,1 = -A 2 n (α n,3,1 +α n,2,2 ). Hence α n,2,1,1 = O(n -1 ).
Thus we have proved that the fourth moment of n i=1 a n,i b n,i is O(n 2 ). By Markov's inequality and Borel-Cantelli's lemma, 1 n n i=1 a n,i b n,i tends almost surely to zero. Proposition 5.2. Fix z 0 ∈ H and let u be a Haar distributed random element of S(H). Then uz 0 u * has the law of ℜ(z 0 ) + |ℑ(z 0 )|S, for S uniformly distributed on the unit sphere of H 0 := {q ∈ H ; ℜ(q) = 0}.

To prove the proposition, we shall use the following lemma.

Lemma 5.3. Let E be a metric space, µ a probability measure on E, and G a compact group such that G acts transitively on E and preserves µ. Let x ∈ E. Then the push-forward of the Haar measure on G by the map g → g • x coincides with µ.

Proof. Let f be a bounded measurable function on E and let µ G denote the Haar measure on G. For all y ∈ E there exists g y ∈ G such that x = g y •y. As a consequence, by right-invariance of µ G , G f (g • y)dµ G (g) does not depend on y.

So G f (g • x)dµ G (g) = E G f (g • y)dµ G (g)dµ(y) = G E f (g • y)dµ(y)dµ G (g) = G E f (y)dµ(y)dµ G (g) = E f (y)dµ(y),
which proves that g • x is distributed according to µ.

Proof of Proposition 5.2. Let us endow H with its canonical Euclidian structure (for which (1, i, j, k) is an orthogonal basis). Then the action of the group of quaternions with norm one on H defined by u•z := uzu * is linear, norm preserving (since the norm is multiplicative on H) stabilizes R and thus also the orthogonal of R in H, namely the space of quaternions with null real part. Moreover, by Brenner's Theorem (see e.g. [13, Th. 2.2]), the action induced on the unit sphere of this subspace is transitive, thus the proposition follows from the previous lemma.

Proof of Theorem 2.3. Let, for each n, z n,1 , . . . , z n,2n be the complex right eigenvalues of X(n), ordered in such a way that for all i = 1, . . . , n, z n,n+i = z n,i and the imaginary part of z n,i is positive and that the joint law of (z n,1 , . . . , z n,n ) is invariant under the action of the symmetric group S n . Then the conjugation classes of its right spectrum are C n,1 := {uz n,1 u * ; u ∈ H, |u| = 1}, . . . , C n,n := {uz n,n u * ; u ∈ H, |u| = 1}, and c n,1 , . . . , c n,n can be defined by c n,1 = u 1 z n,1 u * 1 , . . . , c n,n = u n z n,n u * n for (u i ) i≥1 a family of independent random variables with uniform distribution on the group of the quaternions with norm one, such that {z n,1 , . . . , z n,n } and {u i ; i ≥ 1} are independent.

Note that the random probability measure converges almost surely, as n tends to infinity, to the push-forward of the law U D + C (0,1) ⊗ U S(H) by the map (z, u) → uzu * . To prove that this law, that we shall denote by L, has a density given by [START_REF] Anderson | An Introduction to Random Matrices[END_REF], it suffices to note that by Proposition 5.2, for any Borel bounded function f on H,

f (t)dL(t) = 2 π +∞ x=-∞ +∞ y=0 s∈S(H 0 ) 1 x 2 +y 2 ≤1 f (x + ys)dsdydx,
where S(H 0 ) denotes the unit sphere of the subspace H 0 of H of quaternions with null real part and ds denotes the uniform probability measure on this sphere. By spherical integration on the three-dimensional space of quaternion with null real part, we have

f (t)dL(t) = 1 2π 2 +∞ x=-∞ +∞ y=0 s∈S(H 0 ) 1 x 2 +y 2 ≤1 y -2 f (x + ys)4πy 2 dsdydx = 1 2π 2 (x 1 ,...,x 4 )∈R 4 1 x 2 1 +x 2 2 +x 2 3 +x 2 4 ≤1 (x 2 2 + x 3 3 + x 2 4 ) -1 ×f (x 1 + x 2 i + x 3 j + x 4 k)dx 1 dx 2 dx 3 dx 4 ,
which proves the theorem.

6. Proof of Theorem 2.5

Recall that U S(H) denotes the uniform measure on the sphere S(H). Theorem 2.5 will be proved as follows. We first identify the limit measure ν of the empirical distribution 1 2n 2n i=1 δ z n,i such that the measure 1 2n 2n i=1 δ u i z n,i u * i converges to U S(H) for (u i ) i≥1 a sequence of i.i.d. U S(H) -distributed random variables independent of the z n,i 's. Using the characterization of the equilibrium measure given by Theorem 4.1, we next show by contradiction that there is no quadratic potential V such that ν is the equilibrium measure of V . It follows directly that there is no V such that for (z n,1 , . . . , z n,n ) distributed according to P V n , 1 2n 2n i=1 δ z n,i tends to ν.

Claim: for any sequence (z n,1 , . . . , z n,2n ) ∈ C 2n such that z n,n+i = z n,i and which is independent of the u j 's, we have

1 2n 2n i=1 δ u i z n,i u * i -→ n→∞ U S(H) a.s. ⇐⇒ 1 2n 2n i=1 δ z n,i -→ n→∞ dν(z) := 2|ℑ(z)| 2 dσ(z) a.s.,
where σ is the Haar probability measure on the sphere S 1 . Let us prove this claim. By Lemma 5.1, it suffices to prove that if t is a complex random variable distributed according to dν(z) = 2|ℑ(z)| 2 dσ(z) independent of a S(H)-uniformly distributed variable u, utu * is uniformly distributed on S(H).

* (d) = ℜ(t) + 1 -ℜ(t) 2 S.
Of course, the same applies to u: one also has

u (d) = ℜ(u) + 1 -ℜ(u) 2 S,
for S uniformly distributed on the unit sphere of H 0 = {q ∈ H ; ℜ(q) = 0} and is independent of u. So to prove the claim, it suffices to prove that

ℜ(t) (d) = ℜ(u),
which can easily be verified (the common distribution of ℜ(t) and ℜ(u) is the semi-circular law on [-1, 1]). The claim is proved. The logarithmic potential of ν is given, for x ∈ C by

U ν (x) = S 1 log |x-z| -1 dν(z) = -1 4 (ℜ(x) 2 -ℑ(x) 2 ), if |x| ≤ 1, -1 4|x| 4 (ℜ(x) 2 -ℑ(x) 2 ) -log |x|, if |x| > 1.
The detailed calculation of this fact is given in the appendix.

Let z = x+iy ∈ C. Suppose by contradiction that there exists a quadratic potential V (z) = a 1 z 2 + a 2 z2 + a 3 zz, such that ν is the equilibrium measure of V . Since V must be real valued, we have a 1 = a+ib = ā2 , and a 3 = c ∈ R. So V can be written V (z) = x 2 (a+c)+y 2 (-a+c)+xy(-2b+c), for z = x+iy. By Theorem 4.1, 2U ν + V must be constant on the support of ν. So, we get, for |z| = 1, 2U ν (z) + V (z) = (a + c -1

2 )x 2 + (-a + c + 1 2 )y 2 + xy(-2b + c) = constant. This implies that a = 1 2 , and c = 2b > 0. Hence,

2U ν (z) + V (z) = c|z| 2 = c on |z| = 1.
But, on |z| < 1, we have 2U ν (z) + V (z) < c, which refutes the condition (ii) of Theorem 4.1. So, we obtain a contradiction, and there does not exist a quadratic potential V such that ν is the equilibrium measure of V .

Appendix

In this appendix, we give the calculation of the logarithmic potential of the measure dν(z) = 2|ℑ(z)| 2 dσ(z) used in the proof of Theorem 2.5 (so dσ is the Haar probability measure on the unit sphere S 1 ). We begin with two lemmas. which allows to conclude.

To determine the logarithmic potential for points belonging to the unit circle, we will need the following lemma, whose proof is straightforward using change of variables and mean value property of harmonic functions. By the two previous lemmas, The logarithmic potential of the measure dν(z) = 2|ℑz| 2 dσ(z) on S 1 can now be determined. The last integral is zero by parity, so the result follows by Lemma 4.2 and the previous calculation [START_REF] Ginibre | Statistical Ensembles of Complex, Quaternion, and Real Matrices[END_REF].

Lemma 4 . 2 .

 42 For all x ∈ C, π -π log |x -re iθ |dθ = 2π log r, if |x| ≤ r, 2π log |x|, if |x| > r.

By Proposition 5 . 2 ,

 52 for such random variables t and u, utu * (d) = ℜ(utu * ) + |ℑ(utu * )|S, for S uniformly distributed on the unit sphere of H 0 = {q ∈ H ; ℜ(q) = 0} and independent of utu * . Thus since |utu * | = 1, we have |ℑ(utu * )| = 1 -ℜ(utu * ) 2 . Moreover, ℜ(utu * ) = ℜ(t) (by [13, Th. 2.1.6] and because t ∈ C), so that utu

Lemma 7 . 1 . 1 4r 2 + 2 π 2 .1-a 2 a 2 1 = 2π 1 -r 2 ,r 2 - 1 , 2 = 1 1 1 r 2 -1 π( 1 r 2 + 1 )

 7112222211221211221 We have, for r ≥ 0, log r, if r > 1.Proof. Let I = π -π log |r-e iθ | sin 2 (θ)dθ = 1 -π log(r 2 +1-2r cos θ) sin 2 (θ)dθ. A first integration by parts givesI = -r 2 + 1 4r π -π log(r 2 + 1 -2r cos θ) cos θdθ |r -e iθ |dθ = 0, if r < 1, 4π log r, if r > 1.Now let us calculate A. Integration by parts gives,Let P a (θ) = +1-2a cos θ be the Poisson kernel, for 0 ≤ a < 1. Recall that 1 2ππ -π P a (t -θ)e inθ dθ = a |n| e int , for n ∈ Z.Thus, we obtainA for r < 1,2π for r > 1,the second case being obtained by replacing r by 1 r . In the same way, A -r 2 π(r 2 + 1), for r < 1, , for r > 1,

Lemma 7 . 2 .

 72 We have π -π log |1 -e iθ | 1 π sin 2 θdθ = 1 4 .

1 4r 2 +

 12 log r, if r > 1.

Proposition 7 . 3 . 1 log 1 logπ sin 2 θdθ cos 2 γ + π -π log |r -e iθ | 1 π cos 2 θdθ sin 2 γ + π -π log |r -e iθ | 1 π

 73111 Let dν(z) = 2|ℑz| 2 dσ(z). The logarithmic potential of ν is given, for x ∈ C, byU ν (x) = S 1 log |x-z| -1 dν(z) = -1 4 (ℜ(x) 2 -ℑ(x) 2 ), if |x| ≤ 1, -1 4|x| 4 (ℜ(x) 2 -ℑ(x) 2 ) -log |x| 2 , if |x| > 1. Proof. Let x = re iγ ∈ C. S |re iγ -z|dν(z) = log |r -z| 1 π |ℑ(ze iγ )| 2 dσ(z),since dσ is translation-invariant. It follows thatS |re iγ -z|dν(z) = π -πlog |r -e iθ | 1 sin θ cos θdθ2 sin γ cos γ.

  z n,i by the map z ∈ C → ℜ(z) + i|ℑ(z)|. Thus by Corollary 2.2, it converges almost surely, as n tends to infinity, to the push-forward of the uniform law on the unit circle of the complex plane by this map, i.e. to the uniform law on the intersection of the unit circle with the upper half-plane, denoted by U D + C (0,1) . Moreover, by the strong law of large numbers, 1 n converges almost surely, as n tends to infinity, to the uniform law on the group of the quaternions with norm one, denoted by U S(H) . So by Lemma 5.1, as n tends to infinity, the random probability measure

	of 1 2n	2n i=1 δ n	1 n	n i=1 δ z n,i is the push-forward
				δ u i
			i=1
		1 n	n i=1	δ (z n,i ,u i )
	converges almost surely to U D + C (0,1) ⊗ U S(H) . Thus the random probability measure n 1 i=1 n δ c n,i

This work was partially supported by the Agence Nationale de la Recherche grant ANR-08-BLAN-0311-03.


Julien B Énab Ès
email: julien.benabes@irccyn.ec-nantes.fr

Emilie Poirson
email: emilie.poirson@irccyn.ec-nantes.fr

Professor Fouad Bennis
email: fouad.bennis@irccyn.ec-nantes.fr

Yannick Ravaut
email: yannick.ravaut@fr.thalesgroup.com

INTERACTIVE MODULAR OPTIMIZATION STRATEGY FOR LAYOUT PROBLEMS

Layout design optimization has a significant impact in the design and use of many engineering products and systems. Realworld layout problems are usually considered as complex problems because of the geometry of components, the problem density and the great number of designer's requirements. Solving these optimization problems is a hard and time consuming task. This paper proposes an interactive modular optimization strategy which allows the designer to find optimal solutions in a short period of calculation time. This generic strategy is based on a genetic algorithm, combined with specific optimization modules. These modules improve the global performances of the algorithm. This approach is adapted to multi-objective optimization problems and interactivity between the designer and the optimization process is used to make a final choice among design alternatives. This optimization strategy is tested on a real-world application which deals with the search of an optimal spatial arrangement of a shelter.

INTRODUCTION

Layout problem is inherently a multidisciplinary task [START_REF] Giassi | Multidisciplinary design optimisation and robust design approaches applied to concurrent design[END_REF]. It covers all the aspects of the product design life cycle from the conceptual to the detailed stage and makes necessary the collaboration between experts of technical and economical disciplines. Layout problems are usually defined as optimization problems and in layout design literature, one finds some different definitions of layout optimization problems [START_REF] Cagan | A survey of computational approaches to the three-dimensional layout problems[END_REF][START_REF] Yi | Vehicle configuration design with a packing genetic algorithm[END_REF]. However, the key idea is always the same: given a set of free form components and an available space, a layout problem consists of finding the best arrangement (location and orientation) of components satisfying geometrical and functional constraints and achieving design objectives. This generic definition can be adapted to all real-world applications. For example, Drira et al. [START_REF] Drira | Facility layout problems: A survey[END_REF] and Wäscher et al. [START_REF] Wäscher | An improved typology of cutting and packing problems[END_REF] have adapted the definition of a layout problem to their respective research domain i.e. facility layout design and cutting and packing problems.

A global layout optimization process can be divided in three main steps : the description of the problem, the formulation of the problem and the optimization strategy. The problem description defines the dimension of the layout problem and identifies the layout components, meaning the container and the components which have to be placed into the container. Then, this description and all the designer's requirements have to be translated into design variables, constraints and objectives in order to change the layout problem into an optimization problem.

This paper focuses on the third step, the optimization strategy, which deals with the search of optimal designs with respect all the designer's requirements. In fact, layout problems are generally considered as non-linear and NP-hard optimization problems. Problems are intrinsically harder than those which can be solved by a non-deterministic Turing machine in polynomial time. One finds multiple single or multi-objective approaches to solve layout optimization problems in two or three dimensions [START_REF] Cagan | A survey of computational approaches to the three-dimensional layout problems[END_REF]. Traditional gradient-based approaches can be used for simple layout problems. For more complex real-world applications, some stochastic algorithms are required to avoid local optima. For example, some optimization strategies use genetic algorithms [START_REF] Yi | Vehicle configuration design with a packing genetic algorithm[END_REF], simulated-annealing algorithms [START_REF] Szykman | Constrained threedimensional component layout using simulated annealing[END_REF] or extended pattern search algorithms [START_REF] Su | An extended pattern search algorithm for threedimensional component layout[END_REF]. Most search algorithms are developed for a specific problem and they provide an effective optimization strategy for it. However, they are not generic and can not be adapted to a lot of layout problems. Some of recent studies deal with the search of efficient generic algorithms for solving layout problems. Jacquenot et al. propose in [START_REF] Jacquenot | 2d multi-objective placement algorithm for free-form components[END_REF] an hybrid algorithm based on a genetic algorithm coupled with a separation algorithm. A variant of this approach is also presented in [START_REF] Bénabès | Interactive optimization strategies for layout problems[END_REF].

In general, the development of an engineering object is considered as a single process involving multi-criteria identification of the mathematical model followed by multi-criteria optimization of the object design on the basis of this mathematical model. The direct participation of the designer in the construction of the feasible design and non-formal analysis are the essential stages of the search for the optimal design. For solving the design problem, the designer almost always has to correct either the mathematical model, the dimension of the vectors of design variables and criteria, the design variable ranges, and so on. We can find in [START_REF] Michalek | Interactive design optimization of architectural layouts[END_REF] a significant contribution to this concept applied to the design optimization of architectural layouts. Moreover, interactivity with designer can be used to insert qualitative fitness or user perceptions in the design process [START_REF] Poirson | Integration of user perceptions in the design process: application to musical instrument optimization[END_REF]. In layout design, Brintrup et al. have already developed an interactive genetic algorithm based framework for handling qualitative criteria in design optimization [START_REF] Brintrup | An interactive genetic algorithm-based framework for handling qualitative criteria in design optimization[END_REF]. Also, the designer can interact with the optimization process in order to make a final choice on the alternatives proposed by the optimization algorithm. Interactive decision making environments are necessary to make this final choice [START_REF] Balling | Design by shopping: A new paradigm[END_REF][START_REF] Stump | Design space visualization and its application to a design by shopping paradigm[END_REF] Actually, this paper proposes an interactive modular optimization strategy which allows the designer to solve complex and multi-objective layout optimization problems. The modular approach is based on a genetic algorithm and uses specific optimization modules in order to help the optimization algorithm to find more design alternatives in a short period of calculation time. In this paper, a multi-objective optimization approach is used. It means that the strategy, proposed in this paper, provides some interactive tools to allow the designer to make a final choice on design alternatives. The designer can interact with a solution in order to take into account his personal judgment in the choice of an optimal design. This optimization approach is tested on a real-world layout problem. This problem deals with the optimal spatial arrangement of components inside a shelter. This paper is organized as follows: the section 2 presents the real-world application studied in this paper. It describes in particular the description and the formulation of the layout problem. The section 3 is dedicated to the modular optimization strategy. The different algorithms which result from this modular approach are compared on the layout problem of the shelter. Then, the following section describes the tools, provided by the optimization strategy proposed in this paper, which allow the designer to make a final choice on optimal design alternatives. Actually, the last section concludes this study.

LAYOUT PROBLEM OF A SHELTER

The application studied in this paper deals with the layout problem of a shelter. Eight components have to be located in the shelter, including electrical and energy cabinets, desks and electrical boxes. The CAD model of the shelter is presented in Fig. 1.

This problem is a two dimensional layout optimization problem, according to the fact that the cabinets are full height of the shelter and prevent a superposition of components. One of the possible designs of the shelter, modeled in two dimensions, is presented in Fig. 2. The description and the formulation of this model are also described in [START_REF] Bénabès | Interactive optimization strategies for layout problems[END_REF] and [START_REF] Bénabès | A new approach for specifying and solving layout problems[END_REF].

The layout components are divided in two categories of components: the material and the virtual components. A material component has a mass and can not overlap with another material component. On the other hand, a virtual component has no mass and can overlap with a material or a virtual component, according to the designer's requirements. In fact, in the layout problem of the shelter, the layout components are made up of: 8 material components: 4 cabinets, 2 desks and 2 electrical boxes 6 spaces of accessibility (dotted rectangles in Fig. 2) 1 free space (hatched rectangle in Fig. 2) located below the air-conditioner, where no cabinet can be placed 1 free space in front of the door 1 free corridor located in the middle of the shelter A space of accessibility is linked to a material component. For example, the space of accessibility of the cabinet 1 is defined as the required space, placed in front of the cabinet 1, and used to insert some materials into the cabinet 1. No material component can be placed in a space of accessibility.

The free corridor is used to guarantee that all components are accessible from the shelter's entry. This free corridor, the other free spaces and the spaces of accessibility can be considered as virtual components.

The density of this layout problem, defined as the ratio between the space occupied by the components and the available space in the container, is equal to 105%. This density does not take into account that a virtual component can overlap with another virtual component.

The placement of each material component is defined by two continued variables (X,Y ) for the position of the geometrical center of the component, one discrete variable ( ) for the orientation and one discrete variable ( ) for the direction. As all the layout components are modeled as rectangles in two dimensions, we consider that the orientation ( ) can take two values : 0°or 90°. The direction ( ) can also take two values (1 or 2) which define the position of the space of accessibility in relation to the material component.

The layout problem of this shelter is a multi-constraints and multi-objectives optimization problem. Four non-overlap constraints are defined: C1: non-overlap constraints between material components C2: non-overlap constraints between material components and virtual components C3: non-overlap constraints between components and the exterior of the shelter C4: non-overlap constraints between the cabinets and the free space below the air-conditioner Because of the dimension of this problem and the rectangular shape of the layout components, the overlap is defined as the intersection area between components. The intersection area between the components i and j is defined by:

A i j = max[0, min(x i + l i 2 , x j + l j 2 ) -max(x i - l i 2 , x j - l j 2 )] (1) ×max[0, min(y i + L i 2 , y j + L j 2 ) -max(y i - L i 2 , y j - L j 2 )]
where (x i , y i ) are the coordinates of the center of gravity of the rectangle i. L i and l i are respectively the length and the width of the rectangle i.

Two objectives (min O1, max O2) are also defined. The objective O1 is used to balance the masses inside the shelter. It means to minimize the distance between the center of gravity of the layout components and the geometrical center of the shelter. The objective O2 is used to maximize the distance between the cabinet 1 (energy network) and the cabinets 3 and 4 and the electrical box 2 (electrical network). All the distances between components, used in the computation of the two objectives, are the distances between the geometrical centers of components de-fined by the Euclidean norm. More information about the definition of these objectives are available in [START_REF] Bénabès | Interactive optimization strategies for layout problems[END_REF].

MODULAR OPTIMIZATION STRATEGY

The principle of this modular optimization strategy is to use a genetic algorithm and to insert in this algorithm some optimization modules in order to improve the global performances of the optimization strategy. This section presents the different algorithms which result from this modular approach.

Genetic Algorithm

This paper proposes to use a genetic algorithm process because of the great complexity of real-world layout problems. The complexity of a layout problem is defined in [START_REF] Bénabès | A new approach for specifying and solving layout problems[END_REF]. This complexity is linked to the geometry of layout components, the layout density and the problem formulation.

The problem formulation has a significant impact on the choice of an appropriate optimization algorithm. More numerous the constraints and objectives, more complex the search of a feasible design. The design space is parceled and the designer can not use traditional gradient-based optimization approaches to pass to a feasible region to another one. Stochastic algorithms, as the genetic algorithm, have to be used and the calculation time increases so that the problem is more complex.

In this paper, the Genetic Algorithm Omni-Optimizer is used [START_REF] Deb | Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization[END_REF]. This algorithm is designed to handle single and multiobjective problems. Given a set of initial individuals, randomly generated, the Genetic Algorithm uses basically three operators in order to create a set of new solutions. These genetic operators are the selection, the crossover and the mutation. This genetic algorithm has been tested on the layout problem of the shelter. The algorithm has been initialized by 200 designs, randomly created. The maximal number of iterations is fixed to 100. The simulation has been run ten times because of the stochastic behavior of the genetic algorithm. The convergence of the genetic algorithm Omni-Optimizer is illustrated in Fig. 3. In Fig. 3, the axis of ordinates represents, for each generation of the genetic algorithm, the minimal sum of constraints obtained by one design. It means that, for a specific generation, if this minimal sum of constraints is equal to 0, the genetic algorithm has found a "feasible" design, meaning a design which respects all the nonoverlap constraints. Then, the results, described in Fig. 3, show that the genetic algorithm converges but can not find a feasible solution, which respects all the placement constraints.

The layout problem of the shelter is too complex for this genetic algorithm. Consequently, the main idea of the modular strategy is to combine the genetic algorithm with some specific optimization modules, in order to help the generic algorithm to find more feasible design alternatives. These modules are described in the following sub-section.

Optimization modules

The objective of these optimization modules is to help the genetic algorithm to find more feasible designs. In this paper, three optimization modules are presented.

Module 1 : "Optimization of the direction of the components". In lots of real-world applications, as the layout problem of the shelter, one can find material and virtual components. This optimization module is specific to these layout problems, which deals with the spatial arrangement of material and virtual components.

Let us consider a layout problem, modeled in two dimensions, where the container and all the layout components have a rectangular shape. The problem can be for example the layout problem of the shelter. Let us consider a material component 1 (for example the cabinet 1) and a material component 2 (for example the electrical box 2). A virtual component (for example the space of accessibility of the cabinet 1), represented by a dotted rectangle in Fig. 4, is linked to the component 1. Figure 4 illustrates the two possible directions ( ) for the component 1, meaning the two possible positions of the virtual component.

The objective of the module 1 "Optimization of the direction of the components" is to optimize the placement of this virtual component, by deleting the discrete variable used for the direction and minimizing the non-overlap constraints between virtual components and material components. For example, Fig. 4 shows that the module 1 chooses the case (a), with a direction equal to 1 because this direction minimizes the non-overlap constraint between the space of accessibility of the component 1 and the component 2.

Module 2: "Separation algorithm". Given a layout configuration that does not satisfy placement constraints, the objective of the separation algorithm is to minimize the non-respect of overlap and protrusion constraints. In fact, the separation algorithm is designed to solve a single objective optimization problem, where all the placement constraints are gathered into one objective function.

This separation algorithm has been tested on a simple two dimensional layout problem, which deals with the search of an optimal spatial arrangement of square components inside a square container. Different optimization problems with different densities have been tested and the results are presented in [START_REF] Bénabès | Interactive optimization strategies for layout problems[END_REF].

A hybrid optimization algorithm is presented in [START_REF] Jacquenot | 2d multi-objective placement algorithm for free-form components[END_REF]. It combines the genetic algorithm Omni-Optimizer with the optimization module 2 "Separation Algorithm". Module 3: "Local disruption". This module is used to help the separation algorithm to find a feasible design, meaning a design which respects all the placement constraints. In fact, the separation algorithm, proposed in this paper, only modifies the position variables, it means the continued variables X and Y . It has no effect on the orientation or direction variables. Consequently, for some layout configurations, the separation algorithm does not find a feasible solution. It finds a local minimum which does not respect all the placement constraints. One or several components have to be rotated.

The main idea of this module 3 is to associate to the separation algorithm a local disruption in the layout configuration. This local disruption is used to randomly change the orientation of some components. The components which are rotated are randomly selected. The number of rotated components is fixed by the designer. For example, it can be fixed to 30% of the total number of components of the layout problem.

In fact, a local "disruption" already exists in the genetic algorithm process. This disruption is realized by the genetic operator "mutation". However, the mutation is not dedicated to specific optimization variables. The module 3 is dedicated to the variables which define the orientation of components. Consequently, this optimization module is more effective in the search of feasible designs.

Modular optimization strategy

Different optimization algorithms result from this modular approach. It depends on the layout problem and the designer's requirements. Figure 5 illustrates the optimization algorithm which results from the combination of the genetic algorithm Omni-Optimizer and the optimization modules 1, 2 and 3.

The module 3 can be repeated j max times, where j max is fixed by the designer. Between two applications of the module 3, the optimization process tests if the current design respects all the placement constraints. If so, the optimization process evaluates the design and moves to the next solution according to the genetic operators. Otherwise, the module 3 is run if j < j max .

Moreover, if j = j max and if the separation algorithm has not found a feasible solution, the optimization process continues by considering the design that minimizes the placement constraints among all the designs generated by the separation algorithm.

Comparison of the optimization strategies

This section presents the results obtained on the real-world layout problem of the shelter by considering the different optimization algorithms which result from the modular optimization approach.

In order to compare the performances of the different algorithms, the number of variants generated by each algorithm is measured for each generation. In fact, the design i is a new variant if it differs from the design j by at least one of the following criteria: one of the components of the layout has been displaced from at least mm along one of the axis and ( is fixed to 50 cm in the following simulations) one of the components has been rotated the minimum difference between the objective values of the two designs is bigger than a limit, fixed to 10 cm in the following simulations This number of feasible variants, which respect all the placement constraints, is plotted according to the calculation time. By associating the different modules with the genetic algorithm, with different parameters, five optimization algorithms are proposed: optimization algorithm A: genetic algorithm with the module 1 optimization algorithm B: genetic algorithm with the modules 1 and 2 optimization algorithm C: genetic algorithm with the modules 1, 2 and 3, with j max =3 optimization algorithm D: genetic algorithm with the modules 1, 2 and 3, with j max = 10 optimization algorithm E: genetic algorithm with the modules 1, 2 and 3, j max = 20

The initial population and the parameters of the genetic algorithm Omni-Optimizer are the same for each simulation. The size of the population is fixed to 200 individuals. The maximal number of iterations is fixed to 100. For each optimization algorithm, the simulation has been run ten times because of the stochastic behavior of the algorithm. Figure 6 illustrates the results obtained by the different optimization algorithms tested on the layout problem of the shelter.

Firstly, in this simulation, on the period time defined by the graph, the maximal number of iterations is only attained for the algorithms A, B and C. In fact, the algorithms E and F use the optimization module 3, and this optimization module is time consuming. When the module 3 is run, the module 1 and 2 are also run. Each generation of the global of the algorithm takes more time to generate designs and the maximal number of generations is not attained on the period of calculation time defined by the graph.

Secondly, it is difficult here to define which optimization algorithm has the best performances because it depends on the designer's requirements. The optimization algorithms can be sorted by ascend, according to the number of generated feasible variants, in the order A, B, C, D, E. It means that the optimization modules 1, 2 and 3 have a significant influence on the search of variants, because it helps the genetic algorithm in the search of feasible designs.

Consequently, the choice of an approriate optimization algorithm depends on the layout optimization problem and on the designer's requirements. It is important to know if the designer wants to find lots of solutions without caring about the calculation time or if he wants to generate few solutions in a short period of calculation time.

It can also be relevant to evaluate the Pareto-optimal variants, generated by these optimization algorithms, on this period of calculation time. If we compare their objective values, we can notice that the Pareto-optimal designs, found by the algorithms B, C, D and E have similar performances. Their performances are better than the performances of the Pareto-optimal designs generated by the algorithm A.

INTERACTIVE DECISION MAKING

In multi-objective optimization, the decision on the preferences between objective functions is delayed so that the designer can use the Pareto-front in order to select the most appropriate solution. The Pareto-front is the set of Pareto-optimal solutions, meaning solutions which are not dominated by other solutions. We consider that a design U dominates a design V (Pareto dominance) if U is as good as V for all the objectives and better than V for at least one objective. Mathematically, this can be formulated by:

∀ i ∈ [1, ..., n] f iU ≤ f iV ∃ j ∈ [1, ..., n] f jU < f jV (2)
where the design U is represented by a vector of objectives values F U = ( f 1U , f 2U , ..., f mU ), where f iU is the i th component of the vector of objectives F for the solution U.

Detection of variants

Let us consider the set of Pareto-optimal solutions generated by the optimization algorithm B. This set of designs is made up of 272 layout designs. It is too difficult for the designer to make a final decision on this big number of solutions. Because some Pareto-optimal solutions are very close, the approach, proposed in this paper, suggests to detect only the variants generated by the algorithm. A variant is defined in the previous section.

Let us consider different values of the parameter and the number of detected variants for each value. The results are described in Tab. 1. For the results described in the next subsection, is fixed to 1 m.

Interactive environment

In most real-world layout problems, all designer's requirements can not be integrated in the layout problem formulation by adding simple mathematical expressions. Then, when the designer is exploring the set of Pareto-optimal solutions, he has to make a final decision on optimal designs according to his personal judgment.

Consequently, this paper proposes an interactive environment for decision making, in order to allow the designer to: explore the set of Pareto-optimal variants visualize the solution in two or three dimensions manually and locally modify the solution by changing the position of some components and by visualizing the new values of the constraints and the objectives that result from these modifications.

The main objective of this interactivity with the designer is to improve the performances of the optimal solutions proposed by the algorithm, by inserting in the decision making the personal judgment of the designer. This interactivity needs a efficient graphical and numerical environment, as shown in the Fig. 7.

Figure 7(a) illustrates the interactive tool which allows the designer to explore the set of Pareto-optimal solutions. The designer can click on a point on the graph and visualize the layout design, the constraints and the objectives related to this solution. Figure 7(b) illustrates the interactive tool which allows the designer to locally modify a selected design and compare the modified solution with the initial one and the solution initially proposed by the engineering experts. In this figure, we can see that a white area is displayed around the layout component 5 (desk 1). The area represents the set of positions where the designer can place the layout component 5 without damaging the design objectives. It means that, considering the current orientation of the layout components, if the component 5 moves inside the white area, the new solution won't be dominated by the current one. For the designer, it is an indicator of non-deterioration of the constraints and objectives.

Results

Let us consider the results concerning the optimization algorithm B, previously described. According to Tab. 1, this algorithm, has generated 7 Pareto-optimal variants, with equal to 1 m. As it is explained in the previous subsection, let us consider that the designer selects one of these Pareto-optimal designs. This solution is represented in Fig. 8(b). According to Tab. 2, this solution has better performances than the first solution initialy proposed by the expert engineers, and illustrated in Fig. 8(a). It is important to mention that this initial solution was an intuitive design which had been generated only by considering geometric aspects.

Then the interactive envrionment suggests to the designer to localy and manualy change the position and the orientation of some components of the layout design, generated by the optimization algorithm. The solution, modified by the designer according to his own preferences, is illustrated in Fig. 8(c). Acoording to Tab. 2, this solution has as good performances as the solution proposed by the algorithm.

CONCLUSION

Layout problems are generally considered as complex problems and stochastic optimization algorithms have to be used. The complexity of layout problems is usually linked to the problem formulation. The design space is parcelled so that the designer needs stochastic optimization algorithms, as the genetic algorithm, in order to find feasible solutions.

The application studied in this paper shows that the genetic algorithm is not completely adapted to very complex layout problems. In fact, the layout problem of a shelter, presented in this paper, deals with the search of an optimal spatial arrangement of material and virtual components. This problem has a big density and its formulation is complex, meaning four design constraints and two objectives. The genetic algorithm Omni-Optimizer does not find any solution for this optimization problem.

Consequently, this paper proposes a modular optimization approach, based on the combination of a genetic algorithm with specific optimization modules. These modules are used in order to help the algorithm in the search of feasible designs. Three optimization modules are described: the optimization of the direction of the components, the separation algorithm and the local disruption. The designer can decide to insert these modules in the genetic algorithm process, according to the specificities of his layout problem. For example, the module 1 is only dedicated to layout problems which deal with the spatial arrangement of material and virtual components. This modular optimization strategy has been tested on the layout problem of the shelter, studied in this paper. The results described in this paper show that the optimization modules enable the designer to generate more variants which respect all the placement constraints. The optimization modules are time consuming. The designer has to choose the most appropriate module according to his requirements: to quickly generate lots of variants with average performances or to generate fewer variants with good performances. In the two cases, the calculation time is not the same.

The development of this modular optimization approach is a part of a global design approach used to solve complex layout problems. Because multi-objective optimization strategy is used in this approach, the algorithm generates lots of design alternatives. Consequently, the designer has to make a final choice, by choosing one of the optimal variants created by the optimization algorithm. Then, this paper proposes an interactive environment for decision making which allows the designer to detect the variants, visualize the optimal solutions on a scatter graph and locally modify a design according to his personal judgment. The main objective of this interactivity is to improve the global per-

FIGURE 1 .

 1 FIGURE 1. OVERALL VIEW OF THE SHELTER.

FIGURE 2 .

 2 FIGURE 2. DESCRIPTION OF THE SHELTER IN 2D.

FIGURE 3 .

 3 FIGURE 3. CONVERGENCE OF THE GENETIC ALGORITHM.

FIGURE 4 .

 4 FIGURE 4. DIRECTION OF A LAYOUT COMPONENT.

FIGURE 5 .

 5 FIGURE 5. MODULAR OPTIMIZATION STRATEGY.

FIGURE 6 .

 6 FIGURE 6. COMPARISON OF THE OPTIMIZATION ALGORITHMS.

  (a) display of Pareto-optimal designs (b) interactive display of a design

FIGURE 7 .

 7 FIGURE 7. INTERACTIVE ENVIRONMENT FOR DECISION MAKING.

2 FIGURE 8 .

 28 FIGURE 8. GRAPHICAL RESULTS.TABLE 2. NUMERICAL RESULTS.

TABLE 1 .

 1 EVOLUTION OF THE NUMBER OF VARIANTS AC-CORDING TO .

	(mm)	Variants	Pareto-optimal
			variants
	0	17334	272
	50	904	21
	500	88	8
	1000	64	7

Copyright © 2011 by ASME

ACKNOWLEDGMENT

The authors would like to acknowledge Thales Communications for the application study.


J.-H Kim

P Badel

A Duprey

J P Favre

S Avril
email: avril@emse.fr

Characterization of failure in human aortic tissue using digital image correlation

Keywords: arterial tissue, aneurysm, virtual fields method, digital image correlation

Introduction

An aortic aneurism is a localized dilation of the aorta in a weakened area [START_REF] Vorp | Biomechanics of abdominal aortic aneurysm[END_REF][START_REF] Vorp | Effect of aneurism on the tensile strength and biomechanical behavior of the ascending thoracic aorta[END_REF]. The increase of aneurism size may result in rupture, which will be a life threatening emergency. The mechanism of failure in aneurysms is now relatively well understood. However, only limited research has provided quantitative values for the stresses that cause the failure of pathologic arterial tissue. The evaluation of the local failure stress remains an open problem. In this study we apply digital image correlation (DIC) to excised pieces of tissue that we test in a bulge inflation test. The tissue is taken from the ascending aorta in diseased patients requiring an excision for removing an aneurysm. All procedures are carried out in accordance with the guidelines of the Institutional Review Board of the University Hospital of Saint-Etienne, France.

Methods

Testing device

To identify the constitutive parameters and the stress at failure, an inflation test is performed as shown in Figure 1, providing a biaxial loading. The specimens considered here are taken from the ascending aorta of diseased patients having an aneurysm. Square flat specimens are cut from the cylindrical excised aorta to fit in the inflation test device. Then the specimen is separated into media (including intima) and adventitia layers. Each layer is tested separately. Pressure is applied to inflate the specimen up to failure.

Measurement technique

The in-plane and out-of-plane displacements of the inflated specimen are measured using the Aramis software (www.gom.com). The full-field measurement technique applied here with the Aramis software is the stereo digital image correlation (S-DIC) [START_REF] Luo | Accurate measurement of three dimensional deformations in deformable and rigid bodies using computer vision[END_REF]. It consists in observing the grey speckle pattern at the surface of the tested specimen by two cameras with incidence angles, allowing measurement of 3D coordinates of each subset during deformation. It is assumed that the deformation of the speckle pattern is the same as the deformation of the specimen throughout its whole thickness. The deformation gradient is obtained from the undeformed and deformed coordinates of each data point according to the theory of finite deformation, assuming a plane stress state and constant thickness [START_REF] Ogden | Non-linear elastic deformations[END_REF]. [ ]

∑ = - - + - = 6 , 4 ) 1 ( 2 1 1 1 2 ) 1 ( 2 2 2 i I k i e k k I c W (1)
where c and k 1 are stress-like material parameters, k 2 a dimensionless parameter, I 1 the first invariant of the right Cauchy-Green tensor, and I 4 and I 6 are the squares of the stretches in the direction of the two families of collagen fibres, depending on a mean orientation angle denoted α. The virtual fields method (VFM) [START_REF] Grédiac | The virtual fields method for extracting constitutive parameters from full-field measurements: a review[END_REF] is used as an inverse procedure for the identification of the constitutive parameters. The Cauchy stress tensor is deduced from the strain energy function and the Green-Lagrange strain tensor. Then the difference between the internal and external virtual works is minimized for the identification [START_REF] Badel | Anisotropic and hyperelastic identification of in vitro human arteries from full-field measurements[END_REF]. Once the constitutive parameters are identified, the Cauchy stress components at failure can be calculated, in the circumferential direction of the artery, denoted σ R xx , and in the axial direction, denoted σ R yy . Eventually, the following stress value is deduced:

σ R α = σ R xx sin²(α) + σ R yy cos²(α) (2)
3 Results and Discussion Five samples were obtained from the University Hospital of Saint-Etienne, France. They have been tested with the methodology described previously. Due to different experimental reasons (leakage, poor speckle patterns), only 4 experiments could be analyzed completely. It is worth noting that the existence of thick, stiff and fragile intima layer in some aneurysms may cause intima delamination before rupture, preventing the identification of material properties. Those specimens have to be discarded in our procedure. The currently available results are presented in Table 1.

Discussion and conclusion

Thanks to the novel methodology presented in this paper, the material properties of human aneurismal tissue are identified and the stress at failure is deduced. The obtained values represent important data for the community of vascular biomechanics. They confirm that the aneurism behavior is generally anisotropic. The anisotropy is characterized by parameter α. Stresses tend to be preferably larger in the circumferential direction for α<45° which is typical of a media layer, and preferably larger in the axial direction for α>45°, which is typical of an adventitia layer [START_REF] Holzapfel | A new constitutive framework for arterial wall mechanics and a comparative study of material models[END_REF]. Parameter σ R α is found fairly stable for the media, with an average value of 383 kPa. The importance of this parameter, quantifying the stress in the direction normal to both families of collagen fibres, is confirmed by the observed modes of rupture (Figure 2), which are characterized by oblique tears.

A larger number of tests will now be carried out to confirm the preliminarily observed trends and analyze statistically the inter-individual variations of materials properties. This will also permit to evaluate the validity and effects of different assumptions made in this study, such as the constant thickness, plane stress etc... The methodology also relies on the assumption that the whole experimental procedure does not affect the mechanical properties of the tissue. This fundamental aspect will be investigated further in the near future.

Figure 1

 1 Figure 1 Views of the inflation test set-up 2.3. Identification approachThen the Green-Lagrange strain tensor is derived from the deformation gradient. An anisotropic hyperelastic constitutive model proposed by Holzapfel[START_REF] Holzapfel | A new constitutive framework for arterial wall mechanics and a comparative study of material models[END_REF] is adopted for the strain energy function as in equation 1.

Figure 2 .

 2 Figure 2. Example of a measured strain field and image of the specimen at rupture (sample 2)

Table 1 .

 1 Material properties obtained on 4 samples.

	sample	1	2	3	4
		(adventitia)	(media)	(media)	(media)
	Patient sex	Male	Male	Male	Male
	and age	81	81	69	68
	c (kPa)	0	0	0	0
	k 1 (kPa)	285	133	307	174
	k 2	6770	1963	9883	5118
	α	58°	40°	24°	37°
	σ R xx (kPa) σ R yy (kPa) σ R α (kPa)	418 1143 625	417 339 371	1152 216 368	556 327 410


Bretelle

Menard Jean-Pierre
email: jean-pierre.menard@mail.ap-hm.fr

MD Mazouni Chafika

MD Fenollar Florence

MD PhD; Raoult Didier

MD PhD; Boubli Léon

MD Bretelle Florence

Diagnostic accuracy of quantitative real-time PCR assay versus clinical and Gram stain identification of bacterial vaginosis

Keywords: Atopobium vaginae, Bacterial vaginosis, Diagnostic accuracy, Gardnerella vaginalis, PCR-based test, Pregnancy

Diagnostic accuracy of quantitative real-time PCR assay versus clinical and Gram stain identification of bacterial vaginosis

Introduction

Bacterial vaginosis (BV) is a common cause of vaginal symptoms in women of reproductive age 1. Mounting evidence associates BV, determined by clinical Amsel criteria or the Gram stain-based Nugent score, with susceptibility to sexually transmitted diseases, pelvic inflammatory diseases, preterm labor and preterm delivery 2. Unfortunately, although BV is associated with adverse pregnancy outcomes, regardless of the presence of clinical symptoms, the benefits of screening for and treating BV in pregnant women remain unclear 3-5. The subjective clinical diagnosis is of limited value in assessing an asymptomatic population, and half the women with BV are asymptomatic 6. The artificial Nugent score category of intermediate flora has increased the complexity of the clinical approach to vaginal flora: a significant percentage of the women tested have an intermediate score, but this category remains remarkably uncharacterized 7,8,9. Consequently obstetricians and gynaecologists continue to seek a reliable method for an objective analysis of abnormal vaginal flora.

Recent advances in molecular techniques have increased our knowledge of the microbial ecosystem of BV and associated some bacteria with BV for the first time 10,11. Of these, one of the most interesting may be Atopobium vaginae, an anaerobic and fastidious bacteria recently reported to be highly associated with BV 10,12,13. Specific proportions of different Lactobacillus species are related to the overgrowth of particular BV-associated bacteria, with the disappearance of Lactobacillus species related to the development of Gardnerella vaginalis and A. vaginae, in particular 12,13. Although G. vaginalis and A. vaginae are both commonly present in normal flora, high vaginal concentrations of both are highly specific for BV 12,13. We previously proposed a reliable and accurate molecular tool based on the combination of high vaginal quantification of G. vaginalis (DNA level  10 9 copies/mL) and A. vaginae (DNA level  10 8 copies/mL). It resulted in sensitive and specific BV diagnosis when the Gram stain-based Nugent score was used as the gold standard 14. One of the limitations of that study, however, was it did not apply a clinical approach to vaginal flora, by using the Amsel criteria, an alternative and commonly accepted diagnostic method for BV, as previous molecular studies have done 11,13,15.

The aim of the present study was to compare the diagnostic accuracy of the quantitative realtime PCR assay for G. vaginalis and A. vaginae for the diagnosis of BV with the two most commonly accepted methods, the Amsel criteria and the Nugent score.

Materials and Methods

A prospective study of pregnant women took place at the North University Hospital of Marseille (France). Pregnant women were enrolled from September 2008 to November 2009.

Vaginal samples were used to screen for BV in women who reported abnormal vaginal symptoms before 20 weeks' gestation. We selected only women with singleton pregnancies and for whom vulvovaginal candidiasis, trichomoniasis and gonococcal infection were ruled out after clinical examination and laboratory tests. The University's institutional review board (Ethics Committee of the University of Aix-Marseille, France) approved the study (in a decision dated September 19, 2008), and all participants provided written informed consent.

Before vaginal sampling, the physician performed a speculum examination to note the appearance of the vaginal discharge, the spontaneous vaginal odour, and the odour after the addition of 10% potassium hydroxide. Vaginal pH was measured with pH strips and a colourimetric scale. After the clinical examination, the physicians took two vaginal samples from each woman at the same time, on two different sterile cytobrushes rotated against the vaginal wall (Scrinet, 5.5 mm, Laboratory CCD International, Paris, France). One sample from the first cytobrush was rolled onto a glass slide for Gram staining with an automated stainer (Model 7320 Aerospray Gram Slide Stainer; Wescor, Logan, UT) and Nugent scoring. qPCR assay was performed with a Stratagene MX 3000P (Agilent, La Jolla, CA). The amplification program was run at 50°C for 2 min and at 95°C for 15 min, followed by 45 cycles at 95°C for 30 s and at 60°C for 1 min. Five µL of (1) a pure undiluted DNA sample, (2) a DNA sample diluted to 1/10 µL, (3) a DNA sample diluted to 1/100 µL, or (4) the serially diluted plasmid suspension was added to the 20-µL PCR mix that contained the Quantitect Probe PCR Kit mix (Qiagen, Courtaboeuf, France), the two pairs of primers, the two probes, and 100 U Uracil DNA glycosylase (Sigma-Aldrich, Saint Quentin Fallavier, France). All plasmid scale solutions were tested in duplicate. Negative controls were introduced in each reaction plate. To validate the quality and reproducibility of each PCR result, we verified for each reaction plate of each sample that (1) the standard curve remained linear and reproducible, (2) the cycle threshold values for all microorganisms tested in undiluted and diluted samples were reproducible and linear, and (3) the range of values for the number of albumin copies in the vaginal samples used as an internal control was narrow. The quality and reproducibility of each PCR result were validated, and none of the 163 samples used in this study had to be excluded. The quantitative molecular tool made it possible to reduce the detection limit for all microorganisms to 10 copies per 5 µL (10 3 copies per mL).

The final results were expressed as copies of microorganism DNA per mL of vaginal suspension.

To determine the accuracy of the molecular tool for the diagnosis of BV, the subjects were subsequently classified into two groups according to each method for diagnosing BV described above (Amsel criteria and Nugent score): those with BV and those without BV.

Agreement between the two reference methods and high vaginal concentrations of A. vaginae (DNA level  10 8 copies/mL) and G. vaginalis (DNA level  10 9 copies/mL) was calculated with the kappa value, determined by the javastat online statistics package 18. A kappa of 1.0 indicates perfect agreement. Values greater than 0.75 represent excellent agreement and values 0.40-0.75 fair to good agreement 19. The sensitivity, specificity, and predictive values of A. vaginae DNA  10 8 copies/mL and G. vaginalis DNA  10 9 copies/mL to predict BV were compared with reference methods. The statistical analysis used the UBC Bayesian Calculator Type 2 20.

Results

The study included all 163 pregnant women. The mean age of the study population was 29 (±7) years. All women included had speculum examinations during which vaginal samples were taken. The Amsel criteria, Nugent score and molecular quantification of Lactobacillus species, G. vaginalis, A. vaginae, and human albumin gene were successfully obtained for each woman.

Table 1 reports the BV results according to both reference methods. Fifteen women had BV according to both the Amsel criteria and Nugent score, while 10 had discordant results according to these two methods: (i) 5 women had normal flora according to Amsel criteria but a Nugent score  7; (ii) 5 women had BV according to Amsel criteria but a Nugent score < 7.

In all, 25 (15%) of the 163 women had BV according to at least one of these methods. The remaining 138 women (85%) did not have BV, as shown by both methods.

The molecular characteristics of the vaginal flora are reported in Tables 2 and3. No Lactobacillus species was detected by the qPCR method in 32 (19.60%) of the 163 samples.

The DNA level of G. vaginalis equalled or exceeded 10 9 copies/mL for 22 women (13.5%), and that of A. vaginae equalled or exceeded 10 8 copies/mL for 30 (18.40%). In all, 34 (21%) of the 163 samples had high vaginal concentrations of G. vaginalis or A. vaginae or both. The molecular profile of the 25 samples of vaginal flora identified as BV by either the Amsel criteria or Nugent score is presented in Table 3: 18 had no Lactobacillus species detected by qPCR, and all had high vaginal concentrations of G. vaginalis or A. vaginae or both.

Complete agreement between both reference methods for diagnosing BV and the molecular tool (that is, high vaginal concentrations of G. vaginalis or A. vaginae) occurred in 94.5% (154/163 samples). There was disagreement for nine samples (5.5%). All nine had high vaginal concentrations of G. vaginalis ( 10 9 copies/mL) or A. vaginae ( 10 8 copies/mL), did not have BV according to the Amsel criteria, and were categorized as intermediate flora by the Nugent score (Table 2). There was substantial agreement (kappa=0.81; 95% confidence interval 0.70-0.81) between the reference methods and high vaginal concentrations of both microorganisms. Compared with the reference methods, the molecular tool had a sensitivity of 100%, a specificity of 93%, a positive predictive value of 73% and a negative predictive value of 100% for predicting BV (Table 4).

Discussion

We examined the accuracy of a quantitative real-time PCR assay for G. vaginalis and A. vaginae for the diagnosis of BV compared with both the Amsel criteria and the Nugent score, both reference methods for this diagnosis. The originality of the present study is its simultaneous consideration of both the clinical characteristics of vaginal flora, according to the Amsel criteria, and the categorization of vaginal flora, according to the Gram stain-based Nugent score, to determine the accuracy of the molecular tool for diagnosing BV.

Good agreement (kappa=0.81) and high sensitivity (100%) and specificity (93%) were reported for the molecular tool in relation to both reference methods. These findings demonstrate the interest of molecular prediction of BV. The advantage of our PCR-based test is its ability to predict BV accurately when the standard methods result in false negatives. In this study, of the 25 flora samples with BV, 10 (40%) had discordant results for the Amsel criteria and the Nugent score (Table 3). Five samples categorized as BV by the Nugent score were normal according to the Amsel criteria. Those results are not surprising because the sensitivity of Amsel criteria for BV diagnosis is reported to be poor 21. For the Nugent score, 5 samples categorized as BV by the Amsel criteria were rated intermediate according to the Nugent score. The Nugent scoring system is excellent in diagnosing samples as either normal or BV, but the intermediate flora presents problems 7,8. Vaginal smears with intermediate flora may be considered as heterogeneous flora that most commonly include normal flora rather than BV, according to the definition of Amsel criteria 22. Furthermore, recent PCR assays report the heterogeneous character of intermediate flora, with some of them suggesting a molecular profile more similar to that of BV than to normal samples 13,14.

The molecular criteria's lower positive predictive value of 73% suggests that some positive molecular results are false positives (5.5%), i.e., although the molecular profiles of G. vaginalis and A. vaginae are identical to those seen in BV patients, the women do not meet the clinical ( 3 Amsel criteria) or microbiologic criteria (Nugent score  7) that define BV (Table 2). Alternatively, however, these results may represent true positives for the molecular condition of BV that were missed by traditional diagnostic tools. The false negatives of both standard methods reported above may support this alternative explanation. In any case, our molecular tool, based on PCR quantification of G. vaginalis and A. vaginae, clearly defines a reproducible and standardized molecularly defined BV, irrespective of the clinical and microscopic characteristics of vaginal flora. The clinical implications of this molecular condition should help to improve our understanding of BV, especially during pregnancy. Thus, we recently reported that high vaginal concentrations of G. vaginalis and A. vaginae are associated with a significant risk of preterm delivery in women with preterm labor 23. Some points must be discussed as potential limitations of our study. First, we did no attempt to test for each bacterial species known to be found in the vagina, but the spectrum of targeted microorganisms is significant in BV. It is possible that quantification of additional vaginal microorganisms would modify the results. Second, repeat vaginal sampling to detect changes in the vaginal flora could provide valuable information about the pathogenesis and natural history of the molecular condition of BV. Third, quantitative PCR assays have recently demonstrated a substantial variability in G. vaginalis levels with menstrual cycle 24.

Consequently, the same threshold established in amenorrheic pregnant women may not be appropriate for non-pregnant women. In conclusion, comparison with the reference methods of the Amsel criteria and the Nugent score shows that the quantitative real-time PCR assay, targeting G. vaginalis and A. vaginae, is a reliable tool for the diagnosis of BV. The pathogenesis of the molecular condition of BV should be investigated.

  The second cytobrush was transferred to a sterile tube containing 500 µl of BME Baral Medium (Invitrogen, Carlsbad, CA) and stored at -80°C until DNA extraction and molecular quantification. The two methods used to diagnose BV were (1) clinical diagnosis, based on the combination of any three of the following four criteria 16: vaginal pH greater than 4.5, thin homogeneous vaginal discharge, clue cells on microscopic examination of vaginal fluid, and "fishy" amine odour after the addition of 10% potassium hydroxide (positive "whiff" test); (2) microbiological diagnosis, based on Gram staining graded according to the Nugent score 17 to determine the presence of normal (score of 0 to 3) or intermediate flora (score of 4 to 6), or BV (score of 7 to 10). Clinicians and laboratory staff made their diagnoses independently, unaware of each other's results. The quantitative molecular tool was based on a specific quantitative real-time polymerase chain reaction (qPCR) assay and serial dilutions of a plasmid suspension, as previously described 14. It targeted Lactobacillus species, A. vaginae, G. vaginalis, and a human albumin gene. Human albumin gene quantification was used as an internal control to provide evidence for DNA presence and DNA quality. Briefly, after DNA extraction, a

Table 1 :

 1 Characteristics of vaginal flora according to the Amsel criteria and Nugent score.

	Methods for diagnosis	Women with	Women without bacterial vaginosis
		bacterial vaginosis	Normal flora	Intermediate flora
	Amsel criteria	20 (12%)	143 (88%)	-
	Nugent score	20 (12%)	117 (72%)	26 (16%)
	Amsel criteria and Nugent score	15 (9.2%)	117 (72%)	-
	Amsel criteria or Nugent score	25 (15%)	117 (72%)	21 (13%)

Table

Table 2 :

 2 Molecular characteristics of vaginal flora for women with bacterial vaginosis (n=25) and without bacterial vaginosis (n=138), with the Amsel criteria and Nugent score as

	reference methods.
	PCR quantification	Women with	Women without bacterial vaginosis
	(bacteria/mL)	bacterial vaginosis		n=138
		n=25	Normal flora	Intermediate flora
			n=117	n=21
	No Lactobacillus species	18 (72%)	8 (6.8%)	6 (28%)
	G. vaginalis  10 9 /mL	18 (72%)	0	4 (19%)
	A. vaginae  10 8 /mL	24 (96%)	0	6 (28%)
	G. vaginalis  10 9 /mL and/or	25 (100%)	0	9 (43%)
	A. vaginae  10 8 /mL

Table 3 :

 3 Molecular loads for Lactobacillus species, Gardnerella vaginalis and Atopobium vaginae for women with bacterial vaginosis (n=25) according to Amsel criteria ( 3 criteria) or Nugent score (score  7).

		Method for diagnosis	PCR quantification (bacteria/mL)
	N Amsel criteria Nugent score	Lactobacillus	G. vaginalis	A. vaginae
	1	BV	BV	-	1.15 x10 9	1.09 x10
	2	BV	BV	1.83 x10 3	2.69 x10 10	5.31 x10
	3	BV	BV	-	1.19 x10 9	8.73 x10
	4	BV	BV	-	4.47 x10 8	8.34 x10 10
	5	BV	BV	-	4.73 x10 9	4.84 x10
	6	BV	BV	2.38 x10 8	-	1.40 x10
	7	BV	BV	-	6.32 x10 8	2.30 x10
	8	BV	BV	-	1.88 x10 9	7.20 x10
	9	BV	BV	9.20 x10 5	3.10 x10 9	1.07 x10
	10	BV	BV	-	1.80 x10 9	2.20 x10
	11	BV	BV	-	2.60 x10 8	7.60 x10
	12	BV	BV	-	7.75 x10 9	1.05 x10
	13	BV	BV	-	1.40 x10 9	1.30 x10
	14	BV	BV	-	3.40 x10 9	1.50 x10
	15	BV	BV	5.67 x10 8	3.05 x10 9	6.16 x10
	16	BV	IF	2.38 x10 9	-	2.04 x10
	17	BV	IF	-	1.02 x10 9	4.80 x10
	18	BV	IF	-	5.67 x10 9	1.52 x10
	19	BV	IF	-	3.42 x10 9	6.87 x10
	20	BV	IF	-	1.80 x10 9	1.80 x10
	21	NF	BV	-	5.30 x10 9	1.14 x10
	22	NF	BV	-	-	2.04 x10
	23	NF	BV	-	1.56 x10 10	1.05 x10
	24	NF	BV	3.78 x10 8	5.41 x10 9	3.82 x10
	25	NF	BV	2.44 x10 7	1.50 x10 8	2.00 x10

BV: Bacterial Vaginosis; NF: Normal Flora; IF: Intermediate Flora.

Acknowledgement.

The authors thank Dr Mireille Henry for her expertise in molecular biology, Stéphanie Junoy for her technical assistance, Jo Ann Cahn for editing the manuscript.

Disclosure of interests.

Université de la Méditerranée has applied for a patent on the quantitative molecular tool used in this study. European Patent Office N° 2087134.

Ethics approval

Institutional Review Board (Ethics committee of the University Aix-Marseille, France) approved the study (in a decision dated September 19, 2008).