Jacques Bénasséni
email: jacques.benasseni@univ-rennes2.fr

Alain Mom
email: alain.mom@univ-rennes2.fr

Inequalities for the eigenvectors associated to extremal eigenvalues in rank one perturbations of symmetric matrices

Keywords: doubly stochastic matrix, eigenvalues and eigenvectors, perturbation of rank one, symmetric matrix AMS subject classifications. 15A18, 15A42

HAL is

Introduction

Rank one perturbations are of major interest from both applied and theoretical standpoints. When considering symmetric or hermitian matrices, some central results for eigenvalues are provided by Golub [START_REF] Golub | Some modified matrix eigenvalue problems[END_REF], Thompson [START_REF] Thomson | The behaviour of eigenvalues and singular values under perturbations of restricted rank[END_REF], Bunch, Nielsen and Sorensen [START_REF] Bunch | Rank-one modification of the symmetric eigenproblem[END_REF] or Arbenz and Golub [START_REF] Arbenz | On the spectral decomposition of hermitian matrices modified by low rank perturbations with applications[END_REF]. More recent works focusing on bounds for the perturbed eigenvalues include papers of Ipsen and Nadler [START_REF] Ipsen | Refined perturbation bounds for eigenvalues of hermitian and non-hermitian matrices[END_REF], Bénasséni [START_REF] Bénasséni | Lower bounds for the largest eigenvalue of a symmetric matrix under perturbations of rank one[END_REF], Cheng, Luo and Li [START_REF] Cheng | The bounds of the smallest and largest eigenvalues for rank-one modification of the hermitian eigenvalue problem[END_REF], Cheng, Song, Yang and Si [START_REF] Cheng | The bounds of the eigenvalues for rank-one modification of hermitian matrix[END_REF] among others. It is also worth noting that Ding and Zhou [START_REF] Ding | Eigenvalues of rank-one updated matrices with some applications[END_REF] consider rank-one perturbed matrices of special structure. Finally, Mehl, Mehrmann, Ran and Rodman [START_REF] Mehl | Eigenvalue perturbation theory of classes of structured matrices under generic structured rank one perturbations[END_REF] develop a comprehensive study of the perturbation theory for structured matrices under structured rank one perturbations while Ran and Wojtylak [START_REF] Ran | Eigenvalues of rank one perturbations of unstructured matrices[END_REF] consider curves associated to eigenvalues in the framework of rank one perturbations . However, despite this amount of results for eigenvalues, less work has been devoted to the behavior of eigenvectors under perturbations of restricted rank.

We consider the perturbation of a symmetric matrix A of order p to

B = A + τ cc t (1)
where τ is a real positive constant and c is a unit two norm column vector in R p with c t = (c 1 , . . . , c p ). For i = 1, . . . , p, the eigenvectors u i of A associated to the eigenvalues ranked in decreasing order: λ 1 (A) λ 2 (A) . . . λ p (A) 0 are assumed to have a unit two norm. The same assumption is made for the eigenvectors v i of B associated to the eigenvalues λ 1 (B) λ 2 (B) . . . λ p (B) 0. This paper considers the inner products c t u i , c t v i and u t v i for i = 1, . . . , p . Since the vectors c, u i and v i are assumed to have a unit norm, these three inner products are involved in the fundamental cosine formula of spherical geometry. However, the goal of this paper is to provide new relations for these inners products and to derive properties specific to the eigenvectors corresponding to the largest and smallest non-zero eigenvalues.

The paper is organized as follows. Section 2 is devoted to preliminary results and provides relations involving the inner products c t u i , c t v i and u t i v i for i = 1, . . . , p. In particular it is shown that the matrix of order p with elements (v t i u j ) 2 is a doubly stochastic matrix. Focusing more specifically on the eigenvectors corresponding to the largest and smallest non-zero eigenvalues, Section 3 provides inequalities for the inner products c t v i using a majorization theorem of Hardy, Littelwood and Pólya. Finally, in Section 4, additional inequalities are proposed and refined developments are suggested for infinitesimal perturbations.

Preliminary results

As first lemma we use a result due to Golub [9, Corollary 8.1-5 p.270].

Lemma 1 There exit p real numbers q i satisfying q i 0 and p i=1 q i = 1 such that:

λ i (B) = λ i (A) + τ q i for i = 1, . . . , p.
It should be noted that q i = (λ i (B) -λ i (A))/τ is the percentage of increase of the trace accounted for by the ith eigenvalue when A is modified to B.

The next proposition provides a new formulation of q i which will be useful since q 1 and q p play a central role in several results of the paper.

Proposition 2 For i = 1, . . . , p we have:

q i = (c t u i )(c t v i ) u t i v i (2)
if u t i v i = 0
Proof: The proof of the result is straightforward multiplying the left-hand side of (1) by u t i and its right-hand side by v i and using Au i = λ i (A)u i and

Bv i = λ i (B)v i .
Proposition 3 Let M = (m ij ) denote the p × p matrix whose entries are defined by: m ij = (v t i u j ) 2 . Then M is a doubly stochastic matrix.

Proof: For i = 1, . . . , p we have:

p j=1 m ij = p j=1 (v t i u j ) 2 = p j=1 (v t i u j )(u t j v i ) = v t i ( p j=1 u j u t j )v i = v t i v i = 1
since p j=1 u j u t j is the identity matrix and the eigenvectors v i are normalized for the two norm. Therefore all the rows of M sum to one. Similarly we get p i=1 m ij = 1 for j = 1, . . . , p so that all the columns of M also sum to one. Since all the entries of M are nonnegative, this matrix is doubly stochastic.

