Jean-Baptiste Hiriart-Urruty

Jérôme Malick

Michel Théra

A Fresh Variational-Analysis Look at the Positive Semidefinite Matrices World

Keywords: positive semidefiniteness, optimization, convex analysis, eigenvalues, spectral functions, Riemannian geometry AMS Classifications: 65K10, 90C22, 15A18 1

come   L'archive ouverte pluridisciplinaire

In this article, we gather some results about positive (semi)definite matrices: some are wellknown, some are more original, all have interest. The special feature of this paper is that we adopt the viewpoint of variational analysis, shedding new light on these topics. The term "variational" is not to be understood in its old historical meaning (calculus of variations), but in the broadest possible sense (optimization, convex analysis, nonsmooth analysis, complementary problems,...). We insist in particular on the harmonious interplay between matrix analysis and optimization.

The set of positive semidefinite matrices is a closed, convex cone in the space of symmetric matrices, which enjoys a nice geometry, exploited in several applications. We review some of these useful and sometimes subtle geometrical properties -again with a variational eye. During this study, we will illustrate convex, semialgebraic and Riemannian geometries. As a nice, concrete example of advanced mathematics, positive semidefiniteness also has some pedagogical interest -on top of all its practical uses.

Positive (Semi)Definiteness: a Multi-Facet Notion

We start with a bunch of simple ideas. The goal of this first section is, while sticking to basic properties, to show how different notions and various domains come into play when talking about positive semidefinite matrices. We also recall the background properties, introduce notation, and give a flavour of what comes next.

Let S n (R) be the linear space of symmetric real matrices of size n×n. A matrix A ∈ S n (R) is said to be positive semidefinite (denoted A 0), if

x ⊤ A x ≥ 0 for all x ∈ R n , (1)
where the superscript • ⊤ denotes the transposition of matrices. The matrix A is further called positive definite (denoted by A ≻ 0) if the above inequality is strict for all nonzero x.

2.1 (Bi)Linear Algebra at Work.

Let us recall the key-result for symmetric matrices: the n eigenvalues λ i of a matrix A ∈ S n (R) lie in R, and there exists an orthogonal matrix U such that U ⊤ AU is the diagonal matrix with the λ i on the diagonal, denoted by diag(λ 1 , . . . , λ n ). This result can also be written as follows: there exist n unit eigenvectors x i of A (the columns of U ) such that we have the so-called spectral decomposition

A = n i=1 λ i x i x i ⊤ .
This result mixes nicely linear and bilinear algebra: U allows both the diagonalization of A as U -1 AU = diag(λ 1 , . . . , λ n ) (linear algebra world), and the reduction of the quadratic form associated with A as U ⊤ AU = diag(λ 1 , . . . , λ n ), such that A(U y), U y = diag(λ 1 , . . . , λ n )y, y (bilinear algebra world). There are several proofs of this result; one is optimization-based (see e.g. [8, p.222]). This decomposition is used to define the square root matrix: if A 0, the square root of A, denoted by A 1/2 , is the unique S 0 such that S 2 = A (given explicitly by the decomposition U ⊤ SU = diag( √ λ 1 , . . . , √ λ n )). When A ≻ 0, we also have (A 1/2 ) -1 = (A -1 ) 1/2 so that the notation A -1/2 (that we will often use) is not ambiguous.

We can also reduce two matrices at the same time: the so-called simultaneous reduction (see e.g. [1, 4.6.12]) says that for a symmetric matrix A and a positive definite matrix B, there exists an invertible matrix P such that P ⊤ AP = diag(λ 1 , . . . , λ n ) and P ⊤ BP = diag(µ 1 , . . . , µ n ).

We are not aware of simple results of that kind for more than two matrices; the reason might be deeper than one would think (see Problem 12 in [9]).

Inner Products.

The space R n is equipped with the canonical inner product

x, y := n i=1

x i y i = x ⊤ y.

We prefer to use the notation •, • , often more handy for calculation involving the transpose. Up to a double sum, this inner product is the same for symmetric matrices: we equip S n (R) with the canonical inner product

A, B := n i,j=1
A ij B ij = trace(A ⊤ B) = trace(AB).

A connection between these two scalar products is

Ax, x = A, xx ⊤ .
This easy property has an important role in combinatorial optimization: the so-called "lifting" is the first step of the semidefinite relaxation of binary quadratic problems (see e.g. [START_REF] Poljak | A recipe for semidefinite relaxation for (0,1)quadratic programming[END_REF]). Another interesting connection between the inner products is the Ky-Fan inequality: A, B ∈ S n (R) satisfy the inequality A, B ≤ λ(A), λ(B) ,

where λ(A) := (λ 1 (A), . . . , λ n (A)) ∈ R n is the vector of the eigenvalues of A ordered nonincreasingly. Moreover equality holds in the above inequality if and only if A and B admit a simultaneous eigendecomposition with ordered eigenvalues (see e.g. [START_REF] Borwein | Convex Analysis and Nonlinear Optimization[END_REF] and references therein). This inequality is a key tool for the study of spectral functions and spectral sets [START_REF] Lewis | Nonsmooth analysis of eigenvalues[END_REF]; we will come back to spectral sets from time to time in next sections.

Quadratic Forms and Differential Calculus.

Naturally associated with A ∈ S n (R) is the quadratic form

q : x ∈ R n -→ q(x) := 1 2 Ax, x .
The definition of semidefiniteness (1) reads q(x) ≥ 0 for all x ∈ R n . From an optimization point of view, we have inf x∈R n q(x) > -∞ ⇐⇒ A 0 and the set of minimizers is then ker A. The quadratic form q is obviously of class C ∞ on R n , and we have for all

x ∈ R n ∇q(x) = Ax and ∇ 2 q(x) = A. (2)
This is easy to remember: we formally have the same formulae for q(x) = ax 2 /2 with x ∈ R. Note that the factor 1/2 in the definition of q aims at avoiding the factor 2 when differentiating q.

When A is positive definite, q defines a norm on R n . This can be seen for example by the simultaneous reduction: there exists P invertible such that P ⊤ AP = I n , or in other words, up to the change of variables y = P -1 x, the quadratic form q is just the simpler form • 2 : y 2 = y, y = P ⊤ AP y, y = AP y, P y = Ax, x .

2.4 When Convex Analysis Enters Into the Picture.

Recall that a function

f : R n → R is convex if ∀x, y ∈ R n , α ∈ [0, 1], f (αx + (1 -α)y) ≤ αf (x) + (1 -α)f (y).
When f is smooth, convexity is characterized by the positive semidefiniteness of its Hessian matrix ∇ 2 f (x) for all x ∈ R n (see e.g. [13, B.4.3.1]). From (2), we get that q is convex if and only if A 0. (Let us also mention that strict and strong convexities of q coincide and are equivalent to A ≻ 0.)

During our visit to the world of the positive semidefinite matrices, we will meet several notions from convex analysis (polar cone, Moreau decomposition, tangent and normal cones,...). The first notion is the Legendre-Fenchel transformation, which is an important transformation in convex analysis (see [13, Chap.E]) introducing a duality in convex optimization. The Legendre-Fenchel transformation defined by

q * : s ∈ R n -→ q * (s) := sup x∈R n { s, x -q(x)} ,
has a simple explicit expression for q(x) = Ax, x /2 (with A 0). In the case A ≻ 0, we obtain

q * (s) = 1 2 A -1 s, s .
Incidentally, this expression allows us to establish B -1 ≺ A -1 if B ≻ A, with a quickly variational proof (first use the fact that q ≤ p implies q * ≥ p * , and then the fact that B -A ≻ 0). This latter result is the matrix counterpart of the decreasing of the inverse for positive numbers. Note moreover that the involution A → A -1 of linear algebra corresponds to the involution q → q * of convex analysis. If we just have A 0, then (see e.g. [13, E.1.1.4])

q * (s) = 1 2 x 0 , s where Ax 0 = s if s ∈ Im A +∞ if s ∈ Im A.
Note finally that making the transformation twice, we come back home: (q * ) * = q, as expected.

Do Not Forget Geometry.

A geometrical view is often used to introduce linear algebra (as in textbook [START_REF] Strang | Introduction to linear algebra[END_REF]). The geometrical object also associated with a matrix A ≻ 0 is the ellipsoidal convex compact set