Theorem 4 Let l A and l B denote the two column vectors of R p defined by l t A = (λ 1 (A), λ 2 (A), . . . , λ p (A)) and l t B = (λ 1 (B), λ 2 (B), . . . , λ p (B). Denote also by h the column vector defined by h t = ((c t v 1 ) 2 , . . . , (c t v p ) 2 ). Then:

Ml A = l B -τ h (3)
Proof: Using the definition of M, the ith row of Ml A may be written as:

[Ml A ] i = p j=1 λ j (A)m ij = p j=1 λ j (A)(v t i u j ) 2 = p j=1 λ j (A)(v t i u j )(u t j v i ) = v t i p j=1 λ j (A)u j u t j v i = v t i Av i .
From (1) we then have:

[Ml A ] i = v t i (B -τ cc t )v i = λ i (B) -τ (c t v i ) 2
since Bv i = λ i (B)v i and v t i v i = 1. This proves (3).

Corollary 5 For i = 1, . . . , p, we have λ i (B) -τ (c t v i ) 2 0.

Proof: The result is obvious from (3) since all the entries in M and l A are non negative.

Finally in the next section we shall use a theorem of majorization due to Hardy, Littelwood and Pólya which requires to introduce the following definition:

Definition 6 Given a p-tuple x of nonnegative real numbers with x t = (x 1 , x 2 , . . . , x p ) we denote by x * the p-tuple with the same entries as x but rearranged in non-increasing order. In other words,

x * = (x * 1 , x * 2 , . . . , x * p ) t with x * 1 x * 2 . . . x *
p . The p-tuple x is said to be majorized by the p-tuple y with the notation x ≺ y if :

k j=1 x * j k j=1 y * j for k = 1, . . . , p -1 and p j=1 x * j = p j=1 y * j .
As a simple consequence of the previous definition we have the following corollary whose proof is obvious.

Corollary 7 Consider two p-tuples of nonnegative real numbers x and y such that x ≺ y. For any p × p permutation matrix P , define z = Px .

Letting z t = (z 1 , z 2 , . . . , z p ) and y t = (y 1 , y 2 , . . . , y p ) we then have: Note that this corollary holds when considering in particular the identity matrix for P.

Theorem 8 For two p-tuples of nonnegative real numbers x and y, we have

x ≺ y if an only if there exists a doubly stochastic matrix S such that x = Sy.

This well known result due to Hardy, Littelwood and Pólya can be found in Minc [13, Theorem 2.2 p.110] for example . A comprehensive reference on inequalities in relation with the theory of majorization is also provided by Marshall, Olkin and Arnold [START_REF] Marshall | Inequalities: Theory of Majorization and Its Application[END_REF].

Main inequalities

Theorem 9 Let r denote the rank of A. Then we have the following inequality:

(c t v 1 ) 2 λ 1 (B) -λ 1 (A) τ = q 1 (4)
Furthermore, if c ∈ range(A), we have:

(c t v r ) 2 λ r (B) -λ r (A) τ = q r (5)
and if c / ∈ range(A), we have:

(c t v r+1 ) 2 λ r+1 (B) -λ r+1 (A) τ = λ r+1 (B) τ (6)
Proof: From Proposition 3 we know that the matrix M involved in Equation ( 3) is doubly stochastic. Therefore we can derive from this proposition that:

l B -τ h ≺ l A (7)
by the Theorem 8 of Hardy, Littelwood and Pólya. Noting that l A = l * A and using Corollary 7 because the ranking order of the entries

λ i (B) -τ (c t v i ) 2
is unknown , we then have:

λ 1 (B) -τ (c t v 1 ) 2 λ 1 (A)
which proves (4). Now assume that c ∈ range(A) so that both A and B are of rank r. Then for i r + 1 we have λ i (B) = λ i (A) = 0 and from Corollary 5:

λ i (B) -τ (c t v i ) 2 = -τ (c t v i ) 2 0 so that (c t v i ) = 0. Then: r i=1 (c t v i ) 2 = p i=1 (c t v i ) 2 = c t ( p i=1 v i v t i )c = c t c = 1 and r i=1 (λ i (B) -τ (c t v i ) 2 ) = Tr(B) -τ = Tr(B -τ cc t ) = Tr(A) = r i=1 λ i (A)
From ( 7) used together with Corollary 7, we have:

r-1 i=1 (λ i (B) -τ (c t v i ) 2 ) r-1 i=1 λ i (A) and r i=1 (λ i (B) -τ (c t v i ) 2 ) = r i=1 λ i (A)
so that:

λ r (B) -τ (c t v r ) 2 λ r (A)
which proves [START_REF] Cheng | The bounds of the smallest and largest eigenvalues for rank-one modification of the hermitian eigenvalue problem[END_REF].

Finally if c / ∈ range(A), the matrix B is of rank r + 1 so that λ r+1 (B) > 0 and λ i (B) = 0 for i r + 2 while we have always λ i (A) = 0 for i r + 1.

Therefore from Corollary 5 we have for i r + 2:

λ i (B) -τ (c t v i ) 2 = -τ (c t v i ) 2 0 so that (c t v i ) = 0 and r+1 i=1 (c t v i ) 2 = p i=1 (c t v i ) 2 = c t ( p i=1 v i v t i )c = c t c = 1. Then r+1 i=1 (λ i (B) -τ (c t v i ) 2 ) = Tr(B) -τ = Tr(B -τ cc t ) = Tr(A) = r i=1 λ i (A).
From [START_REF] Ding | Eigenvalues of rank-one updated matrices with some applications[END_REF] used again together with Corollary 7, we have:

r i=1 (λ i (B) -τ (c t v i ) 2 ) r i=1 λ i (A) and r+1 i=1 (λ i (B) -τ (c t v i ) 2 ) = r+1 i=1 λ i (A)
so that:

λ r+1 (B) -τ (c t v r+1 ) 2 λ r+1 (A)
which proves (6) since λ r+1 (A) = 0.

The following corollary provides two additional inequalities.

Corollary 10 With the notation of the previous theorem we have:

|c t u 1 | |u t 1 v 1 | c t v 1 (8)
and

(c t v 1 ) 2 (c t u 1 ) 2 (9)
and

(u t 1 v 1 ) 2 (c t u 1 ) 2 (10)
Proof: First, since

0 q 1 = (c t u 1 )(c t v 1 ) u t 1 v 1 1,
we have

q 1 = |c t u 1 | |c t v 1 | |u t 1 v 1 |
.

From (4) in Theorem 9 we then get

(c t v 1 ) 2 |c t u 1 | |c t v 1 | |u t 1 v 1 | . Thus, |c t u 1 | |u t 1 v 1 | c t v 1 .
or equivalently

(c t v 1 ) 2 (c t u 1 ) 2 (u t 1 v 1 ) 2 (11)
Inequality [START_REF] Golub | Matrix computations[END_REF] follows since (u t 1 v 1 ) 2 1. Finally, noting that in [START_REF] Marshall | Inequalities: Theory of Majorization and Its Application[END_REF] we have (c t v 1 ) 2 1, we get (u t 1 v 1 ) 2 (c t u 1 ) 2 .

4 Further inequalities

First inequalities

In practice, the eigenvalues of the perturbed matrix B are unknown in contrast to those of the initial one A. Therefore, it is interesting to obtain inequalities similar to those of Theorem 9 in the previous section but involving only the eigenvalues of A. This can be achieved by using results of Ipsen and Nadler [START_REF] Ipsen | Refined perturbation bounds for eigenvalues of hermitian and non-hermitian matrices[END_REF] or inequalities of Bénasséni [START_REF] Bénasséni | A note on bounds to the variation of eigenvalues in symmetric matrix perturbation of rank one[END_REF]. A lower bound to (c t v 1 ) 2

based only on the eigenvalues of the initial matrix A and the vector c can be obtained by introducing the lower bound to λ 1 (B) given in the Theorem 2.4

of Ipsen and Nadler or the results in Section 3 of Bénasséni. In the same way, other inequalities in these two papers can be used to obtain upper bounds to c t v r depending only A and the vector c. For the sake of brevity, we only illustrate this approach in the case r = p with the upper bound for c t v p .

First we use the upper bound λ min (U + ) to λ p (B) defined in Theorem 2.1 and Corollary 2.2 of Ipsen and Nadler [START_REF] Ipsen | Refined perturbation bounds for eigenvalues of hermitian and non-hermitian matrices[END_REF]. Letting gap p = λ p-1 (A) -λ p (A)

and norm 2 = (c t u p-1 ) 2 + (c t u p ) 2 we get:

λ p (B) λ p (A)+ gap p + τ norm 2 -(gap p + τ norm 2 ) 2 -4τ gap p (c p ) 2 2 (12)
Incorporating the right hand side of [START_REF] Mehl | Eigenvalue perturbation theory of classes of structured matrices under generic structured rank one perturbations[END_REF] in Inequality (5) of Theorem 9 yields:

(c t v p ) 2 gap p + τ norm 2 -(gap p + τ norm 2 ) 2 -4τ gap p (c p ) 2 2τ ( 13
)
Finally, inequalities in Sections 2 and 3 of Bénasséni [START_REF] Bénasséni | A note on bounds to the variation of eigenvalues in symmetric matrix perturbation of rank one[END_REF] can also be used.

His Section 2 provides for example the following simple inequality:

λ p (B) λ p (A) + τ (c t u p ) 2 + (c t u p ) 4 + 4(c t u p ) 2 { c 2 -(c t u p ) 2 } 2 ( 14
)
which is sharper than the usual inequality: λ r (B) λ r (A) + τ c 2 . Incorporating the right hand side of this inequality in (5) of Theorem 9 we get:

(c t v p ) 2 (c t u p ) 2 + (c t u p ) 4 + 4(c t u p ) 2 {1 -(c t u p ) 2 } 2 ( 15
)
since c is normalized.

Inequalities for infinitesimal perturbations

When considering infinitesimal perturbations, power expansions of the eigenvalues allow the derivation of refined bounds for c t v 1 and c t v p as detailed in the remaining of this section. It should be noted that these infinitesimal perturbations corresponding to small values of τ are involved in many fields of applications such as statistics for example where one is concerned by the effects of small changes in data on some parameters to be evaluated.

More specifically, we focus on a specific eigenvalue λ(A) of the initial matrix A assumed to be simple and on its corresponding normalized eigenvector u. We know from matrix perturbation analysis that, for sufficiently small values of τ , there exist an eigenvalue λ(B) of B and a corresponding non normalized eigenvector v which can be expressed under the following convergent power expansions:

λ(B) = λ(A) + τ µ 1 + τ 2 µ 2 + . . . τ n µ n + O(τ n+1 ) (16)
and

v = u + τ w 1 + τ 2 w 2 + . . . τ n w n + O(τ n+1 ) ( 17
)
Letting C = cc t for notational convenience, a lemma of Wang and Liski [START_REF] Wang | Effects of observations on the eigensystem of a sample covariance matrix[END_REF] provides some general relations for the real numbers µ j and the vectors w j involved in Equations ( 16) and ( 17) when considering perturbation (1). This lemma is given below.

Lemma 11 Using the notation M + for the Moore-Penrose inverse of any matrix M and considering the perturbation B = A + τ C , a solution for the parameters µ j and w j involved in Equations ( 16) and ( 17) is provided by the following relations:

µ 1 = u t Cu ( 18
)
w 1 = -[A -λ(A)I p ] + Cu ( 19
)
and for j = 2, . . . n:

µ j = u t Cw j-1 (20)
w j = -[A -λ(A)I p ] + [Cw j-1 - j-1 i=1 µ i w j-i ] ( 21
)
where I p denote the identity matrix of order p.

The proof of this lemma is provided by Wang and Liski [START_REF] Wang | Effects of observations on the eigensystem of a sample covariance matrix[END_REF] through a usual approach detailed for example in Wilkinson [17,. We follow below their derivation while introducing some necessary complements for the sake of generality.

Proof:

Equating the coefficients of τ j for j = 1, . . . n in the relation:

Bv = λ(B)v (22)
provides the following set of equations:

Aw 1 + Cu = λ(A)w 1 + µ 1 u (23) Aw 2 + Cw 1 = λ(A)w 2 + µ 1 w 1 + µ 2 u ( 24
)
and more generally for j = 2, . . . , n

Aw j + Cw j-1 = λ(A)w j + j-1 i=1 µ i w j-i + µ j u (25)
First, multiplying the left-hand side of ( 23) by u t and using the relations Au = λ(A)u and u t u = 1, we get (18). Now in order to get (19) , rewrite (23) as :

[A -λ(A)I p ]w 1 = -(C -µ 1 I p )u. (26)
The following two remarks are necessary for the derivation.

First, using (18) we get u t (C -µ 1 I p )u = 0 so that (C -µ 1 I p )u is in the column space of [A -λ(A)I p ]. Thus Equation ( 26) is consistent and all its solutions can be expressed as:

w 1 = -[A -λ(A)I p ] -(C -µ 1 I p )u (27)
where

[A -λ(A)I p ] -denotes any generalized inverse of [A -λ(A)I p ].
Second, if we have two solutions w 1 and w ′ 1 of (26), these solutions satisfy:

[A -λ(A)I p ](w 1 -w ′ 1 ) = 0. Therefore w ′ 1 -w 1 is in the null space of [A -λ(A)I p ]
and we have :

w ′ 1 = w 1 + αu (28)
for some coefficient α ∈ R since λ(A) is simple. Note that one particular solution of ( 26) is given by:

w 1 = -[A -λ(A)I p ] + (C -µ 1 I p )u (29)
using the Moore-Penrose inverse:

[A -λ(A)I p ] + = p i=1 λ i (A) =λ(A) u i u t i λ i (A) -λ(A) .
Then, all the solutions of (26) are of the form:

w 1 = -[A -λ(A)I p ] + (C -µ 1 I p + αu (30)
or equivalently

w 1 = -[A -λ(A)I p ] + Cu + αu (31)
since [A-λ(A)I p ] + u = 0. The choice of (19) as particular solution is justified by attractive properties which are detailed at the end of the proof.

Note that u t w 1 = 0 since u is in the null space of [A -λ(A)I p ] + . Now in order to derive (21) for j = 2, . . . n we have simply to rewrite (25) as:

[A -λ(A)I p ]w j = -Cw j-1 + j-1 i=1 µ i w j-i + µ j u. (32)
Premultiplying this last equation by u t we get:

u t [-Cw j-1 + j-1 i=1 µ i w j-i + µ j u] = 0 (33)
Therefore the right hand side of (32) is in the column space of [A -λ(A)I p ] and Equation (32) is consistent. Similarly to w 1 we can choose (21) as a particular solution.

Finally, in order to derive the parameters µ j involved in the expansion of λ(A) in ( 16), we have simply to note from (21) that:

u t w j = 0 (34)
Then, developing (33) and using (34) we get (20). Now, some justifications of the choice of the Moore-Penrose inverse for w 1 in (19) are given below.

First, among all the solutions provided by ( 27), the use of the Moore-Penrose inverse is the only one which preserves the orthogonality between w 1 and u. This is the same between w j and u for j = 1, . . . , n. This orthogonality is crucial for the recurrence process and motivates the choice of ( 19) and ( 21) as solutions.

Second, it should be noted from (28) that:

w ′ 1 2 = w 1 2 + α 2
since u t w 1 = 0. Then, focusing on the first order approximation v (1) = u + τ w ′ 1 of v we have:

u + τ w ′ 1 2 = u 2 + τ 2 w 1 2 + τ 2 α 2 + 2τ α = u 2 + 2τ α + τ 2 ( w 1 2 + α 2 ) = 1 + 2τ α + τ 2 w ′ 1 2 .
Hence, we see that the first order approximation of the norm of v (1) is given by: 1+2τ α which is equal to one if and only if α = 0 or equivalently w ′ 1 = w 1 . Having an approximation of v whose norm only differs from that of the initial vector u by terms of degree 2 or greater allows a better estimation of the direction of v by v (1) .

It should be noted that the previous theorem holds for any symmetric perturbation matrix C . However, in the framework of rank one perturbation, the following proposition provides developed formulations involving the perturbation vector c. Proposition 12 Consider the perturbation B = A + τ cc t defined in Equation [START_REF] Arbenz | On the spectral decomposition of hermitian matrices modified by low rank perturbations with applications[END_REF] . Then the parameters µ j and w j involved in the power expansions [START_REF] Wang | Effects of observations on the eigensystem of a sample covariance matrix[END_REF] and ( 17) can be expressed as follows for j = 1, 2:

µ 1 = (c t u) 2 (35)
w 1 = -(c t u) p i=1 λ i (A) =λ(A) (c t u i ) λ i (A) -λ(A) u i (36) µ 2 = -(c t u) 2 p i=1 λ i (A) =λ(A) (c t u i ) 2 λ i (A) -λ(A) (37)
w 2 = (c t u) p i=1 λ i (A) =λ(A) p k=1 λ k (A) =λ(A) (c t u i )(c t u k ) 2 [λ i (A) -λ(A)][λ k (A) -λ(A)] u i -(c t u) 3 p i=1 λ i (A) =λ(A) (c t u i ) [λ i (A) -λ(A)] 2 u i (38)
Finally, we have also:

µ 3 = (c t u) 2 p i=1 λ i (A) =λ(A) p k=1 λ k (A) =λ(A) (c t u i ) 2 (c t u k ) 2 [λ i (A) -λ(A)][λ k (A) -λ(A)] -(c t u) 4 p i=1 λ i (A) =λ(A) (c t u i ) 2 [λ i (A) -λ(A)] 2 (39) Proof:
The derivation of the formula is straightforward by simply substituting cc t for C in Theorem 11 and using the formulation of

[A -λ(A)I p ] + = p i=1 λ i (A) =λ(A) u i u t i λ i (A) -λ(A)
already given. Now we use the previous expansions of the eigenvalues in power series to provides refined bounds derived from Theorem 9.

Proposition 13 Assuming that λ 1 (A) is simple and that τ is sufficiently small in order to express λ 1 (B) under the following convergent power series:

λ 1 (B) = λ 1 (A) + τ µ 1 + τ 2 µ 2 + . . . τ n µ n + O(τ n+1 )
we have he following inequality.

(c t v 1 ) 2 (c t u 1 ) 2 + τ (c t u 1 ) 2 p i=2 (c t u i ) 2 λ 1 (A) -λ i (A) + τ 2 (c t u 1 ) 2 p i=2 p k=2 (c t u i ) 2 (c t u k ) 2 [λ 1 (A) -λ i (A)][λ 1 (A) -λ k (A)] -(c t u 1 ) 4 p i=2 (c t u i ) 2 [λ 1 (A) -λ i (A)] + O(τ 3 ) (40)
Proof: This result simply follows from (4) used together with Proposition 12 taking u = u 1 .

As simple consequence of this proposition we have the following two corollaries.

Corollary 14 Under assumptions in the previous proposition we have also the following inequality:

(c t v 1 ) 2 (c t u 1 ) 2 + τ (c t u 1 ) 2 p i=2 (c t u i ) 2 λ 1 (A) -λ i (A) -τ 2 (c t u 1 ) 4 p i=2 (c t u i ) 2 [λ 1 (A) -λ i (A)] 2 (41)
Proof: The result is obvious simply rewriting (40) as

(c t v 1 ) 2 (c t u 1 ) 2 + τ (c t u 1 ) 2 p i=2 (c t u i ) 2 λ 1 (A) -λ i (A) -τ 2 (c t u 1 ) 4 p i=2 (c t u i ) 2 [λ 1 (A) -λ i (A)] 2 + τ 2 (c t u 1 ) 2 p i=2 p k=2 (c t u i ) 2 (c t u k ) 2 [λ 1 (A) -λ i (A)][λ 1 (A) -λ k (A)] + O(τ 3 ) (42)
and neglecting in the last line the second order term (which is non negative) as well as higher order terms.

Corollary 15 Under assumptions of Proposition 13 we have the following inequality:

(c t v 1 ) 2 (c t u 1 ) 2 + τ (c t u 1 ) 2 p i=2 (c t u i ) 2 λ 1 (A) -λ i (A) + τ 2 (c t u 1 ) 2 p i=2 p k=2 (c t u i ) 2 (c t u k ) 2 [λ 1 (A) -λ i (A)][λ 1 (A) -λ k (A)] (43)
if (c t u i ) 2 (c t u 1 ) 2 for i = 2, . . . , p.

Proof: It should be noted that in Inequality (40) of Proposition 13 the first order term in τ is nonnegative. However writing the second order term as

(c t u 1 ) 2 p i=2 p k=2 k =i (c t u i ) 2 (c t u k ) 2 [λ 1 (A) -λ i (A)][λ 1 (A) -λ k (A)] + (c t u 1 ) 2 p i=2 (c t u i ) 2 [(c t u i ) 2 -(c t u 1 ) 2 ] [λ 1 (A) -λ i (A)] 2 (44)
we see that this term is also non negative under the condition: (c t u i ) 2 (c t u 1 ) 2 for i = 2, . . . , p so that it can be neglected as well as higher order terms.

Finally, the last proposition is similar to Proposition 13 when considering the smallest eigenvalue.

Proposition 16 Assuming that λ p (A) > 0 is simple and that τ is sufficiently small in order to express λ p (B) under the following convergent power

series:

we have he following inequality.

Proof: Since λ p (A) > 0 we know that A is of rank r = p and we have c ∈ range(A). Therefore the inequality can be simply derived using Proposition 12 with u = u p together with [START_REF] Cheng | The bounds of the smallest and largest eigenvalues for rank-one modification of the hermitian eigenvalue problem[END_REF].

Corollaries similar to the two previous ones could be also derived for (c t v p ) 2 but are omitted for the sake of brevity.


Patrick Jermann

Pierre Dillenbourg

Computer Support for Collaborative Learning 1999

Keywords: constructivism, distributed intelligence, shared knowledge

This contribution analyses the arguments of students in a learning activity entitled "Argue Graph". This activity is intended to make students understand the relationship between learning theories and design choices in courseware development. The analysis of arguments is centered on the effects of discussion and opinion conflict on the elaboration of arguments. We then use an adaptation of a collective intelligence model to describe the knowledge flow among people and artifacts during the learning activity. Finally, the representations produced by the system, used by students to write a synthesis and by the teacher to debrief the class are analysed in relation to metacognition. We propose to consider these representations as metacognitive tools which structure the learning activity.

Introduction

TECFA virtual campus relies on design principles drawn from our five-years experience in teaching with Internet. Its audience are 20 students participating to our master in educational technology. They attend courses for one week at the University and then work remotely for 5 to 7 weeks using a combination of media (e-mail, discussion groups, MOOs, phone,...). While most web-based university training is restricted to presenting texts and multimedia documents, our design focuses on learning activities which mediate and organise the access of students to resources. We follow constructivist principles by providing the students with the opportunity to process/produce the knowledge to be acquired instead of simply absorbing it. Although the activities in the TECFA virtual campus rely on Internet tools, they concern both distance teaching and presential interactions. Designing learning activities is relatively easy when the learning goal is an activity itself. For instance, we teach our students how to program with Authorware by asking them to go through a large set of programming exercises. However, when acquiring declarative knowledge (principles, theories, laws, concepts,...) the learning task cannot simply be derived from the task to be mastered. Therefore we have implemented various learning activities that support the acquisition of declarative knowledge. They follow a similar scenario. Students first complete a task not directly related to the target knowledge to be acquired. While they do so, the system records their activity and then produces a synthetic graphical representation of their performance. Finally, the teacher uses this representation to debrief the class. He turns students' experiential knowledge into academic knowledge by putting labels on new concepts and by structuring the outcome. We introduced the notion of pseudo-task to refer to a task which is not the skill to be mastered, but which produces learning by experience. The synthesis provided by the system represents the students as a collectivity. "Collective" differs from "collaborative" due to the fact that it does not necessarily imply rich interactions among students. Simply, the system collects individual productions or data and makes them available for the whole group. Collective representations bring the social plane into the frame of reference used during the debriefing session. [START_REF] Jermann | Dialectics for collective activities: an approach to virtual campus design[END_REF]. This contribution concerns a learning activity entitled "Argue Graph". We first describe the steps which compose it. We then propose an analysis of arguments produced by students during the activity. In the discussion, we use an adaptation of a collective intelligence model [START_REF] Smith | Collective Intelligence in Computer-Based Collaboration[END_REF] to describe the knowledge flow among people and artifacts during the learning activity. We will finally have a closer look at the representations produced by the system, used by students to write a synthesis and by the teacher to debrief the class.

Description of the "Argue Graph" activity

The goal of the "Argue Graph" activity is to make students understand the relationship between learning theories (e.g. constructivism, behaviorism,...) and design choices in courseware development. The scenario consists of six steps: ÷ Students fill in a questionnaire concerning design choices in courseware development (See subsection 'Coding Example' for an example). There are no wrong or correct answers but questions reflect different teaching styles and theoretical backgrounds that the teacher wants to address. ÷ The choices made at step 1 are then transformed into two scores reflecting whether students privilege system-vs. user-driven interactions on the one hand and a discovery vs. teaching based pedagogy on the other hand. The system draws a scatter plot on the basis of these scores and represents each student's position (Figure 1). The rule used to transform answers into scores was not subject to a formal scaling. The purpose of scores is not to diagnose real teaching styles but rather to provide a basis for the rest of the activity. ÷ Pairs are formed so as to maximise distances between students' positions on the graph. Then pairs fill in the same questionnaire. While filling in the questionnaire, they see the arguments they gave to support their answers in the individual phase. They have to agree on a common answer and provide a common argument. ÷ The system produces a synthesis and a scatterplot representing the "migration" of each student from his initial position to the common position. The synthesis lists the individual and common arguments given for each question and draws a pie chart with the distribution of answers. Finally, a brief statement presents the relationship between underlying theories and the options the students can select in a question. ÷ During this debriefing phase, the teacher reviews all arguments produced by individuals and pairs and articulates them with respect to the various theoretical frameworks in the domain. ÷ Finally, students get some homework. They have to analyse the answers to one of the questions including thereby theoretical stakes and their own opinion. This scenario takes 4 hours to complete (without step 6).

Research question

Our experience reveals a high degree of learner involvement during all steps which indicates that this pedagogical scenario works well. However, the tool was not subject to a formal evaluation procedure. Nevertheless, we collected all answers and arguments in order to grasp learning mechanisms. Namely, we investigate the differences between individual answers and pairs answers.

Subjects

We ran two pre-experiments, with 15 students in 1997 and 17 students in 1998 respectively, after which the system was improved with regard to various functionalities. The experiment reported here was run in October 1998 with 18 students. Most students were located in the same quarter of the graph (Figure 1). This phenomenon is probably due to the fact that the questions did too clearly reflect the pedagogical values sponsored at TECFA and did not take into account the technical or financial dimensions of courseware development.

Variables

From now on, we will designate the first time students answer as `solo' condition and the second time as `duo' condition. Since students answer twice to the same questionnaire, we have the opportunity to examine what differentiates answers given alone and in pairs. In these experiments, subjects seat next to each other in front of the machine. We did not record their discussion (this will be done in the next experiment).

Hence, the analysis is restricted to their answers, i.e. the answer selected and the arguments introduced into the system to justify this choice. We describe these answers with three variables:

Category of argument (solo and duo):

÷ Accept: the argument provided supports the option selected, e.g. "I choose option 2 because it makes the learner autonomous". ÷ Discard: the argument rejects another option, e.g. "I choose option 2 because option 3 is too heavy to implement". ÷ Condition: the argument states some conditions for the option selected, e.g. "I choose option 2 if the learner is very young".

Degree of elaboration of argument (solo and duo):

÷ Justification: the argument contains at least one idea not present in the phrasing of the selected option. ÷ Reformulation: the argument does not contain an idea not present in the selected option.

Semantic relation between solo arguments and duo argument:

÷ Union: the duo argument contains the ideas stated by both solo arguments. ÷ Victory: the duo argument contains the ideas of one of the solo arguments. ÷ New: the duo argument contains an idea which is not present in either solo arguments.

Coding example

Table 1 illustrates the usage of this coding scheme for the solo and duo answers of one pair at question 1. Questions 1 is: In a courseware, when a student makes an error, it is better to: ÷ Tell the student he made a mistake and give him the correct answer. ÷ Tell the student he made a mistake and give him an indication towards the correct answer. ÷ Show the student a blinking icon which allows him to ask the tutor for help. ÷ Give the student some time to find out the mistake by himself" The first solo argument (SOLO1) shows a combination of several types of arguments: options 1 and 4 are discarded and options 3 is accepted conditionally. Notice that option 2, which is the actual choice of the student, is not addressed explicitly by the corresponding argument. Arguments with this level of complexity are quite rare, for most of the arguments were coded with a single category and degree of elaboration, like it is the case for the second solo argument (SOLO2). All three arguments were considered as `Justifications' because they contain new ideas with regard to the option stated in the question. The duo argument is `New' with respect to the semantic content, because it introduces the idea of the learner's autonomy which was not stated as such in the solo arguments.

Results

The system collected 180 solo answers and 90 duo answers to the questionnaire respectively. Some answers were incomplete, for instance when a student made a choice without providing an argument. The valid cases remaining for the analysis are 166 solo arguments and 67 duo arguments. The arguments were coded once by the two authors of this contribution and we did not use a second judge to validate the coding. Yet, most of the coding was straightforward.

Conflicts does occur

For 52% of the duo answers there was a conflict between the two solos answers. In other words, the method used to form pairs was rather effective. There is some relation between the distance in the graph and the frequency of conflict (the five pairs with a distance of 1 have a disagreement rate of 38%, while the pairs with a larger distance have a disagreement rate of 52.5%), but the size of the sample is not sufficient to compute a correlation rate. These situations are of particular interest with respect to collaborative interaction because they enable socio-cognitive conflict [START_REF] Doise | Le développement social de l'intelligence[END_REF]): a social conflict (having a different perspective) has to be solved through a cognitive coordination of the points of view. However, further studies showed that conflict is neither a necessary, nor a sufficient condition for cognitive change. Beyond the intensity of conflict, it is the verbalisation necessary to solve the conflict which seems related to learning effects [START_REF] Blaye | Confrontation socio-cognitive et résolution de problème (A propos du produit de deux sous-ensembles[END_REF][START_REF] Butterworth | A brief account of the conflict between the individual & the social in models of cognitive growth[END_REF]. The role of verbalisation in learning is confirmed by the work on reciprocal teaching [START_REF] Brown | Guided cooperative learning and individual knowledge acquisition[END_REF]) and on self-explanation [START_REF] Chi | Self-Explanations: How Students Study and Use Examples in Learning to Solve Problems[END_REF].

The category of arguments varies between solo and duo conditions

Table 2 presents categories of arguments for the solo and duo conditions. We computed three proportion tests to compare the solo and duo conditions. The proportion of `Accept' arguments is similar in both conditions even if significantly higher in the solo condition (p < .05). It appears that the proportion of `Discard' arguments in the solo phase is higher than in the duo phase (p < .05). The proportion of `Condition' arguments is higher in the duo phase than it is in the solo phase (p < .05). We will comment on the `Condition' arguments when examining the effect of conflict on duo arguments. The degree of elaboration of arguments varies between solo and duo conditions Table 3 presents the degree of elaboration of the arguments for the solo and duo conditions. The proportion of `Reformulation' is very high in the solo phase (more than half of the answers are simple reformulations of the choices proposed in the question). This proportion is much lower in the duo phase (p < .05). We interpret this difference as follows. When answering alone, students had no reason to make the effort to justify their choice with an elaborated argument even if they elaborated one in their head. In pairs, the discussion which was necessary to agree on an argument seems to force students to make it explicit and to elaborate it. This interesting observation confirms the usefulness of this method. The difference could however also be due to the fact that student feel obliged to be produce a more elaborated answer when they answer for the second time to the same question.

The category of duo arguments varies according to conflict

Let us now look at the duo arguments. Because we designed the learning activity in order to create conflicts, we focus the analysis around the variable of conflict to see if it has an influence on the category and degree of elaboration of the arguments. Overall, there is not one student who wins all conflicts to the detriment of his colleague. For each AB pair, we counted the number of times that AB's duo answer corresponds to A's previous solo answer, versus the times it corresponds to B's previous solo answer. We thereby observe that pairs are rather symmetrical, the difference ranging between 0 and 2, with the exception of 2 pairs. Table 4 presents the category of duo arguments for situations with and without conflict. In both cases `Accept' arguments are predominant, students give an argument which directly supports their common choice. `Condition' arguments are interesting because they violate the instructions given to the students: they were asked to choose only one possible option and to give an argument supporting it. This way of proceeding corresponds to the production of `Accept' arguments. Paradoxically, the `Condition' arguments match the underlying pedagogical goals of the activity better than the `Accept' type. It is the goal for the students to discover that there is not only one correct theory in courseware design but that each design choice depends on specific contextual features. All but one of the `Condition' arguments are given in a conflictual situation where students have to defend their choice against another's opinion. The production of this category of argument is a way to solve the conflict by complexifying the argument. Indeed, establishing `if..then..else' constructions allows to make concessions to the loser of the conflict.

Unfortunately we cannot compute a reliable Chi-square test to validate these observations.

The semantic relation between solo and duo arguments varies according to conflict

The semantic relation between solo and duo arguments relates to conflict as can be seen in Table 5. When there is no conflict, students often take the arguments they gave in the solo phase and put them together to produce a `Union' argument. The production of a `Victory' argument corresponds to the pair choosing one of the two arguments and use it as duo argument.

When there is a conflict between the choices students made in the solo phase, the `New' and `Victory' arguments are more numerous. A `Victory' in this context corresponds to one student winning the conflict on both aspects of the answer: the choice and the argument. The production of `New' arguments can be understood as a way to handle the conflict. Even if the choice of one student is chosen by the pair, the 'New' argument has no relation with previous solo arguments. Interestingly, 9 out of 12 `Condition' arguments given in the duo phase are at the same time `New' arguments.

Discussion

Answering together to the questionnaire had an impact on the degree of elaboration of arguments (Reformulation vs. Justification) produced by the students. The duo arguments are more elaborated than the solo arguments. We propose that the reason for this change is that students make their opinions explicit and thereby more elaborated during the discussion. The category of arguments (Accept vs. Discard vs. Condition) also varies across solo and duo conditions. `Discard' arguments are more frequent in the solo condition while `Condition' arguments are more frequent in the duo condition.

In the duo condition, half of the cases are conflictual, i.e. students did not make the same choice in the solo condition. `Condition' arguments appear mostly in a conflictual situation. There is also an increased production of semantically 'New' arguments. We interpret that the production these arguments results from a strategy intended to solve the conflict more fairly than by a `Victory' of one of the students. It also indicates that students produce knowledge and explore the domain.

Furthering our study, we propose to broaden the analysis by using a distributed cognition approach. The central idea of the distributed cognition approach is that our object of investigation is no more restricted to `knowledge in the head' as it was in the case of traditional cognitive science, but includes several agents and the artifacts they use to mediate their activity. Authors like [START_REF] Hutchins | The social organization of distributed cognition[END_REF] and [START_REF] Smith | Collective Intelligence in Computer-Based Collaboration[END_REF] analysed the ongoing activity in a system by observing the knowledge flow among different artifacts. As Nardi (1996) points out, there is also a particular interest in the analysis of external and internal representations and of the transformations they undergo when travelling through the system.

We will now describe the learning activity presented above from two viewpoints, knowledge flow and external representations. (1994) proposes a model of collective intelligence restricted to collaborative groups of 3 to 30 individuals working together for a long period of time to build an intellectual product. He presents a knowledge typology based on the information's persistence of display, i.e how long knowledge can be viewed on a particular medium (See also [START_REF] Dillenbourg | The design of MOO agents: Implications from a study on multi-modal collaborative problem solving[END_REF]. Tangible knowledge is persistent and manipulated by individuals. It comprises the final product (called `target product') and `instrumental products' which support the group's work towards the target but are not part of it. Intangible knowledge is not physically accessible and constitutes the shared and private knowledge people have in mind. Ephemeral products which temporarily take a physical form lie between these two types of knowledge. These allow the transformation of knowledge from one type into the other by the contributions of several members of the group. A semi-persistent media is associated to this type of knowledge. We now attempt to use the same terminology to describe the transformations the knowledge undergoes in the learning activity described above.

Knowledge flow model

Smith

Figure 2: Knowledge flow and types in the Argue-Graph learning activity, adapted from [START_REF] Smith | Collective Intelligence in Computer-Based Collaboration[END_REF]. P=Private; S=Shared; I=Instrumental; T=Target. Numbers represent steps in the activity. During steps 1 and 2, private intangible knowledge becomes shared through the mediation of an ephemeral representation. According to Smith's model, ephemeral knowledge is built by the people themselves. In our case, the system produces a collective representation of the individuals' opinions (Figure 1). Since this representation is accessible to everyone, the students' opinions are already shared to some extent. Students don't know the detailed positions of each of their colleagues but they get an overview of the diversity of opinions. We have labelled this collective representation with the term `social'. In step 3, the passage between private and shared knowledge is more fine grained than in step 1 and 2 because two students have to explicit and discuss their specific choices. There is no physical intermediate representation mediating the transformation of private to shared knowledge. But the questionnaire the students fill in contains the answers and arguments they gave at step 1 and they can rely on these informations to structure their discussion. Smith's model does not include collaborative interactions between two persons. According to Smith's typology the knowledge produced during the argumentative process is not observable and should be labelled intangible. Nevertheless, we propose to add an interindividual ephemeral knowledge type to refer to the process of discussion, which mediates the passage between private and shared knowledge.

Step 4 consists in an instrumental representation. It is persistent and will be used to produce target knowledge. It shows all the arguments and the answers to the questionnaire in a tangible manner accessible to everyone.

Step 5 transforms the instrumental knowledge into private intangible knowledge. The teacher uses the instrumental knowledge produced by the system in step 4 to debrief the class. He reorganises the arguments and puts `scientific' labels on them.

Step 6 is individual and transforms intangible private knowledge students have acquired during the debriefing into tangible target knowledge: students have to choose one of the questions from step 1 and write a short synthesis containing related theoretical stakes and their personal opinion. Students intensively used the instrumental knowledge from step 4 to compose their synthesis. It appears in the model we just described that the knowledge to be acquired stems from a construction where students take an active role. Most of the arguments in favour or against the learning theories appear in the answers given by the students. Knowledge is mediated by various artefacts like graphs, discussions, syntheses. The level of interaction between people also varies from dyadic argumentation to group discussion during the debriefing. Can we deduce that the richer the environment and the interactions it supports, the better the learning? It is certainly not this trivial but the redundancy of information [START_REF] Hutchins | The social organization of distributed cognition[END_REF] may play a positive role in knowledge acquisition.

Collective representations as a support for learning [START_REF] Nickerson | On the distribution of cognition: some reflections[END_REF] addresses the question whether a group of people have metaknowlege. Metacognition has multiple meanings, ranging from the knowledge an individual has of his own mental activity to action regulation and control processes, for instance planification of the activity, supervision of the effects of actions. Finally, metacognition also comprises conception an intuitions the subjects has about the situation he's in [START_REF] Schoenfeld | What's All the Fuss About Metacognition[END_REF]. We used Nickerson's hypothesis on group metacognition as a starting point for the design of several pedagogical scenarios with the common goal to acquire declarative knowledge. The "Argue Graph" activity described in the beginning of this paper is one of those. Some other activities also use representations of students' performance in a pseudo-task. In the "ergonomics laboratory" a bar chart illustrates measures of students' performance when using the six interfaces (number of errors, time,...). In the "Multiple choice questionnaires defects" activity, a scatter plot illustrates the mismatch between the students' self-evaluation of their competence in a domain and the real scores they get. A detailed description of these activities can be found in Jermann, Dillenbourg & Brouze (op. cit.). The collective representations we described present various aspects of differentiation (either between interfaces or between self-evaluation and score or between opinions). We have interpreted the efforts to understand the differences that appear in the representation of performances as being a major source of learning in a previous contribution (Jermann, Dillenbourg & Brouze, op. cit.). These collective representations and syntheses give a trace of the group activity. In some cases, when the students' names appear, they can deduce information about their own behaviour from the representation. When this is not the case, they get a global image of the group. It is not clear though if knowledge like `we have different opinions', `we all make the same mistakes', `we all overestimated our competence' or `I am an extremist', `I succeeded better than my colleagues' have the same impact. We saw that students were fond of representations where they could see their own position and it seems that the comparison with others is strongly motivating. From a metacognitive viewpoint, the representations are used as tools which guide and motivate the construction of knowledge. Students take over the knowledge by interpreting the graphs and data they get.

Conclusion

This contribution presented an analysis of arguments produced by students in a learning activity entitled "Argue Graph" where students twice answer to a questionnaire, a first time alone and then in pairs. We observed that answering in pairs had a positive impact on the elaboration of arguments provided to justify the choices in the questionnaire. We interpreted the improvement of arguments as stemming from the discussion necessary to give a common answer. Students make their opinions explicit and thereby more elaborated during the discussion. We then used a distributed cognition approach to analyse the "Argue Graph" learning activity. [START_REF] Smith | Collective Intelligence in Computer-Based Collaboration[END_REF] model of collective intelligence allowed us to describe the transformations knowledge undergoes during the learning process. Following [START_REF] Nickerson | On the distribution of cognition: some reflections[END_REF] we addressed the question of collective metacognition and proposed to consider collective representations as tools which guide the knowledge acquisition.

Figure 1 :

 1 Figure 1: Scatterplot of individual answers. The students' position in the graph represent their teaching style, as inferred from their answers. The horizontal axis opposes system vs. learner driven interaction. The vertical axis opposes discovery based learning vs. teaching. Names of students have been removed from this figure for confidentiality.

Table 1 :

 1 Coding example Conf lictIf he is directly given the correct answer, he might not remember it, if we don't say anything, he might not be aware of his error... The help icon is certainly a good solution, if one can see clearly that it gives help and that it appears only on errors.

	Opt ion	Argument (we translate)

Table 2 :

 2 Category of arguments across Solo and Duo conditions

	Solo	%	Duo %	u

Table 3 :

 3 Degree of elaboration of the arguments across Solo and Duo conditions

	Solo %	Duo %	u

Table 4 :

 4 Conflict and type of arguments

	Duo type of argument

Table 5 :

 5 Conflict and Semantic relation between solo arguments and duo argument

	(X2= 6.136, p = .047)	Relation between solo and duo arguments
			New	Union	Victory	Total
	Conflict	NO	6	16	10	32
		YES	14	8	13	35
	Total		20	24	23	67

Acknowlegments

TECFA Virtual Campus has been developed with the help of Cyril Roiron, David Ott, Daniel Schneider, Daniel Peraya, Patrick Mendelsohn, Philippe Lemay and Didier Strasser.

Authors' addresses

Patrick Jermann (Patrick.Jermann@tecfa.