E A := {x ∈ R n : Ax, x ≤ 1}.
The eigenvalues of A give the shape of E A (see [START_REF] Strang | Introduction to linear algebra[END_REF]Chap. 6]); it is the unit ball of the norm given by A. The linear function A -1/2 maps the canonical unit ball B to E A ; so the volume of E A is 1/ det(A) times the volume of B (see Problem 3 in [START_REF] Hiriart-Urruty | Potpourri of conjectures and open questions in nonlinear analysis and optimization[END_REF] for a question on the volume of convex bodies). We mention that the inversion A → A -1 coincides for E A with the polarity transformation of convex compact bodies having 0 in the interior (see [13, Chap. C]).

Convex Cone, Visualisation.

The set of positive semidefinite matrices

S n + (R) = A ∈ S n (R) : x ⊤ A x ≥ 0 for all x ∈ R n (3)
enjoys a nice geometry. We give here a first flavour of its geometry when n = 2 and we will come back to this topic again in Section 4.

It is not difficult to show by means of definition (3) that

S n + (R) is a (closed) convex cone. Recall that this means α ∈ [0, 1], A, B ∈ S n + (R) =⇒ αA + (1 -α)B ∈ S n + (R), α ≥ 0, A ∈ S n + (R) =⇒ αA ∈ S n + (R). Since S 2 (
R) is of dimension 3, we can visualize the cone S 2 + (R) as a subset of R 3 . We identify S 2 (R) and R 3 by an isomorphism

ϕ : A = a b b c ∈ S 2 (R) -→ ϕ(A) ∈ R 3 .
We can choose the isometry ϕ(A) = (a, √ 2b, c), but the best looking isomorphism is

ϕ(A) := 1 √ 2 (2b, c -a, c + a)
that allows us to identify the cone S 2 (R)

a b b c : a ≥ 0, c ≥ 0, and ac -b 2 ≥ 0 . with ϕ(S 2 (R)), which is (x, y, z) ∈ R 3 , z ≥ x 2 + y 2 .
Figure 1 shows that ϕ(S 2 (R)) is the "usual" cone K of R 3 , also called Lorentz cone or secondorder cone in R 3 . The boundary of K corresponds to the rank-one matrices, and the apex of K to the zero matrix. To avoid giving an incorrect intuition, we emphasize that even if the boundary of S 2 + (R) deprived from 0 appears to be a smooth manifold, this is not true in general when n > 2 (S n + (R) is in fact the union of smooth manifolds; see Section 4.4).

3 Characterizations of Positive (Semi)Definiteness

Characterizations of Positive Definiteness

The characterizations of positive definiteness are numerous; each of them has its own usefulness, depending on the context. For example, the Gram formulation appears naturally in statistics, the characterization by invariants in mechanics, or the exponential in dynamical systems. We discuss some of these characterizations here: we start with a couple of characterizations that use decompositions; then, we put emphasis on the characterizations by the positivity of n real numbers; we finish with a more original characterization.

Factorization-Like Characterizations

One of the most useful and most basic characterizations is the following factorization: A is positive definite if and only if there exists B invertible such that A = BB ⊤ (indeed in this case Ax, x = Bx 2 for all x ∈ R n ). There exist in fact different factorizations of this form, among those: the Cholesky factorization with B upper-triangular with positive diagonal elements; and the square root factorization, with B symmetric positive definite (see e.g. [START_REF] Zhang | Matrix Theory[END_REF]Chap. 6]).

Other famous decomposition-like characterizations use exponential or Gram matrices: the property A ≻ 0 is characterized by each of the two properties:

• Exponential form (see e.g. [START_REF] Hiriart-Urruty | Exercices d'algèbre linéaire et bilinéaire[END_REF]): there exists B ∈ S n (R) such that A = exp(B).

• Gram form (see e.g. [1, 7.2.40]): there exists a n independant vectors {v 1 , . . . , v n } of R n (hence forming a basis of R n ) such that A ij = v i , v j for all i, j.

Positivity of n Real Numbers

Important characterizations of positive definiteness rely on the positivity of n real numbers associated with symmetric matrices. For example, it is well-known that positive eigenvalues characterize positive definiteness; we gather in next theorem three similar properties.

Theorem 3.1 (Positive definiteness by positivity of n real numbers). Each of the following properties is equivalent to A ≻ 0:

(i) the eigenvalues λ 1 (A), . . . , λ n (A) of A are positive;

(ii) the leading principal minors ∆ 1 (A), . . . , ∆ n (A) of A are positive;

(iii) the principal invariants i 1 (A), . . . , i n (A) are positive.

We recall that the leading principal minors are defined as ∆ k (A) := det A k for k = 1, . . . , n, where A k is the submatrix of A made of the first k rows and first k columns of A. Recall also that the principal invariants of A are (up to a change of sign) the coefficients of the monomials of the characteristic polynomial P A (x) of A; more precisely

P A (x) = (-x) n + i 1 (A)(-x) n-1 + • • • + i k (A)(-x) n-k + • • • + i n (A), whence i k (A) := 1≤n 1 <•••<n k ≤n λ n 1 (A)λ n 2 (A) • • • λ n k (A) (4)
where the eigenvalues λ i (A) are the roots of P A . For example

i 1 (A) = trace(A) = λ 1 (A) + • • • + λ n (A) and i n (A) = det(A) = λ 1 (A) • • • λ n (A).
Another definition of i k (A) is i k (A) := sum of the principal minors of order k of A.

A principal minor of order k is the determinant of the k × k matrix extracted from A by considering the rows and columns n 1 , . . . , n k with 1

≤ n 1 < • • • < n k ≤ n.
Proof. (of Theorem 3.1). There are several ways to prove (ii): for instance, by purely linear algebra techniques, by induction [1, p.404], or by quadratic optimization techniques [8, p.220], [15, p.409]. The result also follows from the factorization of a matrix in a product of triangular matrices; we sketch this proof (see more in [START_REF] Hiriart-Urruty | Exercices d'algèbre linéaire et bilinéaire[END_REF]).

Let A ∈ S n (R) such that ∆ k (A) = det(A k ) = 0
for all k = 1, . . . , n. Then there exists a (unique) lower triangular matrix with ones on the diagonal, denoted by S, such that

A = SDS ⊤ where D = diag ∆ 1 (A), ∆ 2 (A)/∆ 1 (A), . . . , ∆ n (A)/∆ n-1 (A) .
We call

d 1 := ∆ 1 (A), d k := ∆ k (A)/∆ k-1 (A) the so-called (principal) pivots of A. So we have A ≻ 0 ⇐⇒ (d k > 0 for all k = 1, . . . , n) ⇐⇒ (∆ k (A) > 0 for all k = 1, . . . , n).
Then it is easy to establish characterization (ii).

Let us prove here characterization (iii) which is less usual. One implication comes easily: if A ≻ 0, then all the eigenvalues of A are positive; each i k (A) is then positive as well (recall ( 4)). To establish the reverse implication, we assume that i k (A) > 0 for all k, so in particular det(A) > 0. Suppose now that there exists a negative eigenvalue of A, call it λ i 0 (A) < 0. Then observe that

0 < P A (λ i 0 (A)) = (-λ i 0 (A)) n + • • • + i k (A)(-λ i 0 (A)) n-k + • • • + i n (A)
which contradicts the fact that P A (λ i 0 (A)) = 0. Thus we have λ i (A) ≥ 0 for all i, and since 0 < det(A) = λ 1 (A) • • • λ n (A), we get that λ i (A) > 0 for all i, which guarantees that A is positive definite.

Example 3.1 (Invariants in dimension 2 and 3). Let us illustrate in small dimension the third point of the previous theorem. In the case n = 2, we have the simple formulation

P A (x) = x 2 -trace(A)x + det A.
We note by the way that this is a particular case of the development

det(A + B) = det A + cof A, B + det B = det A + A, cof B + det B,
where cof M stands for the cofactors matrix of the matrix M (in general, this development is obtained by differential calculus with the fact that the determinant is multilinear, see [START_REF] Azé | Calcul différentiel et équations différentielles[END_REF]). Let us come back to our situation: the two principal invariants of A are trace A and det A, so we have

a b b c ≻ 0 ⇐⇒ a > 0 ac -b 2 > 0 ⇐⇒ a + c > 0 ac -b 2 > 0.
For the case n = 3, we have

P A (x) = -x 3 + trace(A)x 2 -trace(cof A)x -det A.
which is again a particular case of the nice formula

det(A + B) = det A + cof A, B + A, cof B + det B.
The three principal invariants are

i 1 (A) = traceA = λ 1 (A) + λ 2 (A) + λ 3 (A) i 2 (A) = (traceA) 2 -trace(A 2 ) /2 = λ 1 (A)λ 2 (A) + λ 2 (A)λ 3 (A) + λ 1 (A)λ 3 (A) = trace(cof(A)) i 3 (A) = (traceA) 3 -3trace(A)trace(A 2 ) + 2trace(A 3 ) /6 = λ 1 (A)λ 2 (A)λ 3 (A) = det A. Thus we have   a b d b c e d e f   ≻ 0 ⇐⇒    a > 0 ac -b 2 > 0 det A > 0 ⇐⇒    a + c + f > 0 (cf -e 2 ) + (af -d 2 ) + (ac -b 2 ) > 0 det A > 0 ,
which gives a handy characterization in dimension 3. These principal invariants are widely used for n = 3 in mechanics where they often have a physical interpretation (for example as stresses and strains); see the textbook [START_REF] Truesdell | A First Course in Rational Continuum Mechanics: General Concepts[END_REF].

Characterization by Polar Cones

Here is now a more original characterization, using convex cones in R n . We start by recalling some convex analysis that is needed; those notions (polar cones and Moreau polar decomposition) have some interest of their own, and turn out to be less known than they deserve (see, for more details, [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]).

If K is a closed, convex cone in a Euclidean space (E , •, • ), then the polar cone K • of K is the closed, convex cone of E made of all the points whose projection onto K is 0; in other terms,

K • := {s ∈ E : s, x ≤ 0, for all x ∈ K}. (5)
Examples: for

K = R n + , we have K • = R n -; for a linear subspace K = V , we have K • = V ⊥ .
We see that polarity is to (closed) convex cones what orthogonality is to linear subspaces. The fundamental result on this polarity is its reflexivity: doing the polar transformation twice leads back home, i.e. (K • ) • = K. Another result that we will need later (and that is easy to prove from the definition) is that for an invertible matrix B, we have

[B(K)] • = B -⊤ (K • ). ( 6
)
The most important result on polar cones is with no doubt the following Moreau decomposition. Let x, x 1 and x 2 be three elements of E ; then the properties (i) and (ii) are equivalent:

(i) x = x 1 + x 2 with x 1 ∈ K, x 2 ∈ K • and x 1 , x 2 = 0; (ii) x 1 = Proj K (x) and x 2 = Proj K • (x).
Here Proj C stands for the projection onto the closed, convex set C. The decomposition of R n on K and K • generalizes the decomposition of R n as the direct sum of a linear space L and its orthogonal complement L ⊥ . Note that if we know how to project onto K, we get as a bonus the projection onto K • , which could be interesting in practical cases when K • is more complicated than K (or the other way around).

Let us come back to matrices and prove the following original characterization of positive definiteness.

Proposition 3.1. Let A ∈ S n (R) be invertible and K be a closed, convex cone of R n ; then

A ≻ 0 ⇐⇒ Ax, x > 0 for all x ∈ K {0} and A -1 x, x > 0 for all x ∈ K • {0}.
Note the nice symmetry of the result since (A -1 ) -1 = A and (K • ) • = K. This characterization, whose proof is not straightforward, is due to [START_REF] Han | Conjugate cone characterization of positive definite and semidefinite matrices[END_REF]. We present here a proof, suggested by X. Bonnefond, that uses the Moreau decomposition, as expected.

Proof. The fact that the condition be necessary follows directly from the definition of positive definiteness; we focus on sufficiency. Let A be an invertible matrix satisfying the condition, and consider an eigendecomposition A = U DU ⊤ (where D = diag(λ 1 , . . . , λ n ) with nonzero λ i ). Observe first that up to a change of cone (K ← U ⊤ K), we can assume that A be diagonal: the condition can indeed be written, with the help of (6), as

Dx, x > 0 for all x ∈ U ⊤ K {0} D -1 x, x > 0 for all x ∈ U ⊤ K • {0} = (U ⊤ K) • {0} .
So we consider that A = D is diagonal, and we just have to prove that the condition

           n i=1 λ i x 2 i > 0 for all x ∈ K {0} n i=1 1 λ i x 2 i > 0 for all x ∈ K • {0}
yields that all the λ i are strictly positive.

For the sake of contradiction, assume that only the k (with k < n) first eigenvalues λ 1 , . . . , λ k be positive, while the n -k last λ k+1 , . . . , λ n be negative. We do one more step of simplification of the expression by scaling the variables by

S = diag( |λ 1 |, . . . , |λ n |): introducing K := SK, we observe that              k i=1 y 2 i > n i=k+1 y 2 i for all y ∈ K {0} k i=1 z 2 i > n i=k+1 z 2 i for all z ∈ S -1 K • {0} = K • {0} . (7)
After multiplying these two inequalities together, the Cauchy-Schwarz inequality yields

∀y ∈ K {0}, z ∈ K • {0}, k i=1 y 2 i k i=1 z 2 i > n i=k+1 z i y i 2 . ( 8
)
We apply this inequality to a well-chosen couple of vectors y and z to get a contradiction. Consider the basis vector e = (0, . . . , 0, 1) and note that e does not lie in K nor in K • . So its Moreau decomposition gives

e = y + z with y ∈ K {0}, z ∈ K • {0} and y, z = 0.
Observe that we have z i = -y i for all i = 1, . . . , k so that

k i=1 z 2 i = k i=1 y 2 i .
Now the orthogonality of y and z gives n i=k+1

z i y i = - k i=1 z i y i = k i=1 y i 2 .
This contradicts [START_REF] Alexeev | Recueil de problèmes d'optimisation[END_REF], so proves that k = n, which establishes the characterization.

Characterizations of Positive Semidefiniteness

Most of the characterizations of positive definiteness have their positive semidefiniteness counterparts. In this section, we briefly highlight some similarities and differences between the positive definite and semidefinitenesses.

The property A 0 is equivalent to each of the following statements.

• There exists a matrix B such that A = BB ⊤ . This can also be read as: the quadratic form q A (x) = B ⊤ x 2 is zero on ker B = ker A.

• The eigenvalues λ 1 , . . . , λ n of A are non-negative. The set S n + (R) can thus be seen as the inverse image of R n

+ S n + (R) = λ -1 (R n +
) by the eigenvalue function λ : S n (R) → R n assigning to a symmetric A its eigenvalues in a nonincreasing order. The convex set S n + (R) is then a convex spectral set in the sense of [START_REF] Lewis | Nonsmooth analysis of eigenvalues[END_REF]. Note that, more generally, we can prove that a spectral set λ -1 (C) is convex if and only if C is convex.

• For k = 1, . . . , n, all the principal minors of order k of A are non-negative. This means that the determinants of all the submatrices made of k rows and k columns should be nonnegative -and not only the n leading principal minors ∆ k (A) of Theorem 3.1. Having only ∆ k (A) ≥ 0 does not guarantee semidefiniteness, as shown by the following counter-example where A is not semidefinite positive (it is actually semidefinite negative)

A = 0 0 0 -1 , and det A 1 = det A 2 = 0.
In general, checking all the principal minors to draw a conclusion about the positive semidefiniteness would mean checking 2 n -1 polynomial relations -and not only n as for the positive definiteness, which is a surprising gap! In the next characterization though, only n polynomial relations come into play.

• The principal invariants i 1 (A), . . . , i n (A) are non-negative. This is a sort of aggregate form of the previous condition, since for all k, the invariant i k (A) is the sum of n k principal minors. Checking the positivity of those n polynomial relations does yield semidefinite positiveness. The proof is conducted in the same way as for (iii) in Theorem 3.1 (see [1, p.403]). Counting the number of principal minors involved in this characterization by the i k (A), we naturally retrieve 2 n -1 since

n 1 + n 2 + • • • + n n = 2 n -1.

Geometry of the Set of Positive (Semi)Definite Matrices

The set S n + (R) of positive semidefinite matrices is a closed, convex cone of S n (R) that enjoys nice, subtle geometrical properties. Some aspects are exposed in this section; we see the cone S n + (R) as a concrete example to illustrate various notions of convex geometry and smooth geometry.

Closedness by Matrix Operations

Closedness by Additions. As a convex cone, S n + (R) is closed by addition and by multiplication by α ≥ 0. We can add moreover the following property (easy to see by definitions)

(A 0, B ≻ 0) =⇒ A + B ≻ 0.
The cone S n + (R) is also closed by another addition, the so-called parallel sum. When A ≻ 0 and B ≻ 0, the parallel addition is defined by

A / /B := (A -1 + B -1 ) -1 .
Since both the inversion and the sum preserve S n ++ (R), the parallel addition preserves it as well. This operation was introduced [START_REF] Anderson | Series and parallel addition of matrices[END_REF] by analogy with electrical networks: by the Kirchhoff law, two wires of resistances r 1 and r 2 connected in parallel have a total resistance r such that 1/r = 1/r 1 + 1/r 2 . When A, B 0, we could define A / /B using pseudo-inversion (see e.g. [START_REF] Bhatia | Positive definite matrices[END_REF]). It turns out that this sum has also a natural variational-analysis definition (see e.g. [START_REF] Azé | Analyse variationnelle et optimisation[END_REF]Prob. 25]) as (A / /B)x, x = inf y+z=x { Ay, y + Bz, z }.

We recognize this as the infimal convolution of the two quadratic forms q A and q B ; this operation is basic and important in convex analysis (see [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]Chap.B]).

Closedness by Multiplications. The product of two positive semidefinite matrices is not positive semidefinite in general: the matrix product destroys symmetry. There is no way to get out of this since we have the following (rather surprising) result:

Any n × n-matrix A can be described as the product of two symmetric matrices. This result is presented by [START_REF] Taussky | The role of symmetric matrices in the study of general matrices[END_REF] and [START_REF] Bosch | The factorization of a square matrix into two symmetric matrices[END_REF] that give credit to G. Frobenius (1910). A quick way to prove it is to use the fact that a matrix A and its transpose are similar: there exists an invertible S ∈ S n (R) (non-unique, though) such that A ⊤ = S -1 AS [START_REF] Taussky | On the similarity transformation between a matrix and its transpose[END_REF]. As a consequence, we can decompose A = S 1 S 2 with S 1 = SA ⊤ (which is symmetric by choice of S) and S 2 = S -1 which is symmetric.

Let us come back to (non)closedness by multiplication and give a positive result. Imposing a posteriori symmetry solves indeed the problem: if A, B 0 then the product AB is positive semidefinite whenever it is symmetric -that is exactly when A and B commute. We add here two (not well-known) results of the same kind:

• Result of E. Wigner [START_REF] Wigner | On weakly positive matrices[END_REF]. If A 1 , A 2 , A 3 ≻ 0 and the product A 1 A 2 A 3 is symmetric, then it is positive definite.

• Result of C. Ballantine [START_REF] Ballantine | Products of positive definite matrices iii[END_REF]. Except when A = -λI n with λ > 0 and n even, any square matrix with positive determinant can be written as the product of four positive definite matrices. (For the case left aside, five positive definite matrices are needed.)

We also mention that, for another nonstandard matrix product, S n + (R) is closed without any further assumption. If A = (a ij ) and B = (b ij ), we define the matrix product

C = A • B = (c ij ) by c ij = a ij b ij
for all i, j. Result: if A and B are positive definite (resp. semidefinite) then so is the product A • B (see [1, 7.5.3]).

Convex Sets Attached with S n

+ (R)

Interior and Boundary

The (relative) interior of a convex set is always convex; here the interior of S n + (R) turns out to be exactly S n ++ (R). This is another appearance of the analogy with R + , since the interior of (R + ) n is (R ++ ) n . The boundary of S n + (R) is exactly made up of the singular matrices A 0. There we find the positive semidefinite matrices of rank k, for 1 ≤ k ≤ n -1, forming smooth manifolds fitting together nicely (see Section 4.4).

The Facial

Structure of S n + (R) A convex subset of F ⊂ C is a face of C if every segment [a, b] ⊂ C such that there exists an element of F in ]a, b[ is entirely contained in F . All the faces of S n + (R) are moreover exposed faces: a face F of S n + (R) is the intersection of S n + (R)
with a supporting hyperplane (that is a hyperplane H such that S n + (R) is entirely contained in one of the closed halfspaces delimited by H). More precisely, the result is the following (see [START_REF] Lewis | Eigenvalue-constrained faces[END_REF] pointing to earlier references and discussing about the generalization to spectral sets): F is a face of S n + (R) if and only if F is the convex cone spanned by vv ⊤ : v ∈ V where V is a subspace of R n . The dimension of F is then d(d + 1)/2 if d is the dimension of V . For example with n = 2: there is a face of dimension 0 (the apex of the cone S n + (R)), faces of dimension 1 (extremal rays of S + 2 (R) directed by vectors xx ⊤ with nonzero x ∈ R n ), and a face of dimension 3 (the whole S ++ 2 (R)). There is another way to generate all the faces of S n + (R), as follows. Let L be a linear subspace of R n of dimension m, and set

F L := A ∈ S n + (R) : L ⊂ ker A ;
then F L is a face of S n + (R) of dimension r(r + 1)/2 with r = n -m. When L ranges all the subspaces of dimension m, F L visits all the faces of dimension r(r + 1)/2.

Let us mention that the knowledge of the faces of S n + (R) is useful to for some optimisation problems with semidefinite constraints. Indeed, the so-called "facial reduction technique" uses the explicit form of the faces to reformulate degenerate semidefinite optimization problems into problems in smaller dimension; see the initial article [START_REF] Borwein | Facial reduction for a cone-convex programming problem[END_REF], and the recent [START_REF] Krislock | Explicit sensor network localization using semidefinite representations and facial reductions[END_REF] for an application to sensor network problems.

Polar Cone and Projection

In the space S n (R) equipped with the inner product •, • , the polar cone (5) of

K = S n + (R) is simply K • = -S n + (R).
It is also easy to determine the Moreau decomposition of a matrix A ∈ S n (R) onto S n + (R) and its polar. Indeed consider an orthogonal eigendecomposition U ⊤ AU = diag(λ 1 , . . . , λ n ); then the two matrices

A + := U diag max{0, λ 1 }, . . . , max{0, λ n } U ⊤ A -:= U diag min{0, λ 1 }, . . . , min{0, λ n } U ⊤ are such that A = A + + A -and A + , A -= 0. Thus A + (resp. A -) is the projection of A onto S n
+ (R) (resp. onto its polar -S n + (R)). Said otherwise, to project A onto S n + (R), we just have to compute an eigendecomposition of A and cut off negative eigenvalues by 0. It is remarkable that we have an explicit expression of the projection onto S n + (R), and that this projection is easy to compute (essentially by computing an eigendecomposition). More sophisticated projections onto subsets of S n + (R) are also computable using standard tools of numerical optimization [START_REF] Malick | A dual approach to semidefinite least-squares problems[END_REF]; those projections have many applications in statistics and finance (see [START_REF] Schwertman | Smoothing an indefinite variance-covariance matrix[END_REF] for an early reference of the projection onto S n + (R); see also [29, section 5]). Finally note that we can interpret the projection of A onto S n + (R) = λ -1 (R n + ) with respect to the projection of its eigenvalues onto R n + , namely

Proj S n + (R) (A) = U diag Proj R n + (λ 1 , . . . , λ n ) U ⊤ .
This result has a nice generalization: we can compute a projection onto a spectral set λ -1 (C) as soon as we know how to project onto the underlying C (see [START_REF] Lewis | Alternating projections on manifolds[END_REF]).

Tangent and Normal Cones

Normal cones in convex geometry play the role of normal spaces in smooth geometry: they give "orthogonal" directions to a set at a point of the set. Their "duals", the tangent cones, then give a simple conic approximation of a convex set around a point.

The normal cone to S n + (R) at X ∈ S n + (R) can be defined as the set of directions S ∈ S n (R) such that the projection of X + S onto S n + (R) is X itself. In mathematical terms, this means

N A := {S ∈ S n (R) : S, B -A ≤ 0 for all B ∈ S n + (R)}.
The tangent cone is then defined as the polar of N A and admits the characterization:

T A := N A • = R + (S n + (R) -A).
To fix ideas, we give a illustrative representation of the cone with its tangent and normal space at a point (beware of the fact that this is not a real representation, since for n = 2 the boundary of the cone is smooth).

For the special case A = 0, we have simply The first expression of N A comes from the general result for closed, convex cones (see [13, A.5.2.6]). The second one follows from the (quite surprising) property:

N 0 = S n + (R) • = -S n + (R) and T 0 = S n + (R). For the general case A ∈ S n + (R), we have T A = {M ∈ S n (R) : M u, u ≥ 0 for all u ∈ ker A} (9)
N A = {M 0 : M, A = 0} = {M 0 : M A = 0} = {M 0 : AM = 0} = {M 0 : Im M ⊂ ker A} = {M 0 : Im A ⊂ ker M } . N A A T A S n + (R)
for A, B ∈ S n + (R), we have:

A, B = 0 ⇐⇒ A B = 0.
which has a one-line proof using a classical trick, as follows

A, B = trace A 1/2 A 1/2 B 1/2 B 1/2 = trace B 1/2 A 1/2 A 1/2 B 1/2 = A 1/2 B 1/2 2 .
The third expression comes easily from the second. We can also describe N A one step further from the last expression. Take A ∈ S n + (R) of rank r (< n). The dimension of ker A is n -r, let {u r+1 , . . . , u n } be a basis of it. Then

M ∈ N A ⇐⇒ M = n i=r+1 α i u i u i ⊤ with α i ≤ 0 (i = r + 1, . . . , n).

Spectahedron, the Spectral Simplex

A special subset of S n + (R) plays an important role in the variational analysis of the eigenvalues (see [START_REF] Hiriart-Urruty | Sensitivity analysis of all eigenvalues of a symmetric matrix[END_REF], [START_REF] Overton | Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices[END_REF]) and in some applications of semidefinite programming (as for example for sparse principal component analysis [START_REF] Aspremont | A direct formulation for sparse PCA using SDP[END_REF]). The so-called spectahedron is defined by

Ω 1 := {A 0 : trace(A) = 1}. ( 10
)
This set is convex and compact; its extreme points are exactly the matrices xx ⊤ with unit-vectors x ∈ R n . The spectahedron equivalently defined through the eigenvalues:

Ω 1 = λ -1 (Π 1 ) is the spectral set of Π 1 := {(λ 1 , • • • , λ n ) : λ i ≥ 0, n i=1 λ i = 1}
the unit-simplex of R n . This set and its properties generalize as follows. For an integer m ∈ {1, . . . , n}, set Ω m := {A 0 : trace(A) = m and λ max (A) ≤ 1}.

For example, Ω n is obviously reduced to a single element, the identity matrix I n . Note that we did not add λ max (A) ≤ 1 in the definition of Ω 1 , since it was automatically satisfied. The general result is the following: the set Ω m is convex and compact, and it is the convex hull of the matrices XX ⊤ , where X is n × m-matrix such that X ⊤ X = I m . In other words: the convex hull of the orthogonal projection matrices of rank m is exactly the set of symmetric matrices whose eigenvalues are between 0 and 1, and whose trace is m. The proof of this result

trace(•) = 1 Ω 1 S n + (R) I n
m = λ -1 (Π m ) with the compact convex polyhedron Π m := {(λ 1 , • • • , λ n ) : 0 ≤ λ i ≤ 1, n i=1 λ i = m}.
Then we can determine the extremal points of Π m : the point ( λ1 , . . . , λn ) is extremal in Π m if and only if all the λi are zeros, expected m of them that are ones.

Representation as Inequality Constrained Set: Nonsmooth Viewpoint

A common, pleasant situation in optimization is when a constraint set C is represented with the help of inequalities g 1 (x) ≤ 0, . . . , g p (x) ≤ 0, and the interior of C with the help of strict inequalities with the same functions

g 1 (x) < 0, . . . , g p (x) < 0.
Does there exist such a representation for C = S n + (R) and its interior S n ++ (R) ? The answer is yes. We highlight two types of representing functions: a nonsmooth one in this section, and polynomial ones in next section.

Consider the function g : S n (R) → R defined by

g(A) := λ max (-A) = -λ min (A). ( 11
)
This function is convex and positively homogeneous, as a maximum of linear functions. Indeed, we have the well-known Rayleigh quotient

λ max (A) = max x =1 Ax, x = max x =1 A, xx ⊤ = max X∈Ω 1 A, X ,
where Ω 1 is defined by [START_REF] Poljak | A recipe for semidefinite relaxation for (0,1)quadratic programming[END_REF]. More precisely, the last expression says that λ max is the support function of Ω 1 (the notion of support function is fundamental in convex analysis; see [13, Chap.C]). Let us come back to the representation of S n + (R) as an inequality constrained set: we have a first adequate representation as

S n + (R) = {A ∈ S n (R) : g(A) ≤ 0}, S n ++ (R) = {A ∈ S n (R) : g(A) < 0}.
We can thus represent S n + (R) as a constrained set with a single inequality, but we have to use the nonsmooth function λ max . On the other hand, in Section 4.4, we will represent it with several smooth functions.

We mention briefly that smooth approximations of the nonsmooth representing function λ max give smooth approximations of S n + (R). We start from S n + (R) = {A ∈ S n (R) : λ max (-A) ≤ 0} and, following [START_REF] Nesterov | Smoothing technique and its applications in semidefinite optimization[END_REF], we define for all µ > 0

X ∈ S n (R) -→ f µ (X) := µ log n i=1 exp(λ i (X)/µ)
where the λ i (X) are the eigenvalues of X. This expression of f µ can be transformed to

f µ (X) = λ max (X) + µ log (trace(E(X))) with E(X) = exp X -λ max (X)I n µ .
In [START_REF] Nesterov | Smoothing technique and its applications in semidefinite optimization[END_REF], it is shown that f µ is globally Lipschitz, of class C 1 with gradient

∇f µ (X) = E(X) trace(E(X))
,

and that we have the uniform approximation

λ max (X) ≤ f µ (X) ≤ λ max (X) + µ log n.
Therefore, S n + (R) could be uniformly approximated by {A ∈ S n (R) : f µ (-A) ≤ 0} which is an inner (µ log n)-approximation.

Representation as Inequality Constrained Sets: Semialgebraic Viewpoint

The adequate representation of the previous section used a nonsmooth function. The algebraic nature of S n + (R) gives a representation with polynomials, and it is tempting to consider the positively homogenous polynomial functions ∆ k (A). However we cannot use them to have the desired decomposition since (recall Section 3.2)

S n + (R) {A ∈ S n (R) : ∆ k (A) ≥ 0 for all k = 1, . . . , n}, S n ++ (R) = {A ∈ S n (R) : ∆ k (A)
> 0 for all k = 1, . . . , n}. We still have an adequate polynomial representation: setting g k = -i k , we have indeed

S n + (R) = {A ∈ S n (R) : g k (A) ≤ 0 for all k = 1, . . . , n}, (12)
S n ++ (R) = {A ∈ S n (R) : g k (A) < 0 for all k = 1, . . . , n}. The constraint functions g k are polynomial, positively homogeneous of degree k; obviously they are of class C ∞ , whereas g in ( 11) is nonsmooth. Note that that S n + (R) represented by ( 12) is clearly a cone, but its convexity is less clear (and comes from subtle reasons: hyperbolic polynomials and the convexity theorem of Gårding; see [START_REF] Lewis | Nonsmooth analysis of eigenvalues[END_REF]).

Also note that in the representation [START_REF] Lewis | Nonsmooth analysis of eigenvalues[END_REF] we have the a priori knowledge of the active constraints at a matrix A (those such that g k (A) = 0). Usually, we only know this a posteriori; here we directly know from the rank r of A that: g k (A) < 0 for k = 1, . . . , r and g k (A) = 0 for k = r + 1, . . . , n.

We now briefly discuss the fact that S n + (R), as it appears in [START_REF] Lewis | Nonsmooth analysis of eigenvalues[END_REF], is a semialgebraic set. A so-called semialgebraic set is a set defined by unions and intersections of a finite number of polynomial inequalities. It turns out that these sets enjoy very nice closedness properties (almost any "finite"' operation preserves semialgebraicity; see [START_REF] Bochnak | Real Semialgebraic geometry[END_REF]). These properties are useful tools for the analysis of structured nonsmooth optimization problems (see e.g. [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF], [START_REF] Ioffe | An invitation to tame optimization[END_REF]). One of the main properties of semialgebraic sets is that they can be decomposed as a union of connected smooth manifolds (so-called strata) that fit together nicely. Denoting by R r the smooth submanifold made up from the positive semidefinite matrices of fixed rank r (for r = 0, . . . , n), we observe that the semialgebraic cone S n + (R) is the union of the n + 1 manifolds R r , which are themselves the union of their connected components, the strata of S n + (R). The two extreme cases are: r = 0 the apex of the cone and r = n the interior of the cone. The decomposition as union of manifolds is explicit in the representation of S 2 (R) in R 3 : the point (r = 0), the boundary deprived from the origin (r = 1) and the interior of the cone (r = 2).

The tangent space to R r at A (denoted by T A ) is connected to the tangent cone to S n + (R) at A. In fact, T A is the largest subspace included in T A (recall(9)), namely

T A = T A ∩ -T A = {M ∈ S n (R) : M u = 0 for all u ∈ ker A} .

Natural Riemannian Metric on S n ++ (R)

In practice, the computations dealing with positive definite matrices are numerous and involve various operations: averaging, approximation, filtering, estimation, etc. It has been noticed that the Euclidean geometry is not always best suited for some of these operations (as for example in image processing; see e.g. [START_REF] Moakher | Symmetric positive-definite matrices: From geometry to applications and visualization[END_REF] and references therein). This section presents another geometry in S n ++ (R) having different operations (for example for averaging). Next section connects this geometry to optimization. We refer to [START_REF] Bhatia | Positive definite matrices[END_REF]Chap. 6] for more details and for the proofs of the results. Note that similar developments hold for R r the fixed rank positive definite matrix manifold (see [START_REF] Bonnabel | Riemannian metric and geometric mean for positive semidefinite matrices of fixed rank[END_REF]), but they require more involved techniques. Though we use the language of Riemannian geometry, we stay here at a very basic level.

The cone S n ++ (R) is open, and has two natural geometries: the Euclidean geometry associated with the inner product •, • , where the distance between A and B is

d 2 (A, B) := A -B 2 = A -B, A -B ;
and a Riemannian metric defined from ds = A -1/2 (dA)A -1/2 2 (the "infinitesimal length" at A) by the following standard way. Let A, B ∈ S n ++ (R) and a piecewise

C 1 path γ : [a, b] → S n ++ (R) from A = γ(a) to B = γ(b); then the length of γ is L(γ) := b a γ -1/2 (t)γ ′ (t)γ -1/2 (t) 2 dt,
and the Riemannian distance is

d R (A, B) := inf {L(γ) : γ paths from A to B} . (13)
It turns out that we have nice explicit expressions of d R and associated "geodesics" (locally, the shortest paths between two points). The unique geodesic that connects A and B is the following path

[0, 1] -→ γ(t) := A 1/2 (A -1/2 BA -1/2 ) t A 1/2
that reaches the minimum in [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF], so that

d R (A, B) 2 = log(A -1/2 BA -1/2 ) 2 = n i=1 log λ i (A -1/2 BA -1/2 ) 2 = n i=1 log λ i (A -1 B) 2 .
The last inequality comes from the fact that A -1 B and A 1/2 BA 1/2 are similar matrices, so they have the same eigenvalues. We can verify from this expression that we have indeed the desirable

property d R (A, B) = d R (B, A) (since (A -1 B) -1 = B -1
A, the squared log of eigenvalues are the same). We give a flavour on why this distance has a better behaviour for some applications.

Distance of inverses. We get easily that the inversion does not change the distance: for any A and B in S n ++ (R), we have

d R (A, B) = d R (A -1 , B -1 ). ( 14
)
This property does not hold for the distance d 2 . Here it simply follows from the fact that (A -1 B) ⊤ = BA -1 have the same eigenvalues.

Geometric average (and a little more). Let A 1 , . . . , A m be m matrices of S n ++ (R). Writing the optimality conditions, we can prove that there exists a unique matrix M 2 (A 1 , . . . , A m ) in S n ++ (R) that minimizes X → m i=1 ( X -A i 2 ) 2 , and we get explictly that M 2 is the usual (arithmetic) average

M 2 (A 1 , . . . , A m ) := A 1 + • • • + A m m .
For the Riemannian geometry, we have similarly that there exists a unique matrix X in S n ++ (R) that minimizes

X -→ m i=1 d R (X, A i ) 2 , (15)
and this matrix, denoted by M R (A 1 , . . . , A m ), is called the Riemannian average. An interesting property (not shared by M 2 ) comes from ( 14): we have

M R (A -1 1 , . . . , A -1 m ) is the inverse of M R (A 1 , . . . , A m ). (16)
Finally, the optimality condition of (15) yields that m i=1 log(A i -1 X) = 0 characterizes the Riemannian average.

For m = 2, we see that

M R (A 1 , A 2 ) = A 1 (A 1 -1 A 2 ) 1/2 = A 2 (A 2 -1 A 1 ) 1/2
is the solution of the equation (see [START_REF] Bhatia | Positive definite matrices[END_REF]Chap. 4] for the details). If furthermore A 1 and A 2 commute, we have

M R (A 1 , A 2 ) = A 1/2 1 A 1/2 2 .
This last property explains why the Riemmanian average is sometimes called the geometric average.

For a general m, computing M R (A 1 , . . . , A m ) might be less direct. As far as the symmetry property ( 16) is concerned, one could consider instead another matrix average, the so-called the resolvent average M res (A 1 , . . . , A m ) of [START_REF] Bauschke | The resolvent average for positive semidefinite matrices[END_REF]. It can be defined as the minimum of a function looking like [START_REF] Brinkhuis | Optimization: Insigths and Applications[END_REF] (with a Bregman distance replacing d R ; see [START_REF] Bauschke | The resolvent average for positive semidefinite matrices[END_REF]Prop. 2.8]), but it has also a simple, easy-to-compute expression that can be written

(M res (A 1 , . . . , A m ) + I n ) -1 = ((A 1 + I n ) -1 + • • • + (A 1 + I n ) -1 )/n.
The above equality interprets that the resolvent of the average is the arithmetic average of the resolvents of the A i 's, which give the name "resolvent average". The fact that the resolvent average satisfies [START_REF] Azé | Calcul différentiel et équations différentielles[END_REF] comes from techniques of variational analysis (see [START_REF] Bauschke | The resolvent average for positive semidefinite matrices[END_REF]Th. 4.8]).

Barrier Function of S n ++ (R)

As a function of the real variable x > 0, the logarithm x → log x has a matrix relative which turns out to have a central role in optimization. The celebrated (negative) log-function for matrices is

X ≻ 0 -→ F (X) := -log(det(X)) = log(det X -1 ). (17)
Differential calculus for F in S n ++ (R) gives the "same" results as for the log in R + . The composite function F is of class C ∞ on S n ++ (R); its derivative DF (X) :

H ∈ S n (R) → DF (X)[H] is such that DF (X)[H] = -trace(X -1 H) = -X -1 , H = -trace(X -1/2 HX -1/2 ),
and gives the gradient ∇F (X) = -X -1 . We have furthermore

D 2 F (X)[H, H] = trace (X -1/2 HX -1/2 ) 2 = X -1 HX -1 , H D 3 F (X)[H, H, H] = -2trace (X -1/2 HX 1/2 ) 3 .
We can also prove that F is strictly convex on S n ++ (R). This fundamental property is the topic of several exercises in [START_REF] Hiriart-Urruty | Optimisation et analyse convexe[END_REF].

As mentioned above, this function has a very special role in optimization, more precisely in semidefinite programming [START_REF] Saigal | Handbook of Semidefinite Programming[END_REF]. The function F is indeed a self-concordant barrier-function for S n ++ (R). The role of barrier is intuitive: F (X) → +∞ when X ≻ 0 approaches the boundary of S n ++ (R), which consists of the singular matrices A 0. Self-concordance is a technical property, namely

D 3 F (X)[H, H, H] ≤ α D 2 F (X)[H, H] 3/2
for a constant α (here α = 2 is valid). In the nineties, Y. Nesterov and A. Nemirovski developed a theory [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF], that has had tremedous consequences in convex optimization. They showed that self-concordant barrier-functions allow to design algorithms (called interior-point methods) for linear optimization problems with conic constraints, and that moreover the complexity of those algorithms is fully understood. In particular, the interior-point algorithms for semidefinite programming made a little revolution during the nineties: they provided numerical methods to solve a wide range of engineering problems, for example in control [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF], or in combinatorial optimization [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF].

The log-function F in ( 17) is at the heart of interior point methods for semidefinite programming; it also has a remarkable connection with the Riemmanian metric of Section 4.5. Observe indeed that the norm in S n + (R) associated to D 2 F (X) corresponds nicely with the infinitesimal norm defined by the Riemannian structure,

H D 2 F (X) = (D 2 F (X)[H, H]) 1/2 = X -1/2 HX -1/2 .
It follows that the Riemannian distance naturally associated with the barrier is exactly the natural Riemannian distance [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]. This geometrical interpretation of the barrier function then shows that interior-point methods have an intrinsic appeal, and may explain their strong complexity results (see more in [START_REF] Nesterov | On the Riemannian geometry defined by self-concordant barriers and interior-point methods[END_REF]).

Unit Partition in S n

++ (R)

In this last section, we discuss the so-called unit partition problem in S n ++ (R). Motivated by a problem originated from Economy, I. Ekeland posed it as a challenge in a conference in 1997 [START_REF] Ekeland | Plenary talk at the worskshop of the group MODE of the French applied mathematical society[END_REF]. Given k + 1 nonzeros vectors x 1 , . . . , x k , y in R n , when is it possible to find positive definite matrices M 1 , . . . , M k such that

M i y = x i for all i = 1, . . . , k (18)
and

k i=1 M i = I n ? (19)
The first equation is of the quasi-Newton type [START_REF] Bonnans | Numerical Optimization[END_REF]; the second equation gives the name of the problem.

A condition that guarantees existence of such matrices should obviously depend on the vectors x 1 , . . . , x k , y. It is easy to get from ( 18), ( 19) that a necessary condition is x i , y > 0 for all i = 1, . . . , k and k i=1

x i = y.

Unfortunately, this condition is not sufficient, as shown by the following counter-example. Consider in R 2 , the three vectors

x 1 = 1/2 1 , x 2 = 1/2 -1 and y = 1 0 .
Then observe that for both i = 1, 2, the property M i x i = y with M i ≻ 0 yields

M 1 = 1/2 1 1 α and M 2 = 1/2 -1 -1 β , with α, β > 2. Thus it is impossible to have M 1 + M 2 = I 2 .
Note also that condition [START_REF] Azé | Analyse variationnelle et optimisation[END_REF] is even not sufficient to get a weaker version of the partition [START_REF] Anderson | Series and parallel addition of matrices[END_REF] with M i 0.

We give here a constructive way to get the unit partition of S n + (R) (and later a variant of the result). The result is due to A. Inchakov, as noted by [START_REF] Ekeland | Some applications of the Cartan-Kähler theorem to economic theory[END_REF].

Theorem 4.1 (Condition for unit partition of S n ++ (R)). Let k + 1 nonzeros vectors x 1 , . . . , x k , y in R n , satisfying [START_REF] Azé | Analyse variationnelle et optimisation[END_REF]. Then a necessary and sufficient condition for the existence of M i ≻ 0 satisfying (18) and ( 19) is that

A 0 := I n - k i=1 x i x i ⊤ x i , y
be positive definite on y ⊥ .

Proof. Let us prove first that the condition ( 21) is necessary. The Cauchy-Schwarz inequality gives for all i and for all z ∈ R n M i y, z 2 ≤ M i y, y M i z, z with equality if and only if z and y are collinear, which yields

x i , z 2 ≤ x i , y M i z, z with equality if and only if z and y collinear.

As a consequence, we have

     k i=1
x i , z

2 x i , y -M i z, z = k i=1
x i , z 2

x i , y -z 2 ≤ 0 with equality if and only if z and y are collinear which means q A 0 (z) ≥ 0 with equality if and only if z and y are collinear.

Thus A 0 is positive semidefinite and of kernel reduced to Ry, and we get [START_REF] Taussky | The role of symmetric matrices in the study of general matrices[END_REF].

To prove sufficiency of condition [START_REF] Taussky | The role of symmetric matrices in the study of general matrices[END_REF], we propose the matrices

M i := A 0 k + x i x i ⊤
x i , y .

By construction, we have k i=1 M i = I n ; and moreover, since A 0 y = 0, we also have M i y = x i for all i = 1, . . . , k. There remains to prove the positive definiteness of the M i 's.

It is clear that M i 0, since it is sum of two positive semidefinite matrices. Let us take z ∈ R n such that M i z, z = 0, and let us prove that z = 0. We have

A 0 z, z k + x i , z 2
x i , y = 0, which yields A 0 z, z = 0 (hence z and y are collinear by ( 21))

x i , z = 0.

The conclusion follows easily: there exists α ∈ R such that z = αy, and the condition x i , y > 0 implies α = 0 and then z = 0, so M i is definite positive.

It is interesting to note that ( 21) is of the type (E 0 ) Ax, x > 0 for all x = 0 orthogonal to y, for A ∈ S n (R) and y = 0 in R n , which is a frequently encountered property in matrix analysis and optimization. Here is below four formulations equivalent to (E 0 ) (see e.g. [START_REF] Chabrillac | Definiteness and semidefiniteness of quadratic forms revisited[END_REF]).

(E 1 ) Finsler-Debreu condition: there exists µ ≥ 0 such that A + µyy ⊤ ≻ 0. (E 4 ) Condition on the inverse of the augmented matrix. The matrix Ā is invertible and the n×nmatrix extracted from Ā-1 by taking the first n columns and rows is positive semidefinite.

We finish with a variant of Theorem 4.1 showing that starting from a weaker assumption, we get a weaker result. x i , y > 0 or x i = 0 for all i = 1, . . . , k k i=1

x i = y.

Then a necessary and sufficient condition for the existence of M i 0 satisfying (18) and ( 19) is that

A 0 := I n - {i: x i =0}
x i x i ⊤

x i , y is positive semidefinite.

Proof. Note that under the assumption of the theorem, we have x i , y ≥ 0 for all i = 1, . . . , k and there is x i = 0 because k i=1 x i = y = 0. The proof is similar to (and easier than) the previous one. Let us start with the necessity of the condition [START_REF] Taussky | On the similarity transformation between a matrix and its transpose[END_REF]. We have A 0 y = 0 since n i=1 x i = {i: x i =0} x i = y. With the Cauchy-Schwarz inequality, we write x i , z 2 ≤ x i , y M i z, z , and then {i:

x i =0}
x i , z 2

x i , y -z 2 ≤ 0.

Thus we get A 0 0. As for sufficiency, we propose the semidefinite matrices

M i :=        A 0 k if x i = 0 A 0 k + x i x i ⊤ x i , y if x i , y > 0.
We check that in both cases M i y = x i , and obviously we also have k i=1 M i = I n .

Concluding Remarks

This article highlights nice variational properties of (the set of the) positive semidefinite matrices, and gives pointers to some of their applications. Even if the notion of positive semidefiniteness is basic and taught everywhere, there are still many open questions related to it, and more generally to the interplay between matrix analysis and optimization; see the commented problems in [START_REF] Hiriart-Urruty | Potpourri of conjectures and open questions in nonlinear analysis and optimization[END_REF] and [START_REF] Hiriart-Urruty | A new series of conjectures and open questions in optimization and matrix analysis[END_REF]. The "variational" viewpoint adopted here also opens the way to another notion of positivity, the so-called "copositivity", which also has rich and useful properties: see the recent review [START_REF] Hiriart-Urruty | A variational approach to copositive matrices[END_REF] for example.

Figure 1 :

 1 Figure 1: The usual cone in R 3 , identified with S 2 + (R)

Figure 2 :

 2 Figure 2: (Nonrealistic) illustration of the normal and tangent cones to S n + (R) at A

Figure 3 :

 3 Figure 3: (Nonrealistic) representation of the spectahedron

(E 2 )(E 3 )

 23 Condition on the augmented matrix: the matrix Ā ∈ S n+1 (R) defined by blocks as Ā = A y y ⊤ 0 has exactly n positive eigenvalues. Condition on determinants (that the economists are keen of). For I ⊂ {1, . . . , n}, we note A I the matrix extracted from A in taking only columns and rows of indices in I. Similarly y I is obtained from y by taking the entries y i for i ∈ I. We set ĀI = A I y I y I ⊤ 0 and the condition is det A I < 0 for all I = {1, 2}, {1, 2, 3}, . . . , {1, . . . , n}.

Theorem 4 . 2 (

 42 Condition for unit partition of S n + (R)). Let x 1 , . . . , x k and y = 0 be k +1 vectors of R n , satisfying 

Institut de mathématiques, Université Paul Sabatier, Toulouse, France jbhu@cict.fr

CNRS, Lab. J. Kuntzmann, Grenoble, France, jerome.malick@inria.fr (corresponding author)

Acknowledgement: The authors thank J.-B. Lasserre for having made us aware of the characterization of the positive semidefiniteness by non-negativity of the principal invariants (see Section 3.2).


Jérôme Brulin

Eric Blond

Emmanuel De Bilbao

Amna Rekik

Matthieu Landreau

Alain Gasser

Yannick Colleville

Experimental set-up for mortar / brick interface strength characterization at high temperature

Introduction

In the steel-making industriy, the large chemical reactors are composed of many different linings from inner to outer: the working lining in contact with slag or gas, the safety lining, the insulating lining, and so on as far as outer metal timbering. Parts of the lining of these vessels consist of refractory masonries, with or without mortar. In the case of masonry with mortar, cracks occur most of the time at the unit-mortar interface because it is the weakest link of the assembly (1) . This observation has led to the development of a homogeneous equivalent material with behavior depending on the "joint state": sound or broken. (2,3,4,5) In refractory applications, due to thermal solicitations and shape of the vessels, refractory unit-mortar interface should crack under tensile load, usually denoted mode I fracture and under shearing load, denoted mode II. It is therefore necessary to characterize the refractory brick/mortar interface in modes I and II from RT up to 1500°C. Then, two specially-designed devices are proposed: the high-temperature slant shear test and an especially dedicated tensile test. (6)

Strength criterion

The mode I failure corresponds to a classical Rankin criterion (i.e. tensile cut-off) while the brick/mortar interface shear strength dependence to the normal stress applied to the interface corresponds to a friction-type behavior, classically described by the Mohr-Coulomb yield function. Then, it leads to a yield surface described by two lines in the plane :

(1) where is the stress tensor,  is the shear stress associated to the considered interface, is the normal stress to the interface, c is the cohesion, is the friction angle and f t is the tensile strength.

Materials

An interface is defined by the couple of brick and mortar. In this work, two couples were considered (Tab 1). The first one is made of dense silica bricks with a silica based mortar, denoted A. The second is composed of high alumina bricks with a chemically bonded high alumina mortar, denoted B. Silica bricks were stabilized into cristobalite while alumina bricks were stabilized into corundum. Green mortars were shaped between the two half samples before 24 hours curing at RT and 24 hours drying at 110°C. Shear strength has been characterized for each specimen, whereas the tensile strength has been measured for B only.

High-temperature tensile test

The tensile strength f t can be deduced from different tests (7,8,9) but direct tensile test remains the best method to study the mode I fracture behavior. The set-up developed here has been specially designed to address the alignment of the loading chain including the specimen in the special case of brick-mortar interface characterization. The assembly is made up of a couple of cylindrical refractory units joined with mortar. Two wires inserted in the unit and going through thanks to double holes make possible the block to be clamped. (6) Each wire is made of nickel-chromium alloy to resist high temperature and stress. Both wires are griped to specific clamps out of the furnace (see fig. 1). The wire's diameter is chosen to resist stress while being flexible enough to ensure the alignment of the loading "chain". Using these specific clamps and wires makes it possible the specimen to be aligned with the force direction.

Tensile tests were performed using a universal testing machine equipped with a high-temperature furnace (AET Furnace -1500°C, ref.

OF 25 957 Type SP). The force is measured with a classic load cell. A cooled device is set between the furnace and the load cell. Displacement of the crosshead is also measured. Tensile tests were performed on samples B at three temperatures: 20, 900 and 1200°C. For RT, the tests were performed with a rate of 0.5 mm/min whereas for high-temperature test, the speed rate was tuned to 30 mm/min to avoid the creep of the wires. The tensile strength f t is estimated according to equation:

(3)

where F max is the maximum load reached before the fracture of the sample, S is the area of the transverse section, D and d are the outer and the inner diameters of the cylindrical unit respectively. Results of sensitivity study established that the uncertainty is lower than 5% on the tensile strength (6) .

High temperature slant shear test

To achieve the identification of the Mohr-Coulomb's parameters, dedicated devices have been developed in the civil engineering field. Tests on two bricks pasted by one mortar joint (10,11) or on three bricks pasted by two mortar joints (12,13) are the most used. In this work the high temperature constraint induces two major difficulties: firstly, the set-up must be compact enough to be put in a furnace; secondly, the loading device must stand against high temperature. As presented on Erreur ! Source du renvoi introuvable., a possible solution to overcome these difficulties is to perform a compressive slant shear test on two bricks pasted by one inclined mortar joint (6) . This design allows applying normal and shear stresses at the interface with a usual compression device. The same test has been used coupled to optical measurements at RT to characterize the equivalent interface stiffness in function of the mortar slant angle. (14) The limits of this test at RT and the influence of different shapes and material parameters have been studied by Austin. (15) Figure 1: Specimens A after slant shear test at 1080°C

The local normal and shear stresses applied on the brick/mortar interface are driven by the slant of the joint:

(4) where F is the global applied force, S is the specimen transverse area and α is the angle between mortar joint and the plane normal to the compressive loading axis. Equations (4) are rigorously right as long as the crack initiates at the interface. To produce a shearing fracture instead of a compressive one, the angle must maximize the ratio of shearing stress to normal compressive stress. The identification of the cohesion and internal friction angle requires at least three different angles. The specimen shape was parallelepiped of section 35x35 mm 2 . Its total height depends on the angle but need to be lower than height of homogeneous temperature in the furnace. Detailed dimensions of specimens are summarized in Table 2. The samples A were first heated up to 1000°C for a dwell of one hour to stabilize the mortar. Then, samples were heated up or cooled down to the temperature of the test. A second dwell of half an hour was done before performing the test. The tests were performed at 800°C, 1080°C and 1350°C. The samples B were heated up to 450°C at a rate of 350°C/h, then up to 650°C at a rate of 125°C/h and finally to the temperature of the test at 325°C/h. A dwell of one hour was done at the temperature of the test before performing the experiment. Tests were performed at RT, 900°C and 1450°C. The tests were performed on a classical press with usual compressive device. The cross bar speed rate was tuned to 0.5 mm/min. Figure 1 Erreur ! Source du renvoi introuvable. presents Mohr-Coulomb graph extracted from load versus displacement curves on specimen A at the different tested temperatures. The points clearly define a straight line that allows identifying cohesion and friction angle for each temperature. The difference between 1080°C and 1350°C is small, whereas a real difference appears for the cohesion between 800°C and 1080°C. Moreover, the friction angle seems not to be influenced by the temperature.

Conclusions

Experimental characterization of the strength of mortar/brick interface is a key point as the unit-mortar interface is often the weakest link of the assembly. Currently, there is a real lack of data concerning the refractory masonry strength. Two set-ups and the associated sample shapes were developed to measure the tensile strength and the compressive shear strength.

A special tensile test with dedicated clamping devices has been designed to measure the tensile strength of interface and tests were performed in temperature range from RT up to 1200°C. For the compressive shear fracture, the slant shear test was carried out in the temperature range from RT up to 1450°C to identify the Mohr-Coulomb parameters of the mortar brick interface in function of the temperature. These first results concerning the strength of interface at high temperature should be carefully taken because of the assumption on the prevailing failure mode. This assumption will be reinforced by a further dedicated work.

In conclusion, both experimental set ups proposed here allow the setting of a complete characterization of the brick/mortar interface strength at high temperature. These devices may contribute to enlarge the knowledge on the ultimate strength evolution with temperature of such interfaces.

Figure 1 :

 1 Figure 1: High temperature tensile test set-up

Figure 2 :

 2 Figure 2: Tensile strength versus temperature for specimen B

Table 2 :

 2 presents typical fractures after testing at high temperature. With few exceptions, cracks were clearly localized at the interface. The exploitation proposed here with equations (4) is thereby available only for brittle and quasi-brittle fracture localized at the interface or, at least, initiated at the interface. Specimen dimensions for slant shear test Erreur ! Source du renvoi introuvable. presents typical load versus displacement curves obtained recording these data during the test for specimen B. The different curves correspond to different joint slants tested at the same temperature. The decrease of the maximum load value with the increase of the joint slope is not clearly observed. As illustrated later, it does not prevent to determine reasonably Mohr-Coulomb parameters. Nevertheless, because of the material scattering, the lack of data may lead to use all the experimental data carefully.

Figure 4 :

 4 Figure 4: Load versus displacement curves for specimen B with different joint slopes at 900°C

Figure 5 :

 5 Figure 5: Mohr-Coulomb line for specimen A.

Figure 6 :

 6 Figure 6: Mohr-Coulomb line for specimen B.

Table 1 :

 1 Chemical composition of refractory bricks and mortar

	w. %	A Brick Mortar Brick Mortar B
	SiO 2	95	95
	CaO	< 3	< 1
	Al 2 O 3 < 1.5	< 1	89	86
	Na 2 O				2.75
	N			4.8
	Fe 2 O 3	<1			< 0.